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

Автор gisp_zjz, история, 4 года назад, По-английски

Hello! I'm happy to announce XXI Open Cup: Grand Prix of Weihai, which will be held today.

Authors of this contest come from Nanjing University, including gisp_zjz, zyb, sy_chen, Roundgod, calabash_boy, uuzlovetree,love.zy. This contest was originally used as China Collegiate Programming Contest(CCPC), Weihai Site. Enjoy!

Testers: -skyline-, chenjb, Subconscious, oipotato, 374272,VincentLx, Shedneryan, Icdereap. Thank you!

Contest link: http://official.contest.yandex.ru/opencupXXI/contest/21761/enter (Only visible for users with OpenCup login)

I will post the editorial after the contest. We are looking forward to your participation!

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

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

How to solve A?

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

    Find vertex with the lowest degree $$$v$$$. It should be in the first frame. Choose its neighbour $$$u$$$ and try to check wether there is a solution where $$$u$$$ is a copy of $$$v$$$ in the second frame. Degree of $$$v$$$ is $$$O(\sqrt{m})$$$, so it works fast.

    Now if we know that $$$v$$$ and $$$u$$$ are the same vertex in the first and second frames, we know that all other neighbours of $$$v$$$ are in the first frame. For each such neighbour $$$w$$$ we know that $$$w$$$ and $$$u$$$ should have exactly 2 common neighbours: $$$v$$$ and copy of $$$w$$$ in the second frame. So we can find all copies of neighbours of $$$v$$$ in the second frame. Using the same ideas and bfs we can find all the vertices in all the frames.

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

