Apparently there is no official announcement, so I hijack this. Ask questions here.
Apparently there is no official announcement, so I hijack this. Ask questions here.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
F Editorial says S(p) is the LCM of the loop lengths. Why this?
I would expect that it is the max loop length.
For something like 2 3 1 5 4 the max loop from the first 3 is 3, but if you simulate it through 3 iterations, the first 3 are ok but the last 2 are in the 'odd' phase of their 2-cycle.
Consider $$$P = (2, 3, 1, 5, 4)$$$. The ball wills move like this:
After Snuke shouts three times, Person 4 has Ball 5, so 3 (the maximum loop length) is not an appropriate answer.
Each time Snuke screams, every Person i such that $$$i \neq p_i$$$ gives their ball to Person $$$p_i$$$ simultaneously.
Doesn't that mean, that after the first exchange, $$$4th$$$ and $$$5th$$$ men have to stop exchanging? That's misunderstanding in statement. I counted max loop lengthes.
$$$p_i$$$ don't change after people pass balls. They are elements of a fixed permutation $$$P$$$.
I mixed that up, too. But I think the statement is clear. Especially allways all persons give their ball to p[i]. It is just that i!=p[i], because if i==p[i] that ball would never move at all.
Can anyone please explain the formula given in the editorial for getting the count of each partitions ? It would be of great help.
Consider counting the number of permutations of such $$$(1, \ldots, N)$$$ that it consist of $$$k_1, \ldots, k_m$$$ cyclic permutations. These consist of two factors:
What "cyclic permutation group" does each element belong?
This is equivalent to determining such sequence $$$a_1, a_2, \ldots, a_n$$$ such that:
So this means that element $$$i$$$ belongs a cyclic permutation group $$$a_i$$$, or does not belong to any cyclic permutation if $$$a_i = 0$$$.
How many such sequences are there? Consider a sequence B = (($$$N - \sum k_j$$$ copies of $$$0$$$), ($$$k_1$$$ copies of $$$1$$$), ($$$k_2$$$ copies of $$$2$$$), $$$\ldots$$$, ($$$k_m$$$ copies of $$$m$$$)). This is an $$$n$$$-element sequence, and each permutation of $$$B$$$ correspond to the aforementioned $$$(a_i)$$$ one-to-one. Therefore, the number can be found as:
What does each cyclic permutation look like?
Given a set of elements that forms a cyclic permutation, we have to determine the actual permutation. For simplicity, we consider a cyclic permutation of $$$\lbrace 1, 2, \ldots, Q \rbrace$$$, of length $$$Q$$$.
What should $$$1$$$ map to? It should not map to $$$1$$$ itself, since it will never result in a cyclic permutation of length $$$Q$$$. Therefore there are $$$Q-1$$$ choices. Say $$$1$$$ maps to $$$p_1 \neq 1$$$. What should $$$p_1$$$ map to? It should not map to $$$1$$$, because it becomes a cyclic group of length $$$2$$$; nor should it map to $$$p_1$$$ itself. So there are $$$Q-2$$$ choices. The next element has $$$Q-3$$$ choices for its next mapping direction, the next has $$$Q-4$$$, ... and so on, before determine the destination of the last element, which should now go back to $$$1$$$ (no other option).
Therefore, there are $$$(Q-1)!$$$ options.
But wait, there's more!
To sum up the last two sections, we obtain the following number:
However, in the first chapter we distinguished the cyclic group with the same length. So we have to divide by an additional duplicate-remover.
To do this, let's convert the sequence $$$k_1, \ldots, k_m$$$ into the sequence of occurrences: $$$F_1$$$ elements of $$$k_1, \ldots, k_m$$$ are equal to $$$K_1$$$, $$$F_2$$$ elements are equal to $$$K_2$$$, and so on. Using this notation, the last expression can be re-written as follows:
Now we can divide by the freedom of permutation of same-length cycles:
This is equivalent to the expression in the editorial.
If you know some group theory, you will notice that $$$S(p)$$$ is the "order" of the permutation. If you google this term, you'll probably find a proof for why $$$S(p)$$$ is the LCM of the lengths of the disjoint cycles (what you call loop lengths).
Great.Someone explain me the reason of the solution in the editorial of problem E.Why same number of edges and nodes guarantee that there are exactly two possible ways of directing a particular connected component?
The editorial seems to be updated.
A Connected graph with 'n' nodes and 'n' edges will definitely have a simple cycle. You can think of it as a ring graph.
Since it is a directed graph, their are 2 ways — clockwise and counter-clockwise.
Not a simple cycle, but a simple cycle with paths attached to it.
The last sample is what helped things click for me. It showed a disconnected case, but 2 different arrangements that worked... started with asking if the connected parts had to have a cycle (yes), and then testing what happened with variations based on the part that had a 3-cycle with a vert-and-edge pointing into it. Not a proof, and still had to whip up the brute force sim, but was enough to convince myself... edit: also helped to narrow down range of ok e vs. v relationships, testing out (eliminating) various other graphs like hourglass, 7-segment digital display, flow thingies (start, n mids, end), etc...
I used a different approach instead of e == v relationship. I started from leaf nodes and removed all the leaf nodes sequentially. After this, all the remaining nodes in the graph must have a degree of 2.
Somewhat inspired from this of a recent Div 3 contest.
Can someone help me with [D].I can't understand how for case-> 3 (5,2),(7,2),(10,2) the answer is coming as 2 (https://atcoder.jp/contests/abc226/tasks/abc226_d)
there are two spells :
1.(1,0)
2.(-1,0)
ooh got it thanks!
In B I made a vector of strings,sorted them and calculated the answer.It gave WA and TLE on some tc.But when I made a vector of vectors, sorted them and then calculated the answer, it gave AC. Can someone plz explain this?
WA->(https://atcoder.jp/contests/abc226/submissions/27120194)
AC->(https://atcoder.jp/contests/abc226/submissions/27119995)
You basically make two mistakes:
Thanks for the reply ,understood my mistake! char wont take complete no ‘︿’
An "User Editorial" has been provided for problem F. Can someone explain how we are able to iterate through all possible LCMs without TLE?
Let's fix
N = 50, and we want to estimate what the maximum LCM could be. This is equivalent to, if we partition N to be $$$N = a_{1} + a_{2} + ... + a_{m}$$$，the LCM would be $$$LCM = lcm(a_{1}, a_{2}, ..., a_{m})$$$. Apparently we should make every $$$a_{i}$$$ to be coprime with others, to avoid loss of LCM. So an optimal solution to this would be: $$$a_{1} = 1, a_{2} = 4, a_{3} = 5, a_{4} = 7, a_{5} = 9, a_{6} = 11, a_{7} = 13, LCM = 180180$$$.180180is a loose upper bound, considered that some numbers in[1, 180180]won't be a valid LCM(some large prime, etc.). Actually for N=50, there are only 1056 valid LCM. So enumerating all possible LCMs would be easily fit in the time limit.