632A — Grandma Laura and Apples

There were no successful challenges for this problem. Thumbs up to everyone! I did find a couple of C/C++ solutions with uninitialized local variables though. Fortunately for them, the top of the stack is filled with zeros in the current testing system and compiler didn't decide to place uninitialized local variables in the register.

632B — Alice, Bob, Two Teams

There was quite a variety of off-by-one errors in this problem. My most successful test was

2
1 1
BB

Some solutions just have to flip something. The were also 2 challenges where solution got TL due to slow input.

The most crazy uninitialized variable prize for this problem goes to 16447719:

ll n;
v b(n);

cin >> n;

forn(i, n)
{
    cin >> b[i];
}

What is the size of vector b? Definitely not n. Fortunately for the author, it can't be challenged. Undefined behavior can work in your favor too. BTW, thanks to Codeforces for custom invocation feature. This is my go to tool when I need to know the value of an uninitialized variable.

632C — The Smallest String Concatenation

Most challenges in this problem were anti-quicksort tests for Free Pascal solutions. One person used normal sorting with lexicographical order followed by bubble sort using the correct order. Turned out this is not fast enough on certain tests. Understandably, not everyone knows how to use custom comparator. You can learn C++98 and C++11 way of doing this in the example section here: std::sort. I tried to challenge 2 C/C++ solutions with qsort() but both of them fit in the time limit despite spending O(n²) time for sorting.

632D — Longest Subsequence

Most challenges in this problem used test with the zero answer like:

1 1
2

I am surprised that this test was missing in the author test set. The other half of the challenges were caused by m being bounded by only 438056 instead of 1000000 in the author test set. Some solutions were not fast enough and exceeded time limit for the largest value of m. Also, some solutions didn't merge equal numbers in the input and were challenged by the test with all ones. Spending O(m) time for each one in the input doesn't fit in the time limit. There were also a couple challenges were authors initialized answer (k_max) with 1 instead of 0 while calculating LCM with the maximum answer. So in the case of single number in the input, they used default value of LCM equal to 1. This fails for the test with the different answer like this:

1 3
2

632E — Thief in a Shop

Let us denote a the maximum number in the input. One solution tried to used normal O(k²an) dynamic programming approach (calculate the set of all sums of k numbers from a set of sums of k — 1 numbers) to this problem but with the twist: consecutive sums were compressed to a single interval. This worked very well on the author test set until it was challenged (not by me) with the test where all numbers are divisible by 3. One more solution were too close to the time limit and were hacked by random large test.

I challenged all solutions which used FFT over remainders by modulo p with a single power step. All I needed is to construct a test where the number of ways to get the same sum is divisible by p. I used the test of the form 1, 2, N-i1, N-i2, ... , N-i2D. The sum N + k in this test can be represented in Ci1k+Ci2k+...+Ci2Dk ways as a sum of k+1 numbers where C is binomial coefficient. So I just need to find the set of binomial coefficients which sum is divisible by p. How did I do that? Why I use even number of binomial coefficients? Meet me in the middle here, I can't tell you everything.

Unfortunately, there were no way to challenge dynamic programming solutions. These solutions first subtract the minimum number from the rest of them. This step reduces the problem to a case where the first number is zero. Since zeros doesn't influence sums, we now need to calculate all the sums of no more than k of non-zero numbers. Our dynamic programming will store for each sum the least number of non-zero numbers needed to get it. We will add non-zero numbers one by one. Each time we need O(ak) time to recalculate dynamic programming values. Recalculation should be done from small sums to large so that the current non-zero number could be used multiple times. After n-1 steps we choose all sums with values less than or equal to k. The time complexity of this algorithm is O(akn).

632F — Magic Matrix

A lot of solutions for this problem just randomly choose triplets i, j, k and check condition from the problem statement. They can be challenged by the graph where all edges have length 2 except a single triangle which contains 2 edges of length 0 and 1 edge of length 1. This triangle is the only triplet which doesn't satisfy magic matrix conditions in this graph. A couple solutions tried to optimize the full search by excluding some triplets using various conditions but these optimizations doesn't improve the worst time complexity of O(n³). A couple solutions only checked triplets with i = 0 and a couple more only checked some naive properties like all maximum values in rows are equal to each other.

The prize for the most confusing undefined behavior goes to 16449526. What the first solve function returns at the end? Does it even matter? Experimentally, I figured out that it is simply missing return true. I couldn't challenge it but it failed system tests. I don't know whether it was caused by undefined behavior or some other error though.

PS If I missed some interesting challenge, post it in the comments.