You are not logged in. Please login at www.codechef.com to post your questions!

×

Question regarding problem statement of Sereja and Ballons - SEABAL

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[i] to r[i] 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[i], r[i]]?

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[i]., which can be found as: y[i] = x[i] + ans[i - 1], wherein ans[0] = 0, аnd ans[i] (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[i]?

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

asked 11 Aug '13, 12:51

tyrant's gravatar image

2★tyrant
1.2k202734
accept rate: 12%

edited 11 Aug '13, 12:53


"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[i] is calculated as y[i] = x[i] + ans[i-1], wherein ans[0] = 0, аnd ans[i] (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)

link

answered 11 Aug '13, 13:17

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

edited 11 Aug '13, 13:19

What an answer! Thank you very much. I get it now ;)

(11 Aug '13, 13:28) tyrant2★
1

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

(11 Aug '13, 13:30) tijoforyou2★
1

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

(11 Aug '13, 13:33) tyrant2★

Thank You. :D

(11 Aug '13, 13:35) tijoforyou2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,424
×67

question asked: 11 Aug '13, 12:51

question was seen: 1,112 times

last updated: 11 Aug '13, 13:35