### Prabowo's blog

By Prabowo, 12 months ago,

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!

• +11

 » 12 months ago, # |   +19 Clashes with Atcoder contest.
 » 12 months ago, # |   0 How to solve Div1 D?
•  » » 12 months ago, # ^ |   +5 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
 » 12 months ago, # |   +8 Is there any way to upsolve?
•  » » 12 months ago, # ^ |   0 Yes, you may upsolve the problems here: https://training.ia-toki.org/problemsets/183/problems
 » 12 months ago, # |   0 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?
•  » » 12 months ago, # ^ |   0 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.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 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.
 » 12 months ago, # |   0 Submitting on Training Gate creates this error-Please fix it.
•  » » 12 months ago, # ^ |   0 Hi, can you private message me with how to reproduce this error?