_sunny's blog

By _sunny, 8 years ago, In English

An online contest with the problemset of ACM ICPC Dhaka Regional, 2013 will be held at this site wwww.codemarshal.com. Please note that you need to register there . The contest will take place on 30th November, 2013 at 9 GMT.

Due to some unavoidable situation here, the onsite contest is postponed by 1 week, so the same happens for online too. The online contest will take place on 7th December at the same time(9 GMT).

Gentle Reminder: The contest just started

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

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

Do we need to separately register for the contest, or is site registration enough?

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

The onsite version of this contest has been postponed due to some political issue. Therefore online version may be held on some other day after the on site.

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

I stuck at problem J(DromicPalin substrings). Does anyone have tips for this problem?

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

    A dromicpalin substring has at most 1 character with an odd number of occurences in it. I used bitmasks (26 bits are necessary, which fits into an int comfortably) to determine the parities of occurences of letters for prefixes, and stored those in a map together with how many times they appeared. A substring can be obtained as the difference of 2 prefixes, and the occurencies of letters in that substring are also the differences of their values for those prefixes. So if we iterate over all prefixes, we can count how many prefixes can be subtracted from it to form a dromicpalin: all those whose occurence bitmasks differ from that longer prefix's bitmask in at most 1 bit. That's just 27 possibilities, so we can just check all their values in the map.