Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

### zltzlt's blog

By zltzlt, history, 4 weeks ago,

Rating Predictions

2003A - Turtle and Good Strings

Hint
Solution
Code

2003B - Turtle and Piggy Are Playing a Game 2

Hint
Solution
Code

2003C - Turtle and Good Pairs

Hint
Solution
Code

2003D1 - Turtle and a MEX Problem (Easy Version)

Hint
Solution
Code

2003D2 - Turtle and a MEX Problem (Hard Version)

Hint
Solution
Code

2003E1 - Turtle and Inversions (Easy Version)

Hint 1
Hint 2
Solution
Code

2003E2 - Turtle and Inversions (Hard Version)

Hint
Solution
Code
Bonus

2003F - Turtle and Three Sequences

Hint 1
Hint 2
Solution
Code
• +112

 » 3 weeks ago, # |   +136 ProofByACForces :)
•  » » 3 weeks ago, # ^ |   +19 Proof by magic :)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Problem d2 for (int u = k; ~u; --u) { f[u] = u; for (int v : G[u]) { f[u] = max(f[u], f[v]); } if ((int)G[u].size() >= 2) { t = max(t, f[u]); } } can any one explain the why this if statement is used to find max and how we will using it. I dont get the idea of why we storing.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I created video editorial for D1 and D2Note: This is not a detailed video editorial. Instead, I walk you through my thought process using which I arrived at the solution. Use it as a supplement to the official editorial. Update: I also added commentary for the DP Mindset require to solve the easy version of F.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Bang on whatta explaination realy, but still I miss the fact what with the if statement. If you free pm me lets discuss this approach more thoroughly
•  » » » » 3 weeks ago, # ^ |   0 great as always .
 » 3 weeks ago, # |   +1 Thanks for fast editorial.
 » 3 weeks ago, # |   0 Thanks for the amazing contest :) What topics should I learn To solve D2?
•  » » 3 weeks ago, # ^ |   0 I think DSU and some concept of DP will do
•  » » » 3 weeks ago, # ^ |   0 Any good resource for DSU?
•  » » » » 3 weeks ago, # ^ |   +1 You can learn about DSU in the cp handbook https://cses.fi/book/book.pdf in the section named "Union-find Structure"
•  » » » » » 3 weeks ago, # ^ |   0 Nice book, easy to understand
•  » » » » 3 weeks ago, # ^ |   +4 check in the “edu” section
•  » » 3 weeks ago, # ^ |   +1 dfs
•  » » 3 weeks ago, # ^ |   +1 topological sorting.
 » 3 weeks ago, # |   +2 i panicked and got 2 WAs on A, and then got 2 unnecessary WAs on D1 with some spaghetti code. fml
•  » » 3 weeks ago, # ^ |   0 I found problem A very easy to misread as well. I wish the sample tests were better.
•  » » » 3 weeks ago, # ^ |   +4 Same here, i didn't read For all i < j
 » 3 weeks ago, # |   +1 very nice problem set.enjoyed solving problem $D$.
•  » » 3 weeks ago, # ^ |   0 the worse case of input is already O(n^2)? Is my understanding wrong?
•  » » » 3 weeks ago, # ^ |   0 if you read the problem statement it clearly says something along the lines of "sum of all l[i] across all testcases does not exceed 2e5"
•  » » » » 3 weeks ago, # ^ |   +5 got it, thanks.
 » 3 weeks ago, # |   0 Amazing contest and GREAT IDEAs !!!
 » 3 weeks ago, # | ← Rev. 2 →   +20 In my solution to F, the probability of not obtaining the optimal solution is $(\dfrac{5!-1}{5!})^{600} = 6 \cdot 10^{-3}$ which is actually not very good. But there are only 65 tests so I passed pretests :)Upd: Passed System test, seems that I'm lucky :)
 » 3 weeks ago, # |   +6 In problem C solution: Begin by placing x−y instances of the most frequent character at the start. Why is this optimal? Why not just alternate most frequent character not only with the second most frequent, but with others as well? The rest is obvious but this part is just an assumption basically.
