game (IATI senior)
Time limit: 1.5 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: game theory, value iteration, dynamic programming, segment tree, range queries

![IATI Day 2, Senior group
English](_page_0_Picture_1.jpeg)

# XV INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS

**Task A5. GAME** 1.5 sec. 256 MB

Klimi and Nikol have an integer array $A$ with $N$ cells numbered from 0 to $N-1$ and containing **different** integer values. The girls are playing a game played with a single piece that is moved around the array. Initially, the piece is located in some cell. One move of the game proceeds as follows:

1. The player whose turn it is takes the piece and moves it to another cell that is at distance at most $D$ from the current one. Formally, if the piece is currently in cell $x$ ($0 \le x < N$), then the player is allowed to move the piece to cell $y$ ($0 \le y < N$) if $|y - x| \le D$ and $x \ne y$. Note that this means a player **must** move the piece.
2. After moving the piece to some cell $y$, the player adds $A[y]$ to her score. Note that the score is added **after** moving the piece.

The moves alternate between the two girls and Klimi plays first. The game ends in exactly $10^{100}$ turns, at which point the girl whose total score is higher wins. If their score is equal, then Klimi wins.

The girls aren't quite happy with the time it takes to finish even a single game, so they ask you to just figure out the optimal play results in different scenarios.

Formally, you will be given the initial array $A$ and the value $D$, and then you will have to process $Q$ queries of two types:

- Updates: A single value in the array is changed.
- Questions: You are asked whether Klimi (the one to play first) wins the game, given some initial position of the piece and assuming optimal play.

The updates persist across queries, so each question must be answered considering all updates that have happened so far.

The implementation details section describes the interfaces you should support in more detail.

## Implementation details

You must implement three functions. Your first function `init` must have the following prototype:

```c++
void init(std::vector<int> A, int D)
```

It will be called once at the beginning of the test and will supply you with the array $A$ and the value $D$.

Your other two functions `updateValue` and `isWinning` must have the following prototypes:

```c++
void updateValue(int index, int newValue)
bool isWinning(int startIndex)
```

The total number of calls to either of the two functions will be $Q$ (refer to the constraints section) and all calls will be done after the call to `init`.

The `updateValue` function must process an update query and set $A[index]$ to `newValue`. It is guaranteed that after the updates all values in $A$ are still different.

The `isWinning` function must process a question query and return `true` if Klimi can win the game on the current array, given that the piece starts in cell `startIndex`. It must return `false` otherwise.

Your program must implement the three functions, but should not contain a `main` function. Also, it must not read from the standard input or print to the standard output. Your program must also include the header file `game.h` by an instruction to the preprocessor: `#include "game.h"`

As long as it respects these conditions, your program can contain any helper functions, variables, constants, and so on.

## Local testing

You are given the files `Lgrader.cpp` and `game.h`, which you can compile together with your code to test it. The input format of the grader is:

- $N$ $D$
- $A_0$ $A_1$ ... $A_{N-1}$
- $Q$
- `<Q lines of queries>`

Where the format of the queries is:

- `1` `ind` `val` - Update query setting $A[ind] = val$
- `2` `ind` - Question query for the piece starting in `ind`

For each query of type 2, the grader will print 0 if your function returned `false` and 1 if your function returned `true`.

### Constraints

- $1 \le N, Q \le 2 \cdot 10^5$
- $1 \le D \le 25$
- $1 \le A[i] \le 10^9$
- $0 \le$ `index`, `startIndex` $< N$
- $1 \le$ `newValue` $\le 10^9$
- The values in $A$ are all different at all times, including after updates.

### Subtasks

| Subtask | Points | $N, Q$                  | $D$        | Extra Constraints             |
|---------|--------|-------------------------|------------|-------------------------------|
| 1       | 8      | $N, Q \le 10$           | $D \le 25$ |                               |
| 2       | 18     | $N, Q \le 2 \cdot 10^3$ | $D \le 25$ | There are no update queries   |
| 3       | 16     | $N, Q \le 2 \cdot 10^5$ | $D \le 25$ | There are no update queries   |
| 4       | 27     | $N, Q \le 10^5$         | $D \le 10$ |                               |
| 5       | 31     | $N, Q \le 2 \cdot 10^5$ | $D \le 25$ |                               |

You must pass all tests in a subtask to get the points.

### Example

Suppose $A = [1, 7, 4, 9, 30, 2]$, $D = 2$, and $Q = 5$. An example sequence of calls is:

- Call to `init({1, 7, 4, 9, 30, 2}, 2)`
- Call to `isWinning(0)` which returns `true`
- Call to `isWinning(1)` which returns `false`
- Call to `updateValue(4, 8)`
- Call to `isWinning(0)` which returns `false`
- Call to `isWinning(1)` which returns `true`

The array after the update call is $[1, 7, 4, 9, 8, 2]$. It can be shown that those are the correct answers to the questions if both girls play optimally.

In the format of the local grader this looks as follows:

| Input        | Output |
|--------------|--------|
| 6 2          |        |
| 1 7 4 9 30 2 |        |
| 5            |        |
| 2 0          | 1      |
| 2 1          | 0      |
| 1 4 8        |        |
| 2 0          | 0      |
| 2 1          | 1      |

Starter code:
game.h: #pragma once

#include <vector>

void init(std::vector<int> A, int D);
void updateValue(int index, int newValue);
bool isWinning(int startIndex);


Grader code:
grader.cpp: #include "game.h"

#include <vector>
#include <iostream>
#include <algorithm>

static const long long HASH_BASE = 92792611, HASH_MOD = 1894867301;
static long long INPUT_HASH = 0;

static void addToHash(long long val)
{
    INPUT_HASH *= HASH_BASE;
    INPUT_HASH += val;
    INPUT_HASH %= HASH_MOD;
}

int main()
{
    static int n, D, q;

    std::vector<int> nums;

    scanf("%d %d", &n, &D);

    addToHash(n);
    addToHash(D);

    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        addToHash(x);

        nums.push_back(x);
    }

    init(nums, D);

    scanf("%d", &q);
    addToHash(q);

    for (int i = 1; i <= q; i++)
    {
        int cm;

        scanf("%d", &cm);
        addToHash(cm);

        if (cm == 1)
        {
            int ind, val;

            scanf("%d %d", &ind, &val);
            addToHash(ind);
            addToHash(val);

            updateValue(ind, val);
        }
        else
        {
            int ind;

            scanf("%d", &ind);
            addToHash(ind);

            printf("%d\n", (int)isWinning(ind));
        }
    }

    printf("%lld\n", INPUT_HASH);

    return 0;
}

game.h: #pragma once

#include <vector>

void init(std::vector<int> A, int D);
void updateValue(int index, int newValue);
bool isWinning(int startIndex);


Setup script:

Evaluation script: