### Zap's blog

By Zap, history, 7 weeks ago,

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:

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

 » 7 weeks ago, # |   +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!
 » 7 weeks ago, # |   +33 TROC 18+
 » 6 weeks ago, # |   +41 be menew troc post"we encourage you to read all problems! :)"reads all problemsanswers nonethink about lifelife returns wa verdictsleep
 » 6 weeks ago, # |   +36 Have you finally opened for business?
 » 6 weeks ago, # |   +21 Friendly bump! The contest will start in 40 minutes, good luck and have fun! :D
 » 6 weeks ago, # |   -8 I wish the word minimum was in bold in problem C :(. I guess that serves me right for trying too hard to speedsolve.
 » 6 weeks ago, # | ← Rev. 2 →   +3 Can anyone tell me why this didn't work for E? CodeUPD: Fixed. Thanks Lain _______
•  » » 6 weeks ago, # ^ |   +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.
•  » » 6 weeks ago, # ^ |   +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.
 » 6 weeks ago, # |   +3 Is it possible to see other participants solution?
 » 6 weeks ago, # | ← 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.
•  » » 6 weeks ago, # ^ |   +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.
 » 6 weeks ago, # |   +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?
•  » » 6 weeks ago, # ^ | ← 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.
•  » » 6 weeks ago, # ^ |   0 The editorial describes an $O(N^3)$ approach. What is the $O(N^2)$ approach?
•  » » » 6 weeks ago, # ^ |   +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.
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by Zap (previous revision, new revision, compare).
 » 6 weeks ago, # |   +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)$. SpoilerObserve that if a value of $A$ had been equal to $2^{29}-1$ (say, $A_1$), the names of all other rabbits can be set to anything and this rabbit will always be able to set the xor value to $X$. The answer would then be the product of $A_i+1$ for all i other than 1. If there had been no such value of $A$, we can take a value of $A$ with the 29th bit on (let's say, $A_1$ =2e8). We can subtract the number of solutions where the name of the first rabbit is $0<=name<=2^{29}-1$ by the number of solutions with \$A