Hello,
Grand Prix has just finished!
Can anyone tell us solution for problems F and M? Can you tell me proof for solution of problem J?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 10:30:20 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
M is the same as this problem.
Can anyone tell me how to resolve the terrible precision issue for problem B?
It's an LP of three variables. Nested ternary search worked for me without much trouble, but I don't know why it's precise enough.
Sorry, I use binary search and reduce it to a half-plane intersection problems. I need to check whether the intersection is empty.
And now the precision issue becomes out of control because the range of coordinate can be greater than $$$10^{13}$$$ now and the half-plane intersection problem itself is quite precision sensitive.
I’ve used simplex, our implementation required only good epsilons here, but I’m not very good in this topic, I just think that the implementation is good.
M: Let's work with the inverse permutation, then for each $$$S$$$, elements of $$$S$$$ should lie on a consecutive segment. Among sets that are not contained in other sets find the set $$$S$$$ that could be the leftest segment. It must satisfy the property that for each $$$A, B$$$ that are not contained in $$$S$$$ either $$$A \cap S \subseteq B \cap S$$$ or $$$B \cap S \subseteq A \cap S$$$.
After that we can split permutation into 2 segments $$$T_0 = S, T_1 = { 0, ..., n - 1 } \setminus S$$$. If some set $$$S'$$$ splits $$$T_i$$$ into two nonempty subsets, we know in which order they should be. So we split $$$T_i$$$ until each $$$S'$$$ is either a union of some $$$T_i, T_{i+1}, ..., T_{j}$$$ or contained in some $$$T_i$$$. After that we can solve recursively for each $$$T_i$$$.
F: Choose $$$i$$$ and $$$j$$$ such that $$$s_i = s_j$$$ and $$$i < j$$$. There are $$$2^{j - i - 1}$$$ ways to choose something between them. We also need to choose some $$$k$$$ and choose $$$k$$$ elements to the left of $$$i$$$ and $$$k$$$ elements to the right of $$$j$$$. Choosing the same amount of elements from two sets of sizes $$$a$$$ and $$$b$$$ is the same as choosing $$$a$$$ elements from the set of size $$$a + b$$$. So each pair $$$(i, j)$$$ adds $$$2^{j - i - 1} \binom{i + (n - 1 - j)}{i}$$$ to the answer. We can split it into product of 3 parts: $$$2^{n - 2} (i + (n - 1 - j))! \cdot \frac{1}{i! 2^{i}} \cdot \frac{1}{(n - 1 - j)! 2^{n - 1 - j}}$$$. The first part depends only on $$$i + (n - 1 - j)$$$ the second on $$$i$$$ and the third on $$$n - 1 - j$$$. So we can count it with FFT.
Could you tell a bit more details about counting these values with FFT?
I forgot to mention that we do FFT for each character separately. Fix character $$$c$$$. Let $$$a_i = \frac{1}{i!2^{i}}$$$ if $$$s_i = c$$$ and $$$0$$$ otherwise and let $$$b_i = \frac{1}{i!2^{i}}$$$ if $$$s_{n - 1 - i} = c$$$ and $$$0$$$ otherwise. We calculate convolution $$$a * b$$$, multiply its $$$i$$$-th element by $$$2^{n - 2} i!$$$ and count sum for $$$i = 0..n - 2$$$.
Cool. Looks like it's quite universal approach, which I didn't know about. Thank you!
Of size $$$a+b$$$! Here is a related puzzle: you are blindfolded and in front of you lie a hundred coins — ten heads and ninety tails. You cannot identify the coins by touch, but you are allowed to flip them arbitrarily. You need to separate the coins into two sets (possibly of distinct size) containing the same number of heads each.
Sorry, typo.
Could you explain what the quoted segment means?
Edit: https://math.stackexchange.com/questions/855538/evaluate-sum-k-0n-n-choose-km-choose-k-for-a-given-n-and-m
How to solve G?
For each element with value X we store the link to the closest element to the right with value X or X+1. Only O(1) links are adjacent to each element, so we can recalculate them when the value changes.
We store the links in a link-cut tree with a special added sink vertex to the right. If the element has no link to the right, we link it with sink.
To answer the query we fing the leftmost occurrence of $$$k$$$ on the segment, expose it and the sink and answer some standard query like "rightmost element in a binary tree with value less than something".
Did 16 teams really write link-cut tree?
I also wonder. Still, why else the time limit is 20s?
P.S. Copy-paste, not write.
Actually we wrote Link-Cut Tree for this problem. And it seems we need about 15s to pass some cases. I think it is because of the constraint is very large in this case.
PS: According to what I've been told, the author tried very hard to generate data to prevent some O(nsqrt(nlogn)) to pass this problem...
You can solve it with sqrt decomposition instead of link-cut
What is your complexity for SQRT decomposition? I have solution with one extra log when I am answering to queries, Update is classic $$$O(\sqrt N)$$$ per query. So for me solution has around $$$5\cdot 10^9$$$ operations, for optimal block size.
If you remove log, please explain me your idea :)
You can solve it without extra logs, just follow ifsmirnov ideas, but for linkcut use sqrt decomposition
we also had O(n sqrt n) without logs as far as I understand but we had hard time to pass TL
Can you explain this sentence a little bit more:
Only O(1) links are adjacent to each element, so we can recalculate them when the value changes.
As I understood each element can be right for many other elements, maybe I misunderstood sentence.
I think you misunderstood the part of "value X or X+1". It's not "and", so every node have one outdegree (and two indegree).
Here is a very short sqrt-decomposition which does the job. link. The point is to not batch over arrays, but to batch over queries and solve the problem in $$$O(N + Q^2)$$$ time. Really liked this problem (or maybe I was too stupid).
How to solve L?
The answer is $$$n^{n-2} - \sum_{i=\lceil \frac{n}{2} \rceil + 1}^{n-1} n \cdot \binom{n-1}{i} \cdot i \cdot (n-1)^{n-1-i-1}$$$. In other words, you calculate number of all labeled trees and subtract all trees having one vertex with too large degree. The subtracted value is obtained using generalized Cayley's formula which already appeared in previous Opencup contest.
How to solve C?
Note that we need only the position of the shift, not the number of inversions itself.
What happens if we shift the whole permutation once? Consider the left element. Let it be $$$X$$$. It currently takes part in $$$X$$$ inversions, and will take part in $$$n-X-1$$$ inversion when moved to the last position of the array. So the change is $$$n-2X-1$$$ no matter where other elements are.
To find the shift with minimum value we replace each element with $$$n-2X-1$$$ and find the prefix with minimum sum. It is done, for example, with a treap.
I misread the statement to find the number of inversions :(
J: For every value, calculate the distance to its destination and sum these distances. In a single swap, this sum can not decrease for a 'free' swap and can decrease by at most two otherwise. So $$$sum/2$$$ is a lowerbound for the answer.
Furthermore, it is easy to see it is always possible that you can always choose two values to swap so that the either sum decreases by two, or the swap is free and the sum stays the same (choose a value that is in the wrong place, see what direction it needs to go, if the value in that direction needs to go in our direction or is in its final place, we found a valid swap, otherwise it needs to go in some other direction and continue searching from that value). We cannot keep making free swaps indefinitely, so eventually we will make a swap that decreases our sum by two, which proves that the lower bound can be attained.
How to solve I?
K can be solved with a simple DP. Maybe Nash equilibrium is a scaring word.