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

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

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
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
← 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.
→ Ответить