DEV Community: Danila White

Prefix sums

Danila White — Tue, 04 Jan 2022 21:25:27 +0000

Definition

The prefix sums of array a is such an array b that b[0] = 0, b[1] = a[0], b[2] = a[0] + a[1] and so on, b[n - 1] = a[0] + a[1] + ... + a[n - 2], and finally b[n] = a[0] + a[1] + ... + a[n - 1] that is, the sum of all the elements in the array.

It should be noted that the length of array b is one more than the length of array a.

In order to calculate the elements of the array b, we need O(n^2) time, which is not very efficient. Let's change our formula a little bit. Think about what formulas for b[i] and b[i + 1] have in common. Note that the formula for b[i + 1] is the same as the formula for b[i], but at the end, we just add more a[i]. So the sum of all terms except the last one can be replaced by b[i]. Thus, the formula for b[i + 1] can be simplified to b[i] + a[i].

Construction

Now, we can calculate the array of the prefix sums in O(n). Let's write a code that will calculate an array of prefix sums.

vector<int> mps(vector<int> &nums) {  // make prefix sum
  int n = nums.size();
  vector<int> prefixsum(n + 1, 0);

  for (int i = 0; i < n; i++)
    prefixsum[i + 1] = prefixsum[i] + nums[i];

  return prefixsum;
}

We accept as input the original array nums. Let's designate its size as n. Then we will create a final array prefixsum, which will have a length one more than a and fill it with zeros. Then we go through all the indexes of the array a and apply our recursive formula for each index i. And at the end, just return the final array.

Let's imagine that the elements of the original array are in cells. And the elements of the array of prefix sums are under the partitions between these cells. Their value is the sum of all the elements that are to the left of this very partition.

For example, there is nothing to the left of the zero partition. To the left of the divider of the five there is only a five, to the left of the divider of the eight there are five and three and so on.

Finding the sum on the segment in O(1)

Let us be given an array and some segment of this array. Question: what is the sum of the elements in this segment?

Let's build an array of prefix sums.

Note that the b[5] prefix sum contains all the element we need, but there are also extra ones. What are these superfluous? a[0] and a[1]. But the sum of these elements is exactly b[2]. That is, the sum of the array elements on the half-interval from 2 to 5 is just b[5] - b[2], so if we pre-calculated the array of prefix sums, then we can answer the request in O(1).

Let's summarize, there were numbers l and r, and we took the difference of the elements of the array b at these positions. The answer to problems like RSQ (Range Sum Query) is always b[r] - b[l].

Zero-sum segment

Let's solve one more problem, in which prefix sum will be used.
Let us be given an array, and we are required to find it's some non-empty subsegment with zero-sum of elements. For example, in this case, such a subsegment is suitable for us.

Note that the sum in the segment is equal to zero if and only if the prefix sums corresponding to its ends are equal to each other, because the sum in the segment is just the difference of the prefix sums.

To find such a pair, you can, for example, sort the array and search for identical pairs of adjacent elements. Alternatively, you can use a hash table, storing for each prefix sum the index of the prefix on which this sum is reached.

Number of zeros on the segment

Let us be given an array, and we need to find the number of zeroes on some non-empty subsegment. For example, in this case, the answer is 3.

For each prefix, we will count the number of zeros on it. Then the answer for the request on the half-interval is [l; r) will be b[r] - b[l].

Conclusion

We learned what prefix sums are and how they can be used to find a sum on a segment. Then we learned to find a subsegment of an array with a sum of zero. In the end, we learned how to use prefix sums to find the number of zeros (and not only) on a subsegment.

Теория игр в 19-21 задачах КЕГЭ 2021

Danila White — Sat, 03 Apr 2021 18:30:44 +0000

Введение

Привет друг! Проблемы с теорией игр? В этой статье мы разберем код, который решает любые прототипы стандартных 19-21 задач из КЕГЭ. Чтобы максимально понять ниже описанный код, я крайне рекомендую сначала научиться решать эти задачи ручками.

Условие

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в четыре раза.
В начальный момент в первой куче было 3 камня, во второй куче — S камней, 1 ≤ S ≤ 57. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 61. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 61 или больше камней.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найдите минимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение

Winpos

Первым делом нам надо написать функцию, которая будет возвращать True если игрок находиться в выигрышной позиции и False если игрок не находиться в выигрышной позиции.

Обозначим переменные count1 и count2 как количество камней в 1 и 2 куче соответственно.
Если изначально суммарное количество камней в кучах меньше 61

if (count1 + count2 < 61)

и при любом следующем ходе оно становиться больше либо равно 61

((count1 + count2 + 1 >= 61) or
(count1 * 4 + count2 >= 61) or 
(count1 + count2 * 4 >= 61))

то мы возвращаем True, что означает что игрок находиться в выигрышной позиции.
Иначе мы возвращаем False, что означает что игрок не находиться в выигрышной позиции.

