Round 1C was not too bad, the questions were manageble. I finished the problems post contest, I had some help coming up the solution after reading how others did it and I found them rather enlightening.

Problems for codejam 2018 1C here.

Whole New Word

The most obvious and straightforward way of solving this problem is to generate all possible strings and check them one by one. But to be able to do that, we will first have to get a set of all the characters, L different sets in total.

For each position, we track the possible chracters that can be in that position. Then the build function recursively traverse through these set of characters, returning once there is a valid answer.

Considering there is only N strings in total (all unique), to find the first valid combination, it will take at most N+1 tries.

Lollipop

Well, the most straightforward way is to just give our lollipops willy nilly. But of course, we are able to “guess” the probability of the types of lollipops, judging by the occurance of the different kinds of lollipops (appear more -> more popular -> give later).

Ant Stack

The idea to this problem is fairly interesting. Given an additional ant, the most efficient stack possible containing N ants can only improve (in terms of minimum weight).

With a newer ant that is lighter, one of the ants in the previous stack can be replace. And if the newly added ant does not make a difference, its will not change the optimal stack arrangement.

So how can we check if the newer ant will result in a more efficient stack arrangement? First we check if it is possible to add on the new ant below the currently existing stack of ants (the six times the weight criteria), and if it is possible, it will thus becomes the tallest stack that we have so far.

This idea became clear to me only after a while of tracing, so in case the future me tries to read this and gets a little muddled-head, do some tracing.

end

note to future self: looking at top contestants code can be frustrating, but once you figure out how it works, you can write produce those pretty amazing solutions too.