Dear Codeforces community,
We're excited to invite you to TOKI Regular Open Contest (TROC) #9!
Key details:
- Rated
- Contest links: Div 1 and Div 2
- Time: 23 November 2019, 19:35 UTC+7
- Style: full feedback, 8-minute penalty per wrong submission
- Scoring: You get the score assigned to the problem when you fully solve it
- Writers: AMnu
- Duration: 2 hours
- Problems: 5 for every division
- Allowed languages: C, C++11, Pascal, Java, Python 3
The round uses two divisions system:
- Users with rating less than 2000 or not yet rated should participate in Div 2
- Users with rating at least 2000 should participate in Div 1
Please register to the contest, and we hope you will enjoy TROC #9!
UPD1: Scoring distribution:
- Div 2: 100 — 200 — 300 — 400 — 500
- Div 1: 100 — 200 — 300 — 450 — 500
UPD2: Contest is over! Our Top 5:
Div 1:
Div 2:
Editorial is available here (English on page 5).
You can upsolve the problems here.
We would like to thank hocky and fushar as contest coordinators, and also ayaze and Zoroark as testers.
Thank you for participating and see you on the next contest!
Clashes with Atcoder contest.
How to solve Div1 D?
Notice that Si xor Ti = Si+1 xor Ti+1 is equivalent with Si xor Si+1 = Ti xor Ti+1.
Therefore, transforms all the array A and B to Ai xor Ai+1, then we can now consider them as string matching problem.
Notice too that the number of distinct possible matched subarray of A is only N sqrt N. Therefore, you can ignore duplicates of B, then do standard string matching (e.g. using hashing) and find their matches.
Afterwards, greedily change the value of A to get the answers
Is there any way to upsolve?
Yes, you may upsolve the problems here: https://training.ia-toki.org/problemsets/183/problems
Was E heavy light decomposition with a segment tree where each node has a matrix of dp[x][y] — the minimum time to traverse over the segment, starting on the lane of x and ending on the lane of y? This solution's constant in time complexity looks a bit too large. Is there any other better one?
Yes, but you do not need DP for this problem: you can greedily switch to the non-damaged lane (if there is one) whenever you encounter a damaged lane. This works because the time to switch lane, and the time needed to pass through lanes are given as constants (1, 2, and 5).
We have coded several different solutions, all of which run under 1s, so I believe the solution's constant will still fit the given time limit.
Yeah I did think about greedily choosing the lane as well, but did not notice that it actually worked fine on segment tree too. Thanks for you help xD.
Submitting on Training Gate creates this error-
Please fix it.
Hi, can you private message me with how to reproduce this error?