### duality's blog

By duality, 5 months ago,

Video editorials for B, C, and D are available on ak2006's channel.

Hint 1
Hint 2
Solution
Implementation

Hint 1
Hint 2
Hint 3
Solution
Implementation

Hint 1
Hint 2
Solution
Implementation

Hint 1
Hint 2
Solution
Implementation

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Implementation

### 1844F1 - Min Cost Permutation (Easy Version)

Hint 1
Hint 2
Hint 3
Solution (easy version)
Implementation

### 1844F2 - Min Cost Permutation (Hard Version)

These hints and solution continue from the solution for the easy version, so please read the solution for the easy version first.

Hint 4
Hint 5
Hint 6
Solution (hard version)
Implementation

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Implementation

### 1844H - Multiple of Three Cycles

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
Implementation
• +379

 » 5 months ago, # |   +91 Siyuan Cheng's last minute submmision..DAMN!!!
 » 5 months ago, # |   0 Nice contest and a very fast tutorial. Really amazing.
 » 5 months ago, # |   -9 So fast tutorial
 » 5 months ago, # |   0 don't get fooled tutorial is not available.
•  » » 5 months ago, # ^ |   0 implementation is there at least which is better than last time
 » 5 months ago, # |   +12 amazing E&&F
 » 5 months ago, # |   +50 Problem A: a + b.
•  » » 5 months ago, # ^ |   +3 True
•  » » 5 months ago, # ^ |   +8 lol I did smthg else. 3 cases
•  » » » 5 months ago, # ^ |   0 did Same Thing :)
•  » » 5 months ago, # ^ |   +1 I was scared of submitting my answer because it was so weird for me.
 » 5 months ago, # |   0 best contest ever <3
•  » » 5 months ago, # ^ |   0 Agree
 » 5 months ago, # |   +24 Contest is too Speedforces that even editorial got posted on fast
 » 5 months ago, # |   +8 so fast :O
 » 5 months ago, # |   +3 fast editorial :)
•  » » 5 months ago, # ^ |   0 nice pfp :)
 » 5 months ago, # |   +1 I was quite frustrated because continuously got WA on C while using dp :(However, that means im still too stupid, need to practice more.
•  » » 5 months ago, # ^ |   -6 agree
•  » » 5 months ago, # ^ |   0 ya did the same :(, where you able to find out why the dp solution fails here?
•  » » » 5 months ago, # ^ |   0 well, i sadly couldnt generate my wrong case bro... xd.
•  » » 5 months ago, # ^ |   0 Same. It took me a while to eventually land on the correct solution.
•  » » 5 months ago, # ^ |   +12 Here's my DP solution for C :Consider DP[i] to be the largest bubble you can have to be fused, on the left of the (i + 1)th, (i + 2)th, ..., (n — 1)th bubblesWhen you're facing a big bubble at spot i, and the next bubbles in line, you have three choices : Eliminate the i-th bubble, which gives DP[i + 1] >= Bubble[i + 1], since you removed everything on the left of (i + 1)th bubble Fuse the i-th bubble with the (i + 2)th, which gives DP[i + 2] >= DP[i] + Bubble[i + 2] And the final tricky choice : Keep the i-th bubble to be fused later, and therefore eliminate bubbles (i + 1) and (i + 2) at some point in the process, which gives DP[i + 2] >= DP[i] In the end you get a DP that simply calculates the magic sum of the editorial, but that's the way I found it anywayImplementation is pretty straightforward : https://codeforces.com/contest/1844/submission/213325940
•  » » 5 months ago, # ^ |   0
 » 5 months ago, # |   0 I had a hard time with implementation of E
•  » » 5 months ago, # ^ |   0 Can you explain me the last sample test for E? why is it NO?
•  » » » 5 months ago, # ^ |   0 You can simply try it.. There is no possible answer grid for that condition
 » 5 months ago, # |   0 super fast editorial sheesh!
 » 5 months ago, # |   +43 Thanks for the good problems and amazing fast editorial! Quite a high-quality round, many interesting problems. However, the problem diversity is not that high with most of the problems ad-hoc and constructive, while not including many algorithms in the first 5 or 6 problem. Anyway, great job and wish you can make the problem more diversed next time!
 » 5 months ago, # |   0 In first prb if a=1 b=2 how n must be 3, 2 also right answer I'm correct.bcz 1st player Play game n =1 second player play n = 0 so 3rd turn 1st player failed.
•  » » 5 months ago, # ^ |   0 If player one choses 2 than n = 0 so player 2 would lose
•  » » 5 months ago, # ^ |   0 If there are multiple solutions, you can output one of them. Because this problem use Special Judge.
 » 5 months ago, # |   +37 How to come up with the solution of G? Or is there any similar problem?
