This week in competitive programming

TopCoder SRM 628 took place on Tuesday (problems, results, top 5 on the left). The TopCoder admins are having a hard time finding good problems, so they've ran just two SRMs this month instead of the usual four. I've skipped this round, while Gennady didn't, and he has claimed the first spot in the overall TopCoder rating as the result after winning this round - congratulations!

On Saturday, there was another TopCoder round - TopCoder Open 2014 Round 3A (problems, results, top 12 on the left, my screencast). Just 12 people advanced to the onsite finals in San Francisco, all listed on the left - congratulations to all! I've managed to squeeze out the first place in the last seconds by submitting a heuristic solution for the hard problem (TopCoder login required to view it). I want to discuss my solution in a separate post later this week, but in the meantime, here's what the problem was about: you were given at most interesting 50 points on a line that you need to visit in any order starting from point 0. In addition to moving along the line at one unit per second, you can use teleports between the given pairs of locations. The teleports are non-interleaving (if one teleport connects points a < b, and the other connects points c < d, then either b < c or d < a), and there are at most 25 teleports, each taking exactly one second to use. What's the shortest time required to visit all interesting points?

On Sunday, Codeforces ran MemSQL Start[c]UP 2014 Round 1 (problems, results, top 5 on the left). The round featured one quite technical problem that highlighted a flaw in my preparations: problem E required a suffix structure, like a suffix tree, a suffix array or a suffix automaton to be solved. While I do know in theory how all of those work, using them in practice is always painful for me and takes a lot of time. The reason for that is mostly the fact that those data structures were quite new back when I was actively learning new things in competitive programming, and I haven't caught up with the recent developments in the area. I can definitely do better - and this contest is another good reason to actually figure those data structures out and be ready to use them.

The problem went like this: you are given three strings of total length up to 300000. For each length L, how many triplets of substrings of these three strings exist such that all three substrings are equal and have length L? If a substring appears several times in a string, its occurrences are counted separately.

Thanks for reading, and check back next week!

Tweet