thehumbleguy's blog

By thehumbleguy, 6 months 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

»
6 months 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).

»
6 months 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

»
6 months 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.

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      with practice you will able to come up

      • »
        »
        »
        »
        6 months 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

    • »
      »
      »
      6 months 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.