BRIBETR - Editorial

Author: Kamil Debowski
Tester: Niyaz Nigmatullin
Editorialist: Kamil Debowski

DIFFICULTY:

MEDIUM

PREREQUISITES:

two pointers, dynamic programming

PROBLEM

SLOWER SOLUTION

Let’s first solve the problem in O(N2).

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 two-dimensional array dp[log[N]][N] where dp[r][b] denotes the minimum possible cost of getting the bear b to the r-th ancestor of the leaf where b starts.
To compute dp[r][b] we need values dp[r-1][1…N] — then we consider all possible matches that can happen in the r-th 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[r-1][b1] (i.e. Limak must bribe at least this number of referees to ensure that b1 gets to the level r-1) and b2 can get so far with cost dp[r-1][b2], then:

  • If b1 > b2, the bear b1 can get further with the cost dp[r-1][b1] + dp[r-1][b2], i.e. in the code we do dp[r][b1] = min(dp[r][b1], dp[r-1][b1] + dp[r-1][b2])
  • If b1 > b2 but b1 - b2 ≤ K, the bear b2 can get further with the cost dp[r-1][b1] + dp[r-1][b2] + 1
  • ... (similarly if b2 > b1)

It might seem that this approach has complexity O(N2 * 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(N2) pairs of bears and considering one match takes O(1), we get O(N2) in total.
See the implementation below:

const int INF = 1e9 + 5;
int h, k;
scanf("%d%d", &h, &k);
int n = 1 << h;
vector<int> skill(n);
for(int i = 0; i < n; ++i)
	scanf("%d", &skill[i]);
vector<int> dp(n, 0);
for(int level = 0; level < h; ++level) {
	int block = 1 << level;
	vector<int> old = dp;
	dp = vector<int>(n, INF);
	for(int start = 0; start < n; start += 2 * block)
		for(int i = start; i < start + block; ++i)
			for(int j = start + block; j < start + 2 * block; ++j)
				for(int rep = 0; rep < 2; ++rep) {
					swap(i, j);
					if(skill[j] < skill[i])
						dp[i] = min(dp[i], old[i] + old[j]);
					else if(skill[j] <= skill[i] + k)
						dp[i] = min(dp[i], old[i] + old[j] + 1);
				}
	
}
int ans = dp[0];
if(ans >= INF) ans = -1;
printf("%d\n", ans);

FAST SOLUTION

To get O(N*log2(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(size2).
So far, if the subtree of the left child had leaves b1, b2, …, bp, and the subtree of the right child had leaves bp+1, bp+2, …, b2*p (remember that leaves denote bears that could get to this vertex), then we considered O(p2) matches separately.
Instead, we can build some data structure on costs of b1, …, bp, and then for each of bi in bp+1, bp+2, …, b2*p consider two things:

  • This bi can advance further by winning a match with some bj among b1, ..., bp, but only if skilli > skillj. So we can ask the data structure about the smallest possible cost of some bear from bp+1, bp+2, ..., b2*p with skill smaller than skilli.
  • Or this bi can advance further by winning a match with someone stronger by at most K, what of course will increase the total cost by 1. Here we should ask the data structure about the smallest possible cost of some between with skill in interval [skilli + 1, skilli + K].

Such approach gives the O(N*log2(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:

Setter’s solution can be found here.
Tester’s solution can be found here.

2 Likes

anyone done it using greedy approach ?

I’m not aware of any such solution.

Can we solve this questions using the following approach? I haven’t coded it yet because I’m not sure whether it is correct or not.

The approach is to first create a binary tree in which each node will store the strength of the node that will be the winner from ith index to the jth index in the optimum scenario [Means the case when Limak will be the winner and He would have bribed the min. number of referees.], that means in the starting the root node will contain the strength of the first node because we want it to be the winner from [1,n] indexes and the leaf nodes will contain the strength of the respective indexes. So now we need to find the other missing values of the tree.Now how we will find the value is Let’s take the sample case and in that the case number 2. So in that, the root will contain 18 initially and as we know it came from the left so left child should also contain 18 but what will the value be in the right child??? We can find that value with the value of K and lower_bound because as we know the value of K is 10 so we can’t have a value greater than 28 at the right child so We will select the largest value which is less than or equal to 28 from the right half of the array and we can find that value using Merge Sort Tree. So we will have 26 for this case and similarly recursively we will build the tree. After we have the tree we just need to traverse the tree once to count the number of matches where Limak needs to bribe the referee.

The -1 case can be seen at the time of Binary Tree creation.

I don’t know whether the logic is correct or not and also if it is correct whether with the help of Merge Sort Tree its possible to find the largest value less than or equal to Some integer x for any range [l,r].

1 Like

I don’t think it will work, sometimes it’s not optimal to let lower_bound of A[0] + k qualify for the final round, sometimes it might be lower_bound of A[0], and even sometimes neither of them

In the tester’s solution is segment tree stored per node?

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:

  1. for(int level = 0; level < h; ++level)
  2. for(int start = 0; start < n; start += 2 * block)
  3. for(int i = start; i < start + block; ++i)
  4. for(int j = start + block; j < start + 2 * block; ++j)
  5. for(int rep = 0; rep < 2; ++rep)

Operations require in each for loop:

  1. log(n)
  2. n/(2*block)
  3. block
  4. block
  5. 2

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)

1 Like

@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?

4 Likes