•  » » 3 weeks ago, # ^ |   +3 Going further, does the order of frequencies really matter? Don't we just need to alternate characters in lexicographical order until there are no more left?
•  » » » 3 weeks ago, # ^ |   0 that's what i submitted and it got AC, and i still dont know why:)
•  » » » » 3 weeks ago, # ^ |   0 Me neither. I just followed my instincts. xD
•  » » » 2 weeks ago, # ^ | ← Rev. 4 →   0 This does indeed work, because consider this algorithm:At the first position place any character. At the $i$-th position place any character that is different from the one that you placed at $i-1$-th position. This algorithm will stop only if you exhausted all characters, or if you have left only characters of one kind $c$. Then place all the remaining $c$'s at the end. In this way you will have at most 1 segment of the same characters of length more than 1 (at the end). I think this is the same result the editorial solution gets.
•  » » 3 weeks ago, # ^ |   0 I tried alternate most frequent character with all others, it passed pretests.
•  » » 3 weeks ago, # ^ |   0 It's not so hard. There's something much easier than this solution.Just sort the string then print them in an order like $1,n,2,n-1,3,n-2,\dots$, and that's all.But I just can't prove it.
•  » » » 3 weeks ago, # ^ |   0 nice solution.
•  » » » 3 weeks ago, # ^ |   +5 I did the same thing. I wasn't too sure about my solution so I proved it and that made me submit the problem after one hour.I guess it works because you don't actually care too much about the characters themselves, but only about the changes. Define a change as the number of $i$ such that $s_{i}\neq s_{i+1}$. - If in a given substring you only have zero changes, then the first character is equal to the last and that is good. - If you have only one change then your substring looks like "aa...aabb...bb". Let $i$ be the only change, the only index such that $s_{i}\neq s_{i+1}$, you have that $s_{i}=s_{l}$ and $s_{i+1}=s_{r}$ (where $l$ and $r$ are the first and the last character of the substring), so $(l,r)$ isn't a good pair. - If there is more than one change it's good. If there are three or more different type of characters you can obviously find a change such that $s_{i}\neq s_{l}$ or $s_{i+1}\neq s_{r}$. If it is made only of two type of characters the substring has a block of characters of the first type, then a block of the second type, a block of the first, and so on... So if you take look at the second change you'll have that $s_{i}$ is of the second type and is different from $s_{l}$, and $s_{i+1}$ is of the first type so it is different from $s_{i}$. Note that it doesn't matter if $s_{i+1}=s_{r}$ because you know that $s_{i}\neq s_{l}$.Now, sorting the string as you said is optimal because you minimize the number of $i$ such that $s_{i}=s_{i+1}$ so you maximize the changes in every substring. And in particular there will be zero such indices unless there is a type of characters which occurs more than $\frac{n}{2}$ times, case in which you can't do better. In this sorting every substring will have one change only if the size of the substring is 2. Here you know you can't do better because in a substring with only two elements you can have zero or one changes, but having zero instead of one won't increase the number of good indices because regardless of the sorting, there are $x$ characters of that type and the substring with that character in the first and last position will always be $\frac{x(x-1)}{2}$.Hope that helps :))
•  » » » » 3 weeks ago, # ^ |   +12 I don't think this is true. Using order 1, n, 2, n-1, ... does not maximize the changes.Imagine the sequence 1, 2, 2, 2, 3. Using the order 1, n, 2, n-1, ... we would get 1, 3, 2, 2, 2. This is two changes. We can get five changes with the sequence 2, 1, 3, 1, 2.
•  » » » 3 weeks ago, # ^ |   0 Doesn't this not work for initial string "baa" which makes the new string "aba" which has less pairs than the original?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 OK, so I've thought about it, here's a better proof at least for me to understand. Let's just alternate characters, it's optimal because of the sum we need to minimize. If the most frequent character appears less than n/2 times in the string then we can alternate easily. Otherwise we can cap the most frequent character occurrence by n/2 and build an alternating string, but then we will have a block of the same characters left that we need to insert in the string somewhere. We can insert it only at the beginning or the end, because there it's going to be calculated in the sum only once.Pretty good problem actually, if you think about it, thanks.
 » 3 weeks ago, # |   0 Super fast Editorial...btw problems were good <3
 » 3 weeks ago, # | ← Rev. 2 →   0 Anyone has a solution for F without using randomization? I tried to using some kind of meet in the middle, but it's too hard to merge the answer
