Sunday, March 6, 2011

Google Code Jam , World finals 2010 - City Tour



At the begining, i have small problem with quection description. Quection description says that How to build the city.
according to my understanding the dicription as follows

Initially there are 3 cities. These 3 cities are connected by 3 bi directional lines. So visual representation of this is as follows.Following is the discription which gives us an idea like above.

" the cities started from three points of interest, with each pair being connected by a bidirectional street"

Now , what is next, it says how it evoles from this point onwards.

"then, gradually, new points of interest were added. Any new point of interest was connected by two new bidirectional streets to two different previous points of interest which were already directly connected by a street. "

which means that, if i add new point to above figure , it will looks like as follows.

But when we try to understand the first sample input from this view, it gives nothing.

First input says something like follows.
Input

Output
2
5
1 2
2 1
6
1 2
1 4
4 5
Case #1: 4
Case #2: 6

Ok what is this first input set means. it says there are 5 points of interest. Ok, according to our understanding, it says, there are 2 more points of interest than 3 main points of interests. So , we already know how it's connection looks like according to the previous decription. but it gives us 1,2 and 2,1 two streets.

Also here is the dicription about these inputs.
"
The next N-3 lines each contain a pair of space-separated integers A, B, indicating that the corresponding point of interest was connected by streets to points A and B. First of these lines corresponds to point number 4, second to point number 5, etc. "

if there are 5 points, then 5-3 is 2, so we should have give two (x,y) point inputs. yes they have!
it is interesting to look how we missunderstood this problem.
We thought that (x,y) represents cordinates, but they are not corrdinates, why did we think they are cordinates. Since we did not quection basic thing at the biggning of the quection. what it is. if two newly added points are connected to first 3 points by two bi-diractional lines, there are 3 ways in which this can be done, so we should be given correct configuration. if we had quection this at first, then we won't decide those input to be coordinates! :)



No comments:

Post a Comment