•  » » 5 months ago, # ^ |   0 Apparently, problem I from AIM Tech poorly prepared contest was very similar, at least in terms of solution
•  » » 5 months ago, # ^ |   0 I don't know much about trees, but I know they love bit opeations (e.g., binary lifting). Probably the most common thing is the XOR an a path problem. So it stands to reason to solve the problem in $\mathbb{Z} / 2\mathbb{Z}$ first. After that, it's kinda straightforward.
 » 5 months ago, # |   +7 Will tourist be the king again?
 » 5 months ago, # | ← Rev. 2 →   +29 The saddest thing happened right now. An FST in prob C preventing me from reaching CM for the stupidest bug. int main() { int t; scd(t); frange(_, t) { int n; scd(n); vll vec(n); lli ma = -1e9 + 1; lli eve = 0; lli odd = 0; frange(i, n) { sclld(vec[i]); ma = max(ma, vec[i]); if (i % 2) odd += max(0LL, vec[i]); else eve += max(0LL, vec[i]); } if (ma >= 0 && n >= 2) { printf("%lld\n", max(eve, odd)); } else printf("%lld\n", ma); } } I initialized ma = -1e9 + 1 instead of -1e9-1. :cry:UPD: The +70 delta is now -111
•  » » 5 months ago, # ^ |   +12 Feeling Bad For You :(
 » 5 months ago, # | ← Rev. 2 →   0 Can anyone explain how we are creating graph out of the coordinates in problem E? More specifically, how the following 2 lines are creating the graph with the property mentioned in the tutorial? adjList[min(x1,x2)].pb(mp(n+min(y1,y2),(x1+y1 != x2+y2))); adjList[n+min(y1,y2)].pb(mp(min(x1,x2),(x1+y1 != x2+y2)));
 » 5 months ago, # |   -20 problem A...
 » 5 months ago, # |   0 Has anyone solved c using dp , out of curiosity
•  » » 5 months ago, # ^ |   0 Here is my submission，hope it helps you: 213365683
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 could you please explain the dp logic
•  » » » » 5 months ago, # ^ |   0 I did the same thing after the contest. It is pretty much calling a array dp and calculating the max sum subsequence with it aka the solution in the editorial.Here the only submission that really uses dp, atlest the only one I have found:213325940
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Ye sayad sayad dp ni h ,Khali tumne dp vector use Kiya h
•  » » 5 months ago, # ^ |   0 Spoiler#include #include using namespace std; using namespace __gnu_pbds; template using pbds = tree, rb_tree_tag, tree_order_statistics_node_update>; #define int int64_t #define endl '\n' #define sz(v) ((int) v.size()) #define all(v) v.begin(), v.end() #define vi vector #define pii pair #define inf 2e18 int max(int x, int y) { return x > y ? x : y; } int min(int x, int y) { return x < y ? x : y; } void solve() { int n; cin >> n; vi a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } vector dp(n + 1, vi(2, -inf)); // states: [index][picking?] vi mx(2); for(int i = 1; i <= n; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); dp[i][1] = a[i - 1] + mx[i % 2]; mx[i % 2] = max(mx[i % 2], dp[i][1]); } cout << max(dp[n][0], dp[n][1]); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; cin >> t; while(t--) { solve(); cout << endl; } return 0; } 
•  » » » 5 months ago, # ^ |   0 can you explain the code also plxx
 » 5 months ago, # |   0 This is my submission of D during contest. As one can see it fails on test 15's case 16. However this test case is n = 2 which was also present on sample as well as some of the previous tests. Then why does it show wrong answer only on test 15 ? (It passed pretests during contest but now its showing FST).
•  » » 5 months ago, # ^ |   +4 Your solution is same as tourist. So you must look at his solution. Maybe then you will be able to find the error
•  » » » 5 months ago, # ^ |   0 Got it. Thanks. I initialized with n even before taking n as the input.
•  » » » » 5 months ago, # ^ |   +3 lmao
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 can you help me out in this 213442767 is mine getting WA on test 2 but the same code in c++ 213442685 getting accepted why, somebody please help me out.
 » 5 months ago, # | ← Rev. 2 →   +31 well, there is a greedy solution for F in $O(n)$ (but after sorting). the main idea is to keep checking "is choosing a smaller number able to remain the value unchanged?": if yes then go check the next one, otherwise construct a sequence using those larger numbers just checked. here is the submission.
•  » » 5 months ago, # ^ |   0 orz
•  » » 5 months ago, # ^ |   0 But there's a $O(n\log n)$ sort in the beginning QwQ
•  » » » 5 months ago, # ^ |   0 Oh yeah, I just didn't notice that QAQ. Then it is $O(n)$ only when the list is given ordered. thx!
 » 5 months ago, # |   +9 Tutorial with hints are BEST!!!
 » 5 months ago, # |   0 "the top arrow has the same label as the bottom arrow, and the left arrow has the same label as the right arrow" Could anyone explain why it is so? Greatly appreciated
