Which problems did you enjoy the most? I enjoyed problem N.Kitchen (div.2), a very interesting math problem. How to solve div.2. G and O?
P.S. I have found that upsolving of 15, 16, 17 rounds have appeared!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Which problems did you enjoy the most? I enjoyed problem N.Kitchen (div.2), a very interesting math problem. How to solve div.2. G and O?
P.S. I have found that upsolving of 15, 16, 17 rounds have appeared!
Name |
---|
O: Find two smallest primes which are not equal to given one and multiply given prime by them.
G: Count leading Ls plus trailing Rs and add 1 if there is something between them.
Thank you for G, I didn't realise that after Ls and Rs I need to add 1 if something is between. Upsolved with simple
print length <>=~ s/R.*(?!<L)L//r
In problem O, I couldn't pass TC#1, with this perl code :(
How to solve D, A, C?
D: Let's define
f(i)
as the best score we can get if we end in a positioni
. We need to maintain all available transitions (with respect to the segment length constraints) for the current position. When we movei
to the right, we need to delete one element and add another one. After that, we need to take the maximum off(i)
for all smaller prefix sums and add 1 to it, just take the maximum with the same prefix sum andvthe maximum minus 1 for all larger prefix sums. If we use a segment tree, insertions/deletions are just point updates and getting an optimal transition is reduced to three range max queries.C: One can show that a pair is bad (that is, neither even nor odd) if and only if it lies inside a non-bipartite edge-biconnected component or such a component is reachable from one of the vertices. So we need to find all biconnected components and remove those that are not bipartite. After that, we have several bipartite components. Let
c0
andc1
be the number of vertices0
and1
colors in some component. We need to addc0 * (c0 - 1) / 2 + c1 * (c1 - 1) / 2
to the number of even pairs andc0 * c1
to the number of odd pairs.Can somebody give me a link on statements for GP of Moscow Div2. Or a link on virtual contest. Please