Note: I can't figure out how to place the tutorials inside spoilers. If someone is familiar with how CF spoilers work and can help I would really appreciate it. For now, be warned that the tutorials are visible by default (but everything else isn't)
UPD: I figured out how to use spoilers! Also added implementations for all problems.
Thanks for participating in our contest!
1509A - Average Height
Author: Kuroni
First solve: Nutella3001 at 00:01:02
HintHow can you write the condition that $$$\frac{a_u + a_v}{2}$$$ is an integer in a more useful way? Think of the parities.
Comments from the authors Implementation
1509B - TMT Document
Author: Ari
First solve: blue at 00:04:51
HintYou can think of the partition as associating to each $$$M$$$ character a $$$T$$$ to its left and a $$$T$$$ to its right. What's the best way to perform this assignment?
AnswerAssign greedily from left to right.
Implementation
1509C - The Sports Festival
Author: Ari
First solve: Dukkha at 00:05:32
Hint 1What is the discrepancy of the last stage? How can we make it smaller in previous stages?
AnswerThe discrepancy of the last stage is always the difference between the largest and the smallest $$$a_i$$$. We can make it smaller in the previous stages by placing the smallest or the largest $$$a_i$$$ at the end.
Comments from the authorsThis problem was originally going to appear in Codeforces Round 668 (Div. 2), but it was removed one day before the contest for balance reasons :P
Implementation
1508A - Binary Literature
Author: Ari
First solve (Div. 2): traxex2 at 00:22:48
First solve (Div. 1): tourist at 00:05:04
Hint 1Consider two of the strings. We can obviously achieve our goal using at most $$$4n$$$ characters. How can we save some of them?
AnswerTake advantage of any common subsequence in our two strings by including the characters in it only once.
Hint 2Find a long common subsequence that has a simple structure. You'll need to involve the third string as well.
Hint 3Either $$$00\dots 0$$$ or $$$11\dots 1$$$ is a subsequence of each string.
Comments from the authorsThis problem was originally suggested as a 2B. It turned out to be too hard and was switched to 2C, before being further switched to 1A because it was still too hard. Some testers still believed this problem to be even harder, but we ended up deciding to have it as 1A with a larger score than usual.
Apologies to the testers who had to solve this as if it was the second easiest problem in the contest :^)
Implementation
1508B - Almost Sorted
Author: Both of us!
First solve (Div. 2): shenmadongdong.qaq at 00:29:52
First solve (Div. 1): tourist at 00:08:19
Hint 1What is the general structure of an almost sorted permutation?
AnswerStart with the identity permutation, choose some disjoint subarrays, and reverse each of them.
Hint 2How many almost sorted permutations of length $$$n$$$ exist? In other words, how many ways are there to reverse subarrays?
Hint 3Two options — either solve recursively in a greedy fashion or find a smart bijection.
Comments from the authorsThis problem's creation has a funny story. Back when we were coming up with problems for Round 668, I (Ari) came up the following relatively simple and standard problem and shared it.
The next day, Kuroni saw the problem, but misread it and ended up solving the version that made it into this contest, which we think is a lot cooler!
One more fun fact for your consideration: This problem's name in Polygon is "sorrow".
Implementation
1508C - Complete the MST
Author: Kuroni
First solve (Div. 2): deepspacewaifu at 01:42:36
First solve (Div. 1): maroonrk at 00:33:17
Hint 1How can we solve this problem without the restriction that the xor of all edge weights is $$$0$$$?
AnswerJust assign $$$0$$$ to every unassigned edge :P
Hint 2When does the solution to the unrestricted problem fail for the real problem?
AnswerWhen any minimum spanning tree (of the graph with every unassigned edge having weight $$$0$$$) contains every unassigned edge, and the xor sum of all the edge weights is not $$$0$$$.
Hint 3Leave the xor sum of the weights of the unassigned edges in the spanning tree fixed. How do we minimize their sum?
AnswerAssign the entire xor sum to a single edge, and assign weight $$$0$$$ to every other edge.
Hint 4Exactly one unassigned edge ends up with a non-zero weight. If we don't use all unassigned edges, which others can we use?
AnswerAny edge that isn't part of the MST when we consider unassigned edges to have weight $$$0$$$, and that doesn't form a cycle with pre-assigned edges with smaller weights.
Comments from the authorsIf the unassigned edges in the graph don't form a forest, then the answer is simply the weight of the MST where all the unassigned edges have weight $$$0$$$. Thus the interesting tests in this problem require these edges to form a forest, which means $$$m \ge \frac{n(n - 1)}{2} - (n - 1)$$$. This automatically limits the maximum value of $$$n$$$ to approximately $$$2\sqrt{m}$$$. Concretely, $$$n \le 633$$$ for all interesting tests in this problem. You can also use this to obtain a solution that runs in $$$O(m \sqrt{m})$$$, which a tester found, and which passes if implemented reasonably.
Implementation
1508D - Swap Pass
Author: Ari
First solve: ksun48 at 00:57:13
Hint 1It is always possible to find the sequence.
Hint 2There's a simple algorithm that fixes a point and repeatedly moves its current label to the correct position. When does it work?
AnswerWhen the permutation of the labels is a single cycle.
Hint 3Any permutation can be split into one or more cycles. What can we do to these cycles?
AnswerMerge them, by swapping two elements in different cycles.
Hint 4We would like to merge all cycles of the permutation by swapping elements in different cycles and then repeatedly move each label from a certain point to its correct location. How can we do this without intersections?
AnswerFix a point beforehand to perform the final step, and sort angularly with respect to this point.
Comments from the authorsThis problem was originally proposed with the points always being the vertices of a convex polygon. This allows us to do a slightly different solution where we first merge the cycles and choose the pivot afterwards by choosing a point unaffected by the previous swaps.
The reason for having $$$n = 2000$$$ in this problem rather than a larger $$$n$$$ like $$$10^5$$$ is because of the validator: it is essential to not have three collinear points in this problem, and I don't know how to check this for large $$$n$$$. The small $$$n$$$ also makes the checker much easier to write, though it's possible (albeit tricky) to write a checker that works in $$$O(n \log n)$$$.
Regarding the number of operations used: The solution described in the editorial uses approximately $$$\frac{3}{2}n$$$ operations in the worst case when the permutation consists of cycles of size $$$2$$$. The minimum number of operations is lower bounded by $$$n - 1$$$ by combinatorics reasons when the permutation is a single cycle. Moreover, by Euler's formula, we have an upper bound of $$$3n - 6$$$ operations for any valid sequence, which goes down to $$$2n - 3$$$ when the points are the vertices of a convex polygon. I don't know of a solution that uses $$$cn$$$ operations for some $$$c \lt 3/2$$$, nor do I know of a general test case where it can be proven that at least $$$cn$$$ operations are needed for some $$$c \gt 1$$$, so I'd be really interested in seeing either.
Implementation
1508E - Tree Calendar
Author: Kuroni
First solve: ecnerwala at 01:02:26
Hint 1During the process, we will repeatedly push the same label down until we no longer can. What happens at this point?
AnswerThe labels that have been fully pushed down will look like a post-order of the tree, while the other labels will look like a pre-order of the tree.
Hint 2Look at the children of a particular vertex. What can we say about the ones that are fully pushed down in relation to the ones that aren't?
AnswerEvery fully pushed down label is smaller than every other label.
Hint 3For each node, the order of the labels of its children stays fixed.
Hint 4How can we use the previous observations to identify the state of the process?
AnswerWe can reconstruct the DFS order and the fully pushed down labels. Then check that the current pushing step of the process is valid.
Comments from the authorsThis problem was inspired by a wrong solution to 1477D - Nezzar and Hidden Permutations, but it seems that knowing that problem beforehand doesn't help at all to solve this one.
Implementation
1508F - Optimal Encoding
Author: Kuroni
First solve: ecnerwala at 01:52:02 (The only contestant who solved this problem!)
Hint 1Start by solving the problem for $$$q$$$-encodings only.
Hint 2We can get an encoding by including every possible edge. Which of them can we exclude?
AnswerWe need to keep an edge $$$u \to v$$$ if and only if no other path from $$$u$$$ to $$$v$$$ exists.
Hint 3What does the previous observation look like from the perspective of a single vertex?
AnswerEach vertex has at most two outgoing edges, one on each side, and we can easily characterize when one of them is redundant.
Hint 4We need to solve the full version now. For a vertex $$$u$$$, how do the endpoints of its outgoing edges change when we add a new interval?
AnswerThe endpoints of the right edges increase monotonically, while the endpoints of the left edges decrease monotonically.
Hint 5How can we use the previous observation to characterize edges becoming redundant more concretely?
AnswerFor each right edge, we can find a particular left edge, such that the right edge becomes redundant once the left edge appears. This gives us an interval of times for each edge during which it is relevant.
Hint 6Use Mo's algorithm on the input intervals to find the relevant edges.
Comments from the authorsHuge shoutouts to tfg who came up with one of the key steps of the solution! Including this problem probably would have not been possible without him. ❤️
Implementation
Finally, here's some funny moments that happened while we were working on the round :)
Longest editorial I ever had the chance to read. Anyways thanks, it's awesome <3
Sorry, as we stated the spoilers were not working to our favor :(
It's pretty well documented editorial, thank you once again!!
For Div 2 D, can somebody find a case where it fails? submission, I think on one case it doesn't print any string because my answer gets over n*3.
If you find any mistake or corner case please reply me, my solution fails in the same testcase with the same error (In the test 2 case 43)
Thanks!
I found one: 1 3 001111 110110 000000
https://codeforces.me/contest/1509/submission/113292585 i did according to the tutorial but my submission gives WA on test 9. Where am I going wrong? please someone help
Your mistake, is a common mistake, since a I had the same mistake use a variable ans and print it just once, your mistake is in the fisrt if, you forgget the endl before the return.
skipping this you code have a good implementation good look bro!
PSD: I submmit your code for be sure that im right and sorry for my bad english
gg
i think problem E div1 can be done with HLD & treap by reversing the operations :thinking:
if any one solved the problem with the similar solution please share it : )
This contest was amazing and specially it's editorial after all Thanks for preparing such contests and we're waiting for more contests from you! :D
I don't understand why my B solution is wrong, pls help 113225551
you go through forward and taking the count of Ts and Ms do the same thing for backward it can't be less Ts from Ms from froward and from backward
My solution to F runs in $$$O(n^2)$$$, and is quite simple. Here's my simple condition for an edge being in the graph:
For any vertex $$$v$$$, there are 4 candidates for edges involving this vertex: consider the intervals containing $$$v$$$ which extend the furthest left and the furthest right; let those bounds be $$$l_v$$$ and $$$r_v$$$. Then, $$$v$$$ can have edges to its predecessor in $$$[l_v, v]$$$, its successor in $$$[l_v, v]$$$, its predecessor in $$$[v, r_v]$$$, and its successor in $$$[v, r_v]$$$. Furthermore, an edge exists iff it is a valid candidate for both endpoints.
Then, we can just maintain these candidates and the counts in $$$O(n^2)$$$: starting from the initial state, $$$l_v$$$ decrements and $$$r_v$$$ increments at most $$$O(n^2)$$$ times in total. The code is very short, and runs in less than 1 second.
I'm actually surprised about your solution; I had an $$$O(nq)$$$ solution but I didn't know that $$$O(n^2)$$$ exists (probably the reason is because I abruptly changed the constraint from $$$n = q = 50000$$$ to the current one like 1 day before the round).
Anyway, this solution is very clean and also interesting, thanks.
Why this solution for Div2 C gets TLE despite that fact that it's $$$O(n^2)$$$ ? It is because it should be written iteratively ?
Array bound
Kuroni Yup, AC. Thanks a lot!
Is there any greedy solution for Div2C? It was tagged
greedyin the problemset, hence wondering :)Maybe the fact that the minimum and maximum should be at the end is a greedy intuition?
sorting step; a[i] is either the minimum or the maximum of the first i elements.
I dont think my div1A/div2D is supposed to pass. Can someone hack ?
Done, random generator found a test that fails.
Here is also a smaller test case (n=6), there is no example with smaller n. Maybe it helps:
How you are generating these cases? (some online website or you have your own generator)
For the original test I just generated a bunch of random inputs and tried to see if the solution works (using my own program, basically just a while loop that generates a random input (50% chance for 1 and 50% for 0 at each position) and then runs a simplified version of his code to see if it finds an answer).
For finding the n=6 case, I went over all the possible inputs for n=1...6 and tried each one. There arent too many possible inputs for n=1,2,3,4,5 and for n=6 it found one quite quickly.
Since so many people were asking for problem C (div2), I decided to make a video tutorial for it.
http://youtube.com/watch?v=7CPgT3gYPoc
Hope you like it :)
i failed to recognise these types of dp problems during short contests.so i know i need to practise more of these kinds of problem .it will be a great help if you people suggest me some similar kind of problems .
Search DP Tagged problems on CF and Leetcode.
Some other problems:
Longest Palindromic Substring (link)
Longest Palindromic Subsequence (link)
Matrix chain multiplication (similar problem to div2C)
Burst the balloons (link)
thanks
Auto comment: topic has been updated by Ari (previous revision, new revision, compare).
I cannot understand div2C, help me!!. we have to minimize discrepancies so why are we adding the element having greatest discrepancies. like An-A1???
I will try to explain my approach. First thing to notice is that discrepancy for i = n-1 ( 0- indexing ) will be fixed (max element — min element). Now we put either the max element or the min element at the (n-1)th position that is the only possible way to change the discrepancy for (n-2)th index. Now choosing greedily won't work because we won't know whether our current best move would be a better decision in future also. This is very obvious that we will require to check all possible combinations hence dp is used to optimize the same. So let's talk about,
1. dp States : sort the given array, let's say 'L' = any index to left and 'R' denotes any index to right( greater than 'L')- this would mean we have the option to choose between Lth element or Rth element for some index 'i'.
2. Transition function : this is simple as you can choose between L or R so dp[L][R] = min(go(L+1, R) , go(L, R-1))
3. Base case : L should be less than R
int go(int l, int r){
} void solve(){ int n; cin>>n;
}
My submission : 113239735
Problem C : What exactly do those transitions represent ? and if anyone has some intuitive or any other way to deduce the state of that dp ?
I explained it in my youtube video
But I'll try to give a brief description of my solution (slightly different from editorial)
Basically as mentioned in the editorial we start from the back because we have complete knowledge of d[n]
d[n]= maximum element in a — minimum element in a (Coz it is for the whole array)
Now to minimize d[n-1] we have to remove maximum element or minimum element coz otherwise d[n-1]=d[n]
So after sorting at every stage we have two options either we remove from right side or left side. This gives us a feel for a dp approach because the same state of array can be reached by taking different paths(overlapping subproblems)
So we define dp[i][j] as we have removed elements from left (minimum) i times and elements from the right (maximum) j times. We can obviously deduce the maximum and minimum in the current array as jth maximum and ith minimum in original array
This gives us the transition cost -> jth maximum element — ith minimum element As we can reach state (i,j) from (i-1,j) and (i,j-1)
So basically dp[i][j]=min(dp[i-1][j],dp[i][j-1]) + cost (Very much like grid DP ) The answer is minimum sum we can get after removing exactly n-1 elements
Beautiful it is.
There is an explanation for the author's Dp State that I liked and suhail.loya described in a youtube comment.
The author's solution says that in the optimal solution, suppose after reordering the elements it is
a[p1],a[p2],a[p3],..a[pn]wherep1,p2,..,pnis a permutation of 1 to n, every prefix of this reordered optimal sequence will be a subarray of the sorted sequence.This makes sense because it is always optimal to put the maximum or minimum in the current prefix in the last step. This is basically same as my solution in which I remove elements only from the "ends" of the sorted array so the result will always be a subarray.
So the author's solution starts with a subarray of size 1 for which the answer is 0. Now to expand this subarray either you can
add one element to the left, oradd one element to the rightso at every state we have two options just like my solution(where I remove one element from left or right).State Description:dp[l][r] is the minimum cost you can create such that the elements of the current array area[l],a[l + 1],...a[r]in the sorted arraya.Transitions :You can reach state (l,r) from (l+1,r) [ expanding to left] or (l,r-1) [expanding to the right]. Cost of expanding will be maximum-minimum in the subarraya[l]....a[r]which isa[r]-a[l]since it is sorted.So :
dp[l][r] = a[r] - a[l] + min(dp[l + 1][r], dp[l][r - 1])Answer : = dp[1][n].Glad you liked it :)
jalotra Can you please explain why it will always be true?
Example: s[] = 29 30 67 68 82
optimal[] = 67 68 82 30 29, optimal d = 121.
See that for each prefix i from 0 to len(s) — 1, the optimal sequence is some contiguous subarray of the sorted sequence.
Proof :
S : s[k] => d[1] = 0 here.Now I have to add one element at the back of it.
2a) S : s[k] => Choose either
s[k + 1]s[k - 1], because choosing some other element will make d[2] higher.3a) S : s[k] s[k + 1] => Choose either
s[k - 1]ors[k + 2].3b) S : s[k] s[k — 1] => Choose either
s[k + 1]ors[k - 2].suhail.loya Is this correct?
jalotra consider prefix for i = 3 in optimal solution (67 68 82 30) .How is this a contiguous subarray of s?
The key observation is at every stage while expanding from the current sequence, you want to add an element which is either the minimum of the new sequence or maximum of the new sequence. So you want to either take one step left or one step right in the sorted sequence.
What I meant by the statement "every prefix of this reordered optimal sequence will be a subarray of the sorted sequence." that every prefix will contain elements which are in a continguous subarray of the sorted sequence
So prefix for i=3 (67 68 82 30) although is not a subarray of s[] in exact order but it contains only the elements in the contiguous subarray of s[] from index 1 to 4 (30 67 68 82)
This result is more obvious in the solution I describe in this comment
suhail.loya Thanks for helping me out :).I was confused at the subarray part but now it is clear. Yeah, the exact order thing was creating the problem for me.
So basically we can imagine that we are adding elements to an array let's call it A we know that the last element of that array is either the maximum or the minimum (because otherwise it will make the cost of the function d a lot bigger hence d(n) = max(A) — min(A)) and we work backwards by asking which is the last element max(A) or min(A) and after that we ask the same question for the next biggest and smallest elements left in the original array and here we observe that it must be dp
In the last line i think you meant dp[i][j] = min(dp[i + 1][j], dp[i][j — 1]) + Cost. Nice explanation though.
No, according to my dp states it should be min(dp[i-1][j],dp[i][j-1])
My states are dp[i][j] -> min cost we can get after removing i elements from minimum side and j elements from maximum side. So to reach (i,j) you can remove one element from maximum side in (i,j-1) or one element from minimum side in (i-1,j)
Code
The second solution for Div1A/Div2D is beautiful.
can anyone explain second solution for Div2D im still unable to understand the math over there :/
Let's say we have these strings, and we currently our pointer is pointed to bold ones in all three of them. (say p1, p2, p3)
0 10101
1 10011
1 00100
Since we have three pointers pointed to three different strings consists only of 0's and 1's, then atleast two of them must point to either 0 or 1.(In this case, p2 and p3 to 1)
Now after adding the "1" to our answer, we increment pointer p2 and p3.
0 1 0101
1 1 0011
1 0 0100
Now p1 and p3 is pointed to "0". So in next step, we increment p1 and p3 by 1.
0 1 0101
1 1 0011
1 0 0100
We repeat this process until one of them is completely exhausted.
0101 01
1100 11 (exhausted)
1001 00
Our ans in this case comes to be
1010011 (len = 7)
Now in simple terms, len + (one of the remaining in p1 (01) and p3 (00) ) is always less than or equal to 9 (3n).
Let's suppose our ans has k(7 here) characters, and thus the pointers have advanced by at least 2k(14 here), since at each step atleast two of them is advanced. We have exhausted the characters of s2, so we have advanced p2 by 2n, and the other two pointers have advanced 2k−2n (8 here), and thus one of them has advanced by at least k−n (4 here). Now just add the remaining characters of this string to t. There are at most 2n−(k−n)=3n−k of them, so in the end t has at most 3n characters.
Thanks alot for your detailed explanation , now its clear
Nice Editorial tho
(https://codeforces.me/contest/1509/submission/113217480)
Can anyone please help me where I am getting wrong?
I have considered two cases
2 The number of T should be even and the number of M should be half of the number of T
Am I missing anything?
TTTMMT
Can anyone prove problem C can or cannot be solved with greedy? I use greedy and cannot pass example 3.
Can anyone explain E Solution? Not very clear from tutorial
In the Problem div2B, shouldn't this statement: "A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero) characters" be corrected as: "A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero) characters, without changing the order of the elements"? I wasted some time thinking if the order is important or not -_-
Why stop there?
"... without changing the order of the elements, without inserting new characters, without turning the characters upside down,..." The list can go on.
editorial is awesome
I don't understand why my solution for Div1A is wrong. can somebody please help me check? 113203126. My method was just to try each pair of strings, and for every character of the strings, if they were different, my answer would add each of the characters once, and if they are the same, it would add just that one character. This generates three different solutions, and we take the shortest one. It should guarantee that the shortest string would have a length shorter than 3n. Please help, thanks
Sometimes the length of your ans string is less than 3*n.
Test case :
n=2
0101
1010
1011
I fixed that but still, it gave WA. Then I found this case out. It is possible to make n+1 mismatches(positions in which the bits differ) in between the pairs of the strings. Thus the final string would be of length 3*n+1.
4
00011111
11100111
01010000
What about,
000011110000111100000000000000001111BTW, Same mistake ):
oh wow. thank you guys. I can't believe I made this logic error
Speedforces :))
Is there anyway to bound the maximum of minimum hamming distances of three distinct binary strings? I'd appreciate if someone can give out a proof or explain their intuition behind this. Thanks.
In TMT question I used counting. First incrementing count when T is found and when M is found then decrementing. Also another variable for counting m. If at anytime count becomes negative , solution is impossible. At the end I checked for if count of T == 2 * count of M. Can anyone help me why this solution was not working ?
Check your solution on: $$$TTTMMT$$$
Hi, can somebody tell me I got WA on test2(C++) in B? Code: 113309060. Thanks [Edit]: The accepted solution in Python: 113304387
AC solution c++ — 113310825 compare to find your mistake (this is your code)
Ari sorry if i'm wrong, but in my opinion 2D is much simpler than 2C. In D, the solution comes to mind immediately, and in 2C, vice versa.
You are not wrong, but many people will disagree with you because we have tested and testers rated 2D harder than 2C :) Heck, at first we even proposed 2D as 2B since we had the same opinion as yours (you can check our comments on the problem).
Please suggest some problems like div 2 C (matrix chain multiplication). Thanks in advance.
Great set, even better editorial! Awaiting more rounds from you!
Ari, Please share with us what mistake were you doing in the first place that caused spoiler tags to overflow? Also, how did you rectify it?
In Problem C of div 2 could someone please explain and give a testcase why this approach fails ??? I did this and got WA on testcase 5 .
Keeping the most frequent elements in the front and if frequency of two elements are same then keep the smaller among them in the front.
your approach fails on test case 1 3 3 3 9 9. According to you answer should be 3 3 3 9 9 1, which gives a sum of d's = 20. But there exists another optimal solution 3 3 3 1 9 9 which gives a sum of d's = 18. So, check your solution on this test case.
can somebody please tell me why i am getting tle in case 18 in 3 question if i initialize dp with 0 and ac when initiallizing with -1?
please tell me when to initialize with -1 and when with 0
For this submission of div2-D https://codeforces.me/contest/1509/submission/113251552
can someone provide a small enough test case. I was able to make a test case using random generator but it was large and not useful to find mistake.And i tried to find one myself but failed to do so. So a test case or a logical prove to show that the solution is wrong would be very helpful :) .
4
10111100
00111101
00000000
thanks, also you found it so quickly, i was also trying to make a similar kind of case but failed :(
Also string 1 is just reverse of string 2 XD
It's pretty easy to find it:
Oh ok , I actually tried generating some random cases but didn't got any small case so i thought it was not possible for small cases.Now i feel estupid XD.
in Div2E, how to DFS on the unassigned edges ? In general, the number of unassigned edges could be up to 1e10 so trivial DFS will cause TLE
Refer to 920E - Connected Components?
Thank you !!
I solved Div2C using ternary search. Any idea for the proof. 113242501
Update: hacked
Let me highlight that d1D is really interesting to solve. Thanks for such a great task!
(btw, I failed to spot that d1E was indeed an attempt to 1477D - Nezzar and Hidden Permutations xD)
I remember when I came up with this idea to solve your problem I was soo excited, then I saw it was wrong x(
Can anyone give me a test case or tell me what's wrong with my solution in div.2 D
My approach was to try every possible 2 strings and greedily make a resulting string such that it contains both strings and check if its size is less than 3*n.
Submission link getting wrong answer on test 843 of test-set#6
can anyone tell why my submission getting wa in test case 3 113414122
5
0000000000
0000111111
1110101010
How to solve Div2E/Div1B recursively? or how to find the length of the first block?
Let's suppose there are n elements. Then, if you place a 1 at the front, then there will be n-1 positions to fill; for 2, n-2; similarly for 3, n-3 and so on. Eg. if you put 3 as the first element, this is how the array will look like.
3, 2, 1, ....n-3 elements
Now, if you have n elements, then there are 2 ^ n-1 almost sorted permutations. So, if you put 3 at front, then the minimum ranking of an almost sorted permutation that starts with 3 will be 2^n-1 + 2^n-2 (because permutations starting with 1 and 2 will precede 3). Eg. 1, ...n elements (total: 2^n-1) 2, 1, ...n-2 elements (total: 2^n-2) 3, 2, 1, ... n-3 elements (total: 2^n-3).
Thus if the k is between 2^n-3 (inclusive) and 2^n-4 (exclusive), then the permutation definitely starts with 3, and now you need to find rest of the elements of the permutation in this way recursively. Hope this clears it up.
Btw, did you understand how the second solution works?
Hey thanks for your reply! and yes I do understand how the second solution works.
For div1 F,in Tutorial:
However, there will be cases when u→ur is actually not needed (I will call this phenomenon being hidden). What is the condition for u→ur to be hidden? That's when there's a path from u to ur with length ≥2! Suppose this path is in the format u→⋯→t→ur. We can prove that t<u: if t>u then that implies at>au but at<aur, which means the right edge of u is u→t instead. Because t<u, we can take the range [l,r] such that l≤u≤r, l is as small as possible, and check if there exists an index t∈[l,u] such that au<at<aw. That concludes the solution for finding the optimal encoding for q-permutations.
Here,I think we should check if there exist an index t∈[l,ur] instead of [l,u] such that au<at<aw. Where are I wrong?
You are not wrong, it's just that we have proven that if there is such t then it cannot lie between u and ur, so we only need to query in [l, u].
I don't think you have answered my question correctly.The defination of $$$l$$$ should be different.
In my opinion,$$$l=\min_{i,[u,ur]\in[L_i,R_i]} L_i$$$
In the tutorial,$$$l=\min_{i,u\in[L_i,R_i]} L_i$$$
Ah yeah I see that's true, typo on my part. I will update the editorial.
Edit: similar typo on second part of editorial as well :(
Can't think of the problematic case in div1D, can anyone provide an explicit example?
It is really a ****ing enjoyment to read your code for F(div2)...orz %%%%
Hi, I have tried to solve problem D and pick the smallest y, smallest x point which should definitely be on the convex hull. However, it still passed the tests without encountering the case above.
Are the tests simply weak or is that case really impossible to encounter? Actually, I also cannot think of how that case should happen there should be no segment that can intersect with a border segment. Is my understanding wrong?
Right below that, listed as one of the workarounds: "Always choose the bottom-most and left-most point as a pivot. This makes this potentially troublesome segment predictable, and also allows us to slightly simplify the angular sorting code." That's exactly what you did.
A segment can intersect with a border segment if, for example, you have a square ABCD, you choose A as pivot and your sort by angle puts B and D next to each other(for example, by sorting like C(0°),B(45°),D(315°)).
But in this case, between B and D still lies A, so BD is not a border segment (it's AB and AD the border segments). We can connect B, C and D by swapping B and C, and/or C and D only and then we are certain that all of them belong to 1 circle. Is there a case where we need to connect B and D directly?
A is the pivot, so BC, CD and BD are the border segments.
Ah understood, you exclude A. In my case, I consider A part of the polygon even after using it as a pivot so the troublesome border segment never appears. :) thanks.
I badly wanted to see a greedy solution for problem C. I spent so much time thinking greedily about it ;-;. Amazing problem anyway!
Almost Sorted is the coolest sorting problem I've ever seen, nice explanation
Can anyone pls give any counter example for this logic. This is the code.
div2 C was nice