Nurss's blog

RMI_2019, day1 Restore problem, no editorial = no understanding
By Nurss, history, 21 month(s) ago, translation, In English

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?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by Nurss (original revision, translated revision, compare)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Bump

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

bump bump

→ Reply
»
21 month(s) ago, # |
← Rev. 4   Vote: I like it +26 Vote: I do not like it

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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! got it, cool idea!

    Is there some cf blog for "Simple linear programming" or problems to it?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like 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!

      → Reply