Happy (late) new year Codeforces community!
We are excited to invite you to TOKI Regular Open Contest (TROC) #18!
Key details:
- Contest links: TLX (combined divisions)
- Time: 17th January 2021, 13:05 UTC
- Writer: steven.novaryo yz_
- Duration: 2 hours
- Problems: 7
Scoring distribution: 100 — 250 — 300 — 350 — 450 — 600 — 650
We would like to thank:
- prabowo for
admitting to be a masochistthe amazing coordination of the round. - hocky for
showing his very long tonguehelping 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
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!
TROC 18+
Have you finally opened for business?
Friendly bump! The contest will start in 40 minutes, good luck and have fun! :D
I wish the word minimum was in bold in problem C :(. I guess that serves me right for trying too hard to speedsolve.
Can anyone tell me why this didn't work for E?
Code
UPD: Fixed. Thanks Lain _______
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.
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.
Is it possible to see other participants solution?
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.
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.
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 everya -> b(or equivalentlyb <- a),acomes beforebin our permutation?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.
The editorial describes an $$$O(N^3)$$$ approach. What is the $$$O(N^2)$$$ approach?
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.
Auto comment: topic has been updated by yz_ (previous revision, new revision, compare).
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)$$$.
Observe 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<name<=2^{29}-1$$$ to get the exact same problem with a smaller range of value for this rabbit. This range of values can then be returned to normal (starting from 0) by pretending there is an additional value $$$2^{29}-1$$$. So you must change the value of $$$X$$$ to $$$X xor 2^{29}-1$$$ and the value of $$$A$$$ to $$$2^{29}-2-A$$$. This guarantees that you turn off a single bit of a single value of $$$A$$$. Once you turn off all $$$A$$$'s 29th bit, the problem becomes a 28 bit variation. Repeat this until the problem is trivial (1 bit). It's guaranteed that you don't need to turn off more than $$$28N$$$ values.
In order to perform this "bit turning off", you need to know the product of all other values of $$$A+1$$$. You can maintain the product of all values of $$$A+1$$$ and multiply it by the inverse of the $$$A+1$$$ you're about to turn off. Calculating this inverse is done in $$$O(\log MAX A)$$$, so this method will take $$$O(n \log^2 MAXA)$$$. If you don't want to deal with inverses, you can use a fenwick tree or segment tree to select which values you want multiplied and make the complexity $$$O(n \log n \log MAX A)$$$. You can optimise this once again by looking at all the numbers with this bit on by multiplying all the numbers with this bit off. Store a suffix product of the numbers of on bits. As you iterate through the numbers, reducing them, calculate the prefix product of the new numbers. The final product for each integer can be found by multiplying three numbers: the product of off bit numbers, the prefix product, and the suffix product (you can merge the first two).
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.