BLIMP Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Ashish Gangwar
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

1831

PREREQUISITES:

None

PROBLEM:

There are N cities in a row. The i-th city from the left has a sadness of A_i.

In an attempt to reduce the sadness of the cities, you can send blimps from the left of city 1 that move rightwards (i.e, a blimp crosses cities 1, 2, \ldots in order)

You are given two integers X and Y. For each blimp sent, you can make one of the following choices:

  • Let the blimp fly over every city, in which case the sadness of every city will decrease by Y, or,
  • Choose a city i (1 \leq i \leq N), and shower confetti over city i. In this case, the sadness of cities 1, 2, \ldots, i-1 will decrease by Y, the sadness of city i will decrease by X, and cities i+1, \ldots, N see no change in sadness.

Find the minimum number of blimps needed such that, by making the above choice optimally for each blimp, you can ensure that no city is sad (i.e, in the end every city has sadness \leq 0).

EXPLANATION:

Case \;1: X \leq Y: In this case, since X is always smaller than Y, so it won’t make sense to shower confetti over any city so we would just let the blimp pass over each city and thus for each blimp the sadness of all cities would reduce by Y. Thus our answer would be

ans = \lceil \frac{A_{max}}{Y} \rceil \\ where \; A_{max} = max(A_i), 1 \leq i \leq N

Case \;2: In this case it would be most efficient to show confetti to the farthest right city that has a positive value. This way all the cities before that would have their sadness reduced by Y and the last city would have its sadness reduced by X. Showering confetti before the last city with positive sadness won’t make sense since then the cities after that won’t have any sadness reduced.
In this case we would loop from end to start to calculate and for each say, the i_{th} city, we would calculate its current value, which would be the total number of blimps passed through it before the blimp started showering confetti on it. Let us assume total number of blimps passed as total\_blimps, and the sadness levels of the i_{th} city as A[i]

A[i] = max(0,A[i] - total\_blimps \times y) \\ total\_blimps = total\_blimps + \lceil \frac{A[i]}{X} \rceil

Our final answer would be total\_blimps at the end of the loop.

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2

Why there are to much Observation based problem on codechef ?
I have solved till this question of contest What i have observe is that all the question is to make some observation and implement them .

2 Likes