hora — EJOI contest
Task type: interactive | Time limit: 1 s | Memory limit: 256 MB | Difficulty: 22
Algorithms: mathematics, interactive, binary search

![](_page_0_Picture_0.jpeg)

# Hora

*This is an interactive problem!*

**Hora** is a traditional Romanian and Moldovan folk dance in which participants join hands and form a large circle...

At the 8th European Junior Olympiad in Informatics, $N$ participants started dancing hora, where $N$ is a positive, **even** integer. **The number of boys is equal to the number of girls.** The organizers assigned a circular index to every participant in the hora. The indexes start from 0 and continue consecutively in increments of 1, up to $N - 1$. This means that participants with indexes 0 and $N - 1$ are neighbors, and that each participant's index is one greater than that of their previous neighbor. Please refer to the *Examples* section for visualizing such a configuration.

You don't know exactly which participants are girls and which participants are boys, since you are participating in the competition right now! However, you can make calls to the testing system. Each call consists of two integers $L$ and $R$ such that $0 \le L < N$ and $0 \le R < N$. The response will contain an integer - the number of boys on the continuous circular interval from $L$ to $R$ in our circle. In particular:

- If $L \le R$, then the answer will consider the continuous circular interval of participants with indexes $L, L + 1, \dots, R - 1, R$.
- If $R < L$, then the answer will consider the continuous circular interval of participants with indexes $L, L + 1, \dots N - 1, 0, \dots R - 1, R$.

You are given an integer $K$ ($1 \le K \le N$). Your task is to find a continuous circular interval of length $K$ in our circle for which the **absolute difference** between the number of boys and girls is as small as possible. More formally, you are asked to implement a procedure that returns an integer $S$ ($0 \le S < N$) such that a continuous circular interval of length $K$ starting from $S$ has the smallest absolute difference between the number of boys and the number of girls among all the possible continuous circular intervals of length $K$. Note that a certain circle configuration may have multiple solutions with the same smallest absolute difference between the number of boys and girls. In such a case, you may return any of them.

The absolute difference between two numbers $x$ and $y$ is given by $|x - y|$. For example, $|2 - 4| = 2$, $|7 - 4| = 3$.

## Implementation Details

You should implement the following procedure:

```cpp
int solve(int N, int K)
```

- $N$: the number of participants in the hora.
- $K$: the length of the considered interval.
- This procedure should return $S$, the integer representing the beginning of the interval of length $K$ with the smallest absolute difference between the number of boys and the number of girls dancing in the hora.
- This procedure is called exactly once.

The above procedure can make calls to the following procedure:

```cpp
int ask(int L, int R)
```

- $L$: the start index of the queried interval.
- $R$: the end index of the queried interval.
- Returns the number of boys in the queried interval.
- If the number of calls to the `ask` procedure exceeds $10^5$, the solution will receive a Wrong Answer verdict.

### Example

Let's assume that the circle looks as follows:

![](_page_1_Figure_14.jpeg)

Note that the circles with the white letter B on them represent boys, and the circles with the black letter G on them represent girls. Additionally, the number immediately to the right of each circle represents the index of the corresponding person.

Consider the following call:

```cpp
solve(12, 5)
```

In this example, we have 12 people dancing hora, and we search for the continuous interval of length 5 with the minimal possible absolute difference between the number of boys and the number of girls. Our program makes a call:

```cpp
ask(0, 10)
```

The corresponding answer is 6, meaning that there are 6 boys dancing hora in this interval. We can easily deduce from this that there are 5 girls dancing hora in the same interval.

```cpp
ask(0, 4)
```

The corresponding answer is 4, meaning that there are 4 boys dancing hora in this interval.

```cpp
ask(1, 5)
```

The corresponding answer is 3, meaning that there are 3 boys dancing hora in this interval. We can easily deduce that there are 2 girls dancing hora in the same interval. Since the absolute difference between 3 and 2 is 1, and there can't exist an interval with a smaller absolute difference of length 5, your program returns 1, which is the start of this corresponding interval.

## Constraints and Scoring

- $2 \le N \le 10^5$
- $1 \le K \le N$
- $N$ is even.
- The hora has an equal number of participating boys and girls.
- The grader is not adaptive.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases.

| Group | Score | Limits                                                                                                                     | $Q_{full}$ |
|-------|-------|----------------------------------------------------------------------------------------------------------------------------|------------|
| 1     | 5     | $N = 34$                                                                                                                   | 34         |
| 2     | 13    | $N = 100000$, all the boys are adjacent to each other (all the girls are adjacent to each other as well).                   | 18         |
| 3     | 8     | $N = 100000$, the configuration of the hora was generated randomly.                                                       | 34         |
| 4     | 11    | $N = 100000, K = 50000$                                                                                                   | 18         |
| 5     | 10    | $N = 65536, K = 128$                                                                                                      | 26         |
| 6     | 10    | $N = 100000, K = 400$                                                                                                     | 26         |
| 7     | 9     | $N = 100000, K = 99601$                                                                                                   | 26         |
| 8     | 10    | $N = 100000, K = 330$                                                                                                     | 68         |
| 9     | 24    | Mixed values for $N$ and $K$ (no additional constraints).                                                                 | 34         |

