SuperMo's blog

Problem F Yesterday contest
By SuperMo, history, 4 weeks ago, In English

in problem F the binary search approach why is this equation wrong with large numbers but it works with small numbers

number of time we use current attack = ceil(mid/(c[i]+1))

Update : it's because of the cool down you don't need to wait c[i] round to hit again you actually wait c[i]-1 round so ceil(mid/c[i]) is correct

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

its cause there is a potential overflow for the attack variable. consider h=2e5,n=2e5,all attacks 1 and cooldown 2e5. Using a break should solve the problem. PS i got hacked too

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

    in test case 6 just dividing 19999800001/200001 is giving me 99998.5000125 now is this results wrong ?

    → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I used __int128 and break. too lazy to calculate overflow

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ok I figured it now it's because of the cool down you don't need to wait c[i] round to hit again you actually wait c[i]-1 round

so ceil(mid/c[i]) is correct

→ Reply
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    For $$$i$$$-th attack you can hit in rounds $$$1$$$, $$$c[i]+1$$$, $$$2c[i]+1$$$, $$$3c[i]+1$$$, ..., $$$kc[i]+1$$$, so if you are currently at round $$$T$$$, you can hit max of $$$\Bigl\lfloor \frac{T-1}{c[i]}\Bigr\rfloor+1 $$$ times, which is $$$ceil(T/c[i])$$$

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply