Editorial for DMOPC '21 Contest 8 P1 - Peanut Planning

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: Riolku

Subtask 1

For this subtask, the question is simply whether or not we have enough $2$ ~2~s. If we have at least $\left\lfloor\frac{N}{2}\right\rfloor$ ~\left\lfloor\frac{N}{2}\right\rfloor~ twos, then we can place them in between the ones, and we have a solution.

For the lexicographically least version, make sure to place the ones as early as possible.

Non Lexicographically Least

In order to get any valid solution, we should do two things. One, sort and separate the array into the lower half and the upper half. It is optimal to place the lower half in the odd positions because it gives us the best chance of getting a valid array, for instance, if we have 1 1 2, with $M = 3$ ~M = 3~, it would be a bad idea to put the upper half in the odd positions, because we would get 1 1 2, which does not satisfy the constraints, but 1 2 1 does.

It suffices to put the lower half at the odd indices and the upper half at the even indices and furthermore, to sort the upper half in decreasing order and the lower half in increasing order. For instance, if $M = 5$ ~M = 5~ and we are given 1 2 3 4, then we should make 1 4 2 3, not 1 3 2 4, since the latter does not satisfy the constraints. It can be proven that this algorithm always finds a solution if one exists.

Lexicographically Least

Sort $a$ ~a~. We have to place $a_1$ ~a_1~ somewhere, and as we hinted at before, it is optimal to place it first, so that we only have to find one large element to put next to it, not two.

Then, to choose the rest of the elements, it is optimal to always choose the smallest element we have remaining in order to get the lexicographically minimal solution.

For the second subtask, we can use a list and linear search, for $\mathcal O(N^2)$ ~\mathcal O(N^2)~.

Optimizations

To optimize the solution, we have a few options, the simplest of which is a multiset. We can also binary search and use DSU to check for an element the next free element.

We can actually implement this with just a linked list, storing the sorted elements. We alternate: for odd indices, we take the smallest element in the list. For even indices, we maintain an iterator. At each step, either the element we take is directly after the last even element we took, or it is smaller. This yields an amortized $\mathcal O(1)$ ~\mathcal O(1)~ operation per step.

Comments

3

yeerk16 commented on May 1, 2022, 4:15 a.m.

Fun problem :)!

Would anyone be able to expand on this for me (I solved it differently and am interested in learning some other approaches): "We can also binary search and use DSU to check for an element the next free element." Thank you!

2

Riolku commented on May 4, 2022, 1:08 a.m.

Basically the idea is to use a DSU to "skip over" used elements. At the beginning all the nodes are separate. Then when we use item $i$ ~i~, we merge with $i + 1$ ~i + 1~, so that $i$ ~i~ points to $i + 1$ ~i + 1~ (think of this like a directed edge). Then when we binary search, when we consider an element, if it's used, when we check the DSU, it will point to the next free element.

This is sort of a way to emulate a set when we only remove/add elements.

On that note, we could even use a BIT to emulate this set.

2

yeerk16 commented on May 5, 2022, 1:07 a.m.

Thank you! That is neat. I used the segment tree idea (like the BIT idea that you mentioned) but didn't have that DSU insight.

For DSU, is there a way to get away without using coordinate/index compression here?

2

Riolku commented on May 5, 2022, 5:45 p.m.

Hm, I don't really feel like I'm compressing, but it is required that you sort the input. I suppose since I'm binary searching over the sorted input and merging the indices, it's basically coordinate compression. I'll link my implementation of this, in case people want to take a look after solving.

2

yeerk16 commented on May 6, 2022, 2:16 p.m.

Oh ya, thank you, that was what I meant.

I feel like even with a multiset in C++ this is a 10 point problem? I know that people don't have to prove the greedy idea here and can just guess that it works and use it, though...

2

Riolku commented on May 17, 2022, 4:53 a.m.

Proving it works is indeed non-trivial. However, for most contestants, the intuition is there, and is sufficient in contest situations.