An almost there week

The Sep 4 - Sep 10 week started with two Codeforces rounds. On Monday, Codeforces Round 432 took place (problems, results, top 5 on the left, analysis). AngryBacon has started with the hardest problem F and solved it very fast, which gave them a clear path to victory. Congratulations!

On Wednesday, Codeforces hosted the next Round 433 (problems, results, top 5 on the left, analysis). In a round with 4 problems solvable within an hour and the fifth one too hard to crack, Um_nik has combined excellent speed with 3 successful challenges for a clear first place. Well done!

On the weekend TopCoder hosted not one but two rounds that finalized the list of finalists for its flagship tournament TopCoder Open 2017. Round 3B took place on Saturday (problems — unavailable now, but hopefully the TopCoder website will be fixed soon, results, top 5 on the left). In order to advance one simply needed to solve either the first two (like qwerty787788, Um_nik and ikatanic did), or the third problem (like rng_58 and RRx did). Congratulations to all advancers!

With 1.5 minutes to go in the challenge phase, I had 344.14 points which would be enough to advance with just the easy problem solved, only to make an incorrect challenge that brought me down to 319.14 which was not enough. Of course I didn't know that 344.14 would be enough during the round itself, but seeing the final scoreboard made me quite annoyed at myself for that -25 :)

Here is the easy problem that brought the challenge phase excitement about: you are given two strings of the same length, which is at most 50. You are allowed to swap corresponding characters in the strings (i-th character of the first string with the i-th character of the second string) as many times as you want. Your goal is to obtain two strings with as large as possible longest common substring. Can you see the right approach?

In between the TopCoder rounds, Russian Code Cup 2017 Final Round saw the top contestants compete for glory and prizes (problems, results, top 5 on the left, my screencast, analysis). xudyh was about half an hour faster than everybody else on the first 5 problems. I have tried to leapfrog him by trying to squeeze in a suboptimal solution for the last problem that is fast to code, but it did not pass and xudyh has maintained his first place — congratulations on the win!

I have found the easiest problem of this round to be the cutest. You are given a set 100 distinct integers a_i each up to a million, and need to find any set of 100 integers b_j also each up to a million, such that all 100² pairwise sums a_i+b_j are distinct. What is the nicest way to achieve that?

And finally, the Wildcard Round of TCO 2017 determined the last two finalists on Sunday (problems — unavailable now, but hopefully the TopCoder website will be fixed soon, results, top 5 on the left, my screencast). Only kuniavski and xudyh have solved the hard problem, so it is only fitting that they qualified for the TCO onsite — great job!

I have once again tried to compensate the poor coding phase performance with lots of successful challenges, but was unable to find enough and got eliminated from the TCO. The hard problem that I couldn't crack stated: you are given 50 attractions in a city. You will visit exactly one attraction per day. Each attraction can be visited either in the morning, costing a_i, or in the evening, costing b_i. Every time you visit an attraction in the morning after visiting another attraction the previous evening, you pay an extra cost c. Every time you switch from evening to morning, you pay an extra cost d. Additionally, you are given a directed graph of restrictions — a set pairs of attractions that constrain the order of visits: in each pair, the first attraction must be visited before the second one. Can you see the way to use max flow to find the minimal cost to perform all visits?

Thanks for reading, and check back tomorrow for more backfills!