•  » » 3 weeks ago, # ^ |   +47 Here's a deterministic solution:Let's refer to elements with the same $b_i$ as a "class".Loop through all possible values of $2^{nd}$ and $4^{th}$ numbers and check the validity of the pair. Now, we have three more elements to fill: the one to the left, between two numbers, and the one to the right. For each of these, we know the range of possible values of $a$.Notice that if we consider the five best classes of elements of a set (with the highest maximum cost of elements belonging to that class), then the best element to select in this set will always be among those 5 (the other ones can ban at most 4 classes). So, we need the five best classes for all prefixes with $a$ bounded from above by the next element, and for all suffixes with $a$ bounded from below by the previous element. This can be precalculated easily in $O(n^2)$.The interesting part is what to do with the middle elements (they have both upper and lower bounds for $a_i$). We can maintain a segment tree that works sort of like a merge sort tree, but only stores the 5 best classes. The "key" will be the value of $a$. The segment tree is cleared for each new value of second element, and as we iterate over the fourth elements, we add all the stuff that we already passed to the segtree. So, we can get the middle elements in $O(5 \log n)$.Finally, we just have to merge the three groups of $5$ values using $5^3$ time.The final time complexity is $O(n^2 \log n + n^2 5^3)$, or $O \left( n^{\lfloor \frac{m}{2} \rfloor} \left( m \log n + m^{\lceil \frac{m}{2} \rceil} \right) \right)$ in the general case, which is (barely) good enough.P. S. Please excuse my usage of numbers inside $O()$ notation here, it was just too convenient to write it like that :)
•  » » » 3 weeks ago, # ^ |   +8 I think this meet-in-the-middle solution works in $O(24 * n^2)$: 278171336.I maintain the top 3 answers for pairs ending at i as L[i], and for pairs starting at i as R[i]. Since all pairs ending at an index have the color of that index, we need to store the best 3 pairs of different second color. So L[i] would have answers with (x, b[i]), (y, b[i]), (z, b[i]).Now we can brute-force the 3rd element $i$ (when k = 5) and merge it with the best 1st and 2nd element across all L[j] (j
•  » » » 3 weeks ago, # ^ |   0 I got the same idea and had a bad time inplementing that :)The constant factor is too large for the segtree part and I can only store the 2 biggest values. Beside that some optimizations on the constant factor is also needed for me.Anyway the data was weak enough for that to pass 278190335
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +72 The technique in Problem F can be directly derandomized.We need a family of hash functions $\mathcal{H} = \{ h_i \colon [n] \to [k] \}$ such that for any subset $S \subseteq [n]$ of cardinality $k$, there exists a hash function $h_i$ in $\mathcal{H}$ that satisfies $h_i(S) = [k]$. This is known as an $(n,k,k)$-splitter. Once we have such a splitter, we can solve the problem by trying each hash function $h_i$ from this family.Randomly selecting a hash function is likely sufficient with high probability when $|\mathcal{H}|$ is sufficiently large. Note that for each $S$, the probability that none of the $h_i$ splits $S$ is $\left(1 - \frac{k!}{k^k}\right)^{|\mathcal H|},$there are $n^k$ many such subsets, so we need $n^k \left(1 - \frac{k!}{k^k}\right)^{|\mathcal H|} \leq n^k \cdot \exp\left( - \frac{k!}{k^k}|\mathcal H| \right)$is much smaller than $1$. We need to take $|\mathcal H| \geq \frac{k^k}{k!} \cdot k\log n$.The difference between the analysis above and the official solution is that, once you generates a good $\mathcal H$, it doesn't only works correctly for a current test case, it universally works for all test cases! One practical solution is to hardcode a random seed in your program that has been verified to generate a splitter $\mathcal{H}$.BTW, the explicit construction of an $(n,k,k)$-splitter is theoretically nearly settled by the paper "Splitters and Near-Optimal Derandomization". The authors show how to construct a family of size $e^k k^{O(\log k)} \log n$. Note that the probabilistic method gives $\frac{k^k}{k!} \cdot k\log n$, and since $\frac{k^k}{k!} \approx e^k k^{1/2}$, the explicit construction is quite close to the probabilistic bound.
•  » » » 3 weeks ago, # ^ |   +3
•  » » » 3 days ago, # ^ |   0 I like the idea and firmly believe such splitters exist, but how to verify that the constructed $\mathcal{H}$ is indeed a $(n, k, k)$-splitter? Is there a deterministic approach or just checking a lot of subsets is enough? How many subsets should I check to verify that it is a splitter with 99.9999% probability?
•  » » » » 3 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } Good question, I'm not sure is there any algorithm significantly better than checking all the $k$-subsets...
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Thanks for your help, I have got AC using some kind of MITM :). Feel free to hack my submission!
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I have tried to uphack my submission which editing the magic constant MAX_HOLD into $15$ or $20$ but not successful. Can anyone help me to hack this and this, or prove that is enough for solving this problem? Thanks!
 » 3 weeks ago, # |   0 In the problem C, can we just rotate the character of array and just print it?? or missing something!?
•  » » 3 weeks ago, # ^ |   0 what do you mean by "rotate"? because if it means reversing the string then no, if so then the number of good pairs would remain the same.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 j guess by rotating they meant moving all characters one indice forward and sending the last character to the first place. for example "codeforces" would become "scodeforce"
•  » » » 3 weeks ago, # ^ |   0 moving all characters one indice forward and sending the last character to the first place. for example "codeforces" would become "scodeforce"
•  » » » » 3 weeks ago, # ^ |   0 well, if you passed this problem, then this solution might as well be right, but otherwise i don't really think so, as the increment of good pairs count can't be more than n-1
•  » » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 yes, it failed in test-case 2 Can you tell -What's does this means- wrong answer Participant's answer is worse than jury's: jans = 6, pans = 5. (test case 18) link — 278153049
•  » » » » » » 3 weeks ago, # ^ |   0 i think it means whilst your answer consists of 5 good pairs (pans means participant's answer), the jury's answer has 6 of them
•  » » 3 weeks ago, # ^ |   +3 It wouldn't work. If you have, for example, "edddfg", you rotate and get "gedddf", but "gefddd" is better.
 » 3 weeks ago, # |   0 D1 was nice :)
•  » » 3 weeks ago, # ^ |   0 D2 is even nicer. Problem looks difficult. but all you have to do is, travel from left to right, and right to left. and keep propagating the maximum. that's it.
 » 3 weeks ago, # |   +3 got TLE on D at the last minute by using loop from 0->m :)
