### cry's blog

By cry, 2 months ago,

Thank you for participating! We put a lot of effort into this contest. Special thanks to TheScrasse for contributing to these problems.

Rating Predictions

#### Solutions

##### 1942A - Farmer John's Challenge

Problem Credits: buffering
Analysis: buffering

Hint 1
Hint 2
Hint 3
Solution
Code (C++)
##### 1942B - Bessie and MEX

Problem Credits: buffering
Analysis: buffering

Solution 1

Hint 1
Hint 2
Solution
Code (C++)

Solution 2

Hint 1
Hint 2
Solution
##### 1942C1 - Bessie's Birthday Cake (Easy Version) and 1942C2 - Bessie's Birthday Cake (Hard Version)

Problem Credits: cry
Analysis: cry

Solution (Easy Version)
Solution (Hard Version)
Code (C++)

#### 1942D - Learning to Paint

Problem Credits: sum
Analysis: sum

Hint 1
Hint 2
Solution
Code (C++)

#### 1942E - Farm Game

Problem Credits: cry
Analysis: sum

Hint 1
Hint 2
Hint 3
Solution
Code (C++)

#### 1942F - Farmer John's Favorite Function

Problem Credits: sum
Analysis: sum

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)

#### 1942G - Bessie and Cards

Problem Credits: smax
Analysis: smax

Hint 1
Hint 2
Solution
Code (C++)

#### 1942H - Farmer John's Favorite Intern

Problem Credits: oursaco
Analysis: oursaco / rainboy

Solution 1
Code (C++)
Solution 2
Code (C++)
• +143

 » 7 weeks ago, # |   -31 Thanks for the Lighting fast editorial
•  » » 7 weeks ago, # ^ |   +21 ah you beat me
•  » » » 7 weeks ago, # ^ |   -30 It's a luck Sir
•  » » » » 7 weeks ago, # ^ |   +18 I don't understand. How do all of your comments get downvoted? They seem like pretty normal comments to me.
•  » » » » » 7 weeks ago, # ^ |   0 Because the original comment is unnecessary + kind of a cheeky way to exploit a human bias and get some upvotes.The downvotes on the reply are mostly continuing the process of "punishing" the same guy. Maybe punish is a too strong word, rather discouraging by means of downvoting is the correct expression.
•  » » 7 weeks ago, # ^ |   +24 Bro you're everywhere lightning fast
 » 7 weeks ago, # | ← Rev. 2 →   +8 second :(C was pretty tough imo
 » 7 weeks ago, # |   +10 How can you proof in F (the n>=6 observation)?
•  » » 7 weeks ago, # ^ |   +21 Since $a_i$ are bounded, I just bruteforced inserting bunch of 1e18's to see how far it propagates
•  » » 7 weeks ago, # ^ |   +10 Maybe it is the fact that the 64th root of $10^{18}$ is less than 2.
•  » » 7 weeks ago, # ^ |   +16 Because $\log_{2}\log_{2}n<6$.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +5 I'm very disappointed with the editorial writers for not including this proof.The most straightforward proof is obtained by considering the image of function $f(i, x)$ — the answer after considering $i$ elements, if $a_1 = x$.$|f(i, [L; L + len])| <= |sqrt(len)|$.This can be shown using the inequality $sqrt(a+x)-sqrt(x)<=sqrt(a)-sqrt(0)$, this is because sqrt is a concave function, this is a very intuitive claim, you can kind of guess this by looking at the sqrt(x) plot.With this we can show that $|f(i, [0; 10^{18}])| <= 10^{18/2^i}$.However this isn't a complete proof as the RHS will approach 1, but never actually reach it so it could be that $f(0) = x-eps, f(1) = x, f(10^{18}) = x+1$.Let's say we already know that f(i, x) takes only 3 values, the thing is either $\left \lfloor{\sqrt{x}}\right \rfloor = \left \lfloor{\sqrt{x+1}}\right \rfloor$ or $\left \lfloor{\sqrt{x+1}}\right \rfloor = \left \lfloor{\sqrt{x+2}}\right \rfloor$, so $f(i+1, x)$ will only take 2 values.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +11 or, more simply, we have that $a+b\le a+b+2\sqrt{ab}=(\sqrt a+\sqrt b)^2$$\implies\sqrt{a+b}\le\sqrt a+\sqrt b$$\implies \sqrt{a+b}-\sqrt b\le\sqrt a.$ Then $\sqrt{c+\sqrt{b+a}}-\sqrt{c+\sqrt b}\le\sqrt{\sqrt{b+a}-\sqrt b}\le\sqrt{\sqrt a}=\sqrt[4] a.$ This extends similarly for more nested radicals. Thus, increasing $a_i$ by $x<10^{18}<2^{64}$ will only affect $f(i+6)$ by at most $\sqrt[2^6] x =\sqrt[64] x<2,$ the desired result.
 » 7 weeks ago, # | ← Rev. 2 →   +24 Practice Problem for building intuition for problems like today's D: Learning to PaintI have added hints and thought process for D on CF Step.Practice Problem for learning the technique of merging k-sorted list.
 » 7 weeks ago, # |   -32 Man problem C was mega sexy... during contest it just gave my skills a serious reality check
•  » » 7 weeks ago, # ^ |   0 for real
•  » » 7 weeks ago, # ^ |   -10 It humiliated me
•  » » 7 weeks ago, # ^ |   0 I wonder to know why y is not used in problem C
 » 7 weeks ago, # |   +26 B can also be solved backwards using the observation that the prefix mex is equal to the suffix min. This idea also appeared in the Cyclic Mex problem recently.
•  » » 7 weeks ago, # ^ |   0 It took me 90mins to solve B :(
•  » » 7 weeks ago, # ^ |   0 can u explain more this idea ? the prefix mex is equal to the suffix min
•  » » » 7 weeks ago, # ^ |   0 If you have a sequence from 0 to n-1 (say). Then for any prefix of this sequence the mex will be the minimum element in the remainder of the sequence(suffix).
•  » » 7 weeks ago, # ^ |   0 could you please explain " mex = min(mex, p[i]) " this line in your code. why we will take minnimum value betwenn mex and p[i] as a new mex value ?
•  » » » 7 weeks ago, # ^ |   0 A permutation contains all values from $0$ to $n - 1$. The definition of Mex is the first non-negative missing integer. If you consider the $i-th$ prefix, then which elements are missing from this prefix? All elements in the suffix $p[i + 1], \dots p[n - 1]$ are missing from it. By definition of mex, the minimum missing element should be the mex.
•  » » » » 7 weeks ago, # ^ |   0 Thanks. Understood.
•  » » » » 7 weeks ago, # ^ |   0 I just want to know the concept but still can't get the logic.how this is work.Can you just explain a little bit of this concept.please..
 » 7 weeks ago, # |   +3 Can someone please explain the problem statement of D ?
•  » » 7 weeks ago, # ^ |   0 You can choose some subset of integers on $[1, n]$. The beauty of a subset is equal to the sum of scores of each maximal contiguous subarray of selected elements (e.g. you cannot extend the subarray more to the left or right). A score of a subarray $[l, r]$ is given by $a_{l, r}$. Find the $k$ greatest beauties possible from the $2^n$ possible subsets (including duplicates).
•  » » 6 weeks ago, # ^ |   0 I don't understand the statement of D either......It's like they don't want you to comprehend it :< they could've made it more clear in the Input or testcases description:(
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I take back my words. I found it a lot more comprehensible after reading others comments.Now it's simply that it is difficult:)
 » 7 weeks ago, # | ← Rev. 2 →   0 So many formulas in G :(((. Had the idea but probably bugged something there. Anyway, great problemset. It's funny that the "game" that problem E reduces to (by a series of really nice observations I'd say) (the game being subtract 1 from some number of piles) and the "paranthesis problem" that G reduces to both appear on cses in the problems Another Game and Bracket Sequences 2.
 » 7 weeks ago, # | ← Rev. 3 →   +44 By looking at $f$ as a big integer in a weird changing base, F can be quite easily solved with a modified version of a Trygub Number (Big integer with negative digits)254189455
•  » » 7 weeks ago, # ^ |   0 Is this the same Trygub as antontrygub ?
•  » » » 7 weeks ago, # ^ |   0
 » 7 weeks ago, # |   +3 Quoting problem E's editorial: The number of ways to place the cows in the available positions given the gaps will be $2 \cdot {l - s - n \choose n}$. Pardon me for being in the dark but why is this true? I thought it should be $l - s - 2n + 1$, since for each known set $(g_1,g_2,...,g_n)$, isn't it that the area of cows and inner gaps forms a solid block of $2n + s$ cells, and we would just need to find the starting place to put that block in?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 We are placing the location of each g, so each g counts for one space while choosing locations, which contributes a total of n, so it will end up being l-s-n at the top I am not sure where your +1 comes from
•  » » » 7 weeks ago, # ^ |   0 Wait a second, I got why I was wrong. My claim up above would only secure that $b_i - a_i = g_i + 1$, yet wrongly assume $a_{i+1} - b_i = 1$, which is not always the case.Thanks for your help!
 » 7 weeks ago, # |   +5 I could not solve beyond problem A. :(
•  » » 7 weeks ago, # ^ |   0 Yeah bro I coud not even solve problem A. Forgot there was a contest :(
•  » » 7 weeks ago, # ^ |   +8 Happens, :)Div.1+2 can be somewhat overwhelming to beginners, try some Div.3 problems, or AtCoder Beginner Contests.Also, given the length/duration of the contest, if you didn't solve A, do reassess your approach. Did you play around with some small testcases to see patterns? Looking at the editorial, what could you have done to notice things sooner, etc.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +5 I was able to solve problem A. But could not solve Problem B.I tried to make some observations, but the concept of MEX was somewhat new to me. I only know what it does, not fully studied it's other details+implementations.I do plan to upsolve and go through the editorial tomorrow.Thank you.
•  » » » 7 weeks ago, # ^ |   0 Can you explain the time complexity of B if there is a while loop for increasing mex?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Consider the outer for loop.For any given $i$, there would be at most 1 while-check for has[mex] that yields false (stopping the while loop).Also, consider the number of times that the while-check for has[mex] can be true over all $i$ in total? It is also bounded by $n$, as any time the check is true, mex increases, and mex can only go up to $n$.Thus, overall, the contribution of the considered while loop is $O(n)$
•  » » » » 7 weeks ago, # ^ |   +3 also think that the while loop doesn't start each time from the beginning it will continue from where it stopped before so the whole complexity will be N+N
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 You can also create a set containing the numbers 0 through $n$, and after using a number, delete it from the set. Set's first element will be the current MEX.The total complexity of these operations will be $O(n log n)$. Because set operations are $O(log n)$.
 » 7 weeks ago, # |   +3 For problem C (hard):I think it should be "whether $g$ is odd oe even, we can choose $\lfloor\frac{g}{2}\rfloor$ vertices to make $g$ extra triangles."For example, for a pentagon, if we have chosen $a=1$ and $b=5$, in which case $g=3$, then we can choose $\lfloor\frac{3}{2}\rfloor=1$ vertex ($3$) to make $3$ extra triangles ($123$, $135$, $134$). For a hexagon, if we have chosen $a=1$ and $b=6$, then we can choose $2$ vertices($3$ and $4$) to make $4$ extra triangles ($123$, $134$, $146$, $145$).
•  » » 7 weeks ago, # ^ |   +14 I wasn't counting the first case, solely the second case where the extra triangle shares one side with the $x$-polygon and two with the outer.
•  » » » 7 weeks ago, # ^ |   +3 Oh, I have just understand that. Thanks.
 » 7 weeks ago, # |   +17 My solution on problem D is kinda different and I have no idea why it works Basically you do as editorial says: dp[i] stores the best k values among the prefix [1...i]The bruteforce approach: iterate through the previous lists and see if you can get a better list by binary search. You are changing the last p values with the first p values and then you sort the list The optimized version: instead of doing for every index the updating, you are inducing a order to do so: sort them by the best value of list j + current cost induced by the ith element. And then you do like the bruteforce approach. I don't know if the tests are weak. It is 2-3 times slower then editorial approach.254190056
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 It seems that I used a similar solution to yours, the only difference is that you used binary_search but I used priority_queue. I am also seeking hack data for my solution. 254165883
•  » » 7 weeks ago, # ^ |   +67 Hacked with the same test case as in this comment.
 » 7 weeks ago, # |   0 Can anyone explain the time complexity for the B solution code? How does iterating over the HAS array impact the overall time complexity?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 it's O(n) as we are traversing each element of P and has array only once
•  » » » 7 weeks ago, # ^ |   0 Can you please explain ?
•  » » » » 7 weeks ago, # ^ |   0 as variable mex is all increasing you are going each index of has array only one. sorry i cant explain better than this may be you read this or watch some tutorial about time and space complexity
 » 7 weeks ago, # |   0 A reminder to focus more on geometry .
 » 7 weeks ago, # |   0 Thanks for an Amazing round and a wonderful tutorial, Can someone help me with my code in problem D, I believe I have the same idea with very similar complexity O(nk log(k)). However, it got TLE and I can't figure out why... Here's my submission: 254196468
•  » » 7 weeks ago, # ^ |   +3 Your complexity is $O(N \cdot k^2 \cdot log(k))$.For any index $i$, you are iterating over all $j < i$, which contributes $O(n)$.For each each index $j$, you are iterating over its complete multiset, which contributes $O(k*log(k))$ for each such $j$.
•  » » » 7 weeks ago, # ^ |   0 Oh, thanks, do you have any idea how to speed it up?
•  » » » » 7 weeks ago, # ^ |   +6 Yes, it's a famous interview problem. Given $k$ sorted lists, how do you merge them?The trick is to insert the indices of all the lists in a max heap, with a custom comparator that assigns highest priority to the index with the highest $a[ind]$.Then, you pop $k$ times from this modified heap. The time complexity is now $O(k*log(k*n))$Standard Problem Link
•  » » » » » 7 weeks ago, # ^ |   0 Thank you, thank you, I'm both glad for almost having the solution and disappointed for missing it for a standard problem. Thanks again
•  » » » 7 weeks ago, # ^ |   0 Almost the same code, What a miss! 254211857
•  » » 7 weeks ago, # ^ |   0 Just to clarify the process my solution goes with:1- I assumed there's a source vertex 0 and a sink vertex 2*n+42- I assumed each node has two copies one that can start a segment and one that can end a segment, and the edges from nodeStart to nodeEnd have costs from the 2d array A. 3- Now we DFS from the vertex and calculate the DP of the highest K paths to the sink.
»
7 weeks ago, # |
Rev. 2   -18

I probably found the most interesting sol for the Question A, even idk why i did it -_- ;) ----------------------254136686--------------------------------------------------------

# include

using namespace std;

