yz_'s blog

By yz_, history, 4 years ago, In English

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
  • Vote: I like it
  • +113
  • Vote: I do not like it

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

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 years ago, # |
  Vote: I like it +33 Vote: I do not like it

TROC 18+

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

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 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Have you finally opened for business?

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

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

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

UPD: Fixed. Thanks Lain _______

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

    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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is it possible to see other participants solution?

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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.