You are not logged in. Please login at www.codechef.com to post your questions!

×

# BRIBETR - Editorial

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

MEDIUM

# PREREQUISITES:

two pointers, dynamic programming

...

# 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.

This question is marked "community wiki".

asked 25 Feb '17, 23:37

980118
accept rate: 30%

19.5k348496535

 1 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]. answered 26 Feb '17, 01:36 11 accept rate: 0% 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 (26 Feb '17, 02:33)
 1 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: for(int level = 0; level < h; ++level) 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) Operations require in each for loop: log(n) n/(2*block) block block 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) link This answer is marked "community wiki". answered 26 Feb '17, 23:29 112●5 accept rate: 11%
 0 anyone done it using greedy approach ? answered 26 Feb '17, 00:23 4★docodon 77●6 accept rate: 0% I'm not aware of any such solution. (26 Feb '17, 00:27)
 0 In the tester's solution is segment tree stored per node? answered 26 Feb '17, 04:40 4★ps_1234 59●3 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,029
×2,482
×1,907
×95
×52
×27

question asked: 25 Feb '17, 23:37

question was seen: 1,509 times

last updated: 10 Aug, 16:26