hehezhou's blog

Invitation to 4th Turing Cup
By hehezhou, history, 3 years ago, In English

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: [email protected] (in English), or [email protected] (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.

Survey Link

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 [email protected] (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!

Announcement of The 4th Turing Cup
  • Vote: I like it
  • +129
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Says "Validation failed, please refresh the page and try again". What does that exactly mean?

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

    []

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

    I repeated once more now and a problem has been resolved.

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

    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.

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

      I was facing this issue when I was trying to register my account

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

    Same here :(

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

The discord invitation seems not working, could you send a new one?

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

I like this one, T cup, so big cup

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

Is it pupil-only tournament?

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

born after 2010?????

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

For an hour and fifteen minutes there was an incorrect statement for one problem in an english version, thats ridiculous :)

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

Will there be an upsolving session?

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

How to get 100 points on C intermediate?

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

    Please see the posted tutorial, thanks!

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

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.

  • Given two nodes $$$u<v$$$, find the maximum node $$$m$$$ s.t. $$$u<m \leq v$$$ and the path $$$(u,m)$$$ is a palindrome.

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.

→ Reply