Author: Kamil Debowski DIFFICULTY:MEDIUM PREREQUISITES:two pointers, dynamic programming PROBLEM... SLOWER SOLUTIONLet's first solve the problem in O(N^{2}). It's useful to imagine the tournament as the binary tree, just like one provided in the statement. For each bear b there are only O(log(N)) vertices where he can get (all ancestors of this leaf). We can create a twodimensional array dp[log[N]][N] where dp[r][b] denotes the minimum possible cost of getting the bear b to the rth ancestor of the leaf where b starts. To compute dp[r][b] we need values dp[r1][1..N] — then we consider all possible matches that can happen in the rth ancestor of the leaf with b. Let's also see how to consider a single match in O(1). If we know that that b1 can get so far with cost dp[r1][b1] (i.e. Limak must bribe at least this number of referees to ensure that b1 gets to the level r1) and b2 can get so far with cost dp[r1][b2], then:
It might seem that this approach has complexity O(N^{2} * log(N)) but we don't iterate over all pairs of bears in each of log(N) levels (depths). You can notice that for any two bears (b1, b2) they can fight in only one vertex (their LCA), so only once we will consider a match between those two. Since there are O(N^{2}) pairs of bears and considering one match takes O(1), we get O(N^{2}) in total. See the implementation below:
FAST SOLUTIONTo get O(N*log^{2}(N)) or faster, we should do one more thing. When we consider matches that can happen in some vertex x (i.e. in some way we want to compute for each bear the cost of getting him to the vertex x), we can take all dp values from the children of x (i.e. for each bear the cost of getting him to one of children of x), we can merge the two arrays faster than in O(size^{2}). So far, if the subtree of the left child had leaves b_{1}, b_{2}, ..., b_{p}, and the subtree of the right child had leaves b_{p+1}, b_{p+2}, ..., b_{2*p} (remember that leaves denote bears that could get to this vertex), then we considered O(p^{2}) matches separately. Instead, we can build some data structure on costs of b_{1}, ..., b_{p}, and then for each of b_{i} in b_{p+1}, b_{p+2}, ..., b_{2*p} consider two things:
Such approach gives the O(N*log^{2}(N)) complexity (see the tester's code) and should get AC. It's possible to achieve O(N*log(N)) with two pointers though. More information will be provided tomorrow (but you can see the setter's code now). AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 25 Feb '17, 23:37

@admin @errichto Just a suggestion. But please do keep in mind that a lot of beginners would be reading up this editorial. The concept, may be abstruse for them to understand for them in the first place. And you having a implementation of the N^2 implementation with no comments on what the hell is happening can result in beginners taking 2 hours to comprehend what they could have otherwise comprehended on 40 mins. I am pretty sure you didn't have to come up with that code in the middle of the competition. So, you had enough time to add in a few comments and that could help a lot. You say swap(I,j). Are you swapping the indexes, or the values in the vector, why are you swapping it? What does the variable rep mean? Repetition? Repetition for what? Ofcourse you could always say that it is obvious what those variables mean (but that would only be the case if you are keeping in mind the esoteric set of people who have already spent hours learning up such algorithms and are proficient with algorithms like these. And I don't think they would be needing the editorials as much as beginners do). In general, Codechef admin, make it a point to have well commented code in editorials. This will really help the beginners. The tester or author code is as though they fed the code through some code obfuscating tool like Proguard for Android. I mean, isn't it common sense that you are writing this editorial to people who haven't solved the problem and want to learn. Making it easier for them to do that with a few comments sprinkled isn't going to take you guys years. I am sorry if I am being rude, but I do really get very pissed off when you people do such blatantly obvious things like this. Whatever you are trying to say in the FAST SOLUTION is extremely ambiguous. You haven't even explained what data structure you are using and if you are using a segment tree or not, or what is the main trick you use in merging. And your Problem setter's code is so obfuscated. How is anyone supposed to understand anything looking at that code. We are humans not compilers. Can't you just write proper human readable code with comments and meaningful variable names? How did Codechef even admit this as editorial material? answered 05 Mar '17, 12:24

Proving the complexity for the O(n*n) can be difficult. This is one method showing how we can find the complexity. There are 5 for loops in the code:
Operations require in each for loop:
Operations from loop 2  4 is n/(2*blocks) * block * block * 2 = (n * block) Block value doubles every level. In level i, block is equal to 2^i So total operations are n*(2^i) in each level i sum 2^i for i = 0 to log(n) is equal to n Finally total operations are nn = O(nn)
link
This answer is marked "community wiki".
answered 26 Feb '17, 23:29

anyone done it using greedy approach ? answered 26 Feb '17, 00:23

In the tester's solution is segment tree stored per node? answered 26 Feb '17, 04:40