•  » » 5 months ago, # ^ | ← Rev. 2 →   +6 Here is the idea of the proof, but some parts are omitted.The $2 \times 2$ submatrix must look like x y y z where $x, y, z \in \{0, 1, 2\}$ (or the mirror image of that, but the two cases are identical and thus, it is enough to consider this one case).Every submatrix must contain all three values $\Rightarrow x \neq y \neq z \neq x$Now there are two casesCase 1: Top row difference $x - y \equiv 1 \pmod 3$$x \equiv y + 1 \pmod 3$Now, since $y \equiv y$ and $x \equiv y + 1$, $z$ must have the remaining value, i.e. $z \equiv y + 2$.This means that the difference on the bottom row is $y - z \equiv y - (y + 2) \equiv -2 \equiv 1 \pmod 3$, which is equal to the difference on the top row. We can see that the difference on the left column is equal to the difference on the top row and the difference on the right column is equal to the difference on the bottom row. Thus, the differences on the left column and the right column are equal.Case 2: Top row difference $x - y \equiv 2 \pmod 3$ can be handled in the exact same way as above and we will end up with the same conclusion.
•  » » » 5 months ago, # ^ |   +5 Congrats on Becoming GrandMaster vgtcross
•  » » 5 months ago, # ^ |   0 The fact is that the difference in the tutorial is unidirectional instead of abs hah
 » 5 months ago, # |   +16 How can one easily prove F?
 » 5 months ago, # |   +21 Can someone give proof for this in problem F?"When c≥0 , it can be proven that the minimum cost can be obtained by sorting a in nondecreasing order."
•  » » 5 months ago, # ^ |   +8 You can change the form of summation by first supposing all $b_{i+1}-b_i \leq c$ and then compensate those $b_{i+1}-b_i > c$ twice: $\sum_{i=1}^{n-1} |b_{i+1}-b_i-c| = \sum_{i=1}^{n-1} (-b_{i+1}+b_i+c) + 2\sum_{b_{i+1}~- b_i~>~c} (b_{i+1}-b_i-c) = (n-1)c - (b_n-b_1) + 2\sum_{b_{i+1}~- b_i~>~c} (b_{i+1}-b_i-c)$So we need (least $i$ with $b_{i+1} - b_i > c$) and ($\sum (b_{i+1} - b_i - c)$), and a sorted $b$ certainly satisfies.
•  » » » 5 months ago, # ^ |   0 This explanation is so good that it has to be in the editorial. Thanks a lot!
 » 5 months ago, # |   0 orz fast editorial!! I only was able to solve Problems A and D (had to leave after 2 hours of competition) but very fun round, almost had Problem C's solution!
 » 5 months ago, # |   0 my performance predictor showing infinite level performance by Global Rank 1....!!! Insane.
•  » » 5 months ago, # ^ |   +8 I belive it calculates the performance relative to the performance of the top place and thats why.
 » 5 months ago, # |   0 I thought D was going to be some awful construction or brute force but after looking at the proof I am amazed. Really pretty proof. I got the clique idea but couldn't construct a string with that number of characters
