Let's discuss problems. How to solve 2,5,8 and 11?
Let's discuss problems. How to solve 2,5,8 and 11?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
2 is the same dp as longest common subsequence.
Could you explain solution in more detail?
My solution to 2
We can do this in $$$\mathcal{O}(n^4)$$$ iterate a pair of vertices ( $$$(i,j)$$$ — first from upper polygon, second from lower) that we want to be connected. Then we can define $$$dp(u,d)$$$ to be the best arrangement of edges in segments $$$[i, u]$$$ in upper region and $$$[j, d]$$$ in lower region. Transitions are
$$$dp(u,d) = min(dp(u-1,d), dp(u,d-1), dp(u-1,d-1)) + $$$ distance between last points
In order to make it $$$\mathcal{O}(n^3)$$$ we can notice that each point in upper region must be connected with some point in lower region, so we can calculate this $$$dp$$$ only for $$$i = 0$$$ instead of all possible $$$i$$$.
For problem 7 I had the following approach:
Let's do binary search on the answer $$$|V|$$$ where $$$V=(V_x;V_y)$$$ is needed initial velocity.
The equation of the parabola might be found from the system of equations:
This equation might be as well rewritten as $$$2V_x^2 \Delta y = 2V_x V_y \Delta x - g\Delta x^2$$$. Now we should find those $$$(V_x;V_y)$$$ that it also holds that $$$V_x^2+V_y^2=|V|^2$$$. Solution to this equation may be reparametrized as:
Putting this into initial equation we'll obtain:
Now we should move from $$$\alpha$$$ to $$$2\alpha$$$, thus obtaining linear equation:
Which may be rewritten as $$$A \cos 2\alpha + B\sin 2\alpha = C$$$ where:
From this equation $$$\cos 2\alpha$$$ and $$$\sin 2\alpha$$$ may be almost uniquely determined if we additionally consider $$$\cos^2 2\alpha + \sin^2 2\alpha=1$$$. We may return to $$$\cos \alpha$$$ and $$$\sin \alpha$$$ as $$$\cos\alpha = \sqrt{\frac{1+\cos 2\alpha}{2}}$$$ and $$$\sin\alpha = \pm \sqrt{\frac{1-\cos 2\alpha}{2}}$$$.
Only thing left to do now is to check that for each point $$$(x_i;y_i)$$$ our parabola determined by the equation $$$\Delta y = \frac{V_y}{V_x} \Delta x - \frac{g}{2V_x^2} \Delta x^2$$$ lie higher than $$$y_i$$$ for every point $$$x_i$$$. I implemented this solution, but unfortunately got WA on test 6. Is this more likely to be a precision issue or I have some mistakes in the logic of solution?
We need to use
long doubleto get AC. Also, notice that for fixed initial velocity there are two possible angles, you should always choose the parabola with higher angle.I used long double.. Didn't help somehow. :(
I would say as a rule of thumb try to avoid anything looking like asin, acos or $$$\sqrt{1 - c^2}$$$ in your solution. This inevitably has precision issues when argument is near unit. Use atan2 if you can get both components or atan if you can only get the ratio, they don't suffer from precision issues.
Most of jury solutions use ordinary doubles.
P.S. x87 arithmetics must die already, and long double with it =)
No need to binary search.
The smallest answer given two points $$$(0, 0), (x, y)$$$ is $$$v = \sqrt{g(y + \sqrt{x^2 + y^2})}$$$, $$$\tan \alpha = v^2 / gx$$$. Either all points are below this trajectory, or the answer is a parabola through three points $$$(0, 0), (x_1, y_1), (x_2, y_2)$$$ with parameters $$$\tan \alpha = \frac{x_1^2 y_2 - x_2^2 y_1}{x_1^2 x_2 - x_2^2 x_1}$$$, $$$v = \sqrt{\frac{gx_i^2(1 + \tan \alpha)^2}{x_i \tan \alpha - y_i}}$$$ ($$$i = 1, 2$$$ is unimportant since $$$\tan \alpha$$$ is obtained from equiating these two velocities). Choose the largest $$$v$$$.
Yep, that seems much simpler and having less precision issues, thanks!
Test 6 is the test with maximum possible answer.
For the condition that rock hits the eye and fixed velocity $$$V$$$, I substituted everything related to angle with its tangent $$$\tau = \tan \alpha$$$. Finally, I got the following:
This allows to find starting angle. Moreover, this equation is unit-less, and it is in fact rather clear what numbers $$$\frac{Y}{X}$$$ and $$$\frac{g X}{V^2}$$$ mean.
How to solve 4. My idea was finding the node that maximize information (the number of nodes to discard) in the worst case, but to find this node I used heavy computations with bitsets that got TLE on test 10.
Precalc the decision tree once. It's $$$\mathcal{O}(n^2)$$$ (the input bug vertex is irrelevant, complexity can be boosted even further with bitsets), AC.
Our problem 4 solution
Precalculate reachability matrix ($$$R(u,v)$$$ is $$$true$$$ IFF there exists a path from $$$u$$$ to $$$v$$$)
For each bug we can maintain list of all candidate vertices that cause this bug. As we only have binary queries, for some candidate $$$x$$$ we can split all other candidates into two groups depending on answer about $$$x$$$. In order to reduce amount of candidates as fast as possible we want to ask about such candidate $$$x$$$ that will minimize the difference between two groups. Let's find optimal candidate in $$$\mathcal{O}(candidates^2)$$$ This solution already gives $$$\mathcal{O}(T \cdot n^2)$$$.
To optimize it further we can see that our information is very limited, we only have $$$20$$$ queires with binary answers and a starting position. And our questions are determined with sequence of previous answers. We can memorize this information with perfect binary tree, starting at root for every new bug and moving left with each $$$good$$$ answer and right with each $$$bad$$$ answer. Each vertex in this tree will have predetermined list of candidates and optimal candidate $$$x$$$. We can precalculate such tree in $$$\mathcal{O}(n^2)$$$ or in $$$\mathcal{O}(n^2 \cdot log(n))$$$ if we are storing explicit list of candidates in each node. Or we can calculate this tree lazily.
But it seems that to be able to start from every vertex we need $$$\mathcal{O}(n)$$$ such solving trees resulting in $$$\mathcal{O}(n^3)$$$. However we can safely discard information about starting vertex and think that we always start from the last vertex and it is guaranteed to be reachable from any previous vertex, this gives $$$\mathcal{O}(n^2)$$$ solution, possibly $$$\mathcal{O}(n^2 \cdot log(n))$$$, with some additional time $$$\mathcal{O}(T \cdot Q)$$$ to answer queries using this tree.
Is there any way to prove that your solution always fits into 20 queries?
The original idea was that you can provably reduce graph size at least twofold with one or two well-placed queries. This gives a hard upper bound that 20 queries is enough.
You can always choose a vertex such that there are between $$$n/3$$$ and $$$2n/3$$$ vertices reachable from it. Just pick a root and go into it's biggest son until the number of reachable vertices is greater than $$$2n/3$$$. So, if this works, then greedily picking the best vertex on each step also works.
Even considering just the first part of the solution (find a vertex which minimizes the difference), we can prove that the size of the graph reduces to at most two-thirds. Because assume otherwise, all vertices have reachable sizes either < N / 3 or > 2 * N / 3, but for any vertex reachable(V) <= reachable(C1) + reachable(C2) + 1, and we get a contradiction.
Problem 8 solution.
If $$$\phi$$$ is current angle of rotation, then each detector calculates $$$\lambda cos(\phi + \delta) + \beta$$$. Since $$$\phi\in{0, \pi/2, \pi, 3\pi/2}$$$, this gives us the following equatons:
$$$x_1 = \lambda cos(\delta) + \beta$$$
$$$x_2 = -\lambda sin(\delta) + \beta$$$
$$$x_3 = -\lambda cos(\delta) + \beta$$$
$$$x_4 = \lambda sin(\delta) + \beta$$$
So we can obtain $$$\lambda, \delta, \beta$$$. Knowing these numbers, we can compute $$$cos(\phi), sin(\phi)$$$ for each query and restore the angles.
Oh so both accelerators also could deviate their axis only in $$$Oxz$$$
11: consider the set $$$I(d)$$$ of all points inside the polygon at least $$$d$$$ away from its boundary. One can maintain the boundary of $$$I(d)$$$ as a set of initial sides shifted by $$$d$$$ with events "a side is eliminated by its two neighbours". Once all sides of a single color are eliminated completely in $$$I(d)$$$, print the only vertex of $$$I(d)$$$ of that color.
Can Anyone explain fucking input in the problem 5 ??? We got wa1 -_- and how to solve 10 and 6 ?
You can also have
(it's a bit more convenient due to 1-based indices)
For 6 do radix sort. Compress all the numbers to 0-index. Push all of them into the last bin and do radix sort by extracting numbers into the corresponding of the first 10 bins and pushing them back into the last one.
But why did they use that format?
I second this. If I calculated everything correctly, this compression reduces the maximum input size from 8MB to 4MB, and the maximum correct output size from 20MB to 16MB.
Was this really worth it? Sorry, I can't see any reasons other than making the world a worse place.
Are we the only one who got "check failed" verdict on problem 5? Anything we submitted on that problem got the same verdict.
How to solve 10?
First, let's change the strings into numbers. If we fix permutation of teams, we can greedily find the lowest possible number of the largest team (or $$$\infty$$$ if the permutation is not possible). We want to find maximum of this number across all permutations. Let's do it with subset dp. To find dp value for subset $$$S$$$ we try all possible last teams. If we choose team $$$i$$$ as last then the value is the lowest number that team $$$i$$$ has that is greater than $$$dp[S \setminus {i}]$$$. $$$dp[S]$$$ is the maximum of these values across all $$$i \in S$$$. Of course it's too slow for $$$n \leq 350$$$. But if $$$n \gt \sqrt{350}$$$, then answer is always no and you can change $$$n$$$ to 20.
What is the minimum possible value of $$$K = \sum K_i$$$ that can produce "YES"?
I guess $$$K = N(N-1)+1$$$, but I can only prove that $$$K \geq N(N+1)/2$$$.
It is an open problem: OEIS A062714
Also, you can read about the coNP-completeness of the problem 10 here link
Doesn't it say coNP-complete?
oops, fixed
How are these 2 problems equivalent? I can see some sort of resemblance, but I can't see any clear equivalence (or even implication). The main difference is that here you may use intermediate values and you ought to choose exactly one element from each part of a fixed partition of the sequence. I'm not sure if I'm missing something
Sort pairs (name; id of the list)
Now permutation can be a good order if you can find a subsequence of the second element in pairs that is equal to the given permutation.
Of course, also you can convert any sequence to the instance of our problem.
I did about the same thing. How can you prove that if n > sqrt(350), the answer is no?We could only prove that N > 44 or something like that doesn't work (because then the max product of the sizes of the lists would still be smaller than N!).
And in case N > sqrt(350) how do you find a permutation that can't be obtained? I've randomly generated permutations until one failed but I see no way of proving that there are enough many uncovered permutations for this to work in reasonable time.
We proved for $$$N \gt 25$$$, by each time choosing the set of words with the largest minimum valid value. It follows that $$$26+25+\dots+1=351 \gt 350$$$. Also, cases when $$$N \gt 25$$$ can be easily constructed this way.
I didn't prove it. My intuition was that to get all sequences of length $$$n$$$ we obviusly need $$$n^2$$$ elements. And getting all permutations didn't seem much easier.
To find a permutation I solve the problem for the first $$$20$$$ teams and then add $$$21 \ 22 \ ... \ n$$$ to answer.
Is it true that Benq is on 125th place? Like, how?
Only Spencer was participating and not for the whole contest. :P
Oops I would've taken it seriously if I knew that Ben and Zhezheng were on my team.
Anyway I can get case 6 of problem 10?
What's the trick in problem 5? Why do some teams have +13?