An and-clique week

The Nov 14 - Nov 20 week was busier. TopCoder SRM 702 on Tuesday was the last chance to practice before the TopCoder Open weekend (problems, results, top 5 on the left, analysis). xudyh won the second SRM in a row, and was the only one to solve all three problems. Congratulations!

The onsite event of TopCoder Open 2016, one of the main tournaments of the year, started with Semifinal 1 on Saturday (problems, results on the left, analysis by Bruce). Top 3 advanced to the final round next Monday, and everything was essentially decided by the speed on the 500-pointer. The problem statement was extremely simple: one needs to construct any weighted directed graph with at most 20 vertices that has exactly the given amount k of different minimum cuts. k is up to 1000.

Open Cup 2016-17 Grand Prix of Dolgoprudny took place early on Sunday (problems, results, top 5 on the left). Team Past Glory retook the ground they lost to ITMO 1 in the overall standings a week ago - well done!

Finally, TopCoder Open 2016 Semifinal 2 determined 3 more finalists (problems, results on the left, analysis by Bruce). Unlike the first semifinal, which went more or less normal, this round was very unusual. For the first 10-15 minutes none of the participants, and almost none of the observers, could figure out how to solve the easiest 250-pointer problem. Because of that, the advancement in this round hinged on the ability to give up on a problem and clear one's head before the next one. It's worth mentioning that the 500-pointer was also in no way obvious. Congratulations to Enot on successfully navigating the tricky round and coming out on top!

Here's the problem that puzzled everybody. You are given 1000 positive integers up to 10¹⁸. You need to find any subset of those integers with the following two properties:

1. Bitwise and of all integers in the subset is zero.
2. For any two integers in the subset, their bitwise and is not zero.

Can you see the key solution idea?

In my previous summary, I have mentioned an easy problem: you are given an n times n grid of uppercase English characters, where n is at least 3. This grid was built in the following way: first, we fill it with n different characters in such a way that each row and each column has exactly one occurrence of each character. Then, we replace exactly one character in the entire grid with another character. Your goal is to figure out which character has been replaced, and what was there originally.

Here's a solution that's very easy to implement. First, we count the number of times each letter appears in the grid, and find letters that appear at least twice. Those are the original letters. Then, for each row and column of the grid we check if they contain at least one appearance of those letters. We will find exactly one row and exactly one column that will be missing one of those letters - and those are precisely the row, column and letter that we need to output.

Thanks for reading, and check back later for more!

Tweet