void solve() { int n,k; cin>>n>>k; int arr[n]; int res=1; if(k==1||k==n){ for(int i=1;i<=n;i++){ arr[i]=res; // cout<<res<<" "<<i<<endl; if(i%k==0){ res++; } } for(int i=1;i<=n;i++){ cout<<arr[i]<<" "; }cout<<endl; }else{ cout<<-1<<endl; }

}

int main(){ int t; cin >> t; while (t--) { solve(); } return 0; }

 » 7 weeks ago, # |   0 lol I misread and tried to solve G for cards of types 1, 2, 3 instead of 0, 1, 2
•  » » 7 weeks ago, # ^ |   0 lol, then the probability of winning is 1, b/c everytime you play a card you draw some of them instead of that one.
•  » » » 7 weeks ago, # ^ |   0 now I realize I even missed the first free 5 cards xD my game starts with just 1 card and she'll lose in cases like "1 1 1 special" or "2 special special" xD
 » 7 weeks ago, # |   +5 Did 3 after a long time.. :)
•  » » 7 weeks ago, # ^ |   0 how about div 3 very soon ?
 » 7 weeks ago, # |   +22 Loved problem C1 & C2.... thanks for such a beautiful question :)
 » 7 weeks ago, # | ← Rev. 3 →   0 Hello everyone, I used a weird algorithm to solve Problem D. 254165883I believe that my solution is wrong since that it should have $O(n^2*k*log(k))$, but I used a trick to speed it up. I guess that there is certain hack input, but it is really hard to construct. I failed to construct a sample data to hack myself. Can somebody help me to do that? Thanks!PS: Can somebody tell me how to insert collapsed code blocks? I think my code may be too long here.  for (int i = n; i >= 1; --i) { // dp[i + 1][1:k] -> dp[i][1:k] while (!PQ.empty()) { PQ.pop(); } for (ll x : dp[i + 1]) { PQ.push (x); } for (int j = i; j <= n; ++j) { while (PQ.size() > k) { PQ.pop(); } for (ll x : dp[j + 2]) { if (PQ.size() < k) { PQ.push (a[i][j] + x); } else { if (PQ.empty() || a[i][j] + x > PQ.top()) { PQ.push (a[i][j] + x); if (PQ.size() > k) { PQ.pop(); } } else { // a[i][j] + x <= PQ.top() // I believe that this following line is the trick helps me speed up my wrong solution break; } } } } while (!PQ.empty()) { dp[i].push_back (PQ.top()); PQ.pop(); } sort (dp[i].begin(), dp[i].end(), greater()); if (dp[i].size() > k) { dp[i].resize (k); } 
•  » » 7 weeks ago, # ^ |   +110 Hacked with $a_{i, j} = w_i + w_{i+1} + \ldots + w_j$, where $w_i = n - i$ is the weight of cell $i$.This way, the beauty of a painting is just the sum of weights of individual painted cells. In the best paintings, a long prefix of cells should be painted. And as you go in increasing order of $j$, you discover better and better solutions, substituting the previously found ones.
•  » » » 7 weeks ago, # ^ | ← Rev. 4 →   0 Out of curiosity, I tried something awfully similar but with randomly shuffling previous j values before iterating on them. Is it possible to make a test that TLEs on my solution?Solution: 254452137
•  » » 7 weeks ago, # ^ |   0 I believe I did something very similar to your approach and it passed: 254663089. Not exactly sure why this still passes after your submission was hacked.
 » 7 weeks ago, # |   +15 Nice problemset, thanks!
 » 7 weeks ago, # |   +1 Can someone please help me to understand why my code is failing on the 30th test case in test 2 in the problem C2: #include using namespace std; void solve() { int n, x, y; cin >> n >> x >> y; vector a(x); for(auto &i: a) cin >> i; sort(a.begin(), a.end()); int ans = 0, z = 0; for(int i = 0; i < x; i++) { int p = abs(a[i]-a[(i-1+x)%x]); // gap between two vertices a[i] and a[i-1] if(i == 0) p = n-p; // a[0]-a[n-1] handled separately if(p == 2) ans++; // if it forms a triangle else if(p > 2) { int q = min((p-1)/2, y); // minimum of points that I can add(y) and points that are available between a[i] and a[i-1] (gap size-1)/2 z += q; // added points count increase ans += q; // equal number of triangles formed if(q*2+2 == p) ans++; // gap(p) == 2*q + 2 means an additional triangle can be formed, this is an edge case y -= q; // added points count decreased from available points y = max(0, y); // if y has not become negative } } z += x; // z vertices added, x was initially while(z >= 3) { ans += z/2; z -= z/2; } cout << ans << "\n"; } int main() { int T = 1; cin >> T; while(T--) solve(); } 
 » 7 weeks ago, # | ← Rev. 3 →   0 pleasae help me debug hard C https://mirror.codeforces.com/contest/1942/submission/254210357(nvm found the bug %2 was missing)
 » 7 weeks ago, # | ← Rev. 2 →   +20 I believe my solution to D is $O(n^2+k)$. It uses Eppstein’s algorithm.254149567 (implementation from this blog)
 » 7 weeks ago, # |   0 Rating predictions are actually pretty accurate
 » 7 weeks ago, # |   0 cryCan you provide the test cases for problem C2, I need test 2My code fails at 30th test case in test 2
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 In your code, it seems that you just process the distances one by one. You have to process the even distances from small to large, and then the odd distance from small to large. Please try the follow test case (not official): 1 80 8 2 1 12 23 34 45 49 53 57 Answer: 12, Your output: 10
•  » » » 7 weeks ago, # ^ |   0 Thanks buddy, after I read the editorial I figured it out that I didn't spend time thinking about the difference odd and even creates just simply went with the solution, thanks!
 » 7 weeks ago, # |   0 can someone explain problem B in a little bit more detail please ?
•  » » 7 weeks ago, # ^ |   +1 U have to set a[i] = MEX(p1, p2,...,pi) - p[i] according to the problem statementRearrange it, p[i] = MEX(p1, p2,...,pi) - a[i] for each index i, you have two options:- p[i] = MEX till index i-1 Spoilerthen MEX for index i will be next element not used so far to construct permutation array p which can be retrieved from a set that is initially containing every element from 0 to n-1p[i] != MEX till index i-1 Spoilerthen MEX for index i will remain same as MEX for index i-1, which meansp[i] = MEX-a[i]My code implementation:- Spoiler#include using namespace std; void solve() { int n; cin >> n; vector a(n); for(auto &i: a) cin >> i; vector ans; set s; for(int i = 0; i < n; i++) s.insert(i); int MEX = 0; for(int i = 0; i < n; i++) { // case 1... p[i] == MEX then MEX == *s.begin()... // case 2... p[i] != MEX then MEX remains same... s.erase(MEX); if(s.empty() == true) { if(n-a[i] == MEX) { ans.push_back(MEX); MEX = n; } else { ans.push_back(MEX-a[i]); s.insert(MEX); s.erase(MEX-a[i]); } } else { if(*s.begin()-a[i] == MEX) { ans.push_back(MEX); MEX = *s.begin(); } else { ans.push_back(MEX-a[i]); s.insert(MEX); s.erase(MEX-a[i]); } } } for(auto &i: ans) cout << i << " "; cout << "\n"; } int main() { int T; cin >> T; while(T--) solve(); } 
•  » » » 7 weeks ago, # ^ |   0 how did we come to a conclusion that mex will increase whenever there's a positive element coming and in case of negative it remains same..
•  » » » » 7 weeks ago, # ^ | ← Rev. 4 →   +11 There are only 2 things the MEX can do: increase or stay the same (it can never decrease since we are looking at larger and larger prefixes).In the case of a positive difference, if the MEX stayed the same then it would have to be greater than the current value, which is impossible because that value had to appear earlier on in the prefix. Since the MEX is calculated on a permutation that can’t happen. So it has to increase.In the case of a negative value, the MEX has to be less than the current value. But if it increased that means the current value changed its MEX, meaning its new MEX is at least (current value + 1) and it is actually greater. So it has to stay the same.
•  » » » 7 weeks ago, # ^ |   0 u mean a[i] instead of p[i] right ?
•  » » 7 weeks ago, # ^ |   0 Hmm, I wrote a proof for the last line in the editorial: "you can show that P is unique," but I think a lot of that proof helps you understand the original problem too: https://mirror.codeforces.com/blog/entry/126942#comment-1135215.
 » 7 weeks ago, # |   0 In A's solution: For k=1, the construction 1,2,3…n will always work because in any other cyclic shift, 2 will be before 1.It should be n will be before 1.
•  » » 7 weeks ago, # ^ |   0 fixed :D
 » 7 weeks ago, # |   0 I solved C1 and was so happy for solving 3 problems only to discover after the contest that B got TLE. The phrase "If there are multiple possible p, it is enough to print one of them" confused me, so I made solved it using backtracking instead of a straight forward approach. I wish we had stronger test cases during the contest.
•  » » 7 weeks ago, # ^ |   0 Very sad and unfortunate. But you should also be a bit self-critic as well. It's not a super complicated instruction! In any constructive solution providing problem, of course it's possible to have multiple ways to do a task (construct an answer), and the question should come to your mind naturally that should I find all of them, or only one? If one, which one? In this problem, it was generous as you can print any of them. In some other problems, you are asked to print the lexicographically smaller/larger one (string) or in ascending manner (array of numbers) or has the highest sum over all possible solutions or some other constraints.Take this as an experience. Good luck!
 » 7 weeks ago, # |   +10 I solved B in a peculiar way (probably). Let's define $mex_{i} = mex(p_1,...p_{i})$. Also, notice that at no point, $p_i < mex_{i-1}$ can be true because that number is already present in the $P$ array, $mex_{i-1}$ being larger than that is the evidence to that.Case 1: $a_i = 1$. Imagine how $a_i$ can be $1$. Case 1a: $p_i = mex_{i-1} - 1$. This way, $mex_{i}$ will stay the same as $mex_{i-1}$. But by the contradiction mentioned above, $p_i$ can never be smaller than $mex_{i-1}$. Case 1b: $p_i$ has to be equal to $mex_{i-1}$, which will increase the $mex_{i-1}$ by $+1$ or more. But as it is guaranteed that valid $P$ exists, it will always get increased by $+1$. Otherwise $a_i$ cannot be $1$. Case 2: $a_i \neq 1$. Case 2a: $p_i \neq mex_{i-1}$. So $mex_{i} = mex_{i-1}$, making $p_i$ to be $mex_{i-1} - a_i$. Case 2b: $p_i = mex_{i-1}$. If the previous case fails (results in an invalid $p_i$ such as negative or already taken), take this option. It can be proved that under no circumstance, both approaches of 2a and 2b both can lead to valid $p_i$ for the same $a_i$. If this has to happen, 2a wants $a_i$ to be $mex_{i-1} - ?_{p_i}$ (some mysterious value for $p_i$), whereas 2b wants $a_i$ to be $mex_{i} - mex_{i-1}$ has to hold. For them to be equal, $?_{p_i} = 2 \cdot mex_{i-1} - mex_{i}$. But $mex_{i} > mex_{i-1}$, making $p_i < mex_{i-1}$ (again contradiction).Thus, initializing a $mex$ variable with $0$, I read a number from $a$ and chose appropriate value for $p$. Need to maintain $mex$ variable properly. Complexity $O(n)$.
 » 7 weeks ago, # |   0 D accepted solution in $\mathcal{O}(n^2k)$ in C++20 254217379
 » 7 weeks ago, # |   0 can u explain more why if ( a[i] >=0 ... and the other way ... ) ?
•  » » 7 weeks ago, # ^ |   0 why mex should increase if a[i] >= 0 ? and why should stay the same in the other case
•  » » » 7 weeks ago, # ^ |   0 if p[i] == mex 1 -> i-1 !a[i] = mex till i — p[i] !mex till i = p[i]+1 ?a[i] = 1 !!!!
•  » » » 7 weeks ago, # ^ |   0 if a[i] >= 0 then mex(p1, p2, ..., pi) - p[i] >= 0 or mex(p1, p2, ..., pi) >= p[i]. But mex(p1, p2, ..., pi) can not be equal to p[i] (by definition MEX is an element not contained within the set). So mex(p1, p2, ..., pi) > p[i]. If the mex(p[1]...p[i-1]) = m (meaning the first i-1 elements in p had all the elements from 0 to m-1, and some greater than m(probably). Now when p[i] was added, the mex could either stay the same or increase. But if mex stayed the same it means p[i] is larger than m in which case mex(p[1] ... p[i]) - p[i] will be less than 0 (a contradiction). If you are thinking we might put p[i] as something smaller than m in the case mex does not change, then it is not possible since p is a permutation and all elements from 0 to m-1 is already a part of p.
 » 7 weeks ago, # |   0 Liked rating predictions idea , hope to see it each contest
•  » » 7 weeks ago, # ^ |   0 you mean the current rating is not final yet ?
•  » » » 7 weeks ago, # ^ |   0 problem rating predictions (see the spoiler in the second line )
 » 7 weeks ago, # |   +6 Alternate Solution of D (Editorial's implementation is much simpler than this):Maintain $dp[i]$ as mentioned in the editorial. Now for finding $dp[i]$, we can do binary search on the lowest value of the top $k$ elements. It can be easily done by counting the elements which will be greater than current $mid$ value, if the value is $>= k$, then $mid$ can be the possible answer.Now we have got the lowest value of the top $k$ elements (let's call is $mn$), now to find all the possible values, we will take all the values $>= mn + 1$, whatever count is the remaining from top $k$ elements, append $mn$ that many times. Sort it and proceed.Note : For smaller indices you can do brute force so that atleast $k$ possible combination of values can be obtained.
 » 7 weeks ago, # | ← Rev. 2 →   0 F is really nice! I did similar idea as editorial, but instead i first imagined bsearch working backwards then divided into blocks put in segment tree working backwards same way. Solution here.Why is hint 3 possible?
•  » » 7 weeks ago, # ^ |   0 Also, I liked C and D quite a bit too :). A/B filler, E is math garbage tho.
•  » » 7 weeks ago, # ^ |   0 you are so awesome！could you teach me what should i do to be as good as you !
•  » » 7 weeks ago, # ^ |   +26 This is because $\lfloor \sqrt{a+b} \rfloor = \lfloor \sqrt{\lfloor a\rfloor+b}\rfloor,$ when $b\in\mathbb{Z}$
 » 7 weeks ago, # |   0 can someone please explain why this $O({n^2})$ of mine works for Bessie and MEX problemSubmission
 » 7 weeks ago, # |   0 why this code is giving run time error and the logic is correct right anyone help me please?? submission link
•  » » 7 weeks ago, # ^ |   0 array p is so short that space limit is exceeded but it also wrong when i correct it . so,what are you facking coding ?
 » 7 weeks ago, # |   0 what can i say? how to solve D
 » 7 weeks ago, # |   +10 I have another solution in $O(n \log n)$ for problem B.Using this equation: $p_i = \mathrm{MEX(p_1,\dots, p_i)} - a_i$ We can test with the possible values of $\mathrm{MEX}$ in the current permutation. $\mathrm{MEX}$ always will have 2 possibilities: The actual $\mathrm{MEX}$ of the permutation, define this as $\mathrm{fmex}$. The $\mathrm{MEX}$ if we insert $\mathrm{fmex}$ into the current $p$ So, one of the possibilities will be invalid (Go out of valid values of $p_i$), so we must pick the valid possibility. We can store a copy of $p$ to simulate the second possibility, I used this implementation that allow us to get $\mathrm{MEX}$ queries in $O(\log n)$, we must precalculate the initial array $p$ in $O(n\log n)$.This is the submission 254239126
 » 7 weeks ago, # |   0 Can someone pls explain the D problem statement, tried reading mutiple times didn't get the question itself
 » 7 weeks ago, # |   0 Can someone help me out in understanding how sorting in C1 keeps the algo within the time bounds?
•  » » 7 weeks ago, # ^ |   0 Upper limit for x is 2*10^5 so after sorting (Time complexity nlogn) it will be around 10^6 steps. It is well known that in 1 second you can do around 10^7 to 10^8 steps. So it remains within time limit.
 » 7 weeks ago, # | ← Rev. 6 →   0 In Problem B: The code given in solution 1 of the editorial is giving the answer: 0 1 4 2 4 (which is not a valid permutation)for the testcase: 51 1 -2 1 -1
•  » » 7 weeks ago, # ^ |   0 The problem statement says: "The input is given in such a way that at least one valid $p$ exists." Your input is invalid because there is no answer.
•  » » » 7 weeks ago, # ^ |   0 Thank you for the clarification
 » 7 weeks ago, # |   0 How in problem F do we prove that we can consider f(n) be a floored sqrt and there will no be any calculations error?
•  » » 7 weeks ago, # ^ |   +6 There is no integer $k$ such that $\lfloor f_{i-1} \rfloor +a_i < k^2 \leq f_{i-1}+a_i$, so $\lfloor \sqrt{\lfloor f_{i-1} \rfloor+a_i} \rfloor=\lfloor f_{i} \rfloor$, we can get $\lfloor f_n \rfloor$ correctly.
 » 7 weeks ago, # |   -18 MAN,what can I say?
 » 7 weeks ago, # |   0 In problem D, i did not understand how 2-d matrix came in question Learning to Paint, there are n cells, how are n*(n-1)/2 description given? some one please help me to understand the question
•  » » 7 weeks ago, # ^ |   +10 There is one value for every (l,r) where l <= r. Basically the upper triangle of a square
 » 7 weeks ago, # |   0 in this code for Bvoid solve() { int n; std::cin >> n; std::vector a(n); for (int i = 0; i < n; i++) { std::cin >> a[i]; } int mex = n; std::vector p(n); for (int i = n - 1; i >= 0; i--) { p[i] = mex - a[i]; mex = std::min(mex, p[i]); } for (int i = 0; i < n; i++) { std::cout << p[i] << " \n"[i == n - 1]; }} why are we doing mex = std::min(mex, p[i]);?can anyone please explain it
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +10 When you add a new element the mex either increases or stay the same If it increases then the number you added to the set was equal to mex, if it stayed the same number you added to the set was greater than mex(since p is a permutation). You know the Mex of the entire array is n. Now you have found out the last element. When this element was added to the set of remaining n-1 elements, it either made the mex increase and which means this last number was equal to the Mex of the first n-1 numbers. If it did not increase the Mex then that means this number was something greater than Mex. That statement is just trying to achieve this:
•  » » » 7 weeks ago, # ^ |   0 got it,Thanks
 » 7 weeks ago, # |   0 you are so rude cry
 » 7 weeks ago, # |   0 https://mirror.codeforces.com/contest/1942/submission/254169040Can anyone tell me how to correct this logic. What I am doing wrong how to correct it . Thanks in advance
 » 7 weeks ago, # |   0 Problems are very interesting and educational!!!
 » 7 weeks ago, # |   0 For a simpler problem D, when you just have to find the max score, how can we write the transition equation ?
 » 7 weeks ago, # |   0 can anyone explain me the time complexity for solution 1 of problem B , isn't it n^2 how does it work for 1.5 second time limit?
 » 7 weeks ago, # |   +13 Alternative solution for E (initially I could solve only like this :D):Let's understand that if we take all the cows in the coordinates $x_1$ < $x_2$ < $\ldots$ < $x_{2n}$, then the first player will always lose if and only if for each $1 \leq i < 2*n$, such that $i$ is odd, the difference $x_{i + 1} - x_i$ is also odd. Then from all possible ways, we can remove the number of states when the first player will lose and will get the answer.Let $dp[l][n]$ be the number of states when the first player loses the game ($l$ is the length of the x-axis, $n$ is the number of cows for each farmer).It's easy to see that $dp[l][n] = \sum_{k=0}^{n}{dp[\lfloor \frac{l}{2} \rfloor][k] * dp[l - \lfloor \frac{l}{2} \rfloor][n - k]}$. Let's note that the number of different values of $l$ will be at most $2 * log(l)$ and the following sum, we can calculate using FFT.You can easily to see that the complexity of this solution is $O(l * log(l) * log(n))$, which I guess will not pass TLE, but anyway I decided to share it with you :)
 » 7 weeks ago, # |   +3 The editorial of D , is as poor as it could be.
 » 7 weeks ago, # |   0 In C1, can someone explain why 254296468 is getting Runtime error on test 6, but 254301491 is accepted. Both are based on same logic.
 » 7 weeks ago, # | ← Rev. 2 →   0 **For problem B, the editorial says, ** Note that there is a way to show that $p$ is unique Here's my proof. AFSOC (assume for sake of contradiction) that $\exists P_1, P_2$ such that $\exists i$ where ${P_1}_i \not= {P_2}_i$. WLOG (without loss of generalization), fix such an $i.$Proceed by induction. Base case: any $A$ such that $|A| = 1$ and $a_1 < 0$. No other definition of $A$ satisfies requirements for problem.Inductive hypothesis: $\forall j < i, MEX({p_1}_1, ..., {p_1}_j) = MEX({p_2}_1, ..., {p_2}_j).$Case on parity of $a_i.$ Case 1: $a_i > 0$. $MEX({p_j}_1, {p_j}_2, ..., {p_j}_{i-1}) = p_i$ for $j = 1$ and $j = 2$ because the MEX of a set changes if and only if the new element in the set is the previous MEX.Case 2: $a_i < 0$. This means that $MEX({p_j}_1, ..., {p_j}_{i-1})-a_i = {p_j}_i$ for both $j = 1$ and $j = 2.$Note that in both cases, by the IH (inductive hypothesis), it follows that ${p_1}_i={p_2}_i.$ Since $i$ was fixed arbitrarily, this follows for all $i \in [1, n]$ why do CF and other judges insist on 1 indexing :'( This is a contradiction since we originally assumed that there would exist at least one $i$ such that ${p_1}_i \not= {p_2}_i.$Therefore, $P$ is unique. . Please let me know if there is an error. thanks.
 » 7 weeks ago, # |   +3 C can be solved alternatively by going through the array from back, like for the last element MEX must be n, now you got the last element, subsequently the penultimate element's MEX (MEX(a1,a2,...an-1)) would be Pn since its the only element, not present in the permutation sequence till then, if we go on like this, finding elements from the back, and then exploiting the fact that the MEX(a1,a2,a3,..ai) is min(Pi+1, Pi+2,....Pn)..we can find all the elements of the permutation
•  » » 7 weeks ago, # ^ |   +3 This is also explained as Solution 2 in the editorial!
•  » » » 7 weeks ago, # ^ |   0 oh...i am sorry, my bad
•  » » » » 7 weeks ago, # ^ |   0 No need to say sorry, just pointing it out :)
 » 7 weeks ago, # | ← Rev. 2 →   0 C is quite easy, isn' t it?i think it is easier than B
•  » » 7 weeks ago, # ^ |   0 Nope. :) I solved A, B, and D but none of C1 and C2.
 » 7 weeks ago, # | ← Rev. 3 →   0 What's the O(n^2 + k) solution for D (mentioned in the tutorial) ? Any hints would be appreciated
•  » » 6 weeks ago, # ^ |   0 Did you find that solution? If not then can this problem be modelled as a Best time to buy and sell stock 4 problem? I have a blog related to a n+nlogk solution posted on codeforces regarding it.
 » 6 weeks ago, # | ← Rev. 4 →   0 How can I make this code better.Task — C1 while(t--){ int n,x,y; cin >> n >> x >> y; vector a(x); for(int i =0; i < x; i++){ cin >> a[i]; } setst(a.begin(),a.end()); int ans = x-2; for(int i = 1; i <= n; i++){ if(st.find(i) != st.end()){ continue; } int left = i-1; int right = i+1; if(i == 1){ left = n; } if(i == n){ right = 1; } if(st.find(left) != st.end() && st.find(right) != st.end()){ ans++; } } cout << ans << "\n"; }Time limit exceeded on test 6
 » 6 weeks ago, # | ← Rev. 4 →   0 for the problem E, can anyone help me generate allowed positioning for l=6, n=2? I cant seem to find the positions but the correct answer should be 14. I prefer a notation like "XGOXGO" where, X = cow for farmer 1, O = cow for farmer 2, G = gap Wrong positions are: XOXOGG GXOXOG GGXOXO XGGOXO XOGGXO XOXGGO if we flip X and O, then we get another 6. So I found total 12 Wrong positions out of 30 [2 * ncr(6, 4)]. So my answer becomes 18. Which 2 incorrect positions am I missing?UPDATE: Thanks to a friend, i found out I was missing:GXOGXO XOGXOG
 » 6 weeks ago, # |   0 Does anyone know how/when the winners will recieve the prize?
 » 6 weeks ago, # | ← Rev. 2 →   0 In Problem C1, We have a test case 8 4 0. The answer for this test case is given to be 2. But I found a construction giving 3 triangles. If you number the vertices serially from 1-8, then if we connect vertex 1 to vertices 5,6,7 then we get 3 triangles. Please tell me what am I missing. Construction Link
•  » » 6 weeks ago, # ^ |   0 you cannot use vertex 7
 » 6 weeks ago, # |   0 PROBLEM.C2: Bessie's Birthday Cake (Hard Version) i had the same logic. i cant doubt if its an implementation issue( WA submission ). but here is my submission: 255822976 #include using namespace std; #define all(v) v.begin(), v.end() #define debug(var) cout<<(#var)<<": "< sync_with_stdio(0) #define fastop cout.tie(0) -> sync_with_stdio(0) #define fe(n) for(ll e=1; e<=n; e++) #define line(var) cout<<(var)<<'\n' #define ll long long #define show(var) cout<<(var)<<' ' #define tests(t) cin>>t; while(t--) int main() { ll t, n, x, y; fastio; tests(t){ cin>>n>>x>>y; deque a(x); for(ll &i: a) cin>>i, i--; sort(all(a)); // dbcon(a); vector diff(x); fe(x-1) diff[e]= (a[e]-a[e-1]-1); diff[0]= n-a[x-1] +a[0]-1; sort(all(diff)); auto cmp= [&](ll a, ll b) {return((a&1) > (b&1));}; sort(all(diff), cmp); // dbcon(diff); ll ans= x-2; for(ll i: diff){ ll val= min(i/2, y); ans+=(val+val); if(i == 2*val +1) ans++; y-=(val); } line(ans); } return 0; } 
 » 4 weeks ago, # |   0 in prob B How do I know what number the mex increases each time?