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 Pi (1 ≤ Pi ≤ 106) 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 (P1 = 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 Pi = 1, and otherwise, Pi = Pi − 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 O1..N (0 ≤ Oi ≤ 106). If Oi = 0, then Luther has no idea how much plutonium the warehouse had in stock at the end of the i-th day. Otherwise, if Oi > 0, then Luther believes that the warehouse had exactly Oi boxes of plutonium in stock at the end of the i-th day (in other words, that Pi = Oi).
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.
In test cases worth 6/20 of the points, N ≤ 20.
In test cases worth another 8/20 of the points, N ≤ 2000.
The first line of input consists of a single integer, N.
The next line consists of N integers, O1..N.
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
Sample Input 2
3 1 0 4
Sample Output 2
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.
Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Dec 14, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3