CC November Long featured 9 problems per division, there was a wide range of topics involved. I setted the easiest (ADADISH) and one of the three hardests (RB2CNF).
You can read the Editorials in codechef and the Video-Editorials in youtube. Here is a general feedback on the problems
ADADISH, usually we have an implementation only problems in the first slot, I was a bit afraid some people could not solve it. Fortunately we reached the expected 10K ACs. I messed up with the explanation of the third example (initially there was 4 examples, then I removed one but kept the incorrect explanation). It turns out that even in the cakewalk we got an unexpected solution; since constraint are small, it works to greedily assign each dish to the least bussy burner.
RESTORE, I expected it to be a bit harder than FEMA2, for some reason it got more ACs. I think it was good to place it in div1 instead of FEMA2, because I feel it requires more thinking.
FEMA2, Initially I gave it a simple difficulty, because the first greedy that comes to mind works. It seems after formalizing the law of attraction in a formula and adding the “sheets” it became a bit harder. There was a character error in the statement (>= while the correct one is >) most contestants noticed it because it is more natural to think that we can attract something if the magnetic field is non-zero.
CNDYGAME, it requires some case work analysis, also the rules of the game are a bit intricate. The optimal strategy is very natural. I think many contestants solved it without a proof.
SCALSUM, I liked the idea of sqrt decomposition on layers, at first I thought memory is N sqrt N, but it turns out it is linear. Some contestants got AC with unordered_map anyways. There is another solution using the Mo-trick
UNSQUERS, initially it asked only for an offline solution. We added the online version to have a complete study of the problem. If you know persistent structures, it is not too hard to extend from offline to online. There is also a solution with sqrt-decomposition
CHEFSSM, polynomials and generating functions, it requires some mathematical processing. Initially it contained a formal description, in terms of sets and summations. I think it is better when problems have a story if it naturally fits the formalism.
RB2CNF, for a general expression it is NP, however colours make it solvable in polynomial time! The idea is that to satisfy a set of conditionals we only have to remove all paths that goes from true to false i.e min-cut = max-flow. Initially I expected a medium difficulty, but few preople solved it. The graph of conditions is very special, I’m wondering if is possible to solve such flows more quickly (e.g for N,M<=1e5)
PANIC, The first idea that comes to mind is matrix exponentiation, but in the review I didn’t find an easy way of getting the recurrence. The expected solution required the Berlekamp-Massey algorithm, randomization and compressing the matrix. (Unfortunately?) contestants found an easier solution. The setter suggested changing the problem to prevent such approaches, however it was a bit late to change it. Now that I think about it again, instead of changing the problem we could have added one more problem with the more general recurrence instead of fibonaccies.
SELEDGE, We ended up with three different approaches, the expected randomized solution is the more elegant one, but contestants found another solution based on matchings.
CONGRID, we had some troubles with the statement during the review process, I had to rewrite many parts of it. Some contestants ACed (with zero points) by just printing 0, maybe we should have placed a lower bound on the number of paths to get only meaningful submissions. This is the first time we make the generator public, I think it was a good idea, it prevents possible mismatches with the description of the test generation section.
aleigorithms 