gisp_zjz's blog

By gisp_zjz, history, 4 years ago, In English

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!

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

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

How to solve A?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +24 Vote: I do not like it

please, explain E

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 2   Vote: I like it +11 Vote: I do not like it

        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 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +79 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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 years ago, # |
Rev. 3   Vote: I like it +70 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

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

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      I guess so. Snarks only changed the problem titles in the right menu.

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

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

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

      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 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

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

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 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 3   Vote: I like it +33 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

            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 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I didn't make it to the contest(: