water's blog

Codeforces Round #159 (Div. 2) problem D How to solve this problem?
By water, 14 years ago, In English

I still can't figure out how to solve this problem after I read the tuturial. Can you write your idea carefully :(

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

»
14 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

you want to solve the problem for ( 1 , n ) where 1 is first array and n is the last array. for solving ( i, n) first solve ( i+1 , n ), thus you'll have a integer S, ( 0<= S <= a[i+1] ) and if S>= a[i] then s= s-a[i] , and if s<a[i] then s = a[i] — s. and you can easily use an array to save the sign of any numbers from 1 to n.

→ Reply
»
14 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Let solve this task for all suffixes of array in increasing of size order. For last element it's easy, because it's in [0..an]. let fi is the sum we get for ai..an

Let's add 1 element. Then ai — fi + 1 is in [-ai..ai], so ai — fi + 1 or fi + 1 — ai is OK.

→ Reply