skywalkert's blog

By skywalkert, 11 months ago, ,

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.

UPD4: Hints for this contest are published.

• +211

 » 11 months ago, # |   -23 yay if this is rated i will get out of pupil! :D
 » 11 months ago, # |   -30 i hope it is ratefd
 » 11 months ago, # |   +75 Awesome! Nearly all of the EC regionals are mirrored here now! Thanks for your efforts!
 » 11 months ago, # |   +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
 » 11 months ago, # |   -25 Nenevader eats dick!
 » 10 months ago, # |   -21 :)
•  » » 10 months ago, # ^ |   -13 :))
 » 10 months ago, # |   +32 Am I right that it clashes with Snackdown :(?
•  » » 10 months ago, # ^ |   0 Yeah, you're right, so we decide the online-mirror will start 1 hour in advance. Thank you!
 » 10 months ago, # |   +5 registration isn't start yet?
 » 10 months ago, # |   +7 No registration? Gugugu?
 » 10 months ago, # |   0 I don't like ACM， because I can't hack others during the competition.
 » 10 months ago, # |   -21 no rated = no participation
 » 10 months ago, # |   0 how to solve J? I try O(M^2(logN+logM) + NlogN) solution but TLE on case 4...
•  » » 10 months ago, # ^ | ← Rev. 3 →   +16 There is a memset(cs, 0, sizeof(cs)); in your code, which may lead to TLE if there are 1000 test cases. 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 .
•  » » » 10 months ago, # ^ | ← 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.
•  » » » » 10 months ago, # ^ |   0 wow! thank you for your kind reply!! it's really helpful
 » 10 months ago, # |   +8 Why does this code get WA in PyPy 3 (46753780) but is accepted in Python 3 (46776484)?
•  » » 10 months ago, # ^ |   +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#include #include "testlib.h" using namespace std; const double eps=1e-6; int main(int argc,char* argv[]) { setName("compare files as sequence of lines including real numbers (strictly)"); registerTestlibCmd(argc,argv); ouf.strict = ans.strict = true; int T=inf.readInt(); for(int ca=1;ca<=T;ca++) { double usr_res = ouf.readDouble(); double std_res = ans.readDouble(); if(!doubleCompare(usr_res,std_res,eps)) quit(_wa,format("In case %d, expected '%.12f', but found '%.12f', error '%.12f'.",ca,std_res,usr_res,doubleDelta(usr_res,std_res))); if(ca
•  » » » 10 months ago, # ^ |   +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
•  » » » » 10 months ago, # ^ |   +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.
•  » » » » » 10 months ago, # ^ |   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).
 » 10 months ago, # |   -36 MAN WHY yoy LIE?? you said RATEd and i coult have GOTTEN outof PUPIL but NO you now change it and make it unbrated !?!!?? dumb
 » 10 months ago, # |   +7 Can you share the Chinese solution if the English hints no done yet?
•  » » 10 months ago, # ^ |   0 Published. Please refresh the post.
•  » » » 10 months ago, # ^ |   0 thank you!
 » 10 months ago, # | ← Rev. 2 →   +6 how to solve K?upd: I have know now.
 » 9 months ago, # |   0 How can I see the final standing???
•  » » 9 months ago, # ^ |   +1 Official final standing: https://icpc.baylor.edu/regionals/finder/Asia-jiaozuo-2018/standingsMirrored final standing: https://codeforces.com/gym/102028/standings
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 It would be nice to know the nicknames of the members of each team in CF...