Question regarding problem statement of Sereja and Ballons - SEABAL

long-contest
statement

#1

I’m having a hard time understanding what is the problem asking since the wording is really confusing. So I wonder if anyone could walk me through the example test case? Please note that, I’m not asking for hints, my goal is just to clarify the problem.
Here is the original question:

what is the count of the indices i
(1 ≤ i ≤ m), that all balloons in the
boxes with the indices from l* to
r* are already bursted.

  1. Does “count” means the number of indices from 1 to m?
  2. Does “all ballon” means all the balloons must be busted within range [l*, r*]?

Here is another one:

The next k line contains integers
x[1], x[2], …, x[k]. Index of the
box, in what Sereja bursted a balloon
at the step number i (1 ≤ i ≤ k), is
denoted as y*., which can be found
as: y* = x* + ans[i - 1], wherein
ans[0] = 0, аnd ans* (i>0) — is the
answer on the problem after ith
bursting of the balloons.

  1. Are x[1], x[2], …, x[k] indices of box? Then what is y*?

Now let’s take a look at the test case:
Input:
5 3
1 1 1 1 1
5 5
2 2
1 3
5
4
2
0
2
3

Output:
0
1
1
2
3

So we have 5 boxes (namely 1 to 5, index: 0 to 4), and 3 ranges: (5,5), (2,2) and (1,3)
At the beginning, all the balloons are not yet burst.
1 1 1 1 1
Now Sereja perform busting in k = 5 steps:
Step 1: 4
1 1 1 1 0

Step 2: 2
1 1 0 1 0

Step 3: 0
0 1 0 1 0

Step 4: 2
0 1 0 1 0

Step 5: 3
0 1 0 0 0

This is what I understand by “burst” a balloon at each step, then how come the answer is
0
1
1
2
3


#2

“Count” means number of indices.

“All balloons” MUST BE burst.

Your understanding is wrong. It is something like this, as far as I understood.

x[1], x[2] are not indices of boxes. But, y[1], y[2] are indices of boxes. And each y* is calculated as y* = x* + ans[i-1], wherein ans[0] = 0, аnd ans* (i>0) — is the answer on the problem after ith bursting of the balloons.

So we have 5 boxes (namely 1 to 5, index: 1 to 5), and 3 ranges: (5,5), (2,2) and (1,3)
At the beginning, all the balloons are not yet burst.
1 1 1 1 1

Step 1: 4 ==> x[1] = 4; ans[0] = 0; So, y[1] = x[1] + ans[0] = 4 + 0 = 4

1 1 1 0 1

None of (5,5), (2,2) and (1,3) have all balloons in the boxes burst.

So, ans[1] = 0 (which is the first line of output)

Step 2: 2 ==> x[2] = 2; ans[1] = 0; So, y[2] = x[2] + ans[1] = 2 + 0 = 2

1 0 1 0 1

(2,2) now has all balloons in the boxes burst. So, “count” of indices is now 1, as there is one index such that, all balloons in boxes within the range given in that index is burst.

So, ans[2] = 1 (which is the second line of output)

Step 3: 0 ==> x[3] = 0; ans[2] = 1; So, y[3] = x[3] + ans[2] = 0 + 1 = 1

0 0 1 0 1

Still, (2,2) is the only range where all balloons in the boxes are burst. So, “count” of indices is still 1.

So, ans[3] = 1 (which is the third line of output)

Step 4: 2 ==> x[4] = 2; ans[3] = 1; So, y[4] = x[4] + ans[3] = 2 + 1 = 3

0 0 0 0 1

Now, (2,2) and (1,3) qualify. So, “count” of indices will be 2.

So, ans[4] = 2 (which is the fourth line of output)

Step 5: 3 ==> x[5] = 3; ans[4] = 2; So, y[5] = x[5] + ans[4] = 3 + 2 = 5

0 0 0 0 0

All of (5,5), (2,2) and (1,3) have all balloons in the boxes burst. So, “count” of indices will be 2.

So, ans[5] = 3 (which is the fifth line of output)


#3

What an answer! Thank you very much. I get it now :wink:


#4

I have not yet solved it. But this is what I understood. Hope this clarification helps you to solve it. Good Luck! :smiley:


#5

@tijoforyou: Thanks! Best of luck to you too.


#6

Thank You. :smiley: