Is there an editorial for the IATI 2022 problems, or can anyone explain their solutions? I am interested especially in the day 2 problems.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
12:51:45
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
12:51:45
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 04:43:17 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
are there any problem statements published as of now?
Problem 2 day 2 consists of several steps:
Finding the right approach (best strategy)
Get all the relevant formulas.
The best strategy is to add a character to the smaller string, and if you make a mistake, always remove it.
Let's assume that size of first string is $$$i$$$ and it's smaller than the size of the second string. $$$l[i]$$$ will be the Expected Value of steps needed to a new character to first string. That is increase the size with 1. According to the best strategy, the value doesn't depend on the size of the second string. If Luca wasn't lucky and he made a mistake, he will need $$$lf[i]$$$ steps to go back to previous stage, when the size of first string was $$$i$$$ and the second string has no mistakes.
It's easy to get the following 2 formulas:
$$$lf[i] = 1 + p * (lf[i-1] + l[i-1])$$$
$$$l[i] = 1 + (1-p) * (lf[i] + l[i]) = {{1 + (1-p) * lf[i]} \over {p}}$$$
Day $$$2$$$ problem A: You are given an array $$$a_1,a_2,\ldots, a_n$$$, an integer $$$A$$$ and $$$q$$$ integers $$$R_1,R_2,\ldots R_q$$$ (queries). In one operation you may swap $$$2$$$ adjacent elements of the array for cost $$$a_{i-1} + a_i$$$. You should answer these $$$q$$$ queries independently: for fixed $$$R$$$, what is the minimum possible value of $$$a_1 + a_2 + \ldots a_R + cost \ of \ operations$$$? Here, $$$cost \ of \ operations$$$ denotes the total cost of all operations performed.
Main subtasks are:
I should note that I haven't solved the full problem, but I suspect that it can be solved in $$$O(n \sqrt{n} \log n)$$$.
We should find the right formula for fixed $$$R$$$. So we choose some subsequence of $$$a$$$ of length $$$R$$$ and move it to the left. For a fixed subsequence the cost to do that is
Notice that it is fixed for each $$$i_j$$$, so we can pre-calculate an array $$$f_i$$$ for each $$$1 \leq i \leq n$$$ and simply choose $$$R$$$ smallest values.
By taking a closer look at the formula, we see that the "first part" is fixed for each $$$R$$$. Let it be $$$P_i$$$. So, the formula is
We can conclude that it is simply a line equation. For each $$$1 \leq R \leq n$$$ we need to query all lines at $$$x=R$$$ and take the sum of $$$R$$$ lowest points. This helps us since for each $$$1\leq R \leq n$$$ we can sort our array $$$f_1,f_2,\ldots f_n$$$ with insertion sort. It works because:
With a good implementation of "swap adjacent" sorting algorithm this is $$$O(n^2)$$$ amortized.
Usually when we have lines, we use some kind of CHT (Convex Hull Trick). I'd partition the lines into $$$k$$$ convex envelopes, where $$$k$$$ is a constant I haven't determined yet, but I suppose that it is around $$$\sqrt{n}$$$ (we can always partition an array into $$$O(\sqrt{n})$$$ LIS and decreasing LIS, the same should hold for lines?)
Now, let's fix some convex envelope. We can use binary searches to determine the lowest points, and the sum of lowest points at some $$$x=R$$$. I'll spare the details, but I think it is possible to implement this in $$$O(n \cdot \sqrt{n} \cdot \log ^2 n)$$$ and maybe in $$$O(n \cdot \sqrt{n} \cdot \log n)$$$.
I should note again that I don't have a concrete full solution. If you (anyone) have, please reply to this comment.
Fully dynamic Convex Hull should achieve $$$O(n \log^2 n)$$$.
I suspect one can also use Kinetic Tournament to keep track of the two envelopes in reasonable time (perhaps even $$$O(n \log^2 n)$$$?)
How to solve B6 (Sorting) and A2 (Ones)?
The maximum length of a random sequence is pretty small (because the probability of a $$$0$$$ not appearing at least once in $$$x$$$ positions is $$$(1/2)^x$$$). So, let's generate a random sequence until the maximum length becomes at most $$$20$$$, it shouldn't take many runs. Now, we need to find the position of a $$$0$$$ that changes the answer. We can do this with binary searching and asking every $$$l$$$-th position from a start point, where $$$l$$$ is the maximum length of a $$$1$$$-subsequence. After finding the $$$0$$$ that changes the answer, it's simple to find at least one endpoint (I think even going linearly from the currently changed $$$0$$$ till we meet another $$$0$$$ could work because the maximum length is really small anyway). Once we find one endpoint, the other can be calculated corresponding to the maximum length.
A6 can be solved with min cost max flow.
First thing to note is that we can limit number of different lifts using fake node which is connected to source node with edge having capacity k and cost 0. We can add edge between this node and every node representing some person.
Next, we will add edge with capacity 1 and cost abs(R_i — L_j) between person i and person j, i < j. This means that after person i, person j can call lift which will be empty for exactly abs(R_i — L_j) floors.
There is one problem, we need to make this flow visit all nodes. How we do it? We can for each person make in and out vertex and add edge with capacity 1 and cost -inf between them.
Ok, what about MLE? Trick is we can store only edges for which flow has changed, there will be at most N*K of them. (I haven't implemented this, but I guess this works).
You can solve the problem in $$$O(n k \log^2 n)$$$ by reducing the dense graph to a more sparse one, by imposing extra vertices and edges in the flow network, using a virtual persistent Fenwick tree as a basis (there was a classical problem of simulating Dijkstra on a graph where you have edges between ranges $$$[l_i, r_i]$$$ of vertices, could someone please link to it if you know what I'm talking about?).
Basically, process lifts in order, and then add edges via a Fenwick tree from all lower floors to the starting floor of the current lift of cost $$$l_i$$$ (using a Fenwick tree, again), and then from the ending floor of the current lift to all upper floors of cost $$$-r_i$$$. Do the same for the other direction (upper floors to starting floor, ending floor to lower floors). This way you reduce your network to $$$O(n \log n)$$$ edges, where you can do $$$k$$$ iterations of Dijkstra.
Also, to compute initial potentials, notice that the network is a DAG, so you can relax edges in order of topological sort, instead of Bellman-Ford (although I suspect Bellman-Ford also fits the TL).
I think this is pretty much the problem about simulating Dijkstra that you mentioned: https://codeforces.me/contest/786/problem/B, but it only has node — range edges. The range — range case can be solved in a similar manner anyway.
That is pretty much the intended solution, with the only difference that instead of using a persistent tree, you can easily build the compressed network with divide and conquer.
Here is an official archive of the IATI '22. It not only contains the problems but also the attempts of all of the participants!
Does anyone know the solution to A5 Fork? I couldn't find the explanation in the contest material.
Here you can submit your solutions to problems from IATI 2020 to 2022!