# CHEFPRES DEC 2014

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

You missed editorial?

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

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.

2 Likes

thanks!

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

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 Anyways thanks for the detailed explaination

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

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
worst time 0.53sec (I could have optimize even more) . Doesnāt look like a ājust passā case to me