madhur4127's blog

ABC 090 / ARC 091 Discussion Page
By madhur4127, history, 7 years ago, In English

I found no blog on ABC 90 or ARC 091 discussion, so let's discuss problem here:

ARC 091 — Link

ABC 090 — Link

If similar blog exists, notify me and I will delete this.

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

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem E (LISDL) was already appeared on Topcoder SRM 332 Div1 Hard . (Although I didn't know this problem during the contest)

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

I think I have a better analysis for nim problem which gives .Though it is not a big improvement.I want help to find what is the fault in my method if there is any. So idea is when that ceil(n/k)> , do a single step. And when ceil(n/k)<= .try to reduce ceil value by 1.Remember that N is original number and n is intermediate number.

Each of the two steps cannot take place more than times.Complexity is .

Please find fault in it.

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

    Seems obvious to me. The number of steps where we subtract is and the number of steps where we subtract is also . Approximating the Euler limit is overkill.

    → Reply