Link to the Problem : https://codeforces.com/contest/1332/problem/D
So basically it's a constructive problem.
First Step to realize is that how dp solution is not optimal.
Let's see using an example
I will be using 1 based indexing
In the figure above we see if we move from cell (1,1) to (2,2) then going from (1,1) -> (1,2) -> (2,2) is optimal according to the dp which results is (1 1 0) for block (2,2) . But for block (3,3) we will also use this path only according to dp because it was the optimal path before but that leads to wrong answer. Why? Because if we choose path from (1,1) -> (2,1) -> (2,2) -> (3,3) we will get better answer(1 0 1) than using the dp path(1 0 0).
So only time we want to drop some non optimal path that will be when non_optimal&optimal = non_optimal which basically means that non_optimal always have subset bits set compared to optimal and will never produce a better answer later on.
After this realization it's just implementation.
So we would like to choose a number which dosen't interfere with other bits in the answer and is also < 3 * 1e5 which is the constraint for any given cell . 2^17 seems to be a good number as it's less than 3* 1e5 and also more than 1e5 so it won't interfere with the k.
From the 2nd figure above we can see how arranging elements will produce an error of exactly k.
Answer according to the path of dp will be 0 and optimal path will give result k. So difference is exactly k.
Submission Link : https://codeforces.com/contest/1332/submission/75186543
So basically it's a constructive problem.
First Step to realize is that how dp solution is not optimal.
Let's see using an example
In the figure above we see if we move from cell (1,1) to (2,2) then going from (1,1) -> (1,2) -> (2,2) is optimal according to the dp which results is (1 1 0) for block (2,2) . But for block (3,3) we will also use this path only according to dp because it was the optimal path before but that leads to wrong answer. Why? Because if we choose path from (1,1) -> (2,1) -> (2,2) -> (3,3) we will get better answer(1 0 1) than using the dp path(1 0 0).
So only time we want to drop some non optimal path that will be when non_optimal&optimal = non_optimal which basically means that non_optimal always have subset bits set compared to optimal and will never produce a better answer later on.
After this realization it's just implementation.
So we would like to choose a number which dosen't interfere with other bits in the answer and is also < 3 * 1e5 which is the constraint for any given cell . 2^17 seems to be a good number as it's less than 3* 1e5 and also more than 1e5 so it won't interfere with the k.
From the 2nd figure above we can see how arranging elements will produce an error of exactly k.
Answer according to the path of dp will be 0 and optimal path will give result k. So difference is exactly k.
Submission Link : https://codeforces.com/contest/1332/submission/75186543
No comments:
Post a Comment