•  » » 5 months ago, # ^ |   0 Simply factoring and then calculating mex of all characters that are $d$ positions before, where $d$ is a divisor of $n$. Doesn't feel as a D
•  » » » 4 months ago, # ^ |   -8 will that not give a time complexity of Nroot(N), something to avoid when constraint is 1e6
•  » » » » 4 months ago, # ^ |   +8 It's not $Nsqrt(N)$, only $N$ times the number of divisors of $N$, which isn't more than $240$. With little optimisations it runs fast enough to pass the time limit. My code runs in 717ms
•  » » » » » 4 months ago, # ^ |   +5 Hmm, thanks.Also, this was helpful: link
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 can you explain this solution a bit more. I don't understand your code and it seems much simpler than the solution that I have in mind.The solution I have in mind is find the divisors of N. Then iterate over n incrementing s[i+divisor] for each divisor by 1 if it is the same as s[i]. The problem I have with this solution is that it isn't clear to me why that finds the minimum number of distinct elements. To give a specific example that trouble me, if s[i] is 1, and s[i + divisorA] is 0, s[i+divisorA] will not be incremented. However, for an index j where i
 » 5 months ago, # |   -21 still newbie orz
 » 5 months ago, # |   +15 Amazing contest! Learnt some stuffs. Problems were well-designed and of high quality. Kudos to duality!
 » 5 months ago, # |   +1 Why no one is thinking DP for E ? I spent hours debugging my code but not sure why dp won't work.dp[i][j][c] -> is it possible to color position (i,j) with color c ?
 » 5 months ago, # |   -11 duality orz
 » 5 months ago, # |   +12 I hate constructive algorithms :(
 » 5 months ago, # |   +1 in F: When c≥0 , it can be proven that the minimum cost can be obtained by sorting a in nondecreasing order. As sorting a in nondecreasing order is also the lexicographically smallest array, this is the answer. how?
 » 5 months ago, # | ← Rev. 3 →   +177 Feedback on the problems:A: Good easy problem. I liked that there were multiple meaningfully distinct paths to the solution.B: Fine for its position.C: Fine for its position. Despite the fact that the bulk of the problem was making the necessary observation (i.e. we can take any subset of the odds or any subset of the evens), the proof of the observation is fairly straightforward once you've made it, meaning it didn't feel like I was trying for a proof by AC.D: Okay problem (although I'm embarrassed by the way I solved it...). I think it might have been good to use a somewhat harder task in this position to smooth the gap between C and E, and also to avoid having four one-trick problems at the beginning of the contest.E: Excellent problem; one of my favorites at its difficulty level in recent memory. The process of solving the problem was satisfying in a similar way to a good challenging OI problem: I felt like I was gradually making observations that improved my understanding of the problem's setup, eventually leading to a solution. Most problems that are similarly satisfying are much harder than this one is, so it's impressive to write a task this interesting that's still suitable as problem E.F: Great problem. Like E, I found the process of making conjectures to gradually understand the problem very satisfying. This was also a good use of a subtask, and the score distribution between the two subtasks seems reasonable.G: Great problem. The idea to get rid of the $2 \cdot x_{lca}$ term by taking the equation mod $2$ is brilliant. I've heard some people have seen similar ideas before, but the solution was completely new to me (and I was not even close to solving the problem in-contest). H: Didn't read during the round.The statements were clear, and it looks like there were relatively few FSTs. Moreover, the editorial is well-written; I appreciate that most proofs are included and that hints are provided for all problems. The gap between D and E was a bit large, but it's very difficult to get the difficulty distribution just right, so this is far from a round-ruining issue. Thanks to the author and the coordinator!
•  » » 5 months ago, # ^ |   +8 thanks for the feedback, can I know what is your thought process solving E?
•  » » » 5 months ago, # ^ |   +34 Here's an outline of my solution path. Note that this will likely be less comprehensible than the editorial.I noticed that if you know three of the letters in a 2x2 grid, you can uniquely determine the fourth. This implies that if we fix the first row and the first column, these uniquely determine how to fill in the rest of the grid. From there, I started drawing out possible first rows and analyzing the possibilities for the second rows (based on the two choices of which letter appears first in the second row), and I found that each row must be equal to the last except with each letter shifted forward (i.e. A's turn into B's, B's turn into C's, C's turn into A's) or backward (i.e. A, B, and C turn into C, A, and B). Then, I looked at which diagonal contains two equal elements in each 2x2 grid. I found that in one of the two cases, the diagonals in the next row have the same orientation as the diagonals in the last, while in the other case the diagonals in the next row have the opposite orientation of the corresponding diagonals in the last row. In other words, we can pick arbitrary orientations for all diagonals in the top two rows, and then for each subsequent row, we can either flip the orientation of all diagonals or keep them all the same. From there, I realized this is equivalent to the graph coloring problem described in the editorial (largely because I've seen the same general idea many times in the past). Big picture, the idea is that if we have one boolean for each column representing whether the first 2x2 grid corresponding to that column has identical letters on the main diagonal or the off diagonal, and another boolean for each row representing whether the diagonals in that row are flipped or not, then saying that a given 2x2 grid needs to have equivalent elements on a specific diagonal tells us whether the boolean variables for the corresponding row and column must be the same or distinct. Given a number of booleans and various requirements that they must be equivalent or distinct, we can detect whether a valid assignment of true/false values to the variables exists by creating a graph in which the variables are vertices and the constraints are edges. We can then repeatedly assign some variable an arbitrary value, use BFS or DFS to determine the value of all other variables in the same connected component, and check whether the resulting assignment is valid.
•  » » » » 5 months ago, # ^ |   +3 Geothermal Thank you for such a good explanation. Honestly speaking, I wasn't able to understand the editorial even after reading it multiple times, but your explanation was very clear and intuitive as well. I wish you start uploading on Youtube once again.
•  » » » 5 months ago, # ^ |   +14 Draw some cases.Notice that it looks like row[i+1] is row[i] but +1 or -1 mod 3.Same thing for column.Remember similar problems. It turns into a sort of xor 2sat with variables being the difference between consecutive rows and columns.
•  » » » » 5 months ago, # ^ |   0 you said remember similar problems, can you suggest some please? it's new to me.
•  » » » » » 5 months ago, # ^ |   +10 Problems about a binary matrix where c[i][j] = r[i] ^ c[j]. There are many problems like that but I won't go look for a link.
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 Thank you for the feedback!Can you explain the proof for n>=3 in problem B?
•  » » » 5 months ago, # ^ |   0 In general if we don't include 1 in the sub array then mex will be 1 which is not prime. so we want it to be in the center so that it will be in most of the sub arrays. Now 2 and 3 are primes so by including 1 we want them to be not included. so lets keep them at the ends so that less sub arrays include 2 and 3 . In general if we elements are at end then least sub array will be there including them. Finally , if 1 is there in the sub array then except for 1 case (that is including all elements) 2 or 3 will not be there in any of the sub array . Ans — 2 ---- 1 ---- 3 remaining elements can be anything.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Can you share your idea for F1 please? In particular I don't understand why we fix the maximum element as the 1st element for c<0 case.
 » 5 months ago, # |   0 In the editorial for E it says that "the top arrow has the same label as the bottom arrow, and the left arrow has the same label as the right arrow" in each 2x2 subgrid. Am I understanding this wrong or should it be that the top/left arrows and the bottom/right arrows are the same?
 » 5 months ago, # |   0 I really like problem G. Its intended solution is nice and elegant. Special thanks for this one.
 » 5 months ago, # |   +39 Me waiting for the rating to reach CM
 » 5 months ago, # |   0 Could anyone suggest similar problems to problem E (easier preferably) ?
 » 5 months ago, # |   0 i feel bad because i'm newbie, for third question i have idea same the tutorial but i don't write it down...
 » 5 months ago, # |   +9 problem E is really nice!
