Woburn Challenge 2018-19 Round 2 - Senior Division

Problem 2: Plutonium

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 ≤ N ≤ 200,000) days, and it had P_i (1 ≤ P_i ≤ 10⁶) 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). On each subsequent day i (2 ≤ i ≤ 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..N (0 ≤ O_i ≤ 10⁶). 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..N. It's also possible that Luther's observations are inconsistent with any possible sequence of events.

Subtasks

In test cases worth 6/20 of the points, N ≤ 20.
In test cases worth another 8/20 of the points, N ≤ 2000.

Input Format

The first line of input consists of a single integer, N.
The next line consists of N integers, O_1..N.

Output Format

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

6
1 0 0 0 3 0

Sample Output 1

1 3

Sample Input 2

3
1 0 4

Sample Output 2

-1

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.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Dec 14, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)