game_changer007's blog

problem A div 1
By game_changer007, 11 years ago, In English

how can i solve this problem.No editorial available

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

»
11 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Let the elements of the array be a[0],a[1]...a[n-1]. Since the sum of each pair of consecutive elements has to be the same, if a[0] decreases by 1, a[1] increases by 1 and so on alternately for all a[n-1]. So if n is even there can be no net transfer of coins from the array to the robber. If n is odd however, see that sum of all elements decreases by 1 when we repeat the above process. This coin can be transferred to the robber.

The final greedy process will be 1 coin transferred from a[0]->a[1], 1 coin transferred from a[2]->a[3].....a[n-3]->a[n-2] and a[n-1]->ROBBER. This process takes (n+1)/2 steps for each coin gained and pairwise sum retained. So you have to find how many times this process can be completed in 'm' operations , k times.

Also make sure none of a[0],a[2],a[4]....a[n-1] become negative.

MY SOLUTION

→ Reply
»
11 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

In fact there were two editorials there, but one of them was attached only in Russian interface (even though it was available in both Russian and English), another one was attached to Div. 2 contest (which also has the problem you are looking into). I have reattached both editorials, now you should be able to see them in the contest interface.

→ Reply