Hello Codeforces!

The Baltic Olympiad in Informatics 2024 is coming soon!

We are inviting everyone to take part in the Mirror Contest. It will consist of two competitions, each lasting five hours:

- Mirror Day 1: 11:00-16:00 May 5 (Sunday)
- Mirror Day 2: 11:00-16:00 May 6 (Monday)

These times are given in the current Vilnius time zone. It is **UTC+3**!

The winners are announced here: https://boi2024.lmio.lt/news/mirror-contest/

Online (anonymous) ranking: https://mirror.cms.lmio.lt/ranking/ (will be open for a few days).

Onsite results: https://boi2024.lmio.lt/results/

I wish you all the best of luck.

will there be live standings?

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

Collides with Orthodox Easter.

Excited!

Is there any information about the registration published?

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

They could have problems with the actual competition, as currently the second contest day is running.

Updated, now in the website :)

Thank you

Mirror link?

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

Mirror registration and contest link updated at: https://boi2024.lmio.lt/news/mirror-contest/

How to solve Jobs for subtasks?

Btw, Trains and Jobs were interesting tasks!

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.

Nice solution and the explanation! Aprreciate it.

My solution was simulating this greedy strategy:

For each node store (min starting sum, profit) = $$$(v_i, d_i)$$$.

Start with $$$d_i = x_i$$$, $$$d_0 = s$$$, $$$v_i = max(0,-x_i)$$$

If for some node $$$i$$$ condition $$$d_i \geq 0 \land v_{p_i} + d_{p_i} \geq v_i$$$ holds, merge with parent to form $$$(v_{p_i}, d_{p_i} + d_i)$$$.

Otherwise, find the node $$$i$$$ with min $$$v_i$$$ and $$$d_i\geq 0$$$ and $$$p_i\neq 0$$$ and merge with parent to form $$$(v_i - d_{p_i}, d_{p_i} + d_i)$$$.

Answer will be $$$d_0$$$.

Used small to large/dsu and priority queues for implementation.

The intended solution was also a greedy strategy. But the slope trick solution also sounds very nice!

when will it be ok to discuss day1 problems?

now

It's already okay to discuss :)

Where can we find results of mirror contest?

Hopefully, we will upload soon.

How to solve Portal?

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)

Could you explain how did you calculate that?

If you have 3 vectors, you can reduce it to 2.

Notice, that you can change vector $$$v$$$ to $$$-v$$$ and vector pair $$$(a, b)$$$ to $$$(a, a+b)$$$ without changing the answer.

Using this, reduce $$$2$$$ of the $$$3$$$ vectors to have $$$x = 0$$$ (euclidean algorithm), then you can change those 2 to $$$(0, gcd(a_y, b_y))$$$

Somehow this needs __int128 precision

EDIT: Doesn't need __int128, forgot some %= to keep the vectors small.

That's what I thought about, but didn't manage to find the value of the second vector when I reduce the first one to x=0. I forgot about the Euclidian algorithm. Thanks! .

Where is the scoreboard ?

Hopefully, we will upload soon :D

EDIT: now it's published.

Thanks, and when will results from official contest be uploaded?

High probability that after the closing ceremony.

Aldas25 When will the analysis open?

It's open

Yes, we opened it quite recently. It should be open until tomorrow.

Surprising fact about B:

The answer is 2 * gcd of areas of all NC3 triangles. I have no proof (good luck if you want to try). Unfortunately, I wasn't able to solve beyond N <= 2000 using this.

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.

i dont think this is correct (from experience since i submitted this too i think along with other heurestics). But, it is true that you only need to consider triangles passing through P_0

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

Is there any official solutions of problems?

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)

How to solve wall?

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.

Hmm, thinking about empty spaces is a lot easier lol. I was maintaining $$$dp_i[h] = \text{# ways of prefix 0...i max} = h$$$ in a segment tree for prefix/suffix. Then I updated the answer with $$$\sum_{i=1}^{n} i \times \sum_{h=0}^H min({a \lor b}_i, h) \times dp_{i-1}[h] \times 2^{n-i} $$$ and similarly with a negative sign from the other side.

Thanks for the answer.

I see you are from Lithuania, did you participate onsite?

If you did, can you tell what were the medal cutoffs.

I participated online.

Are there any simple implementation approaches to problem "tiles"?

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:

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

Day 1 rankings now show rankings for day 2, please update the post

Why are you asking? What's your concern?

Updated :)

Why does the ranklist not contain usernames?

It is more fun to look at a non-anonymous leaderboard :D

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.

Official mirror results with names, when?

See this comment

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

How to solve problem B in both days. I managed to solve every thing else except these two (I really hate geometry lol)

is there any scoreboard with names?

Problems are kinda vintage

how to solve day2 p3 ?

How to solve full fires? I managed to solve the first 4 subtasks subtask using O(n^2) solution and add some randomization to pass the fifth one.

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.

why is it true?

imagine 2 segments that cover the whole space and the rest are small not optimal segments. what is the probability that you choose exactly one of those 2 segments out of 1e5 segments

I forgot to say that you choose that random starting segments from the first 1000 longest segments.

I think the test cases were very weak, such a solution have passed during contest only fixing the largest segment, it obviously should not pass.

how have you figured out that your solution is right. it is not clear to me, assume we have one large segment with length 10000 and inside that large segment we have 1000 segments with length 2. assume the optimal answer contains the largest segment, but we are picking 100 elements out of 1000 there is very low probability that we select exactly that largest one:

Is there something wrong with the following algorithm for d2p2? Or am I just too incompetent to implement it?

SpoilerFirst, we "simplify" the polygon and remove the vertices where the two neighboring vertices lay on the same line, e.g. all vertices that don't change the directions. After that, each x-coordinate must be even. Furthermore, for each horizontal line, the adjacent closing line must be at an even distance. For that, we can run a binary search algorithm over $$$k$$$, and run a sweep line from the bottom to the top, while doing range updates on a segment tree. The updates look like:

We obviously need coordinate compression / sparse segment trees because the coordinates can go up to $$$10^9$$$.

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

Does anybody know the official medal cutoffs?

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/

When will tasks be published?

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

There is something wrong with zip archive for test data

ojuz

Will you add these problems on oj.uz?

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

Can I submit code somewhere? Also the tasks zip file in the website doesn't work

good luck for all participants

You are 1 week late.

The problems can be solved on Eolymp.

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?

It seems the test data link is broken. Could you take a look? Aldas25

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

Now if I try it, the download fails after about 10MB. I wonder if this is the result of the website change...

.