CHEFPRES DEC 2014

general
, ,
1

someone please explain the solution of CHEFPRES question asked in DEC 14 long challenge?

2

You missed editorial?

3

I did read the editorial, but could not understand the explanation. Would be great if you can explain it in a more simpler manner.

4

Ok, Iā€™ll tell you how I did this.
I used concept of BFS and LCA.

Given, ā€œthere is exactly one simple path between every 2 citiesā€, you can imagine kingdom as n-ary tree with root at where king lives(K). Now, let Chef be in city C and P[] be array of city where required product is sold.

Now, logic is that the city closest to the King city will be the LCA of C and P[i] (for tree rooted at King node). (Draw picture and see!)

Now, its all easy. Do BFS starting at King node and save dist[i] as distance between city i and K. Also save prev[i] for each city (will be required to find LCA)

Now for each query, a and b, see if distance improves, and if same, if city number is less.

Code: http://www.codechef.com/viewsolution/5566272

2 Likes
5

thanks! :smiley:

6

In such case, you should ask on editorial page next time :wink:

7

I was about to try this approach but didnt think it would pass the time limitā€¦ It seems a little weird it got AC , given the constraint n<=10000 :confused: Anyways thanks for the detailed explaination :smiley:

8

I think the editorials should be a little more detailedā€¦ for someone who wasnā€™t able to solve a question, an explanation like this one would be good

9

BFS O(N). Worst case for this algo when Tree is linear - O(N*N) for each query - looks they didnā€™t have this case :smiley:
worst time 0.53sec (I could have optimize even more) . Doesnā€™t look like a ā€˜just passā€™ case to me :stuck_out_tongue: