There won't be any public live standings. However, we will try to put some scoreboard after the contests.

There are less than 30 minutes left until the start of the contest, but I can't find any link yet :"

Will be posted in a few minutes. (EDIT: now live at the website)

For S = 10^18, you can just do simple DP, because you just need to choose maximal sum of elements in tree, and some DP[node] = maximal profit if I choose that node, would pass.

When tree is chain, then greedy like take node which you can take that would increase profit. You can simulate this easily.

Full solution is to consider DP[node][minimal starting sum] = max profit. You can look how function f(minimal starting sum) = max profit changes. Main idea is to use slope trick. All you have to do now is some casework when you add positive/negative element. You should also use small to large to maintain slope points.

now

It's already okay to discuss :)

Hopefully, we will upload soon.

My solution was to calculate the density of the n-1 vectors (in 2d) in Z^2, where the n-1 vectors are (a[i+1].x-a[i].x,a[i+1].y-a[i].y)

Hopefully, we will upload soon :D

EDIT: now it's published.

It's open

If your claim is true, than this can easily be done in O(n): fix a point in the set P_0, and return twice the gcd of all areas of triangels of the form P_0 P_i P_i+1. any area of triangle p_i p_j p_k can represented as a linear combination of such areas, and therefore if a number g divides all areas P_0 P_i P_i+1, it will divide all areas P_i P_j P_k.

Here is a conceptual proof using some (linear) algebra:

• A module is like a vector space, but over a ring instead of a field. In our case, we are interested in the $$$\mathbb{Z}$$$-module $$$\mathbb{Z}^2$$$ and its submodules.

• For $$$i \in \{2, \ldots, n\}$$$ consider the vectors

• Let $U$ be the submodule generated by those vectors. It should be easy to see that $$$v, w \in \mathbb{Z}^2$$$ should get the same color if and only if $$$v-w \in U$$$. This means that the color classes are $$$\mathbb{Z}^2 / U$$$ and the task is to find $$$|\mathbb{Z}^2/U|$$$.

• We can express $$$U = \text{im}(A)$$$ as the image of the $$$2 \times (n-1)$$$ matrix $$$A$$$ which contains vectors $$$v_2, \ldots, v_n$$$ as columns. For invertible matrices $$$S, T$$$ of shape $$$2 \times 2$$$ and $$$(n-1) \times (n-1)$$$, it can be seen that $$$|\mathbb{Z}^2/\text{im}(A)| = |\mathbb{Z}^2/\text{im}(SAT)|$$$.

• It is possible to find $$$S, T$$$ such that $$$SAT$$$ is in diagonal form

• See here for the algorithm to compute this form. The algorithm is not necessary for the proof, but it is very nice and leads to a 100 point solution.
• In the diagonal form, the answer is just $$$|\lambda_1 \cdot \lambda_2|$$$. (If it is $$$0$$$, we can choose infinitely many colors.)
• Finally, we need the concept of a determinant divisor. The $$$i$$$-th determinant divisor $$$d_i(M)$$$ of a matrix $$$M$$$ is the ideal generated by all $$$i \times i$$$ minors of $$$M$$$. It is known that the determinant divisors are invariant under multiplication with invertible matrices, i.e. $$$d_2(A) = d_2(SAT)$$$ and clearly, $$$d_2(SAT) = (\lambda_1 \cdot \lambda_2)$$$. So the task reduces to calculating a generator of the ideal $$$d_2(A)$$$. The determinant of every $$$2 \times 2$$$ minor corresponds to the determinant of a matrix containing two of the vectors $$$v_2, \ldots, v_n$$$. And $$$\text{Det}(v_i, v_j)$$$ is two times the area of the triangle spanned by $$$v_i, v_j$$$. The generator of the ideal is simply the gcd of all of them.

We will probably upload the solutions (and the task themselves) to the website after the olympiad.

However, you are also free to share and discuss the solutions here. (note: after the mirror contest ends, of course)

Count the amount of water as $$$n$$$ — (open space) — (buildings) instead. Buildings are very easy to count (linearity of expectation, so to say). To count the open spaces (to the left), you use the formula $$$\sum_{i=1}^n (\prod_{j=1}^{i} a_j) 2^{n-i}$$$ or likewise, this can be counted with segment trees.

Change polygon to $$$x$$$ coordinate events $$$[y1, y2, open]$$$, then do sweepline.

Start tiling the polygon from the left, then you will have some tiles with $$$x_2=x$$$ and some tiles with $$$x_2=x+1$$$. Store the y coordinate ranges for those. Treat the outside of the polygon as a tile.

If the set $$$x_2 = x+1$$$ is empty, set the answer to $$$x$$$.

To process an opening event insert it to the $$$x_2=x$$$ set.

To process a closing event, the range must be contained within the $$$x_2=x$$$ set. Cut out the closing event range.

After events, the $$$x_2=x$$$ ranges must have $$$y_1 = y_2 \mod 2$$$.

