Блог пользователя kazuya

Mathematical Proof for a Div2-D Problem
Автор kazuya, история, 5 лет назад, По-английски

1355D - Игра с массивом Solving the problem is easy by observation but can anyone explain the case when Petya will loose i.e for S<2n mathematically?

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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.
→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить