Hey everyone,
Here's an invitation for all programming lovers to participate in the 4th Turing Cup competition!
The Turing Cup is an invitational competition that is organized by one of the most successful informatics competition teams in China, the XinYouDui, and X-Camp.
Several top students of XinYouDui: Chao Li (IOI 2012 Gold Medalist)；Yinzhan Xu (IOI 2014 Individual 1st place winner)；Ce Jin (IOI 2016 Individual 1st place winner):
Top contestants such as IOI Gold medalists, and other top CPers joined the past contest as well.
The 4th Turing Fun cup is open for registration, come and code with us!
Registration link (No Registration Fee)
Novice Group: We'd recommend programmers who have completed learning the language and basic algorithms and who are in USACO silver division, are eligible to participate.
Intermediate Group: This level is for contestants with skills in applying basic data structures and common algorithms to solve problems. Recommended contestants who are in the USACO Gold division are eligible to register.
Advanced Group: This level is for contestants with skills in advanced data structures and algorithms to solve complex problems. Recommended for contestants who are in the USACO Platinum division/ US Camp to register.
Contest Time: Event time link:Saturday,5/14/2022, 6:00:00 PM PDT.
FAQ:
Q: What kind of info does the registration need?
A: Full Name, Email, School, DOB
Q: What will the prizes be?
A:
1st place: Macbook Air;
2nd-6th ranklist, Cherry Mechanical Keyboard;
7th to 21st ranklist: DuSmart Speaker.
Novice Group: awards are only eligible for players born after January 1, 2010
Intermediate Group: awards are only eligible for players born after January 1, 2008
Advanced Group: no age restriction
Q: How to join the contest?
A: You can participate directly by clicking the link in your browser (Chrome, Firefox recommended) during the contest window. When you log in to the system, the problems will show up based on the division you choose.
Q: How can I view the real-time rank list during the contest?
A: Click the link below to check the rank list, you could check different groups' rank lists.
Q: More questions?
A: For Participants, feel free to join the official Discord channel or please email us: info@x-camp.academy (in English), or feedback@xinyoudui.com (in Chinese).
【UPD】
Hi everyone, thanks for participating the 4th Turing Cup competition! We hope that you enjoyed the competition! And thanks everyone for attending the competition, thanks our sponsor Hundsun Technologies Inc., and thanks everyone who supported the competition!
We strive to provide high quality of problems and smooth competition experience for everyone. Any feedback is more than welcome! Please help us fill out the survey below.
We will upload the videos of the opening ceremony and analysis of problem in XinYouDui WeChat official account, X-Camp Academy YouTube channel. We will also update the status here once the videos are posted.
Please use the next 24 hours for dispute for the competition results. Please email your dispute to info@x-camp.academy (in English) with the subject: 4th Turing Cup score dispute.
The winners of the competition will be finalized in around 30 hours once we resolve all disputes, and finish code deduplication. Winners will be announced on the XinYouDui WeChat official account, X-Camp WeChat public account and Discord channel.
For the winners, staff will contact you by email to verify your identity and ask for your recipient's address.
Please see tutorials below.
Here is the upsolve link for The 4th Turing Cup.
We will follow up with another post for the final results of the competition and announce the winners officially!
Says "Validation failed, please refresh the page and try again". What does that exactly mean?
[]
I repeated once more now and a problem has been resolved.
would you mind to share more details of this issue? on which step, registration part or? Will let the technician check later and get back to you asap.
I was facing this issue when I was trying to register my account
Same here :(
The discord invitation seems not working, could you send a new one?
I like this one, T cup, so big cup
Is it pupil-only tournament?
born after 2010?????
For an hour and fifteen minutes there was an incorrect statement for one problem in an english version, thats ridiculous :)
Will there be an upsolving session?
Already in Gym: The 4th Turing Cup
How to get 100 points on C intermediate?
Please see the posted tutorial, thanks!
Can someone elaborate upon this how to calculate dp g(u,v,x) as defined in tutorial of problem F(Trees)(Subtask 5) in quadratic time? Or any other quadratic solution to the problem. Best I could come up with was O(n^2logn) solution with help of convolutions.
nvm I was using FFT for convolutions but starighforward all possible pair multiplication too leads to O(n^2) complexity overall removing the logn factor. gr8 problem thanks :)
We can solve H (Virus Experiment) in $$$O((n+q)\log n)$$$ time.
Instead of using Centroid Decomposition, we'll take an arbitrary root. On the corresponding rooted tree, for each query, we consider the $$$LCA(s,t)$$$ and do similar things as the model solution.
My solution has two non-trivial differences from the intended one. For convenience, we'll write $$$u<v$$$ when the node $$$u$$$ is the strict ancestor of the node $$$v$$$. We'll also define $$$\leq,min,max$$$ by this partial order.
First, we have to answer the following type of question.
To do this, first, for each node $$$x$$$, we find the minimum node $$$y$$$ s.t. the path $$$(y,x)$$$ is a palindrome, and let $$$palmin(x)$$$ denote the $$$y$$$.
For a query $$$(u,v)$$$, we'll first find the maximum node $$$x$$$ s.t. $$$palmin(x) \leq u$$$. We can see that $$$m$$$ should satisfy $$$u<m\leq x$$$. Let's take a node $$$w$$$ s.t. $$$palmin(x)\leq w \leq x$$$ and $$$dep(x)+dep(palmin(x))=dep(u)+dep(w)$$$. In other words, $$$w$$$ is a point of symmetry of $$$u$$$ with respect to the path $$$(palmin(x),x)$$$. Since the path $$$(palmin(x),x)$$$ is a palindrome, the longest palindromic suffix of $$$(x,u)$$$ is the same as the longest palindromic suffix of $$$(palmin(x),w)$$$. Now the problem is almost the same as Case 1 in the official tutorial, and we can solve it in $$$O(\log n)$$$ time per query.
Another non-trivial difference in my algorithm is the analysis of the complexity of Case 2 and Case 3. The $$$O(\log^2 n)$$$ part in the official solution comes from the fact that we need to do binary-lifting for each arithmetic progression.
The complexity is $$$\sum_i ceil(\log(b_i))$$$. Since the number of arithmetic progression is $$$O(\log n)$$$, all we have to estimate is $$$\log(\prod_i b_i)$$$. We can see that $$$|a_i|b_i \leq |a_{i+1}|$$$, and this implies $$$\prod_i b_i \leq n$$$, so the total complexity of this part is bounded by $$$O(\log n)$$$.
Here is my implementation (157862269).
By the way, it would be great if authors would submit their model solutions.
The solutions were submitted here (158099599 158100374) . Thanks for improving the solution :)