On Saturday, September 3rd TopCoder Open comes to Saint-Petersburg. Russia! Event highlights include:
- an onsite round of Algorithm Competition: an SRM-style competition with top-10 participants advancing to the online Wild Card Round, from which two winners go to TCO finals in Washington DC (rules).
- T-shirts for all attendees :-)
- if
during the next week (till July 22nd)by August 19th the event gathers 100 participants, TopCoder will add a lightning Marathon match with the same rules as for NYC regional event — the Marathon itself takes place before the onsite and is open for everybody to attend, and at the onsite closing ceremony the winners are celebrated. At the moment there are266094 registrants.
If you want to participate, register, and the sooner the better :-)
Upd. List of registrants
What's the final decision? Will there be a lightning Marathon contest? I can't tell if the needed conditions were met or not.
No. Last time I've checked was well after the deadline, and we still had to reach 100 registrants :-(
I hope you enjoyed the problems!
"The probabilities will be given with at most 3 decimal places" is almost always irrelevant information -- maybe Hard shed some light on why that might not always be the case ;)
Interesting that I gave absolutely same problem (as today Hard) on VK Cup Finals 695A - LRU but with n <= 20 (because we haven't managed to solve problem with bigger constraints).
Question about USA Regionals. I could not quite understand this solution (need TopCoder login) to this problem . Any ideas?
Considering individual bits, note that an AND with x sets bits that are 0 in x to 0, and the rest are unchanged. Similarly, an OR with x sets bits that are 1 in x to 1, and the rest are unchanged.
Therefore, the final state of each bit relates to the last operation that set that bit (if it was an AND, the bit is 0, if it was an OR, the bit is 1). If no operation set that bit, then it's equal to its initial state of 0.
The trick here is to realize that the problem becomes easier if you consider it backwards, because now, once you decide to set a bit using one of the operations, it can never be unset by any earlier operation, so you know immediately its final state. Noticing this, it's much easier, because setting bits to their correct value is obviously always advantageous to you, and setting bits to their incorrect value is obviously forbidden (because they will never change later). So you should do any operation as long as it doesn't set any bit to an incorrect value.
Maybe the code with bitmasks is easier to understand?