Editorial for WC '18 Contest 2 S2 - Plutonium

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let's iterate over the days in reverse order, from $N$ ~N~ down to $1$ ~1~, while filling in their actual $P$ ~P~ values. We'll use $P_i = 0$ ~P_i = 0~ to represent $P_i$ ~P_i~ being allowed to take on any value based on $P_{i \dots N}$ ~P_{i \dots N}~, and we'll set $P_{N+1} = 0$ ~P_{N+1} = 0~ for convenience.

When processing a day $i$ ~i~, we should first consider whether or not there's a conflict between it and day $i+1$ ~i+1~, such that there's no way to assign both of them valid $P$ ~P~ values. This is only the case when $O_i \ge 1$ ~O_i \ge 1~, $P_{i+1} \ge 2$ ~P_{i+1} \ge 2~, and $O_i \ne P_{i+1}-1$ ~O_i \ne P_{i+1}-1~. If we encounter any instances of this, we should immediately output -1.

We should then fill in day $i$ ~i~'s $P$ ~P~ value. If $O_i$ ~O_i~ is positive, then we must have $P_i = O_i$ ~P_i = O_i~. Otherwise, if $P_{i+1} \ge 2$ ~P_{i+1} \ge 2~, then we must have $O_i = P_{i+1}-1$ ~O_i = P_{i+1}-1~, and in the remaining case (when $P_{i+1} \le 1$ ~P_{i+1} \le 1~), we can set $O_i = 0$ ~O_i = 0~.

Having filled in the $P$ ~P~ values, we can examine them to determine the minimum and maximum possible number of withdrawals. Let's consider each day $i$ ~i~ such that $2 \le i \le N$ ~2 \le i \le N~. If $P_i = 1$ ~P_i = 1~, then there must have been a withdrawal on that day. And if $P_i = 0$ ~P_i = 0~, it's possible that there either was or wasn't a withdrawal on that day.

Comments

There are no comments at the moment.