IOI 2022 Task Discussion (Editorial) is now available here. The link has been posted in the IOI 2022 Tasks page as well.
→ Pay attention
Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:38:59
Register now »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:38:59
Register now »
*has extra registration
→ Top rated
| # | User | Rating |
|---|---|---|
| 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 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 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 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/22/2024 11:56:02 (i2).
Desktop version, switch to mobile version.
Supported by
As mentioned in the editorial, the binary search solution can give an $$$(3 + \varepsilon)N$$$-query solution, and requires some additional optimizations. In particular, if there are $$$t$$$ types, I believe the runtime is upper bounded by something like $$$3N + (\log_2(\lceil N/t \rceil) - 4) t$$$, which only exceeds $$$3N$$$ when $$$N/t \ge 18$$$ or something. However, past this point, I'm not sure how to prove tighter bounds.
The editorial only roughly sketches some optimizations, and doesn't provide any proofs. Does anyone have any formal analysis past this point?
In fact, I think the bound of the binary search solution will exceed $$$3N$$$ (at least when $$$N$$$ is large enough and the interactor is adaptive), and it's hard for me to imagine a simple optimization which could lead to a $$$3N$$$ bound (which has a formal analysis and is either deterministic or with $$$1 - \epsilon$$$ probability).
During the contest, I got a $$$99.89$$$ on my first attempt and an $$$100$$$ after moving the midpoint to the right by $$$0.5$$$. Still, I failed to understand why it got AC and tried a DP approach to calculate the optimal midpoint given the size of the set and the upper bound of an element's occurance. (didn't notice the problem is non-adaptive at that time) It turned out, however, that the bound is no less than $$$3.02$$$. (Chances are that my implementation went wrong)
This DP doesn't consider the optimization that we could skip unnecessary operations (e.g. the first few elements are always inserted so that the calls of
press_button()can be reduced). Yet this only improves the bound by $$$\tilde O(N/t)$$$, which is $$$o(N)$$$ when $$$t = \Theta(N)$$$.Consider a node $$$v$$$ with children $$$c_1, \cdots , c_t$$$. Let $$$a_i,b_i$$$ be the number of threshold assignments to the subtree of $$$c_i$$$ that make $$$c_i$$$ evaluate to 1,0 respectively. Note that $$$a_i+b_i$$$ is independent of the source values. We want to find the number of threshold assignments that make $$$v$$$ evaluate to 1.
The number of assignments that make exactly $$$k$$$ of the $$$c_i$$$'s evaluate to 1 is the coefficient of $$$x^k$$$ in
From here it's easy to see that the number of assignments which make $$$v$$$ evaluate to 1 is $$$f_v'(1)$$$, which is
From here the formula is easy to derive.
This is also how I derived it. However, after reaching this form, we can find a more natural way to rephrase this in terms of probability.
Let $$$p(u)$$$ be the probability that a random assignment makes $$$v$$$ evaluate to $$$1$$$. Then, we claim that $$$p(u)$$$ is the average of all $$$p(v)$$$, where $$$v$$$ ranges through all children of $$$u$$$.
Proof: Let $$$c$$$ be the number of children of $$$u$$$. $$$p(u)$$$ equals $$$\frac{1}{c} \cdot$$$ (the sum of $$$i \times $$$ probability that exactly $$$i$$$ children are black). This is equal to $$$\frac{1}{c} \cdot$$$ the expected number of black children of $$$u$$$. By linearity of expectation, we have the desired conclusion.
Yeah, it was such an easy cheese with generating functions. Not a fan of this task
Thank you for the quick editorial! I really liked the task Thousand Islands.
The answer exists if the source have at least $$$2$$$ out edges and other vertices have at least $$$1$$$ out edges. Remove all other edges, and "hide" one out edge of the source vertex. You get a functional graph and can obtain a tour on functional graph. Hide another edge and obtain another tour, they constitute the "two cycles" which you can concatenate and repeat.
You can easily have that setting since you can repeatedly remove vertices with no out-edges, and if the source have $$$1$$$ out edges you can also remove the source and recursively try to find the answer.
If you did 55 points in that problem, probably you will have some rough ideas like "ok, two disjoint cycles leaving from some vertex reachable from $$$0$$$". This seems very sketchy, we can't even see if the guess is correct, and even if it's true it seems hard to construct such a thing. However, we can actually claim a bold proposition, and somehow that's really easy and clean to prove. It was really nice, and reminded me of the past tasks: 2021 Keys and 2019 Split.
For subtask 6, the editorial mentions that if you take the subset of towers in the global solution that fall into the range $$$[L, R]$$$, you will add at most two extra towers, one between $$$L$$$ and $$$A[i]$$$, and another between $$$A[j]$$$ and $$$R$$$. However, I am unsure what happens when the interval $$$[L, R]$$$ contains no towers in the global solution. The editorial doesn't elaborate on this, since in this case, $$$i$$$ and $$$j$$$ are ill-defined. Does anyone have any ideas how to handle this case?
The answer is always at most 2; if there were 3 towers in the range, then the middle one should be part of the global solution. Then, we can start with the minimum tower in the range and try to add one on either side.
Thanks! I have another question though.
Why would it be true that the middle one should be part of the global solution?
Here is my progress:
If we let $$$A,B,C,D,E$$$ be the towers in order, where $$$B, C, D$$$ are the towers in the empty interval, and A and E are the towers just outside and part of the global solution. We know $$$B, C, D$$$ can communicate with each other, and $$$A$$$ and $$$E$$$ can communicate with each other as well. We want to show $$$A$$$ can communicate with $$$C$$$, and $$$C$$$ can communicate with $$$E$$$.
We know, since $$$B, C, D$$$ can communicate with each other, that there is a tower $$$\geq H[C] + d$$$ between $$$B$$$ and $$$C$$$, and there is a tower $$$\geq H[C] + d$$$.
However, I am not sure how to show that between $$$A$$$ and $$$C$$$, there exists a tower $$$\geq H[A] + d$$$. If we can show that, we would be done, since we have a symmetric argument with $$$C$$$ and $$$E$$$. We still haven't really used that $$$A$$$ can communicate with $$$E$$$.
In this case, the lower of A and B should be included in the global solution next to C: if B is lower than A, then the tall tower to A's left is also to B's left, so that works; if A is lower than B, then the tall tower between B and C also works for A and C.
Hi! I'm sorry for necroposting.
I'm questioning, is there another editorial for day 1, problem Towers? Official editorial was difficult to understand, and I wonder if anyone has better explanation for >60 points solution?