•  » » 3 weeks ago, # ^ |   0 same, damn
 » 3 weeks ago, # |   0 terrible contest! D is much easier then C, B can only be guessed, not solved.Also I got RE26 on D2 using c++20 and WA30 using c++17, how can this be?
•  » » 3 weeks ago, # ^ |   0 Sorry to bother, could D2 be solved by using union-set to get maximal for each vertex?
•  » » » 3 weeks ago, # ^ |   0 Idk, I used only dp
•  » » » » 3 weeks ago, # ^ |   0 also used dp and got rt, make sure that u are initializing dp to the longest size of l_i read
•  » » 3 weeks ago, # ^ |   0 B can be reframed that the person trying to minimise removes the largest number possible, and the person maximising tries removing the lowest number possible.. so in the end, after they cut off all of the numbers from both ends turn by turn.. only thing remaining is the median of the sorted array..
•  » » » 3 weeks ago, # ^ |   0 Exactly
•  » » 3 weeks ago, # ^ |   +8 how can C and B (or D) be guessed
 » 3 weeks ago, # |   0 I tried constructing solution of B the way the game is played(now realized it wasn't optimal)still where has my solution gone wrong 278140256 .Also can you guys suggest resources to build logic and concepts to solve upto div2 C,thanks in advance!
•  » » 3 weeks ago, # ^ |   0 Just practice more div2 C problems and learn the topics needed to solve them if you get to know about some new topic during practicing.
•  » » » 3 weeks ago, # ^ |   0 Thank you for your response!
 » 3 weeks ago, # |   +11 My first contest with AC on div2C. ThankyouThankyouThankyouThankyou!
 » 3 weeks ago, # |   +5 W contest!
 » 3 weeks ago, # |   0 It was a great contest, and I'll soon achieve the "pupil" rank. The first three questions were easy, and I figured out the correct logic for the fourth one. I got a TLE on test 3, and I initially thought it was because I used a set, but later realized it was actually due to m being >= 1e9. Overall, it was a fantastic contest, and I'm looking forward to more like this in the future.
 » 3 weeks ago, # |   +8 It seems that the "In this version of the problem, you can choose the same integer twice or more" suggests the hint "choose the same integer twice" obviously. But D2 is a good problem for Codeforces div2 D. I guess the difficulty of it is *2000.I want to mention that I do too much guesswork in this round. Especially B and C. Although it doesn't matter that this round is a good round for me. Thanks. :D
 » 3 weeks ago, # |   +1 Problem D is really cool!
 » 3 weeks ago, # |   0 solved A and B quite fast but C went right over my head, and the tutorial doesn't help either. I'll keep trying though, ain't no way I'm moving forward without an AC in problem C
 » 3 weeks ago, # | ← Rev. 2 →   0 Weak system tests for C.My code: 278099825A very stupid mistake, I forgot to sort the characters by how often they occur in s, as a result for the test:14ddbcMy code outputs: bcdd (which has 2 good pairs: (0; 2); (0; 3))One of the correct answers: dbcd (which has 3 good pairs: (0; 2); (0; 3); (1; 3))Despite this, my code has passed the system tests and got AC
•  » » 3 weeks ago, # ^ |   +3 you shouldn't count (0, 3) in dbcd since it's the same character so it wont count in the additional good pairs
•  » » 3 weeks ago, # ^ |   +6 You code output has also one more good pair : (2,3)
•  » » » 3 weeks ago, # ^ |   0 Yes, you are right. Thank you. I am sorry. I didn't notice that there exists pairs with len of 2 that can be a good pair
 » 3 weeks ago, # |   +7 I think it's harder to find the right strategy in C than in D1.Thanks for D2. It was fun(And yes, I will finally turn blue)
 » 3 weeks ago, # | ← Rev. 14 →   0 .
 » 3 weeks ago, # | ← Rev. 3 →   +23 Alternate solution to E1 : Lemma 1 : Every interval must have either exactly 1 0, or exactly 1 1(where the definition of 0s and 1s are same as editorial)Proof : The optimum solution must be a local minimum. Fix the other segments and vary the number of 0s and 1s in one segment, it is a quadriatic function with central maxima. Hence, it is minimized at the ends of allowed ranges. Lemma 2 : Some prefix of intervals will have 1 1, and some suffix will have 1 0, proof is left as an exercise Just brute the prefix, and find cost to get O(m^2). Extending to E2 is trivial as left as an exercise. This can probably be extended to get a near-linear solution by computing cost(prefix + 1) — cost(prefix) fast, but i am too lazy to work out the details.
•  » » 3 weeks ago, # ^ |   0 Here's a $\mathcal{O}(m)$ solution for E1 278231107 Proof of correctnessIt's quite obvious that it's efficient to have all 1s in $[1, l_1 - 1]$, one 0 in $[l_1, r_1]$, all 0s in $[r_m + 1, n]$ and one 1 in $[l_m, r_m]$ no matter what numbers are used in $[r_1 + 1, l_m - 1]$. Since the numbers in the interval $[r_1 + 1, l_m - 1]$ can be chosen independently from those which are in it's complement, induction can be applied.
 » 3 weeks ago, # |   -8 This my first Div2 contest I solved 3 problems :)