def winpos(count1, count2):
    if (count1 + count2 < 61) and ((count1 + count2 + 1 >= 61) or
       (count1 * 4 + count2 >= 61) or (count1 + count2 * 4 >= 61)):
        return True
    else:
        return False

Первая функция готова, приступим к написанию следующей.

Losspos

Теперь нам надо написать функцию, которая будет возвращать True если игрок находится в проигрышной позиции и False если игрок не находится в проигрышной позиции.

Если изначально игрок не находиться в выигрышной позиции

if not winpos(count1, count2)

и каждый следующий ход противника является выигрышным

(winpos(count1 + 1, count2) and winpos(count1, count2 + 1) and
 winpos(count1 * 4, count2) and winpos(count1, count2 * 4))

то мы возвращаем True, что означает что игрок находиться в проигрышной позиции.
Иначе, мы возвращаем False, что означает что игрок не находиться в проигрышной позиции.

def losspos(count1, count2):
    if not winpos(count1, count2) and (winpos(count1 + 1, count2) and
        winpos(count1, count2 + 1) and winpos(count1 * 4, count2) and
        winpos(count1, count2 * 4)):
        return True
    else:
        return False

Вторая функция готова, осталась еще одна.

Prewinpos

Последняя функция должна возвращать True если игрок находится в предвыигрышной позиции и False если игрок не находится в предвыигрышной позиции.

Если изначально игрок не находится в выигрышной позиции

if not winpos(count1, count2)

и любой следующий ход противника является проигрышным

(losspos(count1 + 1, count2) or losspos(count1, count2 + 1) or
 losspos(count1 * 4, count2) or losspos(count1, count2 * 4)):

то мы возвращаем True, что означает что игрок находится в предвыигрышной позциии.
Иначе, мы возвращаем False, что означает что игрок не находиться в предвыигрышной позциии.

def prewinpos(count1, count2):
    if not winpos(count1, count2) and (losspos(count1 + 1, count2) or
        losspos(count1, count2 + 1) or losspos(count1 * 4, count2) or
        losspos(count1, count2 * 4)):
        return True
    else:
        return False

Основа готова, осталось просто перебрать значения, чем мы сейчас и займемся.

1 Задача

Условие задачи можно воспринимать так: "Ваня находиться в выигрышной позиции(выигрывает за один ход)".

Изначально в первой куче 3 камня

count1 = 3

а во второй куче S камней, 1 ≤ S ≤ 57

for s in range(1, 58):

Перебираем все возможные комбинации с S, при которых игрок находится в выигрышной позиции

if winpos(count1 + 1, s) or winpos(count1, s + 1) or
   winpos(count1 * 4, s) or winpos(count1, s * 4):

и если хоть одна такая комбинация существует, то мы выводим S на экран и прерываем цикл.

print("19:", s)
break

Получается следующий код, который решает эту задачу

count1 = 3
for i in range(1, 58):
    if winpos(count1 + 1, i) or winpos(count1, i + 1) or
        winpos(count1 * 4, i) or winpos(count1, i * 4):
        print("19:", i)
        break

2 Задача

Условие задачи можно воспринимать так: "Ваня находится в проигрышной позиции".

Перебираем все возможные комбинации с S, при которых игрок находиться в проигрышной позиции, и если такие комбинации существуют, то мы выводим S на экран

for i in range(1, 58):
    if losspos(count1 + 1, i) or losspos(count1, i + 1) or
        losspos(count1 * 4, i) or losspos(count1, i * 4):
        print("20:", i)

3 Задача

Условие задачи можно воспринимать так: "Ваня находиться или в выигрышной или в предвыигрышной позиции"

Перебираем все возможные комбинации с S, при которых игрок находиться или в выигрышной или в предвыигрышной позиции, и если такие комбинации существуют, то мы выводим S на экран

if (winpos(count1 + 1, i) or predwinpos(count1 + 1, i)) and 
   (winpos(count1, i + 1) or predwinpos(count1, i + 1)) and 
   (winpos(count1 * 4, i) or predwinpos(count1 * 4, i)) and 
   (winpos(count1, i * 4) or predwinpos(count1, i * 4)):
   print("21:", i)

2 Способ

Подробней с этим методом решения теории игр вы можете ознакомится на канале Алексея Кабанова

Мемоизация

Для оптимизации рекурсии подключим декоратор cache из модуля functools.

from functools import cache

Moves

Напишем функцию moves, которая принимает количество камней в обеих кучах и возвращает всевозможные варианты ходов.

def moves(heap):
    a, b = heap
    return (a + 1, b), (a * 4, b), (a, b + 1), (a, b * 4)

Game

Напишем функцию game, которая рекурсивно описывает игру.

@cache
def game(heap):
    if sum(heap) >= 61:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    else:
        return max(steps) + 1

1-3 задача

Перебираем все значения s и выводим на экран необходимые данные.

for s in range(57, 0, -1):
    print(s, ": ", game((3, s)), " | ", [game(x) for x in moves((3, s))])

На выходе мы получаем полное дерево игры, в котором можно увидеть ответы на поставленные задачи.