water's blog

Codeforces Round #159 (Div. 2) problem D How to solve this problem?
By water, 12 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

»
12 years ago, # |
  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
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got AC using your idea.:) I really appreciate you and care about your country.:)

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

    I think your expression is better than the tuturial.:)

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

      thank U, but where's the tuturial?

      → Reply
»
12 years ago, # |
← 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