Hello Codeforces,
I am already a retired competitor, but recently the regional contest held in Qingdao is considerably controversial(sorry only Chinese).
Online board here.
Many contestants complained about things like data(solution with higher complexity got passed, while lower one got TLE) and problemset (as you see, 3 problems you may get gold, while silver and bronze at the same time). For me, though not insider, I still felt bad as well. They should have do their best on data and difficulty, as it is their responsibility.
The thing is, our contestants have no where to complain and they do not even know the exact problemsetters, really disappointed.
Have you ever had some regional contest experience? What is your attitude on this one?
Auto comment: topic has been updated by flpt0x (previous revision, new revision, compare).
Many contestants complained about things like data(solution with higher complexity got passed, while lower one got TLE)A little bit more information, the problem features a string that has a length of 10^5. Most of the teams passed that problem with a non-optimized O(n^2 = 10^10) algorithm, while LCP + SA algorithms may receive TLE/AC depending on the implementation.
Gonna translate the top comments cause they deserved it.
The link is broken, this should be the post: https://www.zhihu.com/question/66941603
--Disclaimer: This is just my personal opinion, nothing to do with my uni--
So here is my uni's (HKU) situation in the Qingdao site:
Too Young To AC: 2 problems, Bronze medal
Turtle Racer: 3 problems, Silver medal
It's disheartening to see that my fellow schoolmates received a Bronze medal in their retiring regional competition since they have always received a silver medal in the past 3 years, hoping to get a gold medal before the retire. Yes, they could have solved other problems and secure a gold medal, and there are 4 of them at a reasonable difficulty level. However, years of experience led them to overthink about J, believing that there must be a straight-forward algorithm since so many temams have solved it, while beliving that O(n^2) would never passed system test. (Even if it does, IT SHOULD BE DISAPPROVED MANUALLY.)
On the otherhand, this is the first ever ACM contest for all Turtle Racer members. We are glad to see that they secured a silver medal for Too Young to AC. However, the reason that they passed J is majorly because of they didn't paid much attention to time complexity. This exactly is why some teams are mad about this — Instead of testing your intelligence, this regional tests your bravery.
I think the problemset is not that awfully bad (while it's still indecent to see that there are 4 unsolved problems.). It features a range of different types of problems, with accessable difficulty for teams that deserves gold/silver medal, but the environment onsite is just severely disrupted by problem J — most unskilled teams solved J first, leading to skilled teams focusing on J and missed out other problems.
As an ICPC freshmen, I am not sure if the Xi'An regionals which I competed was great. It feels decent during the competition, and my team received a gold medal. However, when I scroll through the forums afterwards, I realized that lots of the problems have a very similar version online (eg: http://mirror.codeforces.com/blog/entry/55534 ).
First comment:
UPD: AHdoc ( Rumors says that he is the problem setters, no official proofs though), I beg you to spare the lifes of the upcoming ICPC contests participants. (Naning, Hong Kong, Urumqi)
AHdoc do you seriously have no idea why you have such an infamous reputation?
You think this is just a regional contest?
Some teams only attend one regional per year, and this is how you treat them?
Why are the coaches no complaining in such a crucial moemnt? Are we fine with leaving this comittee to ruin EC ICPC?
Additional notes ommited, they carries the same opinion, with a few other examples. It's hard to translate those reference. >_>
Second comment:
What a horrible experience.
Not sure what did the problem authors expected. I could understand that time penalty being a major factor in ICPC for tough problem sets, but now the problem set tests our bravery?
I made a debug submission of O(n^2) at the final 10 minutes for problem J, AND IT GOT AC??!!
So whoever the first dares to submit a brute force submission gets a gold medal?? The shy ones get f**king nothing? So ICPC Bronze = fast typing, ICPC Gold = fast typing + bravery ?
Why don't we just feature a NP-Complete problem with a size of 1000, and the only test case is exactly the sample. How exciting would it be.
As a side note, if brute force can't pass J, then most of the teams could only solve 2 problems (or maybe even gold). If you finish writing the first 2 problems in 20 minutes you receive a silver medal -- I sincerely have no idea what are the setters thinking.
Summary of the problem set: 2 problems extracted from C language examination paper, 2 gold medal level problem (but problem J test cases turned it into a bronze+bravery problem), 3 WF qualifying problems ( pick any 2 ), 4 unsolvable problems. 6666666.
Third comment:
Remember kids
Writing up a string problem could cost your career.
Fourth comment:
Last competition before retiring, what a terrible experience.
My uni is the one who won a gold medal by solving only 3 problems. This year we had the largest team compared to the past few years, sending 6 different teams to regionals. Since February I (the only Year4 student in the team) have led all the 6 teams till Summer break. We thought that we have the greatest chance in the Qingdao site, thus we sent 3 teams, expecting to win 2 silver + 1 bronze. In reality? Team 1: Nothing, Team 2: Gold, Team 3: Silver.
I am a member of team 1. Of course, our school is glad to receive a gold medal, but we have never expected team 1 to win nothing.
First let me share what happened with Team 2. They were following the board stats to search for the easier problems. One of them made a mistake thought J had the most AC ( it was actually I ) so he went ahead reading J. After they had passed B and I, he came up with a O(n^2) algorithm, and asked the leader if he could optimize it. The leader thought he fully understood the idea, and went ahead writing a O(n^2 lgn) solution (translator's note: W.T.F). Since they are not familiar with computing time complexity, they did not knew it has such a high complexity. They went ahead and submitted their solution anyways, and got AC ... Conincidentally tehy became the team with the least penalty and rose to the top of the boards. When I saw the boards I thought it must be broken and I refreshed it, and I was shocked. Just as everyone had said, my uni won a gold medal with pure luck. Team 2 has two new members, and they will be still participating ICPC next year. Indeed, their skills are far from gold medal, if they didn't won one again next year, please don't be harsh on them.
Team 3 received WA for a long time, and they submited a brute force solution desperately and won silver.
And us, we also proposed an O(n^2 lgn) solution initially, and received WA->TLE after a bit of tinkering, thus concluding that brute force is not the solution. Since we understand what Team 2 is capable of, we concluded that they must have came up with an ingenious conclusion, and it must be easy to code. After a while we decided to try other problems instead, I noticed that problem E was about Burnside lemma ( Translator note: problem E is actually not that hard even if you can't prove |g| for the set ... |g| is fixed across all cases trivially, and Sum(X^g) is also trivial so you could actually use the sample cases to brute force the value of |g|. This is exactly what our team did while discussing out of competition and we brute-forced the correct value of |g|. ). But our team haven't practiced related problems for a long time thus we gave up. Then we read F, realizing that the original problem was featured in 2016 Shenyang regionals, with some minor changes. I made some conjectures based on the original solutions, but realizes that it is risky and troublesome to debug the solution, so we gave up. We also tried other problems from time to time, but since problem J had the most AC, we were desperated and decided to group up to solve J. All of our proposals received WA, so we won nothing in the end. We asked Team 2 about their solution, surprisingly they had the exact same O(n^2 lgn) algorithm as ours, but ours somehow received a TLE, so did other teams, maybe it has something to deal with our suffix array template.
After the prize giving ceremony we held a celebration party. I was so broken-hearted and got so drunk, but I still took up the responsibility the share our experiences to other non-retiring members.
I still remember my first ICPC was 2015 Shenyang regionals, AHdoc was the author, and we only solved two problems. The next year in the Shenyang regionals, AHdoc was the author again, and we still won nothing. Then it was the 2016Qingdao regionals, AHdoc was the author AGAIN, and we were so close to silver but we ended up bronze. I was planningto retire, but since I was so close to silver, I decided to give one last shot this year, and made up an intensive training plan based on my prior experience. I am thoughtful that my schoolmates endured the weekly trainings with me, but I did not anticipated that everything would end like this ( Thankfully Team 2, 3 won medals ). Though we have expected that the problemset will be awful since AHdoc wrote it, but it's still shocking that I won nothing. Luckily we still have the silver medal from Xi'An last week to comfort us.
That's it, I am retiring ..... ( Credits to whose who helped the writer in this career )
Fifth comment has nothing to do with the controversial topic. It might be biased for me to not translate this neutral commment.
Summary:
Blogging stuff
Some complains about the technical issues happend in warmup contest
Give credits to the organizers for resolving the issues happened during warmup. Agrees that the problem is hard, a bit negative about problem J.
Congrats to the champion (ZJU) for qualifying WF.
Sixth comment:
A: How many AC did you got?
B: Three.
A: Me too.
B: What did you won?
A: Bronze
B: Gold
-- A joke that I read online.
Seventh comment:
WHAT THE HECK IS THIS EMBLEM???
Translator note:
English on top: New York Alumni Association
Chinese at bottom: Wuhan University
Koosaga they can feel you. I mean it.
No more translations. It takes too much time >_>
Are there English statements and are they public?
Here's an album to questions that my coach shared to my team: imgur
The controversial problem is "Problem J — Suffix".
Thanks, however I wanted to see unsolved problem the most and there's only D out of them :D. I tried coding it, but my answer differs by ~1 on last sample xdd
lol, our team was thinking if D is solvable with several ternary searches.
And by the way, there was a clarification made for D during the contest, although the sample output provided 6 digits, it is only required to get to 3 d.p. for AC as stated in the output format.
Nested ternary searches is exactly my idea. General idea is that optimal curve looks like kinda like enema https://vrota.pl/wp-content/uploads/2015/08/lewatywa2-482x300.jpg :P. Only points where it is not locally a circle can be starting point and points where we transition from land to water, so basically it consists of three arcs (apparently it should be vertically symmetrical). There is also a case that it can be a circle in land. I use one outer ternary search to determine how long is segment of coast included in my area and inner ternary search to determine how much time I should spend on land and within inner ternary search I also have binary search to find α such that
for a particular x. But it seems I miss some cases since my code works on first three cases but gives 1325.08 instead of 1326.02 on fourth one.
I also fear about case when two circles on land I construct will overlap and I don't consider it right now, but that may lead only to overestimating answer and I currently underestimate it.
G: Given n (1 ≤ n ≤ 108), find the number of (x, y, z) such that x2 + y2 = z2 - 7 and 1 ≤ x ≤ y ≤ z ≤ n.
This is just a modified version of Project Euler 223 and 224.
Auto comment: topic has been updated by flpt0x (previous revision, new revision, compare).