svanidz1's blog

HourRank 18
By svanidz1, history, 7 years ago, In English

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.

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

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      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;    
}
      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    Code

    → Reply