•  » » 5 months ago, # ^ |   0 can you explain the solution? and suggest some similar problems on this method?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 First, we draw a line between two cells sharing a unique corner, then there is a unique line in each 2 × 2 subgrid.let $a_{i,j}$ be $0$ if there is a line connecting $(i,j),(i+1,j+1)$, and $1$ if there is a line connecting $(i,j+1),(i+1,j)$. Some $a_{i,j}$s are given, and we should fill the rest. a key observation is, if $a$ is valid, then $\forall i \in [1,n),j \in [1,m)$, the sum of $a_{i,j},a_{i,j+1},a_{i+1,j},a_{i+1,j+1}$ is even. That also means, there exists an array $f$ and an array $g$ consisting of $0$ and $1$, satisfying $f_i \oplus g_j = a_{i,j}$, here $\oplus$ means the bitwise xor.if $a_{i,j}$ is given, then add an edge between $f_i$ and $g_j$. For each component, check if it's able to construct. The time complexity is $O(\sum n+m+k)$.
 » 5 months ago, # |   -48 Such a bad contest. The difference in difficulty between D and E is absurd.
 » 5 months ago, # |   0 What is the reason for you to cheat to provide your fake rating "for cheaters"):
 » 5 months ago, # |   +14 beg for a proof of F. :(
 » 5 months ago, # |   +1 Can anyone explain the proof for n>=3 in problem B
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 You need max primality, so maximum no of subarrays with mex as prime. Which prime numbers are easiest to get in an mex? It's 2 and 3. But to get to 2 (or 3) as MEX you need 1 in the subarray as well. If you think about it, an element can affect the maximum subarrays if its in the middle of the array. At the ends of an array, you have n subarrays you can construct using the first (or last) element of an array. However, this number goes up as we go towards the middle and maximises at the centre. Hence, you take 1 as the middle element. Now you need to make sure 2 and 3 together are included in the least number of subarrays (since MEX will then come out as 4, which is not a prime). How do you do that? By taking them as the first and last element in the array.
•  » » » 5 months ago, # ^ |   0 Got it brother.Thank you for explaining it:)
 » 5 months ago, # |   0 I calculated max subarray sum for even indices and odd indices and printed max of them in problem C , it got Ac
•  » » 5 months ago, # ^ |   0 Subsequence
•  » » » 5 months ago, # ^ |   +8 oh yeah , that means I git ac undeservingly
 » 5 months ago, # |   0 In premise of problem B, if instead of 1, the natural numbers started from any given integer, and the mex calculation also starts from that number itself, would it guarantee the solution, where you need to append the least two primes after the given integer in the front and the back of the array, will always result in a permutation which has maximum no. of subarrays which have prime mex ?