please, explain E

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

    E: You can prove, that one of the optimal paths between two cells either contains a cell which directly shares a side with one of the black holes, or you can just travel along the border of the rectangle bounding the two cells from the query.

    So all you need to do is to precompute the distances from all(168 = 4 * 42) free cells next to the black holes to all other cells, and then to answer the query you need to find the minimum length of the path going through one of those cells from the one query cell to the other one.

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

      Thanks! Worked very well for first 34 tests, but got ML, how did you solved it during contest? Do you have any idea how to fix it? Code

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

        vector<vector<vector<vector>>> is a very bad thing to use if you intend to save some memory.

        I had a similar problem when I was using something like vector dist[170][200000]. Try to calculate distances without using vectors, and it should path easily.

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

        I had the same issue, having 168 * 200000 vectors with one element is very bad, avoid small dimensions at the end.

        I did if (n > m) swap(n, m); and got AC with less than 200MB

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

    I solved E with the technique used in this problem. (https://atcoder.jp/contests/apc001/tasks/apc001_i) (It amazed me that so many teams knew this problem, but it seems that there is a simpler solution.)

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

      The version of the problem in this contest also has the constraint that $$$h \cdot w \le 200000$$$, which makes a couple simpler solutions possible.

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

Great contest!

Can J be solved in other way than sqrt + segment tree + hashes? It took me 350 lines to code it x.x

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

    Segment tree + hashes was enough, I needed no sqrt.

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

    We did segment tree + hashes: to check that two substrings are equal you need to check that:

    • Their first character is the same.
    • The sequence of value differences between adjacent characters starting from the second one is the same.

    First part can be maintained in a segment tree by doing segment updates & point queries. Second part is doable by segment tree over the array of differences: since each update changes differences for only 2 positions, you can do point updates & segment queries.

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

    I don't know what your "sqrt" means, but a usual segment tree is enough. Just add 1 on a segment and also track the maximum value with its position. While the maximum value is $$$65\,536$$$, decrease it by $$$65\,536$$$, and repeat. There will be no more than $$$\lceil \frac{q}{65\,536} \rceil \cdot n$$$ such decreases. To compare the substrings, we maintain hashes.

    My code has only 140 lines.

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

    We used just Fenwick tree + hashing for getting range sum and update value of one element (one Fenwick tree for current prefix hashing and one for getting current value of element after increase queries).

    Really nice tasks!

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

    For a large prime $$$p = k \cdot 2^{16} + 1$$$ (or several such primes) we can find $$$\omega$$$ of multiplicative order $$$2^{16}$$$, and $$$x$$$ of any large order. Substring hashes $$$h(s_0 \ldots s_{n - 1}) = \sum_{i = 0}^{n - 1} x^i \omega^{s_i}$$$ can be maintained with an RSQ structure with range multiplication updates (add $$$1$$$ to $$$a_i$$$ = multiply hashes by $$$\omega$$$).

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

      If I understand correctly, this allows us to have shift updates for values larger than 1?

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

        Yeah; although now I'm not sure there are no fancy collision schemes against this particular method.

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

How to solve G?

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

    Let's assume that there are $$$n$$$ black piles, no white piles, the size of the smallest black pile is $$$x$$$ and there are $$$k$$$ black piles with size $$$x$$$. Then if $$$k = n$$$, the Sprague-Grundy function of this game is $$$x$$$ if $$$k$$$ is odd and $$$x - 1$$$ otherwise. If $$$k < n$$$, it's the other way around: $$$x - 1$$$ if $$$k$$$ is odd and $$$x$$$ if $$$k$$$ is even. You can easily prove this by induction. Now the white piles are just usual nim, so you should xor their sizes with Sprague-Grundy function for black piles and check if it's zero.

    Let's fix the smallest black pile $$$x$$$. Also fix the parity of black piles with size $$$x$$$. Now there are 2 cases: if we don't take black piles with size greater than $$$x$$$, then the value of the game is already fixed, and we just need to check wether it's zero. Otherwise, we need to choose among piles with size greater than $$$x$$$ a subset with a fixed xor so that the total xor is zero. So we reduced our problem to a standard one: maintain a set of binary vectors with 2 queries: add a new vector to the set and count number of subsets with fixed xor. This is solved with Gauss. We maintain the basis of vectors in the set and when we need to count number of subsets with xor $$$x$$$, if $$$x$$$ is in subspace generated by our set, the answer is $$$2^{size \, of \, set - size \, of \, basis}$$$, otherwise it's zero. Also don't forget to check the case when all piles are white.

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

Contest finished! Final scoreboard: link

This problem set was originally prepared for an onsite contest(actually online, but made to work as onsite under many regulations), China Collegiate Programming Contest(CCPC), Weihai Site. When used in Open Cup, snarks permuted the problems and changed the problems' names to prevent some possible unfairness that would occur.

Here we present the original problem statement and the tutorial. You can easily find the correspondence between the problems in both files.

Problem Statement: link

Tutorial: link

Scoreboard for the onsite contest(Chinese): link

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

    The shared links are not accesible. Please fix it..

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

    Was the name changing a reason of different problem titles in statement vs. right menu of Yandex.Contest?

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

    In "E. So Many Possibilities...", how to find "dp(l, S)" in $$$O(2^n n m)$$$ ?

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

      During the l-th operation, enumerate which index(or no index) is dropped to 0.

      Suppose the index is $$$j$$$, it implies $$$s_l = j$$$ and we need to replace $$$a_j-1$$$ number of $$$0$$$ into $$$j$$$ in the sequence $$$s$$$.

      In detail, define $$$ cnt(S) = \sum_{j\in S}a_j $$$ , then

      $$$ dp(l,S)=\frac{1}{n-|S|}\cdot dp(l-1,S) + \sum_{j\in S} \frac{1}{n-|S|+1}\cdot \binom{l-cnt(S\setminus j) - 1 \text{ }}{a_j-1 }\cdot dp(l-1,S\setminus j) $$$
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Right, I was missing the idea of replacing zeroes with non-zeroes.

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

We prepared this contest mainly to fit the requirements for our onsite contestants. We cut some hard problems and modified some constraints to meet that requirement, thus the contest is not very hard. Hope you still enjoyed it. Anyway, thanks for the participation!

The contest is already uploaded to Codeforces Gym. Enjoy!

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

It looks like Memory usage counting for Java on Yandex Contest is completely broken. We got Memory Limit Exceeded for problem I (see submission 1 and even more optimized submission), but the same codes passes in Gym: 97933469 and 97933601 (with 64M or even 8M memory usage).

Could somebody please take a look?

snarknews

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

    Not saying it's not broken on YandexContest but 8MiB doesn't sound right. You have 3 int arrays of length of a 1000000, it is 12Mb already

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

      Yeah, agree that Codeforces doesn't do a perfect job in memory counting also, but at least result is much closer to what I'd expect.

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

        Just as a wild guess after looking at the submission code and nothing else, I think the issue might be in the reading of input. We need to read 1 million lines with 3 integers each. You are creating 5 objects per line (the line itself, tokenizer, 3 strings for each integer).

        Random searching shows that a string with length 8 consumes 60 bytes of memory, not sure how accurate it is, but probably in the right ballpark, so you're allocating on the order of 300M with your 5M objects, and the ML is 256M.

        You're not allocating them all at once, but here I think the real issue of Yandex.Contest manifests: they probably don't pass the correct value for -Xmx (unlike Codeforces), so the garbage collector doesn't see a need to free the objects you're no longer using, because it thinks there's still a lot of memory available.

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

          Good guess! I replaced Scanner with static char buffer and manual integer parsing and got AC with 40M memory usage (interesting, does InputStream.read allocate?).

          Still wondering about differences in Codeforces and Yandex Contest Java configurations. If the only difference is in -Xmx, then for submission 97933601 I'd expect Codeforces to show memory usage, which is bigger than 8M (at least by size of young generation heap).

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

          Don't you think that escape analysis should help in this case?

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

            Good point! I'm way too unfamiliar with the internals of Java to answer :)

            I guess from what we're seeing we can hypothesize that it helps on Codeforces but not on Yandex.

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

I didn't make it to the contest(: