Блог пользователя svanidz1

Автор svanidz1, история, 7 лет назад, По-английски

Hi Codeforces

I'd like to announce 18th HourRank round! The contest will be held on 16:00 UTC Thursday, March 2 2017. Contestants will be given 4 problems and 1 hour to solve. You can sign up for the contest here. Top 10 winners will receive a HackerRank T-Shirt.

HourRank 18 is prepared by me(svanidz1). I want to thank whole Hackerrank team, especially Shafaet for coordinating and Wild_Hamster for testing the tasks.

The contestants are ranked by score. If two contestants gets same score, the person who reached the score first is ranked higher

Wish you good luck.

UPD1: Score distribution : 15-30-50-75. Contest starts in less than 2.5 hours. All problems will have partial scores.

UPD2: Contest is over. Congratulations to winners:

  1. krismaz

  2. LHiC

  3. uwi

  4. anta

  5. I_love_Tanya_Romanova

  6. vintage_Vlad_Makeev

  7. rajat1603

  8. arsijo

  9. chemthan

  10. gvaibhav21

Thank you for participation.

  • Проголосовать: нравится
  • +114
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Interesting problems, thanks!
In problem "C" I used binary search with sparse tables and thought, that it's too straitforward, until reading the editorial — the solution was simple and nice :)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem B, how are we moving from state f(i,m) to f(i+1,(m+x)%3). shouldn't it be f(i,m) to f(i+1,(m-x)%3) ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In the current state, the mod value is m. If we get a "x" and go to next state, the new mod value will be (m+x)%3.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      f(i,m) denotes number of substrings start at i and have m mod under 3. So, lets say we have a substring i.......k which has m mod under 3. So we can write,

      (str[i] + str[i+1] + ...... + str[k])%3 = m%3

      or

      (str[i+1]+ ........ + str[k])%3 = (m — str[i])%3

      So for solving f(i,m) if we remove first position letter the remaining substring should have mod = (m — x)%3. So, how come it becomes (m+x)%3. I even checked with (m-x)%3 code and it works as well:

      long long f(int i, int m){
          if(i == (int)s.size()){
              return 0; 
          }
          if(memoize[i][m] != -1) {
              return memoize[i][m]; 
      	}
          int x=s[i]-'0'; 
          int md = (m-x)%3;
          if(md<0) md += 3;
          int ans = f(i + 1, md) + (md == 0 and x % 2 == 0); 
      
          return memoize[i][m] = ans;    
      }
      
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes it can be f(i, m) --> f(i+1, (m — (x%3) + 3)%3) )

    since (a-b)%m = (a-b+m)%m

    Code