skywalkert's blog

2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest (Online Mirror on Gym)

By skywalkert, 6 years ago, In English

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.

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

Comments Comments (27)
| Write comment?
»
6 years ago, # |
  Vote: I like it -30 Vote: I do not like it

i hope it is ratefd

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

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

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

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

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

so genius of you

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

Nenevader eats dick!

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

:)

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

Am I right that it clashes with Snackdown :(?

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

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

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

registration isn't start yet?

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

No registration? Gugugu?

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

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

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

no rated = no participation

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

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

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

    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 .

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

      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.

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

        wow! thank you for your kind reply!! it's really helpful

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

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

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

    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.

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

      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

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

        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.

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

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

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

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

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

how to solve K?

upd: I have know now.

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

How can I see the final standing???

→ Reply