Solutions for Round 5

Problem 1: The Law and the Cities
Problem 2: NIM
Problem 3: Santa Claus is Coming!...


Problem 1: The Law and the Cities

A first remark is that no one succeeded in solving the problem up to its end, the only ones who were close to it are Ioana Ileana (7 tests out of 8), Dumitru Bogdan and Cadar Cristian (6 tests out of 8).
Let's analyse the complexity of the program. As the number of crossings and roads is at the most 5001, we deduct that the complexity - so that the program might fit in one second's time - should have been of the form n*log(n).
Before presenting the algorithm, I must specify that no order was requested as far as the belts' order is concerned (that is the first belt of the city and then the rest of them, or any other order), as we didn't want to make the program too complicated.
The problem confines to finding out the faces of a planar graph. Let n be the number of points (vertexes) and m the number of edges of a graph. The number of faces is given by the formula:
      m-n+the_number_of_connected_components+1
(1 is added for the exterior face). But the graph is connected, so the formula becomes m-n+2. One edge appears in exactly two faces. If the edge is divided into two orientated arcs, then you can make it so that each arc appears in only one face. To find the belts, you must start on some arc (chosen at random) from a point (vertex) and continue traversing the graph on the arc that forms the smallest angle with the arc you came on.
A belt is made when the starting point is reached. All the arcs through which you passed are erased from the list. All the belts are made when the graph becomes void.
There were given 8 tests, each one scored at 3.75 points. The score was rounded.

Input files: 1 2 3 4 5 6 7 8
Output files: 1 2 3 4 5 6 7 8

Because no source was found to have the maximum score, the author's source is attached.

Solution no. 1 (Pascal)


Problem 2: NIM

This wasn't a difficult problem, but through it we tried an aproach to the style of the IOI from Cape Town, South Africa, 1997. It is surprizing that so few participants have obtained the maximum score. The game is well-known, it can be found in many informatics books. So it is not necessary to explain the strategy of the game.
About the evaluation tests: there were 10 tests, each having between 1000 and 4000 piles. The tests had been verified previously in order to check the execution time. Each test has been marked with 2.5 points for winning and 0.5 points if your problem gets "lost game". The final score was the sum of these points (the sum was truncated).
Units used for evaluation:

NimLib.pas (Pascal)
NimLib.h (C)

Tests: 1 2 3 4 5 6 7 8 9 10

Good sources:

Solution no. 1 (Pascal)
Solution no. 2 (C)


Problem 3: Santa Claus is Coming!...

We think that the Christmas surprise was a real gift for you. You can see the number of maximum scores you have obtained. We are very glad and we send you our congratulations!

Tests

Examples of good sources (in Pascal and in C):

Solution no. 1 (Pascal)
Solution no. 2 (C)

For the New Year we send you the most sincere greetings of health and may your wishes come true. We wish that during the next year we'll have a colaboration that will bring many satisfactions to us all. With the most sincere friendship:

Maria and Adrian Nita teachers,
"Emanuil Gojdu" High School - Oradea


[The problems] [First Round] [Previous Round] [Next Round] [Current Round] [Romāna] [Go Back!]

Go Back!