A week where OEIS helps understand the problem

Another eventful week in competitive programming comes to a close. First up was TopCoder SRM 660 (problems, results, top 5 on the left). After wasting about 25 minutes and getting a very low score on the 250, I've decided to go for 1000 in a bid to still win the match. This turned out to be a good strategy, if only I could finish the solution in time - but I ended up requiring 4 more minutes to get it to work after the end of the coding phase (it passed system tests in the practice room). In the absence of any solutions for the 1000, sky58 has won the SRM thanks to his fastest solution for the 500 - congratulations!

Solving the 1000 could be split into two big parts: coming up with easy-to-understand combinatorial objects that we needed to count, and counting them. The second part was a tough but relatively standard exercise, so I want to cover the first part now.

The problem statement was: consider sequences of N integers, each between 1 and N, inclusive, such that each integer appears at most K times. Consider the following operation on a sequence: pick two arbitrary numbers X and Y from 1 to N, replace all occurrences of X in the sequence with Y and vice versa, and then swap X-th and Y-th elements of the sequence. Consider two sequences equivalent if they can be transformed into each other using several such operations. How many different (pairwise non-equivalent) sequences exist?

This looks to be a quite abstract, and to be honest, arbitrary class of sequences and operation to work with, so it's hard to come up with a way to count equivalence classes. However, it turns out that these sequences are just a different description for a very natural combinatorial object! Can you see which one?

Here's how I approached this. I've quickly wrote an exhaustive search solution that solved this problem for small values of N and K. I've then written down the answers for small values of N and K=N (effectively no limit): 1, 3, 7, 19, 47, 130. I've entered those numbers into the OEIS - and the only result says that this is the number of different mappings from a set to itself (up to renumbering of elements in the set). Having seen that, it's clear where does the operation from the problem statement come from - it's simply switching the numbers of two elements in the set!

Now we just need to count the number of different mappings such that at most K elements map into any single one. This is not an easy task, but it's quite standard and I won't go into detail.

Yandex.Algorithm 2015 Round 3 took place on Saturday (problems requiring login, results, top 5 on the left). Some usual suspects like tourist, Egor and dzhulgakov shared the top 5 with the rising stars umnik2296 and ishraq.huda. Congratulations to all for amazing results!

Codeforces got a part of the competition pie with Looksery Cup 2015 (problems, results, top 5 on the left). Problem H had a very simple statement, and yet allowed a multitude of different solutions, some much easier to implement quickly and avoid bugs in than others. You are given a 2x2 matrix, and you are allowed to add arbitrary 2x2 matrix with zero determinant to it. You need to minimize the maximum absolute value in the resulting sum. How small can you make it?

Gennady has submitted it just 6 minutes into the contest, and it was his second problem to submit :) His first place in this contest never seemed in doubt until two contestants have managed to pass pretests on the hardest problem E - but they both failed the final testing, and Gennady has returned to the top spot. Congratulations on the impressive performance!

Thanks for reading, and check back next week as we start to approach the decisive phase of many tournaments: Google Code Jam and Russian Code Cup will both hold their final elimination rounds, with 25 best competitors selected to fly to Seattle for Code Jam finals, and 50 best competitors chosen to compete for the RCC in the online finals. What's more, the Distributed Code Jam will give the same contestants a chance to try their skills in a completely different - some might say more contemporary - environment: when you have quite a lot of machines to throw at a problem. I'm excited to see how this competition works out - good luck to all participants!

Tweet