Editorial for Yet Another Contest 5 P2 - Big Score - Olympiads Online Judge

Editorial for Yet Another Contest 5 P2 - Big Score

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.

Author: RandomLB

Subtask 1

Notice that the only choice of $i$ ~i~ and $j$ ~j~ for Josh is $i=2$ ~i=2~ and $j=1$ ~j=1~. This means vault $1$ ~1~ must contain more coins than it had originally, and vault $2$ ~2~ must contain fewer coins than it had originally.

Similarly, the only choice of $i$ ~i~ and $j$ ~j~ for Nils is $i=1$ ~i=1~ and $j=2$ ~j=2~. This means vault $2$ ~2~ must contain more coins than it had originally, and vault $1$ ~1~ must contain fewer coins than it had originally.

Since Mike only removes coins from vaults, both vaults must contain fewer coins than they had originally.

So, we will be able to uniquely determine the array that Josh operated on by finding the array with the most number of coins in vault $1$ ~1~, and likewise for Nils by finding the array with the most number of coins in vault $2$ ~2~. The remaining array must have been operated on by Mike.

Time Complexity: $\mathcal{O}(\sum N)$ ~\mathcal{O}(\sum N)~

Subtask 2

Notice that each operation that Josh and Nils make will decrease the sum of coins across all vaults in the array by $1$ ~1~, while each operation that Mike makes will decrease the sum of coins across all vaults in the array by $2$ ~2~.

In other words, if the original sum of coins in all three arrays were $X$ ~X~, the sum of coins in the arrays that Josh and Nils operated on will be $X-K$ ~X-K~, and the sum of coins in the array that Mike operated on will be $X-2K$ ~X-2K~, where $K$ ~K~ is the number of operations that each person performed.

So, we can first find the total remaining number of coins for each array. Two of the arrays will have the same sum, while the remaining array will have a lesser sum. The array with a lesser sum must have been operated on by Mike.

Now, we need to determine who operated on the remaining arrays. It turns out that the lexicographically greater array greater must have been operated on by Josh, and so the other array must have been operated on by Nils.

Proof

Since each of Josh's moves removed two coins from a vault $i$ ~i~ and added one coin to a vault left of vault $i$ ~i~, the leftmost vault operated on by Josh must contain more coins than it had originally.

Conversely, since each of Nils's moves removed two coins from a vault $i$ ~i~ and added one coin to a vault right of vault $i$ ~i~, the leftmost vault operated on by Nils must contain fewer coins than it had originally.

Now, let vault $x$ ~x~ be the first vault operated on by either Josh or Nils. Since each vault to the left of $x$ ~x~ was untouched, they will contain the same number of coins. So, if we are able to show that Josh's vault $x$ ~x~ always contains more coins than Nils's vault $x$ ~x~, we have determined that Josh's array is always lexicographically greater. There are now three cases to consider:

Case 1: Vault $x$ ~x~ was only operated on by Josh.

Josh's vault $x$ ~x~ must contain more coins than it had originally, and Nils's vault $x$ ~x~ contains the original number of coins, so Josh has more coins in vault $x$ ~x~.
Case 2: Vault $x$ ~x~ was only operated on by Nils.

Josh's vault $x$ ~x~ contains the original number of coins, and Nils's vault $x$ ~x~ must contain fewer coins than it had originally, so Josh has more coins in vault $x$ ~x~.
Case 3: The vault $x$ ~x~ was operated on by both Josh and Nils.

Josh's vault $x$ ~x~ must contain more coins than it had originally, and Nils's vault $x$ ~x~ must contain fewer coins than it had originally, so Josh has more coins in vault $x$ ~x~.

Thus, we have shown that Josh's array is always lexicographically greater than Nils's.

Although it is not necessary to prove that Josh's final array is always lexicographically greater than Mike's final array, we also outline it here due to its usage in the full solution.

Since each of Mike's moves can only remove coins from vaults, any vault operated on by Mike must contain fewer coins than it had originally. We can then directly apply the same proof process used to show that Josh's array is always lexicographically greater than Nils's.

Time Complexity: $\mathcal{O}(\sum N)$ ~\mathcal{O}(\sum N)~

Subtask 3

Note that we can no longer determine the array that has been operated on by Mike by simply checking the sums of the arrays.

Instead, similarly to our solution in subtask 2, we can determine the array that is lexicographically greatest. This array must have been operated on by Josh.

We can then determine the array that is lexicographically greatest when considering the array in reverse. This array must have been operated on by Nils, which can be proven similarly to the proof outlined above.

The remaining array must have been operated on by Mike.

Note that a solution that may seem correct but fails is to first determine the array that Josh operated on, then determine the arrays that Nils and Mike operated on by lexicographically comparing them (in non-reverse order). This solution is incorrect since the arrays operated by either person could be the lexicographically maximal array of the two.

As a final note, the full solution presented here works even if each person performed a different (positive) number of operations.

Time Complexity: $\mathcal{O}(\sum N)$ ~\mathcal{O}(\sum N)~

Comments

There are no comments at the moment.