Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

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

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?

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

»
4 года назад, # |
← 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.
→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← 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

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

      → Ответить