thehumbleguy's blog

No English editorial for Atcoder GrandContest29
By thehumbleguy, 6 years 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

Comments Comments (5)
| Write comment?
»
6 years 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

→ Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply