### maomao90's blog

By maomao90, 2 years ago,

Hope that everyone enjoyed the round. Feel free to ask questions in the comments if you do not understand any part of the editorial

Hints
Tutorial
Solution

1672B - I love AAAB
Author: errorgorn

Hints
Tutorial
Solution
Hints
Tutorial
Solution
Hints
Tutorial 1
Tutorial 2
Solution 1
Solution 2
Hints
Tutorial
Solution
Hints
Tutorial
Solution for F1
Solution for F2
Hints
Tutorial
Solution
Hints
Tutorial
Solution
Hints
Tutorial
Solution
• +135

| Write comment?
 » 2 years ago, # |   +3 Auto comment: topic has been updated by maomao90 (previous revision, new revision, compare).
 » 2 years ago, # |   +38 Testdata for E was somewhat a little weak, I passed with parrel binary search with some optimizations. In the actual testdata it took no more than $500$ queries to find the answer.Can anyone hack me?
•  » » 23 months ago, # ^ |   0 Try this: 6 1990 1997 1992 1994 1995 1989 In fact, there is a $20\%$ probability that your solution will use more than $n+30$ queries, when $n=6$ and $l_i=2001-i-d_i$, where $d_i$ is randomly chosen in $[0,10]$.P.S. I didn't do enough experiments so that maybe the probability is not exact at all.
 » 2 years ago, # |   -34 Me Mister Bebra!
 » 2 years ago, # |   0 My solution for D failed pretest 3. What I did is I went from right to left in array b maintaining a set current that contains all the indices in a that are being used, and a map extra that stores a count of all the extra values I can use.Case1 b[i] = b[i — 1]: I will consider b[i] and b[i — 1] together. I find the greatest element in the set, let's call if g. I then iterate from g decreasing. In the current index k, if it isn't in current I skip it. Otherwise if it's equal to b[i], I'll remove k from current and break out of the loop. If it's not equal to b[i], I check if I have an extra a[k] in my map. If not, the answer is NO. Otherwise, I decrease the count by 1, remove k from current, and continue; At the end, I add b[i — 1] to the map extra so that I can use it in the future.Case2 b[i] != b[i — 1]: I'll consider b[i] by itself. Then I'll do the exact same proccess as in Case1. The only difference is that I won't add b[i — 1] to extra and I'll just move on to the next i.At the very end, array a might have some leftover elements. I will iterate over all these elements and see if I have enough values in extra to match them all. If I do, then the answer is YES. Otherwise, the answer is NO.Is my logic wrong? 154756012
•  » » 2 years ago, # ^ |   +4 Input: 1 5 4 4 1 1 4 1 1 4 4 4 Expected Output: YESYour Output: NO
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 I'm a little puzzled myself. I'm doing more or less the same thing, and I pass your given test case.154775344Edit — ah I see the issue, nvm
 » 2 years ago, # |   0 I've spent 1 hour 30 minutes looking for a bug in my solution of D (got WA on the 3rd test)... After the round finished I updated the page every minute, waiting for testcases to be shown... And what I see now is only "wrong answer expected YES, found NO [515th token]", because the test data is truncated.I'm begging to look at the full testdata for test case 3, this is my only dream now
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I'm in a similar situation.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +10 154781966test case 515 20 3 2 2 1 1 3 1 3 3 1 3 2 1 3 1 3 1 1 3 1 3 2 1 1 3 1 1 3 2 2 3 3 1 1 3 1 3 3 1 1
•  » » 2 years ago, # ^ |   +7 Input: 1 6 5 2 3 2 3 2 2 3 5 3 2 2 Expected Output: NOYour Output: YES
 » 2 years ago, # |   +39 I think that problem H was really misplaced. Reading it afterward, it seems pretty straightforward, but I didn't try it during the contest because I thought it would have been much harder.Also, making 1 1 a system test rather than a pretest for E really screwed a lot of people (including me) over.Overall, it was a good contest!
•  » » 2 years ago, # ^ | ← Rev. 2 →   +5 MyCodeDI passed both your above testcases. Not getting what's going wrong.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +4 20 3 2 2 1 1 3 1 3 3 1 3 2 1 3 1 3 1 1 3 1 3 2 1 1 3 1 1 3 2 2 3 3 1 1 3 1 3 3 1 1 Expected yes
•  » » » » 2 years ago, # ^ |   0 Thanks man.
 » 2 years ago, # |   +6 In Problem B, I couldn't understand how AABBABAAAABABABAABAB can be acheived(Output is YES) as they are two succesive B's and good strings are AB, AAB, AAAB,..., so there must be atleast one A between two succesive B's and 'B' is bad string. I believe deletion of one character or substring is not allowed. Sorry if it is too dumb, but could anyone can explain this to me Thanks
•  » » 2 years ago, # ^ |   +3 The problem says "Choose any position of s1 and insert some good string in that position."So we can insert AB into the middle of another AB which results in AABB
•  » » 2 years ago, # ^ |   0 We can do string AABB like this. 1) empty -> AB 2) AB -> AABB (A+AB+B) So we got the string like AABB
•  » » 2 years ago, # ^ |   +3 Ohh I got it nowThank you so much
 » 2 years ago, # |   +41 // Super Idol的笑容 // 都没你的甜 // 八月正午的阳光 // 都没你耀眼 // 热爱105°C的你 // 滴滴清纯的蒸馏水 Now this is epic
•  » » 2 years ago, # ^ |   +6 Where is that from? I mean why is everyone posting this in the comments
•  » » » 2 years ago, # ^ |   0 It's in the solutions above? If you mean what does it mean then it's an epic beautiful song
 » 2 years ago, # |   +181 I found a different, possibly simpler, solution to H (Zigu Zagu). As in the hints I always remove a maximal segment. There are four possibilities: The endpoints of the segment are the same (e.g. we have ..1|101|1..). If we remove this segment we remove two pairs of consecutive 0s or 1s, but create one new pair of consecutive 0s or 1s Its endpoints are different (e.g. ..0|01|1..). In this case we remove one pair of consecutive 0s and one pair of consecutive 1s, without creating any new pairs of consecutive 0s or 1s One of its end points is at the end of the substring. Removing the segment simply removes one pair of consecutive 0s or 1s. The segment is the whole remaining substring. We always finish like this. This means that every segment of type 1 or 3 reduces either the numbers of pairs of 0s or the number of pairs of 1s by 1. This reduces the number of remaining maximal segments by 1. Every segment of type 2 reduces both the number of pairs of 0s and the number of pairs of 1s by one, hence reducing the number of maximal segments by 2. As such our sequence should be: Remove all possible segments of type 2. As long as there are pairs of both 0s and 1s there will always be at least one segment of type 2; so this will take min(0 pairs, 1 pairs) steps Remove all remaining type 1 and type 3 segments. This will take a number of steps equal to the number of remaining 0 or 1 pairs, which will be max(0 pairs, 1 pairs) - min(0 pairs, 1 pairs) Remove the last segment. This gives a total of max(0 pairs, 1 pairs) + 1 steps.To implement this, do a pass through the string calculating the number of 0 pairs and 1 pairs before each element, and we can then trivially calculate the number 0 pairs and 1 pairs for each query, and hence the answer to each query.
 » 2 years ago, # | ← Rev. 4 →   +1 Anyone interested can check my code 154764444 for problem F1 (easier to understand than editorial).
•  » » 2 years ago, # ^ |   +2 brrrrrrr
•  » » » 2 years ago, # ^ |   0 br
•  » » 2 years ago, # ^ |   0 Can you explain your solution?
•  » » » 2 years ago, # ^ |   +7 I took the next greater element for every element in A which will result in making the longest chain of substitutions which then results in the highest sadness. And for every cycle we have of length L, the number of swaps will be L-1.
•  » » 2 years ago, # ^ |   0 Naming the function "brrrr" was key. Editorial missed it totally.
•  » » 2 years ago, # ^ |   +1 that's pretty cool
 » 2 years ago, # |   +21 About A's tutorial, seems $\sum_{k=1}^na_i$ there is a mistake
•  » » 2 years ago, # ^ |   0 Thanks it is fixed.
 » 2 years ago, # |   0 Finally I got FST on problem E because I set the upperbound of binary search 4e9 but not 5e9, and I got WA on test 20. Anyway, it's a good contest with excellent problems.
 » 2 years ago, # |   0 I don't know why I get TLE on problem D 154740846. I think it's O(N). Can someone help me.Orz
 » 2 years ago, # |   0 I could have reached cm today if i didn't fail in (E) Main tests, (〒﹏〒)
 » 2 years ago, # |   0 Misprint In editorial of D, tutorial 1, case 3: "we delete an occurance of ai in S and decrement j", We should decrement i instead of j.
 » 2 years ago, # |   0 Does anyone has a segtree solution for H? I was stuck on how to correctly merge two segments together... And I guess there must be some smart way of doing so.
 » 2 years ago, # |   0 In editorial of D, tutorial 2, I can't understand what is this saying : "As such, we can consider mapping elements of b into elements of a. More specifically, consider a mapping f where f is non-decreasing, bi=afi and we increment cfi by 1 for all i". Can anyone elaborate please? Thanks in advance.
 » 2 years ago, # |   +1 Nice contest, although I did not perform well.Problem A is amazing. I use SG function to solve it, even though I felt that there must be a simpler solution during the contest. It turns out that my guess is right when I read tutorials and notice that I have missed the observation mentioned there.It does not take me too much time to find a solution to Problem B, but I forget a corner case which leads to a WA.It also needs some observation for problem C. I use almost the same idea as in tutorials. It is lucky that my first try is correct.I get stuck in problem D from the beginning, and, until the end of contest. I find that somehow I am quite bad at such kind of problems. During the whole contest, I have never got any chance to get close to the idea in the tutorials. I really get depressed when I see the top ones in the first page of standings, solving D within 15 minutes. This problem is an almost impossible task for me, while it is just like a warm up practice for them. But now, what I can do is only to work much harder and practice more. There is no time for depression.
•  » » 2 years ago, # ^ |   +1 Permutation problems are irritating.
•  » » 2 years ago, # ^ |   0 Instead of taking sadness from this round, take this: Whenever there is a question of applying operations some number of number. Try to think of applying operations in reverse.
 » 2 years ago, # |   0 Last line of tutorial of problem H: shouldn't it be "if $a_{l-1}\neq a_l$" ?
•  » » 2 years ago, # ^ |   0 It is changed. Thank you!
 » 2 years ago, # |   +24 If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints. If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
 » 2 years ago, # |   0 My approach for F1 https://codeforces.com/contest/1672/submission/154768409
 » 2 years ago, # |   +8 OperationForces xd
 » 2 years ago, # |   +30 Is H too similar to this problem? 1329D - Dreamoon Likes Strings
 » 2 years ago, # | ← Rev. 2 →   +1 An only *3000 problem I?? I think the difficulty is too underestimated for such a huge-amount-of-code data structure problem.By the way, ♪♪Super Idol的笑容 都没你的甜♪♪ XD. Is that song also got popularized in Singapore?
•  » » 23 months ago, # ^ |   +1 It is because rainboy decides to deflate the rating numbers by only solving I.
 » 2 years ago, # |   0 wrong answer expected NO, found YES [32nd token] problem D (Test: #2) can i find this test case somehow?
 » 2 years ago, # |   +5 I think there is a typo in editorial for D. For the lineOtherwise, we delete an occurance of ai in S and decrement j. If we cannot find ai in S, it is impossible to transform b to a.Instead of decrement j, it should be decrement i.
•  » » 2 years ago, # ^ |   +5 It is changed. Thank you!
 » 2 years ago, # | ← Rev. 2 →   0 In editorial of F1: "Proof: (⇒) There exists a cycle decomposition of the graph that uses at least cnt1+1 cycles. Since a single element of 1 can only go to a single cycle, there exists a cycle without 1."We are basically decomposing such that each cycle has only one occurrence of element 1. Why don't we need to do for elements 2, 3,...
