rng_58's blog

GP of SPb
By rng_58, history, 5 years ago, In English

How to enter the contest?

The d1 link leads to ejudge.

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

Comments Comments (51)
| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Read here.

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

Judge is not working now :(

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +95 Vote: I do not like it

Is this some kind of Div2 OpenCup?

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

How to solve C and D?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In C we asked vertices for which we haven't got -1 and with maximal probability to reach edge to another component. This could be estimised by deg(v) — size_connected_component(v)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We took the vertex with the highest degree from the smallest component and that also worked well.

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

        I took random vertex (which I haven't got -1) from the smallest component and that also worked well.

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

          We just picked any vertex (except -1) with the minimal degree

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

        We took arbitrary vertex (ofc that we haven't got -1 already) from smallest component. I don't think degree of the vertex is useful in this case.

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

          We took the vertex with the lowest degree (don't care about its component) and got AC. Seems like the judges want to make people happy and let everyone pass :D

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

      I took a random permutation and asked 2 times for each vertex in the permutation, somehow that got AC.

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

        Wait... But in random graph random permutation ~ $$$1, 2, \ldots, n$$$.

        So is it really working to ask(1), ask(2), ..., ask(n), ask(1), ask(2), ..., ask(n)? (>﹏<)

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

          Indeed, this problem works in mysterious ways rofl it didn't pass for 1 2 3 4 5 ... n

          → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Our submissions has not judged in last an hour (still running). Did someone else have the same problem?

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

How to solve B?

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

    Enumerate every field in table and xor indices of fields with ones

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it
  1. No C++11 in a testing system. Judges are still in 2007 or what?!
  2. Submissions sent in 04:20 are still running
  3. No one answered on our clar submitted at 04:15, and didn't even read it

Worst opencup organization ever

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

How to solve A without Gauss elimination?

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

    A could be solved by interpolation. But under this constraints it is not better than gauss

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

    In A we can use the fact that for every $$$k\geq d+1$$$ the following holds:

    $$$\sum_{i=0}^k(-1)^i\binom{k}{i}P(a+bi)=0.$$$

    Then we choose random $$$a$$$ and $$$b$$$ and increase $$$k$$$ until we get equality modulo $$$mod$$$.

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

    Fact: If $$$f(x)$$$ is a polynomial with degree $$$n$$$ then $$$f_{1}(x) = f(x + a) - f(x)$$$ (with any constant $$$a$$$) is a polynomial with degree $$$n-1$$$. If we define $$$f_{k}(x) = f_{k-1}(x + a) - f_{k-1}(x)$$$ then $$$f_{n}(x)$$$ will be a non-zero constant and $$$f_{n+1}(x) = 0$$$. The converse is also true. Therefore you can ask integers of form $$$b+at$$$ with some random constants $$$a$$$, $$$b$$$ and compute values of $$$f_{k}(x)$$$ accordingly. As soon as we find out $$$f_{k}(b) = f_{k}(b+a) = 0$$$ we can determine with high probability that $$$f(x)$$$ is of degree $$$k+1$$$.

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

How to solve D? We solved it O(N * sqrt(N) * log(N)), but we do not know the verdict yet.

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

    Our solution is $$$O(N^{3/2})$$$.

    Just do sqrt decomposition. It`s easy to deal using some precalculation before the queries with a pair of sqrt blocks (sort each block), with an element and a block (just sort each block and calculate values in increasing order of elements using some pointers for each block), and, finally, after the query you solve for a pair of "pieces of blocks" (using the fact that you can store all sorted prefixes and suffixes of all blocks in $$$O(N^{3/2})$$$ time and memory).

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got AC with your complexity, making the block size as low as possible and getting rid of the log in precalculation. The only part with log was sorting the "pieces of blocks" but that works quite fast since it uses little memory.

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

    I solve D with Mo + Fenwick Tree + Hard Struggle

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

      I solved D with $$$O(n^{1.5}\log n)$$$ after TLE for 10+ times. And my $$$O(n^{1.5})$$$ solution got MLE :(

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

Where is the baobab in the Math&Mech facility?

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

So what was the jury interactor's strategy for C?(I hope it's not a secret)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    No strategy, no secret, described in the statement: the graph is random and fixed in each test case.

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

      But nothing was said about about how vertices in interactor's responses are chosen(well, except for the samples).

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -57 Vote: I do not like it

        The edges of the graph are ordered (uniformly at random) in advance. Then, for each question about vertex $$$v$$$, the answer is the first edge incident to $$$v$$$ in that order, or $$$-1$$$ if there is no such edge left.

        This strategy is actually given in the Note section after the example:

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

          I thought that this Note is describing a strategy for the example, not for all tests. I don't think that Note is a proper place for jury strategy description :)

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

          I thought the last sentence only applied to the example tests. Not sure if that was your intention :) But thanks for the answer anyway.

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

            Yeah, I see now how this can be misleading.

            Sorry for the confusion!

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

Our C still in queue.

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

How to solve G?

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

    You are given $$$N$$$ functions of the form $$$f_i(\theta) = |r_i sin(\theta + \alpha_i)|$$$, and you want to find $$$\theta$$$ that maximizes the sum of $$$K$$$ smallest values among $$$f_i(\theta)$$$.

    This sum is a "piecewise trigonometric function" with $$$O(N^2)$$$ pieces, so we can explicitly represent this function and compute the maximum.

    The border between two pieces is a point that satisfies $$$f_i(\theta) = 0$$$ or $$$f_i(\theta) = f_j(\theta)$$$ for some $$$i,j$$$. We should list all such angles and sort them, and do various things carefully.

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

Will be editorial or upsolving?

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

One of our submission is still pending: problem B in Java, at 0:52 during the contest. No response for clarifications. I believe the judge is broken.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We received "Check failed" verdict for problem B solution on Java during the contest. Switched to C++ to get it judged.

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

How to solve F?

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

    Greedy. Let's store the answer for each vertex $$$v$$$ — the indices of taken decorations in its subtree. The answer for some vertex $$$v$$$ is the union of answers for all its children plus $$$w_v$$$ values of $$$v$$$. Truncate that list to $$$min(t, w_v)$$$ most expensive values, that'll be the answer. Use small-to-large and store the answer in a map to achieve $$$O(n \log^2 n)$$$.

    → Reply