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

Автор skywalkert, 5 лет назад, По-английски

Greetings!

Ugh! That guy comes with another online-mirror and ruins my timeline again.

Here is the last one this year I could share with you, 2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest. It will start on Saturday, December 8, 2018 at 17:00 (UTC+8) and last for 5 hours. You are able to register 6 hours before the contest starts. However, before the registration starts, you may not view this contest on Gym. By the way, other Asia east continent regional contests shared by my friends and I could be found at Nanjing, Shenyang, Qingdao, Beijing and Xuzhou.

This onsite contest was held by Henan Polytechnic University on November 25th. It is the first time one regional contest was held on HPU, but it is quite memorable. Among the above 6 regional contest, I could definitely say Jiaozuo is the second easiest one. Though it may contain a few hard problems, several problems are solvable for beginners.

The problems are prepared by AHdoc, Claris, quailty and me. Thanks to zscc for discussing ideas, yefllower and niike0goood for testing, and MikeMirzayanov for developing wonderful platforms and kindly answering technical issues.

There is one thing we need to point out again. For everybody who has already read the problems, please do not to participate in this online-mirror contest or discuss solutions before the contest has ended. We have shared solution sketches (in simplified Chinese) in this site, so if needed, we would share some hints (in English) after online-mirror.

At the end of my post, I sincerely recommend authors of Asia-Hongkong (was held on Nov. 18) and Asia-East Continent Final (will be held on Dec. 16) would share problems with the public at any website. Your efforts should be rewarded!


UPD1: As a kindly reminder, our sponsor Jisuanke will hold another online-mirror contest soon after the contest on Gym, which will start on Sunday, December 9, 2018 at 12:00 (UTC+8) without the onsite board.

UPD2: Contest will start 1 hour in advance, as there is a CodeChef SnackDown contest soon after.

UPD3: Registration starts. You may view this page to register.

UPD4: Hints for this contest are published.

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

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

i hope it is ratefd

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

Awesome! Nearly all of the EC regionals are mirrored here now! Thanks for your efforts!

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

hello!!! we can still read this line!!!

"Ugh! That guy comes with another online-mirror and ruins my timeline again."

so genius of you

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

Nenevader eats dick!

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

:)

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

Am I right that it clashes with Snackdown :(?

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

    Yeah, you're right, so we decide the online-mirror will start 1 hour in advance. Thank you!

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

registration isn't start yet?

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

No registration? Gugugu?

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

I don't like ACM, because I can't hack others during the competition.

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

no rated = no participation

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

how to solve J? I try O(M^2(logN+logM) + NlogN) solution but TLE on case 4...

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится
    1. There is a memset(cs, 0, sizeof(cs)); in your code, which may lead to TLE if there are 1000 test cases.

    2. There is no need to use std::set. Try to get rid of .

    The standard solution uses the line-sweep technique from left to right, and uses a segment tree to maintain each row. There is a vector in each segment tree node, denoting those rectangles covering this interval. When a rectangle id occurs, we simply find the segment tree nodes, and do push_back(id) in their vectors. Note that there is no need to delete rectangles in these vectors.

    When we want to know which rectangles cover each tile, we can just DFS the segment tree. When we come across a node, just check the end of the vector, when this rectangle is valid(still cover some part on the sweeping line), we get one rectangle, otherwise we just need to do a pop operation. So this solution runs in .

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

      There is another method to figure out which 1 or 2 rectangles covered each tile. This method doesn't need data structure.

      Let's use 3 arrays a[1501][1501], b[1501][1501], c[1501][1501].

      When a tile is covered by only one rectangle: For each rectangle id, add id to a[xl..xr][yl..yr]. This can be easily done in O(N + M2). The answer is a[i][j].

      When a tile is covered by two rectangles: For each rectangle id, add id to b[xl..xr][yl..yr] and add id2 to c[xl..xr][yl..yr]. This can also be easily done in O(N + M2). Suppose the answer of tile (i, j) is (x, y), we know that x + y = b[i][j] and x2 + y2 = c[i][j]. So find the solution of these equations. It is a math problem.

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

Why does this code get WA in PyPy 3 (46753780) but is accepted in Python 3 (46776484)?

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

    This problem uses a specialized checker as follows, but I can't test your solution on Polygon as it doesn't support PyPy3.

    drifting-car-checker.cpp

    Implied from checker comment in 46753780, your program may print something extra, like invisible character, at the end of some line, or this may be a bug like bug in php.

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

      I think the problem is with PyPy.
      On Windows, it seems readEoln() of testlib.h expects \r\n line terminator if strict mode is on. However PyPy is using only \n regardless of platform, though os.linesep is defined correctly and using it gives AC: 46822975

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

        Thanks for your useful investigation! As I know, Java would have the same issue. In Java, if you want to use the formatted output to print \n on Linux and \r\n on Windows, you can use %n instead of \n.

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

          Thanks, I just tried it and you're right about Java. Important lesson learnt. However I don't think that checkers should be this strict. I was under the assumption, perhaps a wrong one, that extra whitespace is always ignored by checkers. Even the source of readEoln has a comment saying Use it in validators (and not checkers).

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

Can you share the Chinese solution if the English hints no done yet?

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

how to solve K?

upd: I have know now.

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

How can I see the final standing???