Feel free to discuss the problems here :)
And here's my new rating:
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | adamant | 155 |
4 | cry | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Feel free to discuss the problems here :)
And here's my new rating:
Name |
---|
Congratulations on an unprecedented achievement!
It's even more epic because Petr predicted it before the rating update. (He asked admins about this possible problem)
And what's the point about Petr's new rating, for those who don't catch a trick?
his rating is 0 now. He was the only one to participate in the parallel 3B round. Only those who advanced from 3A could be in it.
And here is the reason if anyone is wondering:![](/predownloaded/f6/f1/f6f1a08d2ce67de498c742e896d91c9cffbceea5.gif)
I must present you initial version of Easy. You are given W and H. What is the minimum N for which you can fill grid with squares 1, 2, ..., 2N - 1? Who will be the first to find the intended (very short) solution?
Something like this? Or even shorter?
Much shorter. And ofc. it's not about language tricks, it's about very nice solution.
Let's try:
So cool! I wonder how that was the intended solution, though :p
I can't prove this solution in a way other than considering all cases and proving that this formula handles it :)
(also, it seems that your solution above doesn't work: the answer for the test
2 2
should be2
, but your code gives3
)Congratulations KAN! But please think about some math function doing the same :D
Please ignore, I had misread the problem.
Hmm, we can
return 64 - __builtin_clzll(sum)
, but only in g++. Is there a way to do it without floating-point operations and without such__builtin
functions?This is the best way to calculate logarithm I've ever seen :D
PS. It reminds me one time when I calculated product of p - 1 numbers modulo and it was always equal to 1.
To make things clear — answer is
.
What did you expect? You weren't even able to overperform anybody in the contest you've participated :)
How to solve 800?
Let's draw a directed graph with n vertices and n edges: from x to f(x). Let's look at the required function g(x) as a mapping on this graph: we map each vertex to some other vertex. The condition f(g(x))=g(f(x)) means that mapping should be such that whenever there's an edge from a to b, there should be an edge from g(a) to g(b), so we're kind of embedding the graph onto itself.
The graph has exactly one outgoing edge for each vertex, so its structure is some cycles with some directed trees growing into the cycles. Consider a vertex X on the cycle of length A. Where can it be mapped? Because of the "edges are mapped to edges" condition, it must be mapped to another vertex on a cycle, and the length of that cycle should divide A. Let's just iterate over all vertices Y that X can be mapped to.
For each particular Y, the mapping of all vertices on X's cycle is uniquely determined. As for the trees growing into this cycle, we can compute the number of ways to embed them using the following dynamic programming: we just count the number of ways to embed a subtree going to each vertex P in such a way that P is mapped to Q for each vertex Q. When we want to embed a subtree in such a way that P maps to Q, that means that all predecessors of P must be mapped to predecessors of Q, so we can use our dynamic programming results to compute the number of ways to map each branch of the tree, and multiply them.
The working time of the solution is O(N^2).
Screencast