•  » » 2 years ago, # ^ |   0 Because we only want to prove that there exist a cycle without $1$? So we do not have to care about what happens to any other element
 » 2 years ago, # |   0 F1 the Checker comment said "wrong answer B does not have the minimum possible sadness (test case 33)" 7 7 2 5 4 7 4 2 I Print 4 7 2 5 2 7 4 Why I Wrong answer？
•  » » 2 years ago, # ^ |   0
•  » » 2 years ago, # ^ |   0 Your array only has sadness $4$, while the maximum has sadness $5$. Construction of sadness 44 7 2 5 2 7 44 2 2 5 7 7 47 2 2 5 7 4 47 2 5 2 7 4 47 2 5 4 7 4 2
•  » » » 2 years ago, # ^ |   0 thx
 » 2 years ago, # |   -20 Dislike for referring to politics in task E
 » 2 years ago, # |   0 I am still confused about the graph representation of problem F1/F2. Why can we build the graph by rep(x,1,n+1) al[arr[x]].pub(brr[x]); in the sample solution of F2. As far as I understand, a permutation has a cycle representation, for example, the permutation 1 2 3 4 5 -> 1 3 5 2 4 can be represented by circles $(1)(2,4,5,3)$. But it seems that the construction in the solution is different from this kind. So far I couldn't understand where the idea comes from. Can anyone post some detailed tutorials or other related resources or problems?
 » 2 years ago, # | ← Rev. 5 →   0 Edit: Deleted.
 » 2 years ago, # |   0 in problem F1 ,why the lower limit of number of swaps of every cycle of length x equal to (x-1)?
•  » » 2 years ago, # ^ |   0 For example, if $x=5$, we can turn 1 2 3 4 5 into 2 3 4 5 1. And that costs at least 4 swaps.
•  » » » 2 years ago, # ^ |   0 ok but why the number of swaps can't be less than x-1 in this example?
•  » » » » 2 years ago, # ^ |   +11 You can think that there is an edge from $a_i$ to $b_i$. If we let $b_i=a_{i+1}$, it will form a cycle. In each swap we can only let at most $1$ number to it's right place, so we should have at least $x-1$ swaps to turn $a_i$ into $b_i$.
•  » » » » » 2 years ago, # ^ |   0 can you please explain the construction part in F1?
•  » » » » » » 23 months ago, # ^ | ← Rev. 5 →   0 consider the following example : 1 2 3 1 2 it contains two cycles :(1 2 3) and (1 2),find all of these cycles and shift them left by 1 , so the cycles after shift will be (2 3 1),(2 1) respectively.then put these cycles in their original positions in the array, so the array will become :2 3 1 2 1 codeimport sys input = lambda: sys.stdin.buffer.readline().decode().strip() for _ in range(int(input())): n, a = int(input()), [int(x) for x in input().split()] cnt, mx = [[] for _ in range(n + 1)], 0 ans = [0] * n for i in range(n): cnt[a[i]].append(i) mx = max(mx, len(cnt[a[i]])) cyc = [[] for _ in range(mx)] for c in cnt: for i in range(len(c)): cyc[i].append(c[i]) for c in cyc: for i in range(len(c)): ans[c[i]] = a[c[i - 1]] print(*ans)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +18 The proof by SpadeA261 isn't too correct In each swap we can only let at most 1 number to it's right place Take the cycle of size 2, in 1 swap we can move both numbers into its right place. A correct proof is as follows.There are $2$ types of swaps (pretend the trivial swap that swaps an element with itself doesn't exist): swaps that swap elements in the same cycle swaps that swap elements in different cycles In the first type, the number of cycles will always increase by $1$. In the second type, the number of cycles will always decrease by $1$.Anyways we can see that the number of cycles can only increase by at most $1$. So When there is a single cycle of length $x$, we need at least $x-1$ moves to break it into $x$ cycles, with all length $1$.
 » 8 months ago, # | ← Rev. 2 →   0 Can someone tell why there should be X no of some cycles ? why cant be X no of chains ? i1->i2->i3->i4->i5 ? something like this. Isn't having cylce itselfreduce one swap so I was thinking in something in lines of X no of swap chains instead of cylces ?