•  » » 3 weeks ago, # ^ |   0 Why this much hate :( did I post anything wrong?
 » 3 weeks ago, # |   0 in problem F, why is the probability of getting the optimal solution in one attempt is $\frac{m!}{m^m}$ ?
•  » » 3 weeks ago, # ^ |   +3 Consider a set S = {s[1],s[2],...,s[m]} of all distinct b[i] in an optimal answer. To be able to get this answer from bitmask dp, all f(s[i]) must be distinct, where f(x) is mapping from x to a random number in [1,m]. The number of such mappings is m!*(m^(n-m)), m! is because f(s[i]) must form a permutation, m^(n-m) is because for any b[i] not included in S ,f(b[i]) can be any number and it doesn't affect answer. Number of all possible mappings is m^n, since for each b[i] there are m possibilities. Then, the probability of finding a mapping, where we can get an optimal answer is m!*(m^(n-m))/m^n = m!/m^m .
 » 3 weeks ago, # |   0 Hi, please check this 2 submissions, they have mostly the same code, the only difference is that the vectors are global in the first one. The second code gives TLE and by a big margin. Is this a bug or what? https://mirror.codeforces.com/contest/2003/submission/278156729 https://mirror.codeforces.com/contest/2003/submission/278156524
•  » » 3 weeks ago, # ^ |   0 Definitely not a bug. You're creating vectors of size 2e5 for every test case. It's a common mistake.
 » 3 weeks ago, # |   +17 top 3 reason for depression breakup Substance Abuse WA in div2 A
 » 3 weeks ago, # | ← Rev. 2 →   +19 I solved F deterministically in $\mathcal{O}(n^2 * k^3)$:Let’s say we compute $dp(i,j)$ = answer if we have to take $j$ elements from the suffix of the array starting at position $i$. In order to avoid repeating some values from $b$, we also store the vector of chosen values (let’s call it $V$).The issue is that choosing exactly those values may “block” you later. To prevent this, we also compute the best answer if we avoid using each of the values from $V$ separately. It’s easy to see that one of these $k+1$ candidates will be optimal.Although my code’s complexity is $\mathcal{O}(n^2 * k^3)$, I believe it can be improved to $\mathcal{O}(n^2 * k^2)$. Given that I got AC in the last 12 seconds of the contest, I didn’t have time to even think about optimizing anything.Here is my submission: 278149543 :)
•  » » 3 weeks ago, # ^ |   +38 Hacked with this test case: 6 4 1 2 3 6 5 4 3 2 4 3 2 1 1 1 1 2 2 1 When you get to the suffix starting with b = 4, you'll only keep {4, 2} and {4, 3} as options for your b-values. But you actually need to use {4, 1} because of the 2 and 3 on the left.
•  » » » 3 weeks ago, # ^ |   0 Good catch! I’m surprised that there are over 60 testcases and none of them cover scenarios like this one you describe
•  » » » » 3 weeks ago, # ^ |   0 Bad setting imo, this problem needed multitests
 » 3 weeks ago, # |   0 I really can't get this: the first player can remove a number adjacent to a larger number, while the second player can remove a number adjacent to a smaller number.
•  » » 3 weeks ago, # ^ |   0 You can think of it as. 1 player can pick any 2 numbers and remove the smaller one, and the other player can pick any 2 numbers and remove the bigger one
 » 3 weeks ago, # |   0 Hey everyone, does anyone have any advice for coming up with proofs for problems (apart from solving more problems or working with smaller cases)? I have realized that I can often think of the solution, but can't prove it, so I don't end up implementing it. Any help would be greatly appreciated! :D
•  » » 3 weeks ago, # ^ |   0 well I think it's fine to try and implement a solution even if you haven't completely proved it. while implementing it, you might actually notice the flaw and then you can correct it, or start coming up with a new solution. this can waste a lot of time, if you're not efficient at implementing, but it's a decent approach if you find yourself not being able to prove easy problems
 » 3 weeks ago, # |   0 What topics should I learn to solve D1 and D2?
•  » » 3 weeks ago, # ^ |   0 dp — ad hoc?
 » 3 weeks ago, # | ← Rev. 2 →   0 I got compilation error twice in B, when I was using g++20, but the same code got accepted in g++17. Why did this happen? Compilation error 1 : https://mirror.codeforces.com/contest/2003/submission/278061013 Compilation error 2 : https://mirror.codeforces.com/contest/2003/submission/278072152Pretests passed : https://mirror.codeforces.com/contest/2003/submission/278078881delayed my submission from 8 mins to 22 mins :(
 » 3 weeks ago, # |   0 I guessed B and C
 » 3 weeks ago, # | ← Rev. 3 →   0 Can anyone please explain, how, in example 1 for problem D1, f(4) = 4
•  » » 3 weeks ago, # ^ |   0 just dont do anything? x is 4 and you can leave it be
•  » » 3 weeks ago, # ^ |   0 Oops!! I got it now.. We can do zero operations to get max value of x as 4 itself.
•  » » » 3 weeks ago, # ^ |   0 it took me about 10 mins to understand why f(4)=4 :(
 » 3 weeks ago, # | ← Rev. 2 →   0 In D1 first test case 3 4 2 0 2 3 2 3 3 4 7 0 1 5 how is f(4) = 4, can someone explain? thanks
•  » » 3 weeks ago, # ^ |   0 Perform zero operations on x
•  » » » 3 weeks ago, # ^ |   0 yea thanks got it
 » 3 weeks ago, # |   0 can someone help me with problem D1?
•  » » 3 weeks ago, # ^ |   +1 the result of mex(x,ai,1,ai,2,…,ai,li) for every sequence is only two possible mex!for example a0= {0, 1, 3, 4} the mex of this sequence is {2, 5}if(x == 2) mex = 5, else mex = 2. and since i can choose every sequence multiple times, then whatever the value of x is, i can get 5 (f(2) --> 5, f(number != 2) --> 2 --> f(2) --> 5)so calculate each two mex for all sequence and choose the max_mex then the result is(max_mex * numbers_less_than_or_equal_to_max_mex) + (max_mex + 1) + (max_mex + 2) + .... + m
•  » » » 3 weeks ago, # ^ |   0 Thanks
 » 3 weeks ago, # |   0 278173974 (D2) I think the approach is similar to the editorial sol but I have no clue why it's failing, can someone help?
•  » » 3 weeks ago, # ^ |   0 Take a look at Ticket 17495 from CF Stress for a counter example.
 » 3 weeks ago, # |   0 I made a big mistake of starting to code problem D before working the example cases to ensure i understood the problem. Too bad I missed a crucial part even after the notification during contest that we can pick multiple sequence and moreover we can pick the same sequence any number of times. This misunderstanding led me to solve a completely different problem.
 » 3 weeks ago, # | ← Rev. 4 →   +17 E1 (Edit: and E2) can be solved in O(n) time: Solution for E1The key observation is that after sorting 0's ("small" numbers) and 1's ("big" numbers) in descending order (separately), the number of inversions of form (i, j), where the j-th number is "small", is equal to the sum of indices of all "small" numbers (using 0-indexing). That is because for a given "small" number, it is smaller than any previous number, since 1) all previous "small" numbers are greater because we sorted them in decreasing order, 2) it it smaller by every previous "big" number, by definition. So the total number of inversions is equal to $\frac{b(b-1)}{2} + \sum_{}^{}i_0$, where $b$ is number of "big" numbers, and $i_0$ is a set of indices of "small" numbers.Let's define a gap interval like this: for any adjacent pair of intervals $(l_x, r_x)$ and $(l_{x+1}, r_{x+1})$, $(r_x+1, l_{x+1}-1)$ is gap interval. Additionally, the border ones: $(1, l_1-1)$ and $(r_m+1, n)$ are also gap intervals. Now, another observation is that for any non-empty gap interval in an optimal permutation, it can be split into 2 parts, such that the left part consists of only "big" numbers and the right one consists of only "small" numbers (note that some part can be empty, so the whole gap interval may be filled with number of one type). That is because it is always optimal to sort the interval by decreasing order. So, we can sort of "extend" each normal interval to the left adding some "small" numbers, or to the right, adding some "big" numbers.The solution is greedy: First assume that the permutation contains as many "big" numbers as possible, so for every interval, only the first element is "small" and we extend each interval to the right, so each element in a gap interval is "big". Now, we will gradually extend "small" numbers by extending intervals to the left (while shrinking the previous interval's right border) or, for a given interval, assuming that k+1 first elements are "small", instead of k. Now, what happens with our answer when we switch the i-th element from "big" to "small"? Basing on the first formula and doing a little bit of math, it turns out that the answer increases by $i+1-b$ (this number can be negative, so the answer can actually decrease), also note that after the operation, the value of $b$ decreases by one. Is is quite intuitive and easy to prove that we want to first expand the "small" numbers into largest indices, that way our answer will increase the most. So we expand in the following order: first, expand from the right border as much as we can. Then, expand the last interval into the right as much as possible, then to the left. Next, take the second last interval and do the exact same thing, and so on. Keep track of the answer in each point in time, and the final answer to the problem is the maximum one. Solution for E2(Read the solution for E1 first)The idea is pretty much the same as in E1, but additionally we need to check whether a solution exists, and if so, for every $i$ check if the i-th element must be "small", must be "big" or can be any (let's call the third case the free elements). We first assume all free elements are "big" and just like we did previously, we will increase the number of "small" elements by expanding them into free elements (starting from the largest indeces, same as in E1). Implementation for E1 is very straightforward: 278182451. E2 is a little messier, but still not that bad: 278261466
 » 3 weeks ago, # |   0 Thank you for interesting problem.I've got +64!
 » 3 weeks ago, # |   0 Can someone help me with my solution of d2,which got WA on 27? 278147838Thanks
