Saturday, December 19, 2015

A 500+1000 week

The Dec 7 - Dec 13 week had two "usual suspects": a Codeforces round and a TopCoder round. Codeforces Round 335 took place a bit earlier on Wednesday (problems, results, top 5 on the left, editorial). TooSimple has climbed into a clear second place in the ratings after the amazing victory which included submitting problem E just 16 minutes into the contest - congratulations!

TopCoder SRM 675 happened on Thursday (problems, results, top 5 on the left). The top spot was decided in the challenge phase this time, and Milanin and Um_nik took advantage of this by climbing above the coding phase leaders tourist and ainu7 - great job!

Finally, let me give a small hint for the interactive string guessing problem from NEERC I've mentioned in the previous post: the judges have a hidden binary string of 1000 zeroes and ones, and you have to guess it using at most 1500 attempts. For each attempt, you output some string of 1000 zeroes and ones, and the judge responds with one of three answers: either your guess is correct (and that means you've won); it's incorrect but _exactly_ half (500) of all characters are correct; all other incorrect situations grouped together.

The first idea is to find a way to get at least one "500" answer. Then we can start getting information about individual characters by applying small changes to the string and checking if the answer stays 500. But how do we find at least one string that matches the hidden string in exactly 500 positions? Check the next week's summary to find out :)

No comments:

Post a Comment