An icosahedral week

TopCoder SRM 676 was the first event of last week (problems, results, top 5 on the left). The match has once again provided ample challenge opportunities, but ACRush made sure he can relax during the challenge phase by being the only one to submit three correct solutions - congratulations! As a result, he has also moved to the clear third place in the all-time SRM victory stats.

Open Cup 2015-16 Grand Prix of Peterhof wrapped up the week on Sunday (problems, results, top 5 on the left). Problem C was very beautiful as it allowed several different approaches, and yet required a significant insight to come up with any of them. Here's what it was about: two strings of 0s and 1s are considered equivalent, if one can be obtained from the other by repeatedly removing or inserting (anywhere in the string) the following substrings: 00, 111, 0101010101. For example, 100110 and 010011 are equivalent, since we can do the following sequence of transformations: 100110 --> 1110 --> 0 --> 0111 --> 010011. Given 4000 strings of total length at most 50000, find out the groups of equivalent strings among them.

Finally, let me give the final pieces of the puzzle for the interactive string guessing problem from NEERC I've mentioned in two previous posts: 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.

Let's just make a random guess, 1000 random bits. What's the probability that we'll get 1000 matches? It's just 1/2**1000, a very, very small number. However, the probability that we'll get the other interesting answer - exactly 500 matches - is much higher, since there are many ways for the matches to happen. More precisely, it's C(1000, 500)/2**1000, which is about 2.5%! Which means that, on average, we'll get at least one "500" answer after just 40 random attempts.

After we get one "500" answer, we can do the following: let's flip exactly two bits in our string - bit 0 and bit x, for all values of x from 1 to 999. If the answer stays "500", it means that exactly one of bit 0 and bit x is correct, and in the other case they're either both correct or both incorrect. After doing this for all 999 pairs, we know the correct value of each bit if we assume that bit 0 is correct, and the correct value of each bit if we assume that bit 0 is incorrect, so we have just two remaining candidate strings to check, and one of them is guaranteed to give answer 1000.

In total, we're using about 1040 queries on average. Of course, on some testcases we might require more, but it's not hard to check that we're extremely unlikely to come even close to the allowed limit of 1500.

An interesting fact about this problem is that it's still not clear if any deterministic solution that fits into 1500 queries exists. Can you come up with one?

Tweet