ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1023. Buttons

explain the logic behind this problem
Posted by Unsocial_A 20 Sep 2018 23:44
I have seen many people solve this problem using divisor of given number(k).But i cannot understand how it works.Can anyone explain me how this logic works??

sorry for bad english
Re: explain the logic behind this problem
Posted by PO 18 Jan 2019 12:58
you need to be in control. you are in control when you keep the first player in "loop". if you take number of buttons is 6, say, then the "loop" length is 3, i.e. if you take max number of buttons as 3 - 1 = 2, then whatever amount the first player takes you can keep them in loop. if they take first time 1, you take 2 - in sum 3, 3 - remaining, you are a winner. if they take 2 - you take 1, 3 remaining again - you are a winner.
so, idea is to find the smallest divisor of a number > 2 & answer will be that - 1. hope that makes sense.

Edited by author 18.01.2019 19:50
Re: explain the logic behind this problem
Posted by topcoderme123 7 Jun 2022 10:19
WLOG, let's break `k` elements of heap into block of length `d`. The numbers below are listed from 1, ..., k in their congruent modulo of `d`.
[1, 2, ...., (d - 1), d], [1, 2, ...., (d - 1), d], ......(k / d) blocks. Here [..] is a block notation. B = #blocks of length `d` = (k / d)

Basis: If B = 1, it's always true, as `first player` can pick whatever from 1, ..., (d - 1), `second player` always left with atleast 1 element by less then d to be picked. So `second player` player will greedily pick all remaining element in the block as an optimal move for his/her winning.

Hypothesis: Let say it's true upto (B - 1) blocks that `second player` has taken the last element.

Proof:
If we have B block then since it is true for (B - 1) blocks we left with 1 block of element to pick and since `first player` is the who pick first in the last 1 block by using the `basis` we know that `second player` is always the winner. Hence, if we take the divisor of number of elements in the heap (k) we always end of with `second player` being the winner.

Edited by author 07.06.2022 10:23

Edited by author 07.06.2022 10:23