I have been trying to solve Day1 C problem and there is no editorial(at least I didnt find it). I've tried understanding codes, but I have no idea. If somebody did solve it could you explain your idea?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I have been trying to solve Day1 C problem and there is no editorial(at least I didnt find it). I've tried understanding codes, but I have no idea. If somebody did solve it could you explain your idea?
Name |
---|
Auto comment: topic has been translated by Nurss (original revision, translated revision, compare)
Bump
bump bump
I was actually on this competition. Took me years to upsolve the task. The solution is the following:
It uses a technique called "Simple Linear Programming". Essentialy each of the queries can be reformulated as "we need at least k ones or at most k ones in the subbaray [l, r]". Now let's define a prefix array in which p[i] is the sum of ones up until i. Then we can set some constraints:
1) Query for at least k ones between l and r. Then p[r]-p[l-1] >= k then p[l-1]-p[r] <= -k;
2) Query for at most k ones between l and r. Then p[r]-p[l-1] <= k;
3) p[i]-p[i-1] <= 1 and p[i-1]-p[i] <= 0
Now we can turn each constraint into an edge in the following way: each constraint p[i]-p[j] <= x, becomes a weighted edge (j, i, x);
Now you probably wonder how does that help? Well, if you have a negative cycle in this graph, there is no answer to the problem. Why? I leave this link to an MIT lecture as a proof.
In the end, you can create an auxiliary vertex, connect it to all other vertices with edges with weight 0. Run Belman-Ford and assing p[i] = dis[i]. You can see that this way all constraints will be satisfied.
I hope this will be helpful to you, as I myself have struggled with this task a lot.
Thanks! got it, cool idea!
Is there some cf blog for "Simple linear programming" or problems to it?
I would suggest you check out the Usaco Guide on Negative cycles. Unfortunately, they don't provide any other tasks on "Simple Linear Programming" but have other very cool tasks with negative cycles worth checking out. Good luck!