SuperMo's blog

Problem F Yesterday contest
By SuperMo, history, 23 months 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

Comments Comments (7)
| Write comment?
»
23 months ago, hide # |
 
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
»
23 months ago, hide # |
 
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
  • »
    »
    23 months ago, hide # ^ |
    ← 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