| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
Yesterday IEEEXtreme 17.0 was held, and there are a lot of problems to upsolve, so let's discuss problems here.
If there is a problem that you can't solve, maybe ask here and someone will help!
I will start with this problem, Cool Sum, I couldn't get more than 50% points and the only thing that came up online while searching for similar problems is “Generating Functions”, help.
Can you make a PDF of the problemset? IEEEXtreme is famously very closed. I can't access the problem you want help with, it sounds cool.
All the tasks from some of previous IEEEXtreme contests can be found here, https://csacademy.com/ieeextreme-practice/tasks/
Maybe try logging in csacademy ?
Yes, weirdly I can now access it...
For Cool Sum, there's a "trick" for computing sums of binomial coefficients with step $$$k$$$:
Let's look at the binomial formula: $$$(1+X)^n = \sum_{i=0}^n \binom{n}{i}X^i$$$.
The "trick" is to consider $$$X$$$ as the $$$k$$$-th roots of unity. This is because they wrap around when multiplied to the $$$k$$$-th power.
In essence, for some $$$\omega$$$ where $$$\omega^k = 1$$$ you have that:
$$$(1 + \omega)^n = \sum_{i=0}^n \binom{n}{i}\omega^i = \sum_{i=[0:n:k]} \binom{n}{i} + \omega \sum_{i=[1:n:k]} \binom{n}{i} + \ldots + \omega^{k-1} \sum_{i=[k-1:n:k]} \binom{n}{i} $$$.
Here $$$[a:b:c]$$$ is the set of numbers starting from $$$a$$$ until $$$b$$$ with step $$$c$$$ (similar to Python notation of slices).
So, in essence, $$$(1 + \omega)^n = ans_0 + ans_1 \omega + \ldots + ans_{k-1} \omega^{k-1}$$$. In other words, it's the answer (seen as a polynomial) evaluated in $$$\omega$$$.
Now, the FFT/NTT step comes naturally: first, compute $$$(1 + \omega_i)^n$$$ for all $$$\omega_i$$$ $$$k$$$-th roots of unity. Then, interpolate the polynomial given these $$$k$$$ $$$(\omega_i, (1 + \omega_i)^n)$$$ pairs. Because the $$$\omega_i$$$ are roots of unity, the "interpolation" can, in fact, be achieved by simply applying the inverse DFT on the array given by $$$(1 + \omega_i)^n$$$.
did you manage to solve Rectangles and Polygon Cutting?. I wasn't able to solve both. It'd be great if you share your intuitions for these
polygon cutting
For the Rectangles, you can create a graph where there is an edge between $$$i$$$ and $$$j$$$ if $$$i$$$ and $$$j$$$ are coprime, then you can iterate over the cliques in this graph and calculate the maximum sum of a clique.
This seems to pass within the TL when you don't consider the elements that are coprime with everything else.
True. But max independent set is NP hard. So I used a bitmask DP with time complexity O(2^25 * poly), considering the set of prime factors used below 100.
Cool sum:
Very short solution: Answer is the coefficients of (1+x)^n.
More details: In FFT, the degrees are "cyclic", which means x^a * x^b = x^((a+b)%L), where L=2^k is the length of FFT. So even if n is very large, the degree of each term in (1+x)^n is taken modulo by 2^k.
Actually, the answer is the coefficients of $$$(1 + X)^n \textbf{ mod } (X^k - 1)$$$, which happens to be exactly the ring under which DFT space works.
It should be $$$(1 + X)^n \textbf{ mod } (-1 + X^k)$$$ ?
You are right. Fixed, thanks!
Someone knows how to solve Dice?
The answer is the n-th coefficient of generating function $$$(D^1+D^2+...+D^k)/k$$$, where $$$D=(x^1+x^2+...+x^6)/6$$$ represents a single die. Simplify the formula and you will finally get something easy to calculate.
Could you please elaborate a bit more? I can only think of methods using FFT, which is too slow.
$$$(D^1+\cdots+D^k)/k=\dfrac{D^1-D^{k+1}}{(1-D)k}$$$
Continue on substituting with $$$D=\dfrac{x^1-x^7}{6(1-x)}$$$
And finally you can get the n-th coefficient of the formula without FFT.
Got it, thanks! It is quite surprising that inverse part can be done in a way without involving complex methods.
Could you explain a bit more how you get the nth coefficient of that polynomial? I'm struggling with the division.
Can I get a hint for Powerful Strings?
It’s dp on aho corasick dp[length][node]
with some optimizations.
Elaborating on "some optimizations":
Let's create matrix $$$A$$$, where $$$A[x, y] = \operatorname{pw}[\operatorname{cnt}[y]] * \operatorname{edges}[x, y]$$$, where $$$\operatorname{edges}[x, y]$$$ is a number of transitions in Aho-Corasick automaton from $$$x$$$ to $$$y$$$. Now answer is equal to the sum of coefficients $$$A^n[1, i]$$$.
Let's denote the answer for given $$$n$$$ as $$$f[n]$$$, then $$$f[n]$$$ follows a linear recurrence of size $$$m$$$, where $$$m$$$ is a size of matrix $$$A$$$. Therefore, you can find first $$$2 \cdot m$$$ values of $$$f[n]$$$ with DP in time $$$O(m^2 \cdot 26)$$$, find the linear recurrence in $$$O(m^2)$$$ with Berlekamp-Massey, and after that you need to find $$$n$$$-th element of linear recurrence, which can be done in $$$O(m^2 \cdot \log N)$$$ with polynomial exponentiation, or even in $$$O(m \log m \log N)$$$ with FFT.
Why tf I’m getting these downvotes?
I tried doing that, but I keep getting only 40%, this is my code.
I generated more than $$$2 \cdot m$$$ elements of the sequence then used Berlekamp-Massey, but I get WA on most cases.
Can you please provide a link to your code, or tell me what's wrong with my approach?
In line 137 it should be
cnt[root] += 1;, notcnt[root] = 1;. It is not guaranteed that the input strings are distinct.Thank you!! That was really stupid of me, I just got 100%.
For those wondering why you have 9 on cosinus peoblem. Try reading negative numbers incorrectly. First read the integer part(with minus), then read the fractional part(as positive number) and ADD them. So when you see -1.1 solve the problem for -1.0 + 0.1 = -0.9.
Upd: 0.9 -> -0.9, a typo
actually it doesn’t matter 0.9 or -0.9 because cos(-x) = cos(x)
No wonder. During the contest, I had already known that the test data is wrong. A lot of strong teams got the same 9 points, and our team's solution had been revised for a whole day :(
BTW, what was the solution?
How to solve Rumors ?
The idea is simple Get every connected component using only "??" edges And now you can test every component alone. If someone in the component has an in degree edge "->" then the whole component fails to be the source other wise all of them are possible sources.
Make a weighted tree, i.e., If a->b exists: add edge (a, b, 1), (b, a, -1) For a ?? b add edge (a, b, 0), (b, a, 0)
For each node as root find the sum of weight of edge going away from root. If the sum is exactly equal to the number of edges a->b (form) then it is a possible source. Basically, you need to find sum of weight of edge for every node as root node. For this, you will do rerooting.
Here's my accepted code:
How to solve Theme Park?
I only managed to get 60 points by floyd-warshall, iterating over all edges as options, taking the best option, and if d = 2, take the best option after taking the one selected before.
This might be not the best answer, as maybe you can take two edges that are not the best, but their sum are the best. But I didn't know any better approximation
It is enough to consider only pairs of edges which have a common vertex (either starting or ending one), which leads to $$$O(n^3)$$$ solution.
Why: let's say we have a pair of edges $$$(u \to v)$$$ and $$$(x \to y)$$$, then at least one of options $$$u := x$$$, $$$x := u$$$, $$$v := y$$$, $$$y := v$$$ is not worse. You can prove it by contradiction by writing down inequalities.
how i solve Rumors problem ?
Make a weighted tree, i.e., If a->b exists: add edge (a, b, 1), (b, a, -1) For a ?? b add edge (a, b, 0), (b, a, 0)
For each node as root find the sum of weight of edge going away from root. If the sum is exactly equal to the number of edges a->b (form) then it is a possible source. Basically, you need to find sum of weight of edge for every node as root node. For this, you will do rerooting.
Here's my accepted code:
You can erase all nodes you can reach from any node in a path where the first edge is directed (the -> edges). The answer are the remaining nodes. This is because, if a-> b, then obviously b can't be the source of the rumour. a, or an ancestor of a must be the source. Now, as b heard the rumour, all edges that the node b has should be directed from b, say b-> x for all edges b ?? x
if we suppose there could be x-> b then b heard the rumour from two sources ( x and a )which is not possible.
Then, x heard the rumour and you can continue erasing nodes until there are only left nodes with ?? edges and no -> edges.
How to solve happy numbers and Labradoodle?
For Labradoodle, you can solve it by brute forcing every prefix and suffix of the potential words, and checking for their existance using
std::mapor something like that then checking for ambiguity, if you're having a hard time implementing that you can check my code here.As for Happy Numbers, you need to know Digit DP before you can solve it, so you can try learning that then coming back to it.