Nurss's blog

By Nurss, history, 20 months 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

»
20 months 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)

»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Bump

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

bump bump

»
20 months 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.

  • »
    »
    20 months 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?

    • »
      »
      »
      20 months 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!