How to solve B, D, E, J?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:53:06
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:53:06
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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
Время на сервере: 22.11.2024 11:41:54 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Were there errors in tests with problem S ? I have seen people passed it only after making +60 , +30 submissions.
J: Calculate dp[mask] — the longest possible distance from the center of mass to the rightmost point of all books with indices in mask. You can add books from top to bottom. If you have some books in mask, you can add another book to bottom in two ways:
Right side of the new book aligns with the center of mass for the books in mask;
Left side of the new book aligns with the center of mass for the books in mask.
By this technique you can calculate dp for the whole mask.
I don't know the right solution for other tasks. We implemented some weird $$$26 n \log^2 n$$$ in D, but it got TL.
In D change each letter to the distance to the previous occurence of this letter
Yeah, we were more or less ready to speed the solution up to $$$O(n \log(n)(\log(n)+26))$$$, but $$$O(n \log^2(n)26)$$$ was enough.
Impressive, I wrote the $$$O(n \log(n)(\log(n)+26))$$$, and it still took 2.3s out of the 5s time limit.
Our $$$O(n \log ^ 2 (n) 26)$$$ took 1.6 s. I think in this case it much more depends on the implementation rather than complexity.
Oh, nice idea, thanks!
C xd?
Let's say we generate two independent trees, and then for each vertex $$$v$$$ calculate the expected number of pairs of vertices $$$i,j$$$ s.t. $$$v$$$ is an ancestor of $$$i$$$ in the first tree, and $$$v$$$ is an ancestor of $$$j$$$ in the second tree. A simple DP can do this.
Next, using these values, for each vertex $$$v$$$, calculate the expected number of pairs of vertices $$$i,j$$$ s.t. $$$v$$$ is the vertex with maximum index with the abovementioned property. Let $$$f(v)$$$ be this value.
Here's the trick: I said two trees, but the value $$$f(v)$$$ is the same as the expected number of pairs of vertices $$$i,j$$$ s.t. $$$v=lca(i,j)$$$ when we consider only one tree. This is because the paths $$$i \rightarrow v$$$ and $$$j \rightarrow v$$$ are disjoint.
And the rest is straightforward.
How did you calculate $$$f(v)$$$? We had to use the observation that there are few triples $$$i,j,k$$$ such that $$$i \vert j$$$ and $$$j \vert k$$$, so our runtime is like $$$O(n \log^2(n))$$$. Realizing the graph was small enough to enumerate all reachable pairs was definitely a surprise for me.
The std is also $$$O(n\log^2 n)$$$. Enumerating on the transition graph is the intended solution. (We tried to make it faster for a long time but we failed.
Let $$$g(v)$$$ be the answer to the first DP. Then $$$f(v)=g(v)-\sum_{i|j} f(v) \times (the\ probability\ the\ path\ j\rightarrow i\ exists)^2$$$. When we fix $$$i$$$, we can calculate $$$(the\ probability\ the\ path\ j\rightarrow i\ exists)$$$ for all $$$j$$$ in $$$O((n/i)\log(n/i))$$$ time. So the total time complexity is $$$O(n\log ^2(n))$$$.
Wow, it somehow looked intractable to me during contest, but now it doesn't even look that hard :,( Nice trick
How to solve I ?
B: Do D&C. For some interval passing trough the middle the optimal subinterval either passes through the middle or is fully contained in one of the halves. For each prefix of the right half calculate the greatest sum of its subinterval and the greatest sum of its subprefix. The same for left half (but for sufixes ofc. Let's create triples $$$(subinterval, subprefix, side)$$$ with side being $$$0$$$ or $$$1$$$. Sort them in nondecreasing order of $$$subinterval$$$. Now go from smallest to biggest and when you pair some triple $$$i$$$ with each passed tripple $$$j$$$ (with different side) the result is either equal to $$$subinterval_i$$$ or $$$subprefix_i + subprefix_j$$$. If you also maintain the triples sorted by $$$subprefix$$$ it's easy to see that the first case will happen for prefix and the second case for sufix, so Fenwick tree does the job.
B is kind of an easier version of 1458F - Range Diameter Sum from Round 691, which was just 24 hours earlier; they have both a similar statement and a similar D&C solution. I definitely got a hint from looking at solutions to 1458F earlier in the day.
B is doable in $$$O(n\log(n))$$$ with stack and segment tree. Consider an easier problem where you need to calculate max segment sum for queires $$$[l, r]$$$. We can go from right to left and maintain for each position the largest sum segment ending in this position. When we are at point $$$l$$$ we need to ask maximum on $$$r$$$-th prefix of segment tree to get answer for query $$$[l, r]$$$.
Now in our problem we need to count sum of those maximums which seems harder. But we can store those maximums in the segment tree instead of actual values. Since everything is monotone we can remax with a simple assignment on segment.
E: I'm omitting the proof here, but $$$|str(c)| \in [|str(\left\lfloor n/2 \right\rfloor)| - 1, |str(\left\lfloor n/2 \right\rfloor)|]$$$ where $$$|str(\left\lfloor n/2 \right\rfloor)|$$$ is achieved if:
1(but not10), and $$$n \mod{11} \neq 10$$$.And the following factorizations $$$n = a + b$$$ are enough:
Each of the cases can be verified in $$$O(n)$$$ time (some simple greedy algorithm).
Maybe it can be done a bit cleaner than that?
The case where n is odd and n % 11 == 10 can be handled as follows:
There could be none of 9s and 0s, but it's not a special case. somethingequalx might be empty though. Then we can do:
You are very brave for writing that down
How did you guys solve A? We reduced it to undirected vertex geography and thus finding the max matching of $$$G \setminus \{v\}$$$ for each vertex $$$v$$$, but didn't know if there was a well known way to proceed from there.
We used the randomized Tutte matrix trick for finding a maximum matching (https://www.cc.gatech.edu/~rpeng/18434_S15/matchingTutteMatrix.pdf ): construct the Tutte matrix, substitute in a random value of $$$\mathbb{F}_{998244353}$$$ for each formal variable, and then use Gaussian elimination to get it into RREF. Then, a starting move is winning iff the elementary vector $$$e_i$$$ is a row of the RREF.
Not sure what you mean. Do you ask how do you solve undirected vertex geography through matchings or how to do it fast enough?
Yeah, how to solve it fast enough; in particular, how do you find max matching when removing each point?
We compute max matching once (call it $$$M$$$). Then we look at each vertex v. If it doesn't belong to $$$M$$$ then we are happy. If it does then let $$$u$$$ be the neighbor it was matched to. We remove $$$v$$$ from the graph and search for an augmenting path from $$$u$$$.
There was no point in my life when I understood blossom algorithm, so I can't say that with confidence, but I think my teammates seemed convinced it indeed works in $$$O(m)$$$ per augmenting path as one would expect, so in total that gives $$$O(nm)$$$. Unfortunately even with $$$O(nm)$$$ we faced some TLE issues and that turned out to be decisive about the win ;_;
A Codechef problem helps...
This F... XD I am always enthusiastic about hard geometry problems, but in my life I've had enough of "shortest path on a plane with forbidden polygon" problems and they are always a struggle.