•  » » 5 months ago, # ^ |   0 no , it wouldn't guarantee I think
 » 5 months ago, # | ← Rev. 2 →   0 For Problem C, would taking the max of maximum Subarray Sum of odd-indexed arrays and even-indexed arrays work?I am unable to think of a countercase.EDIT: I am a dumdum, Maximum Subset Sum is what we need not Maximum Subarray Sum! :(
 » 5 months ago, # |   +76 G is one of the greatest problems I have ever seen. I solved it but I am still shocked that any problem can be solved like that... It just doesn't feel right... Fascinating!
 » 5 months ago, # |   +8 I have proved the case of c>=0 through complex inequalities about F1, is there any simple proof or understanding?
 » 5 months ago, # |   0 A+BForces
 » 5 months ago, # |   0 Hi, anyone would like to study (code) together with me?
 » 5 months ago, # |   +21 Can anyone explain me please how to prove the fact that nondecreasing order in case of c >= 0 (F task) gives optimal result? It makes sense, but i can't prove it formally for a long time
 » 5 months ago, # |   +18 Problem F is pretty similar to 1685D2 - Permutation Weight (Hard Version), and is essentially a particular instance of this generalization, with the extra bit of finding the lexicographically minimal Euler tour a little faster by using the structure of the problem.
•  » » 5 months ago, # ^ |   0  with the extra bit of finding the lexicographically minimal Euler tour a little faster by using the structure of the problem Can you please elaborate here? I am not able to understand it. Thanks in advance
 » 5 months ago, # |   0 Can anyone tell me what is wrong in this solution and why in problem F1 we include i+1 , i-1 's differnece , that does not make sense to me. Please helpMy code:- 213562733void solve(){ int n,c; cin>>n>>c; vi v(n); fov(n,v); if(c>=0){ sort(v.begin(),v.end()); printArr(v); return; } sort(v.rbegin(),v.rend()); for(int i=0;ii;j--) { if(v[j]>=v[i]) continue; if(i>0){ preCost = abs(v[i]-v[i-1]-c) + abs(v[i+1]-v[i]-c); newCost = abs(v[j]-v[i-1]-c) + abs(v[i+1]-v[j]-c); } else{ preCost = abs(v[i+1]-v[i]-c); newCost = abs(v[i+1]-v[j]-c); } if(j<(n-1)){ preCost = preCost+ abs(v[j]-v[j-1]-c) + abs(v[j+1]-v[j]-c); newCost = newCost+ abs(v[i]-v[j-1]-c) + abs(v[j+1]-v[i]-c); } else { preCost = preCost+abs(v[j]-v[j-1]-c); newCost = newCost+abs(v[i]-v[j-1]-c); } if(preCost==newCost) { swap(v[i],v[j]); break; } } } printArr(v);}
 » 5 months ago, # |   0 B's an interesting problem, could someone help me understand why in the solution MEX values of other primes such as 5,7,11,13 are not relevant to this solution? Like I get this construction maximizes the number of subarrays with MEX values 2 and 3, but somehow I thought the solution would involve finding each prime and trying to build a subarray that would contain each prime value in MEX as many times as possible.Also the final remark (note that we don't even need to sieve for primes!) given whatever the heck I did with this problem in the contest might be the most inadvertently cheeky and emotional damage inducing line in an editorial I've ever had to read.
•  » » 5 months ago, # ^ |   0 So first of all, every subarray not containing 1 is bad so we want to maximize number of subarrays containing 1(which is quite easy you just place it in the middle and get quadratic number of arrays containing it).So now we are looking only at subarrays that contain middle point. Idea is, because 2 and 3 are only connected primes in natural numbers, to use that fact to get all the subarrays that have middle to also have prime MEX like this: if we place 2 on the end of the array that means that ALL subarrays including 1 and not end of array(the '2') have MEX = 2(now we are left with only subarrays containing 2 which are also the suffix subarrays). Similarly we can put 3 on the other end and then even subarrays including 2 have MEX = 3. So now there only remains 1 subarray that we haven't made a prime MEX, which is full array, but that one doesn't matter cuz its MEX is anyway n + 1 so we can't make it prime if it ain't. Hope this helped :)
 » 5 months ago, # |   0 I have another interesting solution for problem E, which is O(n + m + k^2). Idea is as stated in a solution version 2, that if you have '/' it means right up corner is same as down left corner and as for '' if we reverse logic it means that right up corner is different than down left corner. Also, as stated, transitions in each row are either completely the same as in previous or completely reversed(try for yourselves). So now connections in a graph will be : are 2 slashes in same row equal or different(there are k^2 pairs of slashes max). After we create such a graph we can do simple 2-color search :)My submission: 213578347
 » 5 months ago, # |   0 for E, editorial says:The conditions imply that all labels are 1 or 2, and in each contiguous 2×2 subgrid, the top arrow has the same label as the bottom arrow, and the left arrow has the same label as the right arrow.but, for example, in the subgrid below: 1 2 2 0 the top arow is 1 and the bottom arow is 2, their not the same. and the right arow is 2 while the left arow is 1.can somebody explain?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +18 Bottom arrow has value -2 (we are looking at the value modulo 3, not on the value module), and 1 == -2 modulo 3Edited: the same thing with left and right arrows. It's important that if you count the value of left arrow as "bottom value — top value", then you should calculate the value of right arrow the same way (ignoring the negativity of the result)
