Блог пользователя Petr

Автор Petr, история, 9 лет назад, По-английски

Feel free to discuss the problems here :)

And here's my new rating:

  • Проголосовать: нравится
  • +137
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Congratulations on an unprecedented achievement!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        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.

»
9 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

And here is the reason if anyone is wondering:

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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?

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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));
    
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

    Let's try:

    ll sum = (w + h) - 1;
    int n = 0;
    while (sum >> n) n++;
    return n;
    
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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)

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Please ignore, I had misread the problem.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +24 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится +14 Проголосовать: не нравится

          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 .

»
9 лет назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

How to solve 800?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится