Petr's blog

TopCoder Open 2015 Round 3B
By Petr, history, 9 years ago, In English

Feel free to discuss the problems here :)

And here's my new rating:

  • Vote: I like it
  • +137
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Congratulations on an unprecedented achievement!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    It's even more epic because Petr predicted it before the rating update. (He asked admins about this possible problem)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      And what's the point about Petr's new rating, for those who don't catch a trick?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        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.

        → Reply
»
9 years ago, # |
  Vote: I like it +32 Vote: I do not like it

And here is the reason if anyone is wondering:

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Something like this? Or even shorter?

    if (w > h) swap(w,h);
if (w <= 0) return 0;
if (h <= 1) return 1;
int n=0;
while ((1ll<<n) < h) n++;
return max(n, min(n+1, calc(w, h-(1ll<<(n-1)))+1));
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Much shorter. And ofc. it's not about language tricks, it's about very nice solution.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Let's try:

    ll sum = (w + h) - 1;
int n = 0;
while (sum >> n) n++;
return n;
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So cool! I wonder how that was the intended solution, though :p

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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 be 2, but your code gives 3)

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Congratulations KAN! But please think about some math function doing the same :D

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Please ignore, I had misread the problem.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 4   Vote: I like it +14 Vote: I do not like it

          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 .

          → Reply
»
9 years ago, # |
  Vote: I like it +75 Vote: I do not like it

What did you expect? You weren't even able to overperform anybody in the contest you've participated :)

→ Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve 800?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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).

    → Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Screencast

→ Reply