Thanks for the participation!
1863A - Channel was authored by Endagorion and prepared by irkstepanov
1863B - Split Sort was authored by Endagorion and prepared by ch_egor
1863C - MEX Repetition was authored by Endagorion and prepared by amethyst0
1863D - Two-Colored Dominoes was authored by Endagorion and prepared by AndreySergunin
1863E - Speedrun was authored by Endagorion and prepared by Golovanov399
1863F - Divide, XOR, and Conquer was authored by Endagorion and prepared by ch_egor
1863G - Swaps was authored by Endagorion and prepared by zemen
1863H - Goldberg Machine 3 was authored by Endagorion and prepared by Endagorion, irkstepanov
1863I - Redundant Routes was authored by Endagorion and prepared by Endagorion, irkstepanov
1863A - Channel
Solution
1863B - Split Sort
Solution
1863C - MEX Repetition
Solution
1863D - Two-Colored Dominoes
Solution
1863E - Speedrun
Solution
1863F - Divide, XOR, and Conquer
Solution
1863G - Swaps
Solution
1863H - Goldberg Machine 3
Solution
1863I - Redundant Routes
Solution
what is test 81 in test case 2 in D ?
probably ..UU LRDD ..UU LRDD
E is a really good problem!! Thanks for fast editorial.
Slowforces
can't understand editorial of b
take for example a permutation where 2 appears after 3 whereas to make the permutation sorted 2 needs to appear before 3. For this to happen we must choose 2 as our x and perform the operation this will reposition 3 after 2. Hence we do this for all x where x+1 lies before x in the given permutation.
The worst case for this will be O(n^2). Won't it give me TLE?
it can be done in O(n) using map or visited array or it can also be done as mentioned in this comment
thanks for the help and apologies for the late reply
It says that if the pair of values $$$(k, k+1)$$$ appears inverted in the input permutation, then you need to perform the operation with $$$x = k+1$$$ in order to get rid of that inversion. Now, just note that if you consider all these pairs and perform the operation when needed, starting from $$$k = 2$$$ until $$$ k = n$$$, the permutation will be ordered.
thanks for the help and apologies for the late reply
let's start from k = 1 and see if the (k + 1) position comes after the k position we stop when the condition fails and count it as a turn we chose x as the last item that we get, then we pick another k just the last item we didn't get from the previous turn, Each time we write a set of numbers in the correct order as much as we can, So the answer is the number of turns. To do that just count how many pos[i] > pos[i + 1] for all i from 1 to n — 1. It's exactly this problem : Collecting Numbers
thanks for the help and apologies for the late reply split sort and Collecting numbers can be done like this sort the array keeping their index start iterating from i = 2 if(index of i < index i — 1) ans++
it can further be optimised as number are 1 — n, we can just place the index of x to the index x in sorted array
thanks suggesting the Collecting Numbers as it made me understand the concept https://cses.fi/paste/17d0c105267da8d76a177b/
Video tutorial for problems A&B&C in english: https://youtu.be/X08zbEDtaI8
Thought would be useful to the community
really liked D and E. I hope there will be more such great contests!
me too
Video Editorial for problem A,B,C,D.
how is O(N^2) possible in F with the given constraints on N? also can you provide test case 3? 1863F - Divide, XOR, and Conquer
Finally, editorial written not in broken English
Can't understand E. explain
Let, firstly, solve simpler problem. Assume starting time is $$$0$$$ (meaning the first imaginary quest which is prerequisite of any other quest was done at day 0, hour 0). Maintain a $$$dp$$$ array, where $$$dp[v]$$$ is the day when the quest $$$v$$$ is completed. It's clear that if the quest has no prerequisite it's $$$dp$$$ value is zero. Otherwise, let $$$u_1,...,u_k$$$ be prerequisites of $$$v$$$, then $$$dp[v] = max(dp[u_i] + f(u_i))$$$ where $$$f(x) = 1$$$ if $$$h[x] > h[v]$$$ and $$$f(x) = 0$$$ otherwise. Answer to the problem is maximum value of $$$dp[v] * k + h[v]$$$ (Since we are counting starting time as $$$0$$$ and $$$v$$$'s quest is done after $$$dp[v]$$$ days on $$$h[v]$$$ hours). However, we need to choose optimal starting time and somehow maintain the answer. Notice that optimal starting time is some $$$h[i]$$$, where $$$i$$$'s quest has no prerequisite. Assume $$$v_1,...,v_k$$$ are such quests and WLOG assume $$$h[v_1] <= ... <= h[v_k]$$$. We will update starting time from $$$0$$$ to $$$h[v_1]$$$, from $$$h[v_1]$$$ to $$$h[v_2]$$$ and so on to $$$h[v_n]$$$. Let assume we are making transition from $$$h[v_i]$$$ to $$$h[v_{i+1}]$$$. So firstly we must update $$$dp[v_{i + 1}]$$$, then we mist update it's children. So we can simple use DFS. Also notice that every quest will be updated only once, so it should pass the time limit.
don t you update dp[vi] in the transition?
Yes, I do. Its value increases by 1.
We only going deeper from the current vertex only if dp[v] is increased by one (and this can happen only once). Correct me if I am wrong, please.
Indeed.
Would someone please help me understand why my submission for E (221172178) giving TLE. According to me, the time complexity of this code should be O(m+n*lgn), since I am traversing through each edge only once while doing DFS.
Your final for loop is O(N^2) since you call max_element
Ohh, got it. Thanks!
I was stuck finding mistake in recursive function, just ignored this. Thanks a lot :)
EFG are all excellent problems. Failed to solve F because I mistakenly thought that 1<=n<=1e5.
Why for problem E f(x, y) is defined only with y?
Has to be a typo. In the definition they meant to write z >= max(x, y).
Thanks for this nice round, and fast editorial!
Here is my advice about the problems:
Great problem A ! Simple statement, simple solution (that still requires some idea), simple implementation, not a "formula" problem, perfect!
Creating a good div2 B is very hard but I think that this one does a great job! It is also very educative as showing an upper bound/lower bound is quite standard so yeah, great problem
I enjoyed this problem a lot but maybe it is a bit too easy for its rank ? Simulating the process by hand with n=4 is enough to find the solution.
It is probably a bit too easy for its rank? The problem is quite cool though
Really really great problem! Bonus point for the story
Seems like a cool problem, I couldn't solve it but it is enjoyable to try to solve it
Also, could you please clarify a bit the second part of the editorial of F please ? Maybe I'm just bad at english but I don't understand what mask_start and mask_end correspond to
Thanks :)
For point $$$i$$$, if the xor of an interval $$$[i, r[$$$ contains a bit of $$$maskStart_i$$$, then it means it is obtainable, since at one point prior, an interval $$$[i, r'[$$$ with $$$r' > r$$$ had that bit for most significant bit of the xor. Same for $$$maskEnd_i$$$.
So you keep these $$$2N$$$ masks as you iterate over subarrays in length non-increasing to know which ones are obtainable.
By the way I love your profile picture, where is it from ?
Thanks, very clear!
You already know where it comes from
Azure Lane
Can u pls clarify how upper/lower bound is used in B.
C can also be solved using binary lifting. Overkill, but if you spot it quickly, you could just a use a template for insta solve Here is my solution
In problem E, can ternary search be used for finding the optimal starting point?
I thought on the same idea during the contest, but couldn't do it. The problem with the ternary search was that the function isn't strictly increasing/decreasing, meaning there is some value x, for which $$$f(x) = f(x + 1)$$$, but $$$f(x)$$$ isn't extremum of the function.
I think it's not just about $$$f(x) = f(x + 1)$$$, but that the function can also alternate going up and down wildly (or at least, that's what I saw when testing this locally).
You could be right. I just tested the given examples and noticed the problem I mentioned above. I didn’t dig deeper.
Hi all, it would really help if you can post some insights/hints for the problems of this contest on https://starlightps.org ! Here's a link to the problems: https://starlightps.org/problems/collection/cf-pinely-2/. This will help us get more data so users can have a platform to:
Check it out if you're interested. Thanks!
thanks for the exciting tasks, as for me the gap between D and E is too big
For problem E, I didn't understand the editorial, and most other solutions seemed to use some form of Dynamic Programming, which seems different from what I did.
I start by calculating the maximal end time when you start questing at the earliest possible time, which is easy to calculate in O(V + E) time using the topological ordering of the DAG. However, this might not be optimal: it can be better to defer some quests to day 2 so we can start later in day 1, without affecting the end time. So I consider all the starting times of quests that have no dependencies. The key is that I update the end times for other quests incrementally, for an overall O(V + E log V) solution.
Submission with a (too many) comments: 221200048
There's no need for that log, that's what I did as well. Your first step is dp, so I don't get why you're talking about others "using some form of DP".
mark me if I am wrong ? What I got from your code is that particular (ith) quest with (0 dependency) can either be done at (h[i] or h[i]+k) hours so after that you are checking effect of (h[i]+k) ending on other quest so , its complexity will be O((number of 0 dependency node)*(ElogV)) how its possible to get accepted , or It is like each quest can be updated one ,if it is then why it is updated once , please explain
I tried to explain that in the last two paragraphs of the comments at the top of the file. It's not immediately obvious, but for each vertex v, we increase end_time[v] at most once, by exactly K. That means it's actually just O(V + E log V) time overall, not O(V + VE log V) as it would otherwise be.
And tfg pointed out, correctly, that the priority queue is not needed, so instead of O(E log V) it could be something like O(E), but the really important part is that it's not O(VE), which would be much too slow to pass. The difference between O(E) and O(E log V) is relatively small.
Thank you so much. Easy to understand.
It is the greatest contest I have ever seen
How to solve D if you must colour all cells, not only the domino ones?
First I saw the $$$n\le10^4$$$ constraint so I went for an $$$O(n^2)$$$ solution. But then, I realized that Codeforces problems rarely have $$$O(n^2)$$$ problems with $$$n$$$ bigger than $$$5000$$$. So I gave up immediately and went for an $$$O(60^2\times n)$$$ solution, which is a bit smaller and could definitely pass the problem.
Here's my wrong idea on F: (maybe it's right, I don't know)
Let $$$s(l,r)=a_l\oplus a_{l+1}\oplus\dots\oplus a_r$$$.
First let's reverse the operations. Instead of changing subarray $$$[1,n]$$$ into $$$[i,i]$$$, we try to expand $$$[i,i]$$$ into $$$[1,n]$$$. For a subarray $$$[l,r]$$$, we need to find an adjacent subarray (either $$$[r+1,x]$$$ or $$$[x,l-1]$$$) which has a smaller $$$xor$$$ value than $$$s(l,r)$$$, and merge them.
Let's look at the maximum most significant bit of all $$$a_i$$$. Let $$$cnt$$$ be the number of $$$a_i$$$ s that have this bit. Let $$$b_1,b_2,\dots,b_{cnt}$$$ be all $$$i$$$ that $$$a_i$$$ has this bit.
If $$$cnt$$$ is odd, then only $$$b_1,b_3,\dots,b_{cnt}$$$ are valid.
If $$$cnt$$$ is even, then all $$$i\in[b_{2k-1}+1,b_{2k}-1]$$$ are invalid. We can merge all $$$a_{b_{2k-1}}\ \ ,a_{b_{2k-1}\ \ +1},\dots,a_{b_{2k}}$$$ into one number, which is $$$s(b_{2k-1},b_{2k})$$$. Then, the maximum most significant bit is gone and we go on to solve the problem for a smaller bit. What I still can't figure out is how to solve for $$$a_{b_i}$$$. Maybe it could be solved using Segment Tree.
Some people like gamegame solved it in something like you tried to do. https://mirror.codeforces.com/contest/1863/submission/221171705
Thanks! This code is even faster than the editorial. I will check it out.
Can you explain why we can merge in the part when $$$cnt$$$ is even?
I love F very much.Hope there will be more problems like this.
https://mirror.codeforces.com/contest/1863/submission/221150801
Can I ask? Why my 7th test got a negative number? I didn't see any "out range" in my variety (for example, when I'm finding the missing number, I'm using long long)
(n+1) * n will overflow because n is an int. Cast n to long long or declare it that way from the beginning
When you multiply
(n+1)andn, because they are bothintvalues, it overflows before stored into variablemissing. Just change one of them intolong longthen multiply.long long missing = (n + 1) * (n) / 2;should be changed tolong long missing = 1ll * (n + 1) * (n) / 2;orlong long missing = (long long)(n + 1) * (n) / 2;.I see, thank you both for helping me.
is there any other solutions to f？
Can someone explain F more clearly?
what is test 72 in test case 2 in D?
4 4
Can someone help me with P5? My idea was to perform a dfs to find pairs (s1,s2) of optimal start time and end time for each component of the directed graph. If d is the number of connected components in the graph, then we will have d such (s1,s2) pairs. Then, I sorted this vector of pairs and found the optimal time.
Issue is I am getting TLE on test case 18. I don't see which operation is being so expensive. Any help will be highly appreciated.
Source Code
What is test 72 in test case 2 of D
Getting wrong answer for that https://mirror.codeforces.com/contest/1863/submission/221170325
In problem E can anybody help me understand why every node's time is going to be updated at most once ??
If you start the process on the 2nd day instead of the first, every value will increase by 1. So, if you had started earlier (meaning on any time of the day 1), values couldn’t have been bigger. Hence, they can increase only once.
How difficult are the H and I questions? How come no one has worked them out during the contest... Including our dear Tourist, Radewoosh, JiangLY and so on...
I just want to ask what happens if the number in the array provided is not in 0 to n as it is obvious that it wil come in 0 to n+1 with leaving the last element but how can a person do that question because in c it is already given it is in 0 to n So what wil be the difficulty of the above with the present C?
If the original array could have duplicates or values outside of range
[0, n]the solution would be still pretty much the same. You can manually perform one operation on the original array, now all values are going to be MEX of some arrays of length $$$N$$$, so that guarantees that all values are now in range[0, n], moreover, after performing such an operation there can't be two duplicate values in the array. All that's left to do now is to decreasekby one and calculate the cyclic shift for k modulon + 1.Yes it's true but can you please explain how to implement this in O(n). Thanks for replying.
Well this is the approach I came up with during the contest, my submission: 221139985
Although I believe it has $$$O(nlogn)$$$ time complexity because I used a
set<int>to calculate the MEX values, also you might want to be a little bit more careful to handle the out of range and duplicate values correctlyOhh thankyou so much that's what my intention is your code is same like that
In problem C, let n=1,k=1,arr={3} then MEX would result " -2 according to code " but in question its states that mex cannot be negative. Please justify.
Elements in array can't be bigger than n.
Ok got it. Thanks woonder!
In the solution of problem F，should the condition be $$$s & mask_start_l > 0$$$ or $$$s & mask_start_r > 0$$$
Yes, a symbol ^ represents AND logical operation in mathematics.
Ohh,I forgot it. Thank you!
In the solution of problem F，should the condition be
s & mask\_start_l > 0 or s & mask\_start_r > 0？Endagorion, big thanks to you for enchanting problemset!
Can someone help with the proof/intuition of D? Why can we color the dominoes in any order? I thought that coloring the dominoes according to a row/column might affect the other rows/columns.
I tried to implement my solution in E problem but it was giving TLE on testcase 5. please can someone show the mistakes in my code.
my submission: link
Here I have tried to explain my logic:
1. sorted the given array of time at which quest will start and then mapped the indexes accordingly.
2. made an array ind to store indegree of every node of the graph.
3. then calculated the time needed if we start from each node with 0 indegree(as it can be started independently), using calc function.
x = no. of nodes with 0 indegree.
idx: contains the index of node with 0 indegree.
val: contains the time needed to complete the quest if we start from here (to complete all the quests that are dependent on the particular node).
4. used some prefix, suffix logic to get the final ans. (to decide at which point to start)
I didn't get most of the edi, but I think that I is much easier (and I upsolved it this way):
I've stopped reading after getting to the point that we will take whole classes of adjacent paths. So let's connect them and make a directed edge from class of shorter paths to a class of longer paths if they contradict with each other. There surely is a way to extend one of the shorter paths into one of the longer paths if this is the case. So we might as well only use edges from a class to a class of paths longer by one. Aaaaaand this graph turns out to be a tree, where each vertex has a weight (number of paths in this class) and we have to pick a subset such that no pair ancestor-descendant is picked, so easy dp.
The solution to 1863E says: So if we define $$$f(x,y)$$$ to be the smallest $$$z\ge y$$$… Is it a typo that the latter $$$y$$$ should be $$$x$$$?
Yes
For the F solution, why do we want that
s ^ mask_start > 0ors ^ mask_end > 0?(Also if my understanding is correct, are
mask_startandmask_endsuffix and prefix xors of the initial array? Or am I potentially misunderstanding this part?)Big BRAIN MOMENTTTT!!!!!!!!!
Can someone help me to solve problem E. I want to do it with topological sort, and in order to solve it, I need to solve one subproblem first. How can I get the smallest lexicographic configuration of topological sort. For example, if there are two correct toposort configurations [4,1,2,3] and [1,4,2,3], how can I get the second one? Thanks in advance
Is this round unrated now?
https://mirror.codeforces.com/contest/1863/submission/243936605
for d problem why this solution is giving WA
what is the problem in logic ?
Thanks for the editorial !! It helped me to upsolve.
b] test: [6,4,3,5,2,1] x=5, [4,3,2,1,5,6] x=3, [2,1,3,4,5,6] x=2, [1,2,3,4,5,6] this does the job in 3 operations why is the answer given as 4?
I did D a bit more constructively,initially assigned all L,U as W and all R,D as B,then iterated the grid row-by-row,flipping vertical dominoes if W>B and then iterated column by column,flipping horizontal domnoes if w>b.
why does this test case gives different answers for jiangly's and tourist's code for problem E