•  » » 3 weeks ago, # ^ |   +3 Take a look at Ticket 17496 from CF Stress for a counter example.
•  » » » 3 weeks ago, # ^ |   0 Got it,thank you.
 » 3 weeks ago, # |   0 I don't understand the solution for C problem, Can anyone explain what does ∑(i=1 to m−1) ai ⋅ ai+1 mean?, and how is it derived ?
 » 3 weeks ago, # | ← Rev. 2 →   0 what is ans for D1 for below testcase.2 01 02 0 3
•  » » 3 weeks ago, # ^ |   0 3 501 23 1 2 34 0 1 2 3And also ans to this.
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   0 Your test case: 2 0 1 0 2 0 3 ans: 2
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 So the ans to3 501 23 1 2 34 0 1 2 3 is 3 ???
•  » » » 3 weeks ago, # ^ | ← Rev. 5 →   0 No Actually, I wrote 2 as the answer to the first case you asked. But you asked the second question exactly the same time when I replied to your first query. You also can see the timing is almost the same.Your case: 3 50 1 2 3 1 2 3 4 0 1 2 3The answer to the second case is 1285 (5*4 + sum(50)-sum(4))
 » 3 weeks ago, # | ← Rev. 3 →   0 In problem D2, how is the answer to the 3rd test case 1281? Test case: 2 50 2 1 2 2 1 2 Answer: 1281 In my calculation, only 0 is the only value on which an operation can be made to get the 3. For other values (1 — 50), just take the value itself to get a better answer. So, it's the same as: 1+2+3+...+50. And, we'll get 1275 and +3 (that we got from the value 0). Then in total, it'll be 1278. But I didn't understand how the answer was 1281. Where is this extra 3 coming from?
•  » » 3 weeks ago, # ^ |   0 For x = 1, 2. First apply the operation for i = 1. So x = mex(x, 1, 2) = 0. Now, you can apply the operation for i = 2, x = mex(0, 1, 2) = 3. So, optimal value for x = 0, 1, 2 is 3.
•  » » 3 weeks ago, # ^ |   0 For values 1 and 2 you can use the first sequence to get x=0, and then use the zero with the second sequence to get x=3.
 » 3 weeks ago, # |   0 Have a question about D13 2 3 3for f(2) put mex(2,2,3,3) is 1 and put mex(1,2,3,3) is 4.Did I misunderstand the description?
•  » » 3 weeks ago, # ^ |   0 actually, you also have to consider 0 as well (non-negative). So, or f(2) put mex(2,2,3,3) is 0 and put mex(0,2,3,3) is 1
•  » » » 3 weeks ago, # ^ |   0 Oh my bad thanks
 » 3 weeks ago, # | ← Rev. 2 →   0 Can any one explain for 2003C - Turtle and Good Pairs, why PyPy3-64 is being slower here 278121635 and getting TLE and also the memory limit, when the same code works fine with Python3 here 278206914. Thought PyPy always works faster than Python, what am I missing?
 » 3 weeks ago, # |   0 in the first problem we can write this string "abcda" by your code it's (NO) , but we can split it into : ab cd a , so why ??
•  » » 3 weeks ago, # ^ |   0 First character of string ab is equal to the last character of string 'a' which is not good according to the problem statement so answer is no for this testcase.
 » 3 weeks ago, # |   0 Did the second example in D1 change during contest?? Or I am having Mandela effect...
 » 3 weeks ago, # |   0 https://mirror.codeforces.com/contest/2003/submission/278211183this is my submission can anyone help me which case i am missing ??
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 if(expected==(int)het.size()&&flag==1){ expected++; } Just update this
•  » » » 3 weeks ago, # ^ |   0 thanks
•  » » 3 weeks ago, # ^ |   0 hintwhen do you increase expected after the while loop ? answeryou only increae it when flag==1
 » 3 weeks ago, # |   0 Can someone tell me why my code Wrong on C test3wrong answer Participant's answer isn't a permutation of the given string. (test case 267)278220017
•  » » 3 weeks ago, # ^ |   0 I find it...char s[N], n; char s[N]; int n;
 » 3 weeks ago, # |   0 https://mirror.codeforces.com/contest/2003/submission/278254550Can someone please figure out why it is giving TLE
 » 3 weeks ago, # | ← Rev. 2 →   0 Please can anyone explain to me Problem C's solution, I am unable to understand the intuition and the approach through the editorial given?
 » 3 weeks ago, # |   0 In problem B why is it always best for Turtle to remove the i'th smallest element and not to maintain the current count of the current maximum element? Same argument for Piggy
 » 3 weeks ago, # |   0 The solution of D1 was O(n * l) and 1 ≤ n ≤ 2⋅10^5, 1 ≤ l ≤ 2⋅10^5 then why it does not give TLE
