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.