someone please explain the solution of CHEFPRES question asked in DEC 14 long challenge?
You missed editorial?
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.
I did read the editorial, but could not understand the explanation. Would be great if you can explain it in a more simpler manner.
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