Let's discuss the tasks here.
How to solve problem B?
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Let's discuss the tasks here.
How to solve problem B?
Название |
---|
Was bitset intended for I? My $$$O(\frac{n^3}{w})$$$ solution runs in only 350ms.
No. There is simple $$$O(n^2)$$$ greedy solution.
Note that $$$1$$$ is always in the answer. Then we should greedily add vertices $$$2$$$, $$$3$$$, ...
For example, we want to add $$$i$$$ to the answer. We should also add all vertices from $$$i$$$ to $$$1$$$ and for each we should check that there are no bad vertices added. We can note that check for each vertex need $$$O(n)$$$ time, and if we check all vertices once, we will achieve $$$O(n^2)$$$.
How can we accomplish this? Can you elaborate more? Other than that, my solution is same, except using bitsets to speedup the check to $$$O(\frac{n}{w})$$$.
Suppose we are trying to add vertex $$$v$$$ to the current set $$$S$$$ and we find a path from $$$v$$$ to $$$S$$$: $$$v = p_1, p_2,...,p_l$$$ ($$$p_l \in S$$$). Then we just iteratively check if $$$p_i$$$ is consistent with $$$S \cup $$${$$$p_{i+1},...,p_{l-1}$$$}. If we find that some vertex $$$p_j$$$ is a not consistent and we stop at vertex $$$p_j$$$, we simply mark all vertices in {$$$p_1,...,p_j$$$} bad and do not need to re-calculate the consistency of them anymore. On the other hand, if no bad vertices are found, then we just add $$$p_1,...,p_{l-1}$$$ to set $$$S$$$. From this you can see that for each pair $$$(u,v)$$$ we check at most once if the path from $$$u$$$ to $$$v$$$ is a palindrome of length greater than $$$k$$$.
B: "Set of edges without cycles" is a matroid. "Set of edges after which deletion graph is still connected" is also a matroid. You need to find the largest element in the intersection of these two and check that the remaining edges form a tree.
How to solve F (in 10 minutes)? Is it well known in Japan? We had a solution, which we didn't even try to implement because we thought we need at least 1,5 hours to do so.
https://oj.uz/problem/view/JOI20_hamburg I copied from here :P
Seems it appeared in JOISC 2020 Day 1...
B: Firstly, divide the whole graph into a tree and a forest, then 1+3 is the tree and 2 is the forest. Division plan can be found by matroid intersection.
By the way, how to solve C?
C: For a fixed $$$k$$$ we need to choose $$$g = gcd(a, b)$$$, then $$$a' = a/g$$$ and $$$b' = b/g$$$ are coprime divisors of k, and $$$g$$$ should be a divisor of $$$k/a'b'(a'+b')$$$, so you can calculate the number of solution by trying all the possibilities for $$$a'$$$ and $$$b'$$$ and then calculating the number of divisors. So, to have a lot of solutions $$$k$$$ should have a lot of divisors, so let's generate some reasonable set of candidates (something like highly composite numbers but a bit looser) and check only them. With some very loose criteria (use only primes up to 40, each prime exponent starting from 5 is at most 1 greater than the previous one) works a couple of minutes on my laptop. I would not be surprised if it is possible to choose some tighter criteria so the solution can run on server and fit in TL.
How to solve J? We guessed the answer by coding a naive solution with infinity being 500, but honestly to me it even sounds weird that the answer isn't always 1 (given $$$p \neq 1$$$).
There is a well known problem about two players playing a game with probability of winning equal to p for the first player (see https://en.m.wikipedia.org/wiki/Gambler%27s_ruin). You just need to tend the amount of money for one of the players to infinity
I see, thanks
I have some different solution:
Let's solve the problem for one dimension (for many dimensions we should multiply probabilities for separate dimension).
Consider we are at position 1. Let's see all possible ways to get 0. We can count this ways using correct bracket sequences. For +1 we will use "(" and for -1 we will use ")". So, probability to get 0 we can calculate using this simple formula:
$$$P = C_0 \cdot q + C_1 \cdot p \cdot q^2 + ... = (\sum_0^{\infty} C_i \cdot (p \cdot q)^i) \cdot q$$$.
So we can use generating function of Catalan numbers: $$$G(z) = \frac{1 - \sqrt{1 - 4 \cdot z}}{2 \cdot z}$$$. We should calculate $$$G(p \cdot q) \cdot q$$$.
Then we should understand, that if we was at position x, then answer is $$$(G(p \cdot q) \cdot q)^x$$$.
Another solution:
Let's $$$w$$$ — probability to get $$$-1$$$ after some movements. Then $$$w = p + q \cdot w^2$$$
Is the opencup website not available outside of contests? I haven't been able to load it in quite some time.
Editorial for D:
Note that the rotation operation in a binary tree does not change the order of numbers during forward traversal.
Also pay attention to selection sort — it sorts the array using the least number of swap operations.
Thus, the minimum answer will be equal to the minimum answer for sorting the array, obtained by direct tree traversal.
Let's learn how to do $$$swap(i, j)$$$ for a tree. To do this, we can use the following algorithm:
Thus, we can solve the problem using the minimum number of swap operations.
Unfortunately, this solution will not work, since the total number of operations will be exceeded (we can have $$$O(n^2)$$$ of them. One of two approaches can be used to solve this problem:
In total, we obtain a solution in $$$O(n \log n)$$$.
Can anybody explain solution to problem F please?
Consider the "tightest" constraint in each direction: the leftmost right edge, the rightmost left edge, the topmost bottom edge, and the bottommost top edge. Clearly, we should never place points further outside than these edges. If the leftmost right edge and the rightmost left edge cross, then all rectangles must share a common x-range, so 1D greedy; likewise with the other two. Otherwise, in order to cover all rectangles, there must be at least one point on each of these 4 edges.
For $$$m <= 3$$$, this means at least one point must cover two of these edges, so we can pick one of the 4 corners and recurse on the remaining rectangles with $$$m-1$$$. This takes $$$O(4^m n)$$$ time.
For $$$m = 4$$$, either one point covers two edges (in which case we pick a corner and recurse on $$$m = 3$$$) or there is exactly one point on each edge. Let's visualize the 4 edges as a rectangle, where we pick one point on each side. In this case, each shelter rectangle imposes one of a few types of constraints:
Now, let's pick/sweep over all possible locations of the point on the left edge. If this is fixed, then we should greedily pick the points on the top and bottom to be as far right as possible. In particular, casework on either the top point or bottom point to be further left, and choose it as far right as possible to avoid breaking OR constraints with the left side and top/bottom OR constraints. Then, choose the other top/bottom point as far right as possible. Finally, check if there is a valid choice of the right point.
To implement this, we just need to be able to query, for a particular choice of one point, which range constraints does it impose on the others. This can be done with several range-update point-query-min/max seg trees, approximately one on each pair of sides. This leads to an $$$O(n \log(n))$$$ time solution.
Interestingly, this paper claims to also give an $$$O(n \log(n))$$$ solution for $$$m = 5$$$: https://www.cs.bgu.ac.il/~segal/pierce.pdf.
Problem G's semantics seem a little strange. I managed to get AC by disabling liveness checks for direct references but not indirect references. In particular, my AC submission prints
versus
Is this intended? I would've thought that both are supposed to be errors. (My original code was getting WA on test 14.)
My solution prints an error for both programs. There is a rule for this (which I'm sure you saw but anyway):
You cannot pass a value variable and a reference to that variable at the same time on the same line.
It seems that 34 tests is not enough for this kind of problem, considering that there are 100 tests for others.
That makes sense, but my solution only passes tests when I changed it to allow the first case :'( Does anyone know what test 14 is?
14 test case was:
Also, both previous examples should output "Error" due to the rule in the comment above. Here, indeed, 34 tests were not enough.
Ah ok that explains my bug, I forgot to reassign
a
a new variable ID. Thanks!I just noticed that my first attempt failed on the last test, which happened to not handle this rule correctly :(
For my first attempt, it prints
Valid
in the following test (excpectedError in line 2
)One question: what does "at the same time" mean? Does it mean to the same function? Are you allowed to use the same variable if it is passed to different function call subexpressions? (Perhaps only if the borrow occurs before the move?) If this is the case, is there a well-specified order-of-evaluation for subexpressions?
I believe in this problem for the sake of understanding you can actually omit "at the same time", since (I think) it only matters if they are on the same line (which we treat as one instruction in this problem).
You cannot pass a value variable and a reference to that variable at the same time on the same line.
By our design, this means that you can use the variable by name or you can use its references, but not both on the same line.
This rule is necessary to resolve the uncertainty of the order of function calls, which is not described in the statements.