•  » » » 5 months ago, # ^ |   0 I get it now. thank you very mutch.
 » 5 months ago, # |   0 I think the idea of G is a bit similar to what's explained in this Veritasuim's video.
 » 5 months ago, # |   0 This submission should not work. It is O(N^2). Someone hack it: 213539286.
 » 5 months ago, # |   0 I remember some time ago I came across this problem from leetcode which reminds problem C from this contest. It turns out that the problem linked has a DP solution of O(N^3) (there is also the video explanation in the first problem of this video by Errichto). However, I cant understand why the problem C from this contest has a demonstrated DP solution of O(n) (see for example the solution explained by JeanBombeur in the comments) while the leetcode problem linked has O(n^3) as optimal DP solution, despite the two problems are almost the same. Please, can somebody help me understand why the two problems are not solvable in the same way?
 » 5 months ago, # |   +13 God damn, finally, i got the proof for statement in f-task (that non-decreasing order gives optimal result in case of c >= 0). Don't know if where is anyone who still have interest in this proof, but if you are — you are welcome (i will write it as the answer to this message, sorry if you won't understand, i'll try my best to explain)
•  » » 5 months ago, # ^ |   +3 Note that the order of values in A doesn't matter, so let the A array be already sorted. In that case, we can simply write a difference between all adjacent alements, and every difference will be no less than zero. So, let's define array D: D[i] = A[i+1] - A[i], and as i just said, D[i] >= 0 for all i. There also is an important picture representation of array A and it's random permutation: imagine the values from A as points on an integer line, now D[i] is the length of section between points A[i] and A[i+1]. Random permutation is now a sequence of jumps on this line, every jump ends at a not visited yet point, and every jump (starting from second) starts in the end of previous jump, first jump just starts at some A[i].Every jump is a transition from B[i] to B[i+1] (for some i). Also, every jump has it's difference (i mean B[i+1] — B[i], let's define it as DB[i]), and is equal to some union of "elementary jumps" (by elementary jump i mean D[j] for any j). Declaring B[i] = A[f[i]], |DB[i]| = sum from (min(f[i], f[i+1])) to (max(f[i], f[i+1]) — 1) {D[j]}, and sign(DB[i]) = -1^(f[i+1] < f[i]).First idea: there is a bijection between DB and D, satisfying the condition: for every comparison DB[i] <-> D[j] expression (min(f[i], f[i+1]) <= j && j < max(f[i], f[i+1])) is true. Other words, d[j] lies in the union of elementary jumps, which is equal to DB[i]. (If there is a misunderstanding, read the previous paragraph again, also drawing on paper might help)Proof: let's take a look at the following invariant: before every jump we have a set of points, from which we haven't started a jump yet, we are standing in one of these points and between every such adjacent points there is exactly one elementary jump, which has not yet been used by the bijection construction algorithm. The algorithm is to jump from the first member of permutation to the last, and for each jump, match it to the first (in the direction of the jump) elementary jump that has not yet been used to it. It is easy to make sure that the invariant is not violated during the execution of the algorithm. (use a picture with integer line, and alternating sequence of points and elementaary jumps), after every jump we have one less point to jump to and one less elementary jump we can use in matching, but these two were adjacent on the line, so we can simply throw this pair out from the line).Now, let's proof that any permutation is not better that non-decreasing order of A (from the point of view of the minimality of the amount |B[i+1] — B[i] — c|)Note that we have 4 types of jumps in a random permutation: left/right and "matching elementary jump is < c / >= c". Matching elementary jump — from paragraph about bijection. Elementary jump < c means D[i] < c. The main idea is to compare value of function |B[i+1] — B[i] — c| on jump of permutation and matching elementary jumps. Case: right jump, matching D[i] >= c. In that case elementary jump gives d[i] — c, permutation jump gives D[i] — c + (D[v1] + D[v2] + ... ). I mean that DB[j] for right jumps is equal to D[v] + D[v+1] + ... + D[u], for some u <= i <= v. So, right jumps are definitely not better than matching elementary jumps.Case: right jump, matching D[i] < c. In that case we can get better result than matching elementary jump, but we can't reduce the value of (|B[j+1] — B[j] — c|) by more than min(c, DB[j] — D[i]). We will need this fact later, to proof that "casualities" on left jumps are not less than "profits" on right jumps with d[i] < c.Case: left jump, matching D[i] >= c. In that case, elementary jump gives D[i] — c, while the "original" jump gives DB[i] + c, so the difference is DB[i] — D[i] + 2c, I.e. we took DB[i] as a union of elementary jumps, removed D[i] and added two segments of length S.Last case: left jump, D[i] < c. In that case difference is equal to DB[i] + D[i].So, why we can't make better result than with non-decreasing order? Let's fix a random permutation B, fix random elementary jump D[i], and check every permutation jump, "covering" (containing, other words) this elementary jump. Define x as the number of right jumps, containing this elementary jump, and y as the number of left jumps, -//-. Note that |x — y| <= 1. If permutation jump (matched to fixed elementary jump) is right, then contribution of fixed elem. jump in decreasing the value of some right jumps <= (x-1)*D[i] (it decrease the value of every right jump, containing this elem. jump (not as a matching), but every decrease is no more than d[i]). In the same time, D[i] contribution in increasing values of every left jump, containing D[i] is equal to y*D[i] (because no one of these left jumps contains D[i] as matching). Since |x-y| <= 1, we can be sure that y*D[i] >= (x-1)*D[i] (other words, we didn't get any profit from this elementary jump)/Otherwise, if matching permutation jump is left, then contribution of fixed elem. jump in decreasing the value of some right jumps <= x*D[i] (and if D[i] >= c, we can restrict it even stronger, with value x*c). On the other hand, contribution in increasing values of left jumps is equal to (y-1)*D[i] + 2*D[i] (in case of D[i] < c) and (y-1)*D[i] + 2*c (in case D[i] >= c). It's not hard to notice, that in both cases (D[i] < c / D[i] >= c) maximum increment value is not less than maximum decrement value.Other words — we proved that there is no permutation with sum |b[i+1] — b[i] — c| less than non-decreasing order sum.Yeah, i really like it then "can be proven" facts proof is several time bigger than the solution. However, if anyone has shorter and simplier proof — it would be very nice to get acquainted.P.s. proof for c < 0 is obvious, multiply by -1 all A[i] and c, every module has not change it's value, but now c is > 0, so (-a[i]) should be sorted in non-decreasing order <=> a[i] should be sorted in non-increasing order.
•  » » » 5 months ago, # ^ |   +8 might be late but I think you missed the proofs section of the editorial of F2
•  » » » » 5 months ago, # ^ |   0 Oh really...Sorry then, I definitely have a problem with attention :(
 » 5 months ago, # |   0 So unique for G's solution.
 » 5 months ago, # |   0 I have received a mail and a message from the codeforces system that my solution of problems A, B and C of codeforces round #884 Codeforces Round 884 (Div. 1 + Div. 2) coincides with a person with codeforces user handle Yash_1308.I came to see now that he was using my template in the previous round, which I had been using for the last one year. It is the case of some code pasted before the contest, and nothing was done during the contest.Problem A: My submission 213301983 Problem A: His submission 213308099 Problem B: My submission 213315128 Problem B: His submission 213332212 Problem C: My submission 213338146 Problem C: His submission 213352663 I regularly give contests and use this template from around 30 previous contests. So, this shows that I am not a cheater, and I have neither provided any solution nor copied during the contest, which proves that I am not a cheater.I would request MikeMirzayanov and duality to please look into the matter and remove my plag as I have not done anything wrong.
 » 5 months ago, # |   0 Great contest!
 » 5 months ago, # | ← Rev. 3 →   0 In the proof section in problem F2, "furthermore, any optimal permutation b satisfies b1=a1 and bn=an". Why is that the case?
 » 5 months ago, # | ← Rev. 2 →   -14 In The 1st question output written is wrong which mislead the question. In 3rd case when a=9 and b=26 output will be 35 but it is written 3.
 » 5 months ago, # |   0 i am not able to understand the proof for problem B , can any one help with that...
 » 4 months ago, # | ← Rev. 3 →   0 Problem: Subtraction GameSolution: a+b(addition)
 » 4 months ago, # |   0 Did someone solve G with virtual trees? We can image that a edge is connecting i to i+1,then we merge the n-1 "edge"s in some order and we will keep knowing all the value of "edge" in the virtue tree.But I don't know how to update the virtue tree.
 » 3 months ago, # |   +1 What does MEX refers to in the problem number B?
 » 4 weeks ago, # |   0 My thought process on D:- noticed that it is enough to just output $abababa\ldots$ for an odd $n$.- noticed that $abcabcabc...$ always works for any $n$ as long as none of its divisors pickup a "full $abc$ part". So, it won't work if $n$ has divisors $3/6/9/...$- Why so, because of cyclicity. Led me to thinking that we must avoid any letter repeating at a distance = any of the divisors of $n$.- To minimise the number of characters, we will still have to have cyclicity in the string. So, lets make a string that is cyclic in the length = smallest number that is not a divisor of $n$.