WC '18 Contest 2 S2 - Plutonium

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types
Woburn Challenge 2018-19 Round 2 - Senior Division

Ethan Hunt has traced a string of illegal plutonium trafficking down to a remote warehouse situated on a frigid island in Nunavut!

The warehouse has been operating for a period of N (1 \le N \le 200\,000) days, and it had P_i (1 \le P_i \le 10^6) boxes of plutonium in stock at the end of the i-th day.

At the end of the first day, there was a single box (P_1 = 1). On each subsequent day i (2 \le i \le N), it's possible that a buyer came to withdraw all of the plutonium in the warehouse in the morning. Whether or not that occurred, one new box of plutonium then arrived at the warehouse in the afternoon. In other words, if a withdrawal occurred on day i, then P_i = 1, and otherwise, P_i = P_{i-1} + 1.

Ethan has entrusted the task of monitoring the warehouse to his friend and fellow IMF member Luther Stickell. Accurately monitoring the warehouse proved problematic, but Luther did his best to come up with a list of observations O_{1 \dots N} (0 \le O_i \le 10^6). If O_i = 0, then Luther has no idea how much plutonium the warehouse had in stock at the end of the i-th day. Otherwise, if O_i > 0, then Luther believes that the warehouse had exactly O_i boxes of plutonium in stock at the end of the i-th day (in other words, that P_i = O_i).

Ethan would now like to use Luther's observations to determine how many sellers withdrew plutonium from the warehouse. Due to gaps in Luther's observations, there may be multiple sequences of events which are consistent with them, so Ethan is interested in both the minimum and maximum possible number of withdrawals which could have taken place over the course of days 2 \dots N. It's also possible that Luther's observations are inconsistent with any possible sequence of events.


In test cases worth 6/20 of the points, N \le 20.
In test cases worth another 8/20 of the points, N \le 2\,000.

Input Specification

The first line of input consists of a single integer, N.
The next line consists of N integers, O_{1 \dots N}.

Output Specification

Output either two integers, the minimum and maximum possible number of withdrawals, or the single integer -1 if it's impossible for Luther's observations to be accurate.

Sample Input 1

1 0 0 0 3 0

Sample Output 1

1 3

Sample Input 2

1 0 4

Sample Output 2


Sample Explanation

In the first case, it's possible that plutonium was only withdrawn a single time, on the morning of the 3rd day. It's also possible for as many as 3 withdrawals to have taken place, on the mornings of the 2nd, 3rd, and 6th days.

In the second case, the warehouse could contain at most 3 boxes of plutonium at the end of the 3rd day (if no withdrawals had taken place), which is inconsistent with Luther's observed count of 4.


  • 3
    kevinyang  commented on Jan. 17, 2021, 10:33 p.m.

    It might be helpful to know that although the problem statement says that P_1 is always 1, it does not necessarily mean that O_1 will always be 1