•  » » 3 weeks ago, # ^ |   0 sum of $l_i$ in all test cases dont exceed $2 \cdot 10^5$
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 ok i got it, thank you
 » 3 weeks ago, # |   0 I need some help with debugging my code, I seem to have every edge case covered, yet I find myself with a WA on Test 27 :( https://mirror.codeforces.com/contest/2003/submission/278263899
 » 3 weeks ago, # |   0 Solution to E1/E2 was a little hard to understand, so I'll write mine Separation of numbers into small/big parts was also very hard to understand, so I'll write the explanation too Consider the border of $max\ a_i = A$. Now, for some optimal answer convert every number into $0$ if $\leq A$ and $1$ otherwise. It's guaranteed by construction, that all numbers in the left parts are $0$ and right parts are $1$. On the other hand, if we have some 01 coloring, we can provide an answer greedily. That's why the iff (if and only if) statement is true.Now let's solve the whole problem. What do we want the segments to comply with in a 01 coloring? The leftmost element must be $0$, the rightmost element must be $1$ and the numbers in the segment must be non-decreasing, or in the other words for each $i$ in $(l, r]$ $c_{i - 1} \leq c_i$ must be true.Let's try and build some DP, in which checking this would be easy. We want to be able to check the previous number and update the total number of inversions. I think the most straightforward DP to try here is $dp[prefix][count\ of\ 1][last element] = \text{the max number of inversions on a prefix with given number of ones}$. The transitions are easy. If we add a $0$, it's the smallest number amongst the prefix, so we need to add $prefix$. If we add a $1$, it's the smallest number amongst ones, so we add $count\ of\ 1$.Now, how do we check the conditions on the segments? Just don't iterate over states and transitions that are impossible. If the current number is fixed, just iterate over it. If we should check index $i$ to be not less than $i - 1$, do that. That's it.Solution 278270951
 » 3 weeks ago, # |   0 Can anyone please explain to me how the following tc answer is 16 for D2? 3 4 2 0 2 3 2 3 3 4 7 0 1 5 isn't here f(0)=3, f(1)=3, f(2)= 2, f(3)=3, f(4)=4? and total is 15.
•  » » 3 weeks ago, # ^ |   0 In f(2), you find mex for 3-th sequence: mex(2, 7, 0, 1, 5) = 3 so you got f(2) = 3. (Sorry for my bad english)
 » 3 weeks ago, # |   0 Can anyone please explain the approach for problem D2
 » 3 weeks ago, # |   +5 O(N) solution for E1. The logic is based on examples and reasoning, despite not a complete and rigorous proof. https://mirror.codeforces.com/contest/2003/submission/278303362 The idea is to assign value 0 or 1 to a signature array that can be used to uniquely yield the optimal permutation (similar to the concept in tutorial). There are 2 separate passes. In the first pass, we handle intervals in head and tail and meet in the middle, and maintain counters for number of 0 in prefix and number of 1s in suffix. It is optimal to place 0111...1 in head if pre0 <= suf1 and otherwise place 00...01 in tail. In the second pass, we handle indexes not within any interval. In this phase, it is optimal to have value 1 at the index if pre0 < suf1 and 0 otherwise.
 » 3 weeks ago, # |   0 Hi, this is my first comp, but had a little trouble understanding q A. The editorial says, the answer is just comparing the first and last letters of the string, but couldn't you split the string up in such away, that substrings 1st and last letters would be different without the first and last letters being the same? For example the string "AABA", though the first and last letters do not match, cant we divide the string like this? — "A", "AB" and "A", such that i can just choose t0 to be "A" and t1 to be "AB", The first and last being different? Maybe I didn't properly understand qA?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 U are right but T1=AB and T2=A, so the first and last character match for i=1 and j=2.As for the solution, it's standard greedy solution. If the first and last characters donot match, we can split the string in 2 parts. First part has all characters except the last one and second part has the last character from s.
•  » » » 3 weeks ago, # ^ |   0 I understand. Thank you!
 » 3 weeks ago, # |   0 why wa test 2 ? [submission:https://mirror.codeforces.com/contest/2003/submission/278313212]
 » 3 weeks ago, # |   0
 » 3 weeks ago, # |   0 Love the rating predictions! Would love to see those on more editorials
 » 3 weeks ago, # |   0 Can someone tell me why my solution of D1 is not Working?https://mirror.codeforces.com/contest/2003/submission/278484674I doing exactly The same thing as the editorial aren't i?
•  » » 3 weeks ago, # ^ |   0 the first number on every sequence is it's size not an elements in it
•  » » » 3 weeks ago, # ^ |   0 Yeah i figured it outholy shit i felt really stupid though
 » 3 weeks ago, # |   0 problem D1 and D2 are beast... D1+D2 cost me 3 hours to upsolve it. DP on graphs are sure tough one.
 » 7 days ago, # |   0 In the editorial solution for D2, why are we allowed run a loop from $0-\min(m,k)$? I think I am missing something obvious, but according to the constraints the maximum value for $m$ is $10^9$. $k$ from the editorial is the $mex$ so theoretically they can reach the similar range for $a_i$ which is also $10^9$. Would it not result it TLE?