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

Автор yz_, история, 4 года назад, По-английски

Happy (late) new year Codeforces community!

We are excited to invite you to TOKI Regular Open Contest (TROC) #18!

Key details:


Scoring distribution: 100 — 250 — 300 — 350 — 450 — 600 — 650

We would like to thank:

  • prabowo for admitting to be a masochist the amazing coordination of the round.
  • hocky for showing his very long tongue helping with problem preparation.
  • malfple and markus_geger for testing the problems and giving invaluable feedback.
  • fushar for the amazing TLX platform.

Please register to the contest, and we hope you will enjoy TROC #18!

P.S. we encourage you to read all problems! :)

UPD: Contest is Over!

Congratulations to our top 5:

  1. uwi
  2. neal
  3. natsugiri
  4. Pyqe
  5. noimi

Congratulations to our first solvers:

Editorial is available here (English version is available on page 8)

You can upsolve the problems here.

Thank you for participating and see you on the next contest!

P.S.(2) Did you notice an easter egg in the problemset?

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

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

Can all problems be solved with Extended Li Chao Tree, as stated in rama_pang's blog?

Jokes aside, I hope this will be a fun contest!

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

TROC 18+

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

be me

new troc post

"we encourage you to read all problems! :)"

reads all problems

answers none

think about life

life returns wa verdict

sleep

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

Have you finally opened for business?

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

Friendly bump! The contest will start in 40 minutes, good luck and have fun! :D

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

I wish the word minimum was in bold in problem C :(. I guess that serves me right for trying too hard to speedsolve.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Can anyone tell me why this didn't work for E?
Code

UPD: Fixed. Thanks Lain _______

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    When you lazily propagate, you can't just XOR the entire segment with $$$x$$$. Think about it — if there is an even number of elements in your segment, it's XOR won't be affected when you XOR every element by $$$x$$$.

    To fix it, store the size of the segment and propagate accordingly.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Whether you "flip" (as in your code) node value or not, depends on the range that node corresponds to.

    In particular, if the range is even, you shouldn't "flip" the node value.

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

Is it possible to see other participants solution?

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

Is there a solution possible for problem F which uses construction of directed graph. If the graph is cyclic, answer is 0. Otherwise we say that is v is reachable from u, operation v should occur after operation u compulsarily.nodes are the operation from 1 to n-1. Finally, the answer is number of topological sort of this graph.

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

    You can use the DAG and DP to determine $$$f(l, r)$$$ the answer for using operations from $$$l$$$ to $$$r$$$. And you know which operation can occur first (using the DAG) so you can break $$$f(l, r)$$$ into summation of $$$f(l, i - 1) * f(i + 1, r) * ncr(r - l, r - i)$$$ if operation $$$i$$$ can occur first.

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

Thanks for the contest. I had $$$O(N^2)$$$ for F, but I'm wondering if it's possible to do better than that.

I was able to reduce the problem to this: given an arrangement such as 1 -> 2 -> 3 <- 4 <- 5 <- 6 <- 7 -> 8 -> 9, how many permutations of 1 through $$$n$$$ (in this case $$$n = 9$$$) satisfy that for every a -> b (or equivalently b <- a), a comes before b in our permutation?

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Ok I think I have $$$O(N \log^2 N)$$$ using div-conquer and FFT.

    Feels like there might be something nicer than that, like a pure combinatorics approach -- the only thing that should matter is the lengths of the chains.

    Edit: never mind, the div-conquer / FFT idea doesn't quite work.

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

    The editorial describes an $$$O(N^3)$$$ approach. What is the $$$O(N^2)$$$ approach?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      The $$$N^2$$$ is to solve the version of the problem I stated above. You go from left to right and use a single DP state of "how many remaining slots in the permutation come before my previous number?"

      E.g., if you have already placed _ 2 _ 3 4 _ _ 1 _ and you want to place 5 next, it doesn't matter where 1, 2, and 3 are, it only matters that there are two empty slots in front of the 4.

      The reason the original problem reduces to the problem above is that this is the structure for the order dependency of the swaps.

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

Auto comment: topic has been updated by yz_ (previous revision, new revision, compare).

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

I found an $$$O(n \log MAX A)$$$ solution for G. The editorial's method is $$$O(n^2 \log MAX A)$$$ so I thought I'd share my solution. I found an $$$O(n \log^2 MAX A)$$$ on contest, but my implementation was $$$O(n^2 \log^2 MAX A)$$$.

Spoiler

It appears that plenty of people found an algorithm with the same complexity, as seen on the time leaderboard for upsolving. I don't know if any of them use this exact method. It would be interesting to hear other people's solutions.