thehumbleguy's blog

By thehumbleguy, 5 weeks ago, In English,

Looking for a solution to task C of the recent atcoder grand contest since the editorial given is only in Japanese. I tried converting it to english but it's a very bad conversion.

I cannot understand how you can verify in O(N) if its possible to satisfy the given condition by using at max X distinct characters. (the check(X) function used in Binary search)

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by thehumbleguy (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

You may watch Petr's screencast with commentary for hints:

AtCoder Grand Contest 029 screencast with commentary

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry for the delay, we'll finish it within this week.

Inside the binary search, basically, we decide S1, S2, ... greedily. S1 should be the lexicographically minimum string of length A1. Then, S2 should be the lexicographically minimum string of length A2 that is greater than S1. But we need to do this efficiently.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how do you guys think? its so frustating for me to think the solution of problem c.I tried for 2 hour and nothing come up with solution.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      with practice you will able to come up

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes i am practicing,but sometime my mind dont able to think even problem A, it take approx 15-20 min to solve A(lol) , i can solve A B but no able to solve that fucking C.hope practicing will help me

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      its so frustating for me to think the solution of problem c

      ask god why he gave you a less intelligent brain. lol. do you really have to beat yourself up over this? Everyone has his/her own strengths. Go and find yours.