prabowo's blog

Invitation to TOKI Regular Open Contest #9
By prabowo, 4 years ago, In English

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:

  1. jonathanirvings
  2. YogayoG
  3. wiwitrifai
  4. Pyqe
  5. ollpu

Div 2:

  1. YouKn0wWho
  2. ipul23
  3. Egor
  4. farmerboy
  5. markus_geger

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!

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Clashes with Atcoder contest.

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

How to solve Div1 D?

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

    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

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

Is there any way to upsolve?

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

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?

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

    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.

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

      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.

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

Submitting on Training Gate creates this error-

Please fix it.

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

    Hi, can you private message me with how to reproduce this error?

    → Reply