Take a test in a group with parameter $Q_{full}$ and Score. Let $Q$ be the number of calls to the `ask` procedure for that test. If $Q \le Q_{full}$ you get awarded Score points for that test. If $N \ge Q > Q_{full}$ you will get awarded $Score \cdot \left(1 - \left(\frac{Q - Q_{full}}{N}\right)^{0.05}\right)$ points. If $Q > N$ or the answer of your program for that test is wrong you will get awarded 0 points for that test. The score for the group is then the minimum score among all of its tests.

Calling the `ask` procedure more than $10^5$ times will result in a Wrong Answer verdict.

## Sample Grader

The sample grader reads the input in the following format:

- line 1: $N$, $K$
- line 2: $A[0], A[1], \dots, A[N - 1]$, where the array $A$ is a string representing our hidden circle of participants. In particular, if $A[i] = \text{'X'}$, the corresponding person in our circle is a boy, and if $A[i] = \text{'Y'}$, the corresponding person in our circle a girl.

The sample grader outputs each question in the following format:

- line 1: ? $L$ $R$

The sample grader outputs each answer in the following format:

- line 1: $x$ boys

The sample grader outputs the contestant's answer in the following format:

- line 1: ! $S$

At the end of the interaction, in the last line of the standard output the grader reports the number of calls to the `ask` procedure made by the contestant.

Starter code:
hora.h: #include <cstdio>
#include <cstdlib>
#include <vector>

int solve(int N, int K);
int ask(int L, int R) {
    printf("? %d %d\n", L, R);
    fflush(stdout);
    int x;
    if(scanf("%d", &x) == EOF) {
        exit(0);
    }
    return x;
}

int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    int S = solve(N, K);
    printf("! %d\n", S);
    fflush(stdout);
    return 0;
}

interactor.cpp: #include "testlib.h"
#include <cmath>

constexpr int Q_full[10] = {100000, 34, 18, 34, 18, 26, 26, 26, 68, 34};
constexpr int Q_limit = 100000;
int N, K;
std::string A;
std::vector<int> cnt, sum;
int Q;
int ask(int L, int R) {
    Q++;
    if (Q > Q_limit) {
        quitf(_wa, "The number of inquiries exceeds 10^5");
    }
    if (L <= R) {
        int res = cnt[R];
        if (L > 0) res -= cnt[L - 1];
        return res; 
    }
    else {
        int res = cnt[R + N];
        if (L > 0) res -= cnt[L - 1];
        return res;
    }
}
int solve(int N, int K) {
    printf("%d %d\n", N, K);
    fflush(stdout);
    while(true) {
        std::string op = ouf.readToken();
        if (op == "?") {
            int L = ouf.readInt(0, N - 1), R = ouf.readInt(0, N - 1);
            printf("%d\n", ask(L, R));
            fflush(stdout);
        }
        else if (op == "!") {
            int S = ouf.readInt(0, N - 1);
            return S;
        }
        else {
            quitf(_wa, "Unknown Operation");
        }
    }
}
int main(int argc, char** argv) {
    registerInteraction(argc, argv);
    N = inf.readInt(), K = inf.readInt();
    int subtask_id = inf.readInt();
    A = inf.readToken();
    cnt.resize(N + N), sum.resize(N + N);
    for (int i = 0; i < N + N; i++) {
        if (i > 0) cnt[i] += cnt[i - 1];
        if (i < N) cnt[i] += (A[i] == 'X' ? 1 : 0);
        else cnt[i] += (A[i - N] == 'X' ? 1 : 0);
    }
    for (int i = 0; i < N + N; i++) {
        if (i > 0) sum[i] += sum[i - 1];
        if (i < N) sum[i] += (A[i] == 'X' ? 1 : -1);
        else sum[i] += (A[i - N] == 'X' ? 1 : -1);
    }
    int ans = K;
    for (int i = 0; i + K - 1 < N + N; i++) {
        int num = sum[i + K - 1];
        if (i > 0) num -= sum[i - 1];
        ans = std::min(ans, abs(num));
    }
    int S = solve(N, K);
    int res = sum[S + K - 1];
    if (S > 0) res -= sum[S - 1];
    res = abs(res);
    if (ans != res) {
        quitf(_wa, "Wrong S found\nS = %d, user_sum = %d, jury_sum = %d\n", S, res, ans);
    }
    if (Q <= Q_full[subtask_id]) {
        quitf(_ok, "Q = %d\n", Q);
    }
    else if (Q <= N) {
        double score = (1 - pow((double)(Q - Q_full[subtask_id]) / N, 0.05));
        quitp(score * 100, "Q = %d\n", Q);
    }
    else {
        quitf(_wa, "Q = %d\n", Q);
    }
    return 0;
}