Блог пользователя prabowo

Автор prabowo, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Clashes with Atcoder contest.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div1 D?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Is there any way to upsolve?

»
5 лет назад, # |
  Проголосовать: нравится 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?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      5 лет назад, # ^ |
      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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Submitting on Training Gate creates this error-

Please fix it.