Nickolas's blog

By Nickolas, 8 years ago, translation, In English

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 are 26 60 94 registrants.

If you want to participate, register, and the sooner the better :-)

Upd. List of registrants

  • Vote: I like it
  • +68
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the final decision? Will there be a lightning Marathon contest? I can't tell if the needed conditions were met or not.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No. Last time I've checked was well after the deadline, and we still had to reach 100 registrants :-(

»
8 years ago, # |
  Vote: I like it +57 Vote: I do not like it

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 ;)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    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).

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Question about USA Regionals. I could not quite understand this solution (need TopCoder login) to this problem . Any ideas?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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?

    code