Editorial for COCI '19 Contest 2 #2 Slagalica
Submitting an official solution before solving the problem yourself is a bannable offence.
The first subtask was solvable via simple case analysis with a couple of well-placed if statements.
The second subtask could have been solved by trying out all permutations of puzzle pieces in time complexity .
The third subtask could have been solved by observing that we must alternate between pieces of type 1 and 4 so it's always optimal to take the piece that fits and has the smallest number written on it. If we have some leftovers at the end, the puzzle cannot be solved.
Regarding the fourth subtask, let's assume we have already placed some pieces and the last one that was placed had a hole on its right end. The next piece that will be placed must have a bump on its left end, and that condition is satisfied only by pieces of type 1 and 2. If we place a piece of type 2, the right side remains a hole and we will again need to place a piece of type 1 or 2 next. On the other hand, if we place a piece of type 1, then in the next step we'll have to place a piece of type 3 or 4 (following a similar argument). Therefore, we could think of piece 1 as a piece that, in a sense, changes the form of the next piece. By analogy, the same holds for piece 4. Therefore, in this subtask we will first place all pieces of type 2 (or 3, depending on the left bound), then we'll place a piece of type 1 (or 4), and finally we'll place all pieces of type 3 (or 2). We always place the piece of the proper type with the smallest possible value. We must also take extra care of a special case where there is no piece of type 1 or 4.
Finally, to solve the entire task, let's consider a naive greedy algorithm in which we always pick a piece that fits and has the smallest possible number written on it. The problem is that we may end up with some leftover pieces of types 2 or 3 (if any other type remains, the puzzle cannot be solved). We can fix this by inserting those pieces in the last place (farthest from the left) where they could fit. That place will always be adjacent to the last piece of type 1 or 4.
Time complexity:
Comments