My solution, which had K = 5, had Anna give information to Bertil in phases, where the first n₁ houses she is led to constitute the first phase, the next n₂ houses constitute the second phase, and so on. In each phase, Anna should give all the information that Bertil needs in order to determine exactly which houses she visited in the previous phase. This is important because when Anna knows which houses were in the previous phase, she can discard them as they are no longer relevant. Finally, when Anna only has a small number of houses left to visit, I used a precomputed bruteforced strategy which allowed Anna to tell Bertil both which houses were part of the previous phase and which two houses Bertil should use as guesses.

In the first phase, Anna just writes 1 on all the doors she visits. This gives Bertil a great deal of information about which doors were in the first phase, but he can't know for sure if a door with a 1 on it was part of the first phase or if it was part of a later phase and just happened to get a 1 anyway. But I designed the strategy so that the vast majority of all 1s would be in the first phase (for example by avoiding writing any 1s in the second phase), which means that only a relatively small amount of information is needed to identify which 1s belonged to the first phase. To send this information to Bertil, Anna uses an error-correcting code and writes numbers in the second phase in accordance with that code. The reason why the code has to be error-correcting is that Anna can't control which houses are in the second phase and which ones are in the third or later phase (these are the errors).

Designing the code is the hardest part of this solution. My solution was to encode whether each house was part of the first phase as either 0 or 1, and then hash each prefix of the resulting binary vector, and reduce the hash modulo K. Then Bertil could use Viterbi decoding to reconstruct the vector in a streaming manner.

I'm leaving out quite a bit of details here, and I'm happy to admit that I would definitely not have been able to implement this solution during the competition. I was one of the testers for the competition, and making this solution work took me days! I'm impressed that prvocislo managed to get a K = 17 solution working during the contest!

Hi! I'm the author of this task. Here's the solution writeup that I created when submitting the problem to the EGOI. As you might notice, I originally submitted the task intending $$$K = 17$$$ to be the full solution. There is actually a pretty clean implementation for this (looks kind of like the update and query functions of a simple segment tree):

#include <bits/stdc++.h>
using namespace std;

const int MN = 100005;

int n, st[MN * 4], a[MN];

int upd(int l, int r, int v, int dep, int x, int idx) {
    if (++st[idx] == r - l + 1 && !v) v = dep;
    if (l == r) return v;
    int mid = (l + r) / 2;
    if (x <= mid) return upd(l, mid, v, dep + 1, x, idx * 2);
    else return upd(mid + 1, r, v, dep + 1, x, idx * 2 + 1);
}

pair<int, int> solve(int l, int r, int dep) {
    if (l + 1 >= r) return {l - 1, r - 1};
    int mid = (l + r) / 2;
    int lc = 0, rc = 0;
    for (int i = l; i <= mid; i++) if (a[i] == dep) lc = i;
    for (int i = mid + 1; i <= r; i++) if (a[i] == dep) rc = i;
    if (lc && rc) return {lc - 1, rc - 1};
    else if (lc) return solve(mid + 1, r, dep + 1);
    else return solve(l, mid, dep + 1);
}

int init(int N) {
    n = N;
    int K = 1, len = 2;
    while (len < N) len *= 2, K++;
    return K;
}

int choose_value(int i) {
    return upd(1, n, 0, 0, i + 1, 1);
}

pair<int, int> guess_secret(vector<int> A) {
    n = A.size();
    for (int i = 0; i < n; i++) a[i + 1] = A[i];
    return solve(1, n, 1);
}

int main() {
    cin.tie(0), cin.sync_with_stdio(0);
    cout.tie(0);
    int P, N;
    cin >> P >> N;
    if (P == 1) {
        int K = init(N);
        cout << K << endl;
        for (int i = 0, u; i < N - 1; i++) {
            cin >> u;
            cout << choose_value(u) << endl;
        }
    } else {
        vector<int> A(N);
        for (int i = 0; i < N; i++) cin >> A[i];
        pair<int, int> guess = guess_secret(A);
        cout << guess.first << " " << guess.second << endl;
    }
}

However, around two weeks before the contest, I was told that someone from the scientific committee had found a more efficient solution with $$$K \le 7$$$. This was very surprising news for me, as I struggled for a long time to see how to whittle $$$K$$$ down even further. I believe it is possible to directly optimize my solution slightly by adjusting the branching factor of some of the layers of segments, but I don't see any clean techniques that get it all the way down below $$$7$$$. I'm also curious to see if anyone has a nice implementation of the full solution!

there doesn't seem to be an easy way to fix it, but you can upsolve on open kattis instead https://open.kattis.com/problem-sources/European%20Girls%27%20Olympiad%20in%20Informatics%202023

yeah I agree it is quite standard. I think it is a decent problem, and it fit into the rest of the problemset in terms of topics and difficulty.

But I appreciate that you have high expectations, it is something for the scientific committee to think about for next year.

First, let's solve the problem if we didn't have the INFLATION operation. It's easy to see that we can keep a data structure (for example a map) with the number of occurences of each value ($$$f_x$$$ = how many dishes have price x). Now, we can easily to the updates:

$$$answer = answer - x \cdot f_x$$$ // we need to subtract what we had before

$$$answer = answer + y \cdot f_x$$$ // we add the new stuff

$$$f_y = f_y + f_x$$$ // every dish which had price x will now have price y

$$$f_x = 0$$$ // there are no longer any dishes with price x

After each query, the answer is held in $$$answer$$$(which is initially the sum off all prices).

To fully solve the problem, we can observe that the "brute force" is to do replace $$$f_i$$$ with $$$f_{i-x}$$$ after each INFLATION operation. This would take too much time, so instead we can see that when we make a SET operation, we can actually just replace the values $$$x$$$ and $$$y$$$ with $$$x - inflated$$$, $$$y - inflated$$$, where $$$inflated$$$ = the sum of values $$$x$$$ from the INFLATION updates we made before this SET operation. It shouldn't be too hard to see why this works.

Time complexity: $$$O((n + q) log_2 n )$$$

Some of the solutions have been published here.

When i submit this code in d2C, it takes 100 points.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

	cout << "NO";
}

yes, the test data for day2C is quite weak unfortunately. Here is a solution sketch I wrote just now: