kazuya's blog

Mathematical Proof for a Div2-D Problem
By kazuya, history, 4 years ago, In English

1355D - Game With Array Solving the problem is easy by observation but can anyone explain the case when Petya will loose i.e for S<2n mathematically?

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

»
4 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Think it this way ->

  1. if S < 2 * N and all elements are positive, then Ai can be either 1 or 2.
  2. Atleast one number in the array is 1 since S < 2 * n
  3. Sum should be equal to K or S — K is equal to fact that sum of any subarray in circular array is equal to K.
  4. Start from the element = 1 until Sum < K.
  5. There are only 2 possibilities now. Sum = K or Sum = K + 1.
  6. if Sum = K, subarray is found.
  7. if Sum = K + 1, we can remove our first element = 1 and we get Sum = K, subarray is found.
  8. So, It's always possible to get sum = K.
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yeah but this proof only make sense for array like [2 2 2 2....2 1 2] but array can be like some 1's some 2's and some numbers not (1's and 2's) such that S<2n

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

      the more smaller elements, more pain in the ... so we try to distribute sum S evenly. that makes all the element 1 or 2.

      → Reply