After processing events increment $$$x$$$ and swap sets $$$x_2=x$$$ and $$$x_2=x+1$$$.

My terrible code:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct event {
    int x;
    int y1, y2;
    bool open;
};

struct point {
    int x, y;
};

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

    int N, M;
    cin >> N >> M;
    point A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i].x >> A[i].y;
    }
    vector<event> E;
    for (int i = 0; i < N; i++) {
        int j = (i + 1) % N;
        if (A[i].x != A[j].x) {
            continue;
        }
        if (A[i].y > A[j].y) {
            E.push_back(event{
                    A[i].x, A[j].y, A[i].y, false
            });
        } else {
            E.push_back(event{
                    A[i].x, A[i].y, A[j].y, true
            });
        }
    }
    sort(E.begin(), E.end(), [&](event a, event b) {
        return a.x > b.x;
    });
    if (!E.back().open) {
        for (int i = 0; i < E.size(); i++) {
            E[i].open ^= true;
        }
    }
    int ans = 0;
    int x = 0;
    set<pair<int, int>> X;
    set<pair<int, int>> O;
    vector<pair<int, int>> C;
    while (x <= M) {
        if (!E.empty()) {
            int x1 = E.back().x;
            if ((x1 % 2) != (x % 2)) {
                x1--;
            }
            x1 -= 2;
            if (x1 >= x) {
                x = x1;
            }
        }
        if (X.empty()) {
            ans = x;
        }
        auto bad = [&](pair<int, int> a) -> bool {
            return (a.first % 2) != (a.second % 2);
        };
        int cnt = 0;
        while (!E.empty()) {
            if (E.back().x != x) {
                break;
            }
            event e = E.back();
            E.pop_back();
            if (e.open) {
                int y1 = e.y1;
                int y2 = e.y2;
                while (true) {
                    auto it = O.lower_bound({y1, y2});
                    if (it != O.end()) {
                        if (it->first == y2) {
                            y2 = it->second;
                            if (bad(*it)) {
                                cnt--;
                            }
                            O.erase(it);
                            continue;
                        }
                    }
                    if (it != O.begin()) {
                        it--;
                        if (it->second == y1) {
                            y1 = it->first;
                            if (bad(*it)) {
                                cnt--;
                            }
                            O.erase(it);
                            continue;
                        }
                    }
                    break;
                }
                if (bad({y1, y2})) {
                    cnt++;
                }
                O.insert({y1, y2});
            } else {
                C.push_back({e.y1, e.y2});
            }
        }
        bool ok = true;
        for (auto c: C) {
            auto it = O.lower_bound({c.first + 1, -1});
            if (it != O.begin()) {
                it--;
                auto o = *it;
                if (o.first <= c.first && c.second <= o.second) {
                    pair<int, int> a = {o.first, c.first};
                    pair<int, int> b = {c.second, o.second};
                    if (bad(o)) {
                        cnt--;
                    }
                    O.erase(it);
                    if (a.first < a.second) {
                        if (bad(a)) {
                            cnt++;
                        }
                        O.insert(a);
                    }
                    if (b.first < b.second) {
                        if (bad(b)) {
                            cnt++;
                        }
                        O.insert(b);
                    }
                } else {
                    ok = false;
                    break;
                }
            } else {
                ok = false;
                break;
            }
        }
        if (!ok) {
            break;
        }
        if (cnt != 0) {
            break;
        }

        swap(O, X);
        C.clear();
        x++;
    }
    cout << ans << "\n";
    return 0;
}

I implemented the algorithm from this paper and it was reasonably simple.

Why are you asking? What's your concern?

Updated :)

We did not collect the consent for showing names. We didn't want to deal with that legally, and also there could have been inappropriate names filled.

See this comment

The top participant results here: https://boi2024.lmio.lt/news/mirror-contest/

Is there is interval i where Si > Ei, you change Ei to M + Ei.

Observation 1: If there are more than 1 intervals equal Si, we will always choose the one with greatest Ei.

Observation 2: If we are currently at interval i, we will jump to interval j, such that Si <= Sj <= Ei and Ei < Ej and Ej is maximal. If there are more best j, we take the one with smallest S.

Now, we can build directed graph using the observations above.

For each interval i, we will use binary search and binary lifting to find the first interval j, such that Ej >= Si + M.

Note that we should build the graph in NlogN which can be achieved using segment tree.

Choosing around 100 random starting points and checking each in O(n) also works.

Didn't read the whole thing but your second sentence is already suspicious to me, consider a polygon like

.xx
.xx
xx.
xx.

Onsite scoreboard will be posted in the BOI 2024 website soon.

You can find them on the cses website

here

thanks TimaDegt

The results are published here as well: https://boi2024.lmio.lt/results/

https://boi2024.lmio.lt/tasks/

https://oj.uz/problems/source/655

You are 1 week late.

there were some math camps for beginners on the old website but's now broken and can't find it. are you willing to re-upload it?

Hi! The website will be moved to a permanent place, and then the link will be fixed. Hopefully, we will do this soon :)