### prvocislo's blog

By prvocislo, 5 weeks ago,

We hope you enjoyed the problems! Thank you for your participation! We are really sorry that A and D turned out to be harder than usual.

Problem A: idea by prvocislo and satyam343, prepared by prvocislo

Hint 1:
Hint 2:
Hint 3:
Solution:

Problem B: idea by prvocislo, prepared by prvocislo

Definition:
Hint 1:
Hint 2:
Hint 3:
Solution:

Problem C: idea by prvocislo, prepared by prvocislo

Hint 1:
Hint 2:
Hint 3:
Solution:

Problem D: idea by prvocislo and TimDee, prepared by prvocislo and TimDee

Hint 1:
Hint 2:
Hint 3:
Hint 4:
Hint 5:
Solution:

Problem E: idea by prvocislo, prepared by prvocislo

Hint 1:
Hint 2:
Hint 3:
Hint 4:
Hint 5:
Solution:

Problem F: idea by prvocislo, prepared by prvocislo

Hint 1:
Hint 2:
Hint 3:
Solution:
• +214

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by prvocislo (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 2 →   +4 first. please don't downdoot mealso I think B was a very nice problem
•  » » 5 weeks ago, # ^ |   0 you have a great growth within 10 months on your profile how do you manage to do so?
•  » » » 5 weeks ago, # ^ |   +15 I appreciate it broski but I have also done a lot of leetcode so, between the two platforms, it is normal growth. I think that leetcode is better than codeforces when you are beginning 100%.
•  » » » » 5 weeks ago, # ^ |   0 will surely try leetcode because i have barely any growth on cf. any tips?
•  » » » » » 5 weeks ago, # ^ |   +8 don't waste time or energy learning advanced stuff, just focus on simple 9th grade math, logic and thinking. after u got better at that(rating around 1000), learn prefix sums, sets, lower/upper bound
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 yup i kind of couldn't even get 1st problem here in this contest
•  » » » » » 5 weeks ago, # ^ |   +14 In my opinion, leetcode is the best way to start competitive programming because it introduces the most common competitive programming concepts (greedy, binary search, dp, graphs/trees, etc etc) through more or less straightforward problems. The good thing about this is that you aren't gonna have to do some weird math things while solving leetcode dp problems, for example. You can just focus on learning dp. Another benefit of leetcode is that it has a much bigger community than cf. If you get stuck on a problem, you will have much more than just a single editorial to read. There are videos, writeups, and there is even a solutions tab that you can use to understand the problem.If I were you, I'd go to https://neetcode.io/roadmap and just start working through that list. NeetCode, the guy who made that website, has great explanations for each problem. Once you finish that list, start doing random mediums, and when you feel comfortable with those, start trying some hards. When I was grinding out mediums, I'd try to limit myself to 45 minutes and then I'd look at the solution.Make sure you're doing the weekly and biweekly contests while you're practicing. Once you reach a 2000+ rating, I'd say that you should start practicing on some more serious competitive programming websites. 2000 rating should get you to specialist on codeforces at least.
•  » » » » » » 5 weeks ago, # ^ |   0 will surely try so
•  » » » » » » 5 weeks ago, # ^ |   0 Thanks a lot man, very helpful :)
•  » » » » » » 5 weeks ago, # ^ |   0 Yes I agree, I did Leetcode for a few months and now codeforces seems much more approachable to me. I still have a lot to learn, but at least I can now understand what topics, and how to learn them
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Growth starts from the point you feel like quitting. Do leetcode but don't leave cf. Leetcode contests are very good, try that also.
•  » » » » » » 5 weeks ago, # ^ |   0 true that my growth has just been downwards wanted to quit but did that once and ended up in not so good institution so won't do that again
•  » » 5 weeks ago, # ^ |   0 I am not able to solve problem A. Can you help me with the logic. I couldnot understand the editorial. only got -1 part. and how do you come up with such logic.
•  » » » 5 weeks ago, # ^ | ← Rev. 5 →   0 So you understand that if the sum is odd, the answer must be -1. Let's show that if the sum is even, the answer is never -1. In order for p1 + p2 + p3 to be even, all 3 must be even or 2 / 3 of them must be odd. We can achieve all possible (p1, p2, p3) when p1, p2, p3 are even through just wins (aka by adding 2 to each one independently). Now for the case where 2 / 3 of them are odd, we can just throw in a draw between the two which we want to be odd (add 1 to each), and we can then keep adding 2 to each one of them and we can see that, by doing this, we can achieve all (p1, p2, p3) where 2/3 of them are odd. So whenever p1 + p2 + p3 is even, the answer is never -1.Now that we know that, how can we find the max number of draws? Well let's try to take draws from the two greatest elements in (p1, p2, p3). You can think of this intuitively like this: if you take a draw (that is subtract 1) from the two greatest elements in (p1, p2, p3), you bring the elements in (p1, p2, p3) closer together. If the elements are closer together, there is more "drawing potential" since if the elements are all equal to each other, we can guarantee that all the games can be draws (we can draw p1, p2 then draw p2, p3 then p1, p3 and then our elements become (p1 — 2, p2 — 2, p3 — 2) and we can do this down to 0). Hopefully the intuition here makes sense.So the algorithm is just sort (p1, p2, p3) and while the second greatest element is > 0, take a draw between the first and the second greatest elements and resort the list.Don't focus too much on the proof of div. 2 A in contests though. This comment doesn't even prove the greedy algorithm but rather shows what the intuition to get there might be. Do your best to solve A by educated guesses.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Is the math written in the solution correct:I'll just put the scores in here: 0 0 0 1 0 1 2 1 1 3 1 2 3 2 3 3 3 4 This is what the math in the bonus states the answer should be. I get that there can be another draw between p2 and p3. Just wanting to know whether I'm doing the math wrong or the math written in the bonus question is incorrect.
•  » » » » » 5 weeks ago, # ^ |   0 looks right to me
•  » » » » » » 5 weeks ago, # ^ |   0 But I did the above calculation for the case where the final scores are 3 4 5. Yet the final result on following the calculations is coming out to be 3 3 4. Seems like there's a typo in the bonus hint then.
•  » » » » » » » 5 weeks ago, # ^ |   0 Where are you confused? You wrote out 5 draws to get to 3 3 4 and you can add another draw to get to 6 draws at 3 4 5. The answer is min( (3 + 4 + 5) / 2, 3 + 4), which is 6
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   -10 Deleted
•  » » » 5 weeks ago, # ^ | ← Rev. 4 →   +4 If you want the explanation for the $O(1)$ solution, it goes like this:As, we are always increasing $p_1+p_2+p_3$ by $2$ ($1,1$ in case of draw and $2,0$ in case of win), the invariant is pretty clear, i.e.., $(p_1+p_2+p_3)\%2 = 0$ for a valid game.Now, we have $p_1 \le p_2 \le p_3$, so we can always have atleast $p_1$ draws. Thus, from $p_2$ and $p_3$, we have to remove $p_1$ points, leaving us with $p_2+p_3-p_1$ points. Obviously, in the most optimal case, we could have $(p_2+p_3-p_1)/2$ more draws (if we had equal points left for both), but this is not necessarily the case as it is possible that $p_2 < (p_2+p_3-p_1)/2$, in such a case, we can add $p_2$ to the score. So my final $O(1)$ solution looks like:1) If $(p_1+p_2+p_3)\%2 \ne 0 \implies$ No solution possible.2) Otherwise, the answer can be found out using the expression $p_1 + min(p_2,(p_2+p_3-p_1)/2)$.Hope this helps!
•  » » » » 5 weeks ago, # ^ |   0 Thank you
•  » » 5 weeks ago, # ^ |   0 could you explain this claim in detail ? if the array is k-lonely, the array is also k+1-lonely .
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Sure. If we look at this problem bit by bit, there are two cases: The ith bit is not set anywhere in the array. If this is the case, we can think of the array as [0, 0, 0, 0 ...] where array[j] represents whether or not the jth element in the original array has the ith bit set. The or of all subarrays in this array is 0 so every k works. The ith bit is set in some places in the array. We can think of our set bit array as [0, 1, 1, 0, 0, 1, 0, 1] or something. In order for some k to work, it must be the case that every subarray of length k contains at least 1 set bit. This is true because there is at least 1 subarray of length j (1 <= j <= n) that has at least 1 set bit, so therefore all subarrays of length k must contain at least 1 set bit for this k to work. If every subarray of length k contains at least 1 set bit, then surely every subarray of length k + 1 contains at least 1 set bit. So if k works, k + 1 works too.
•  » » » » 5 weeks ago, # ^ |   0 thanks got it !
 » 5 weeks ago, # |   0 idk why in B i' didn't think of binary search
 » 5 weeks ago, # | ← Rev. 3 →   +6 can someone please the logic of this solution for B: 261346413, I'm not getting itEDIT: got it explanation for anyone who didn'timagine there exists a bit j, such that $x-1$ consecutive elements don't have that, I claim that the answer is at minimum x.why? imagine the answer is x-1(or anything less), then by the pigeon-hole principle there exists at least 1 segment where that bit hasn't occurred, thus its OR is different with one segment that has it. now for each bit from 0 to 20, find the longest subarray where no elements have that bit, and take the maximum of all of them in the answer.
•  » » 5 weeks ago, # ^ |   +4 Look at the problem bit by bit: in order for all of the subarrays of length k to have the same or, for each bit, there has to be at least 1 of them in each subarray or there has to be 0 of them in all subarrays (aka 0 of them in total).For example, if we have the array [1,0,0,1,0,1], and we try to have k = 2, well there is a subarray of length 2 that doesn't have an on bit and the rest of the subarrays have at least 1 on bit. So k = 2 can't work. Looking at a few more examples, you will see that k has to be the maximum distance between consecutive 1s so that once a subarray loses a 1, it will surely gain another 1.The answer will be the max of these maximum distances for each bit that is present in the array. If a bit is not present in an array, we can disregard it.
•  » » » 5 weeks ago, # ^ |   +1 thx for the explanations, I just understood how it works and it took a while to write the edit, sorry for the waste of time, maybe someone doesn't understand my explanation and yours is more understandable, sorry for the inconvenience
•  » » » » 5 weeks ago, # ^ |   0 haha no problem broski, the more explanations the better
•  » » » 5 weeks ago, # ^ |   0 SO, for example 2 0 4 0 2, why is the answer not 3, but 4??
•  » » » » 5 weeks ago, # ^ |   0 for 2 bit, the array is [1, 0, 0, 0, 1]
•  » » » » » 5 weeks ago, # ^ |   0 Ahh, my bad !!!. Was thinking from another angle . Got it, thanks. Will try more next contest :)
 » 5 weeks ago, # |   +1 Interesting, I thought of binary seraching for B but couldn't come up with the NlogA traversing algorithm, so instead I stumbled on the NlogA solution.
 » 5 weeks ago, # |   0 C is really good
 » 5 weeks ago, # | ← Rev. 2 →   +15 Wow rating changes and editorial were kinda fast... speedforces
 » 5 weeks ago, # |   0 I used segment tree for B. I am sooorry ;).
•  » » 5 weeks ago, # ^ |   0 that's what happens when u learn something too soon, it could be solved using just prefix sums for query, or sparse table at worst, a segment tree...
•  » » » 5 weeks ago, # ^ |   +7 Haha my solution used sparse table. The core idea is that range or has a similar property to range minimum, that is a range can be split into two overlapping subranges and merge the result.
•  » » » » 5 weeks ago, # ^ |   0 me too. what's the complexity?
•  » » » 5 weeks ago, # ^ |   0 Can you please look into my code and tell why its giving me MLE i m not sure what is going wrong 261444005
•  » » » » 5 weeks ago, # ^ |   0 I couldn't understand the logic, nor the reason of mle
•  » » » » » 5 weeks ago, # ^ |   0 It is binary search on all values of K,it led to TLE during contest. So i tried to optimise it using hashing for previous values of K for any index or the maximum subarray of size K' form the same index. So here is the first iteration: from B.S--> K=3 i.Since its first iteration than map will be empty. ii. For all subarray of size K=3,we also can hash the OR for all subarrays from an index i, of size t such that t<=K (i.e 3,2,1) which is why i used the map[(index,K_size)]=OR_value. iii. The prev is just for checking if there are different OR.iv.Next time when BS gives K=5,then i found the max(t) such that (t<=K) from the map using findK function.If it finds it then we will use it for all index that it has already computed and for indexes it hasn't we will compute it normally.This led to MLE
•  » » » » » » 5 weeks ago, # ^ |   0 Finally understood the code, I believe there is a way to set up the inputs such that the map will take n² pairs of numbers leading to tle
•  » » » 5 weeks ago, # ^ |   0 Not really too soon, I think learning it is good but overusing it is really problematic
•  » » 5 weeks ago, # ^ |   0 Me too!! Used binary search with segment tree!!
 » 5 weeks ago, # |   0 B without binary search: 261388922
 » 5 weeks ago, # |   +26 prvocislo orz <3
•  » » 5 weeks ago, # ^ |   +9 berr orz <3
 » 5 weeks ago, # |   +8 I think for Problem C hint 2 should be n/2-1.prvocislo
•  » » 5 weeks ago, # ^ |   0 Thank you, I will fix it
 » 5 weeks ago, # |   0 C was nice from the proof and math work side
 » 5 weeks ago, # |   +7 in C 2nd hintn/2 -1 not +1
 » 5 weeks ago, # |   -11 B with segment tree and binary search 261367730
 » 5 weeks ago, # |   0 Can someone explain the intuition, rather than proof, behind problem C? "... Then since $n$ belongs to an odd index, the $a_i$ for each odd $i$ will be at least $n+1$ while the $a_i$ for each even $i$ will be at most $n$."While I can indeed verify this statement after the contest, I found it rather counter-intuitive that a simple greedy method would work, so I quickly dismissed the thought of trying it out. Any thoughts?
•  » » 5 weeks ago, # ^ |   +8 The fact that n is even should signal that maybe you can somehow split numbers into two groups.Secondly, it'd fairly common to sort permutations in opposite directions (ascending/descending) and match them greedily.Also worth noting, it's very easy to get sums of all elements of final array to be equal to (1+n), by matching $p_i$ with (1+n-$p_i$).This was my thought process during the contest, it's really just 3 standards ideas combined together. If you write all these out at some point you'll notice that you can ensure (n+2) is reachable in n/2 points so ot suffices to make the others no greater than n+1, which like we said has an easy construction.
•  » » » 4 weeks ago, # ^ |   0 Makes sense, thanks for this
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +10 I ended up coming up with the editorial solution and another in the contest, so I'll describe them both: Editorial Intuition We suppose $n$ has odd index and then try to make all odd elements into peaks. Is it possible? The worst case might be when $1, 2, 3 ... n/2-1, n$ are the elements in the odd positions and $n/2, n/2+1, ... n-1$ are the elements in the even positions. We can even go further and assume $n-1$ is next to $1$ and $2$, and $n-2$ next to $2$ and $3$ and so on. Obviously let's assign smaller labels to the ones in the even position and larger labels to the ones in the odd positions. Well $n-1$ gets the label $1$, so $1$ and $2$ need the labels $n$ and $n-1$ respectively, and then continuing in this way we can make the observation that you call counter-intuitive. My Intuition We can construct $q$ so that all the $a_i$ are equal (make $q_i + p_i = n+1$). Now we want to reorder some elements of $q$ such that all the odd/even elements become peaks. Since all elements of $a_i$ are equal at this point, we just need to reorder the elements of $q$ so that the ones in odd indices increase, and the ones in even indices decrease (or vice versa). There's a lot of ways to do this, the first one that came to my mind is just suppose that $n$ appears at an even index $2k$ and sort the odd indices in increasing order of value. Then do $q_{o_1} \rightarrow q_{o_2} \rightarrow q_{o_3} \dots \rightarrow q_{2k} \rightarrow q_{o_1}$. i.e. the smallest odd index gets value of the next larger odd index, etc. and the largest odd index gets the value of n.
•  » » » 5 weeks ago, # ^ |   0 Nice alternative approach :)
•  » » » 5 weeks ago, # ^ |   0 So after making the sum equal at all indices, we have to solve the problem: increase values at even indices and decrease values at odd indices. This (for me at least during the contest) was not helping to explain why there will always be a solution that gives n/2 — 1 peaks (though i agree it is easy to get the solution for n/2 — 1 peaks this way). We still need the editorial approach to build the worst case and show that n/2 — 1 peaks will always exist (for best q). Can you elaborate if you could show n/2 — 1 peaks always exist with your intuition?
•  » » » » 5 weeks ago, # ^ |   0 With my approach, first we get a permutation $q$ that makes all values of $a$ equal. Then we increase the value of $q_i$ at all odd indices, without increasing any value at an even index. (In fact, we decrease the value at one of the even indices.)Therefore $a_i$ increases for odd $i$, and doesn't change change (or decreases) for even $i$. Therefore all odd indices will become peaks and we will have $n/2 - 1$ peaks. This is pretty much independent of the editorial approach.
 » 5 weeks ago, # |   0 in problem C hint 2, it should have been n / 2 — 1 : )
 » 5 weeks ago, # |   +1 B is a very nice problem.
 » 5 weeks ago, # | ← Rev. 4 →   +39 My idea for C is slightly different and imo cleaner. Its also much easier to prove why my idea actually works.Here's my code: 261430375 The explanationAlright so we know that the answer is at most $\frac{n}{2} - 1$ (the proof is given in the editorial)We will of course construct a solution that has exactly these many local maximums, and that has to be optimal.So here's the idea. Before thinking about making some indices local maximums and some minimums, can we make everything equal by mapping the given permutation $p$ to a permutation $q$? AnswerYes we can! We just map $p[i]$ to $q[i] = n + 1 - p[i]$, and the sum is going to be $n + 1$Now, without loss of generality let us assume that $p[j] = 1$ and $j$ is odd. Then we want to make all the elements in the even positions the local maximums. Incase $j$ was even, we'd make the positions at odd indices local maximums. How do we achieve this?We iterate over the elements at even indices in increasing order of their value. Let us say that the value of the current element is $x$. Then we perform the following operation - swap(q[pos[x]], q[pos[1]]); (Here $pos[x]$ is the index of the value $x$ in $p$, ie. $p[pos[x]] = x$)And we are done! The resulting array $q$ is our answer! Why does this work?Note that $q[pos[i]]$ > $q[pos[j]]$ for $i < j$And since $q[pos[1]]$ > $q[pos[x]]$, after the swap $pos[x]$ becomes a local maximum (as all the elements were same initially and after the swap the value at $pos[x]$ increased)And as we are swapping with increasing value's of x, the values at even indices become more than the values at their neighbours.Hence the even indices are all local maximums.Incase I explained something poorly, please let me know! And I'll try to help if I can. :D
•  » » 5 weeks ago, # ^ |   +8 great explanation sir : )
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Excellent solution! I didn't get the part "We iterate over the elements at even indices in increasing order of their value." -> could you explain this part?Overall, how did you come up with this thinking, if you could share your thought process!
•  » » » 5 weeks ago, # ^ |   +8 Yeah, so lets take an example, lets say the array is this - Spoileridx: 1 2 3 4 5 6 ----------------- p: 5 1 6 2 4 3 q: 2 6 1 5 3 4 ----------------- 7 7 7 7 7 7 Here $p[2] = 1$, so we try to make values at odd indices local maximums.The values at odd indices are ${5, 6, 4}$.Since we are going to iterate over increasing values, we go in the order $4 \rightarrow 5 \rightarrow 6$.So we first swap(q[pos[1]], q[pos[4]]) to get - Spoileridx: 1 2 3 4 5 6 ----------------- p: 5 1 6 2 4 3 q: 2 3 1 5 6 4 ----------------- 7 4 7 7 10 7 Then we perform swap(q[pos[1]], q[pos[5]]) to get - Spoileridx: 1 2 3 4 5 6 ----------------- p: 5 1 6 2 4 3 q: 3 2 1 5 6 4 ----------------- 8 3 7 7 10 7 Then we finally perform swap(q[pos[1]], q[pos[6]]) to get - Spoileridx: 1 2 3 4 5 6 ----------------- p: 5 1 6 2 4 3 q: 3 1 2 5 6 4 ----------------- 8 2 8 7 10 7 And we are done!
•  » » » » 5 weeks ago, # ^ |   0 Thanks!
•  » » 5 weeks ago, # ^ |   0 Damn ! that's a nice observation
 » 5 weeks ago, # |   0 in problem A, what's the intuition behind if p1 + p2 > p3 , then the answer is (p1+p2+p3)/2 ? , I wasn't able to prove it, all I did was guess it based on the test cases
•  » » 5 weeks ago, # ^ |   0 After giving it a thought, I was able to come up with this explanation, correct me if I'm wrong please.Since each 2 points contribute to a game, (p1+p2+p3)/2 is the total number of games, and since we want to maximize the number of draws, we would consider all the games to be a draw.
•  » » » 5 weeks ago, # ^ |   0 ah yes and for the case p3>p1+p2 it is not possible to have all the matches draw
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 You can check out https://codeforces.com/blog/entry/129556?#comment-1149923 for an intuitive explanation :)
 » 5 weeks ago, # |   0 Thank you prvocislo for all the hard work <3
 » 5 weeks ago, # |   +8 I have another solution for F, which run in 796ms, but I don't know the time complexity for ithttps://codeforces.com/contest/1973/submission/261433060Idea: - Calculate least common multiple (lcm) for each pair a,b- Calculate lcmv = gcd of all lcms- Reduce a,b of each pair to gcd(lcmv, a), gcd(lcmv, b)- Add cost of all elements with the same new a,b (From the observation that for any i,j, if ai == aj and bi==bj then we must either swap i,j or not swap any)- Sort all triple (a,b,c) by a ascending, b ascending- For each item, maintain a map of (a,b) => minc; with a,b is the current gcd of sequence a,b; c is minimum possible cost- After that, we create the array of [(sum gcd value), (min cost)] ascending for both elements, and do binary search for each query
 » 5 weeks ago, # |   0 Can anyone explain problem A intuition? why are we drawing between two maximums?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 Our task is to maximize the number of draws . So the first thought should be to assume if all games played are draw . We know each game played contributes 2 points to the total . So total_games=(p1+p2+p3)/2 Our assumption fails if all games are not possible to be a draw . Only time this fails is if (p1+p2)
 » 5 weeks ago, # |   0 can someone please tell why am i getting TLE on test2 in this submission
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 You only need to query K times for one iteration but in your case it can get >K times, Take K=1 case and all elements are same then in this case you are iterating n * ( n+n/2 + n/3 +n/4....) or n^2 logn which is clearly greater than n query .
•  » » » 5 weeks ago, # ^ |   0 Thanks
 » 5 weeks ago, # | ← Rev. 2 →   +1 It seems that there's a typo in problem C, Hint 1."the number of the prefix maximums" -> "the number of the local maximums"?prvocislo
 » 5 weeks ago, # |   0 What a talented prvocislo, writer of one of the best Div2 round. A great round and great problems.
 » 5 weeks ago, # |   +3 I don't understand the Editorial for problem E. Isn't L + n > R + 1? it's very confusing
•  » » 5 weeks ago, # ^ |   0 think i kinda understood it by algebra, but it doesn't look intuitive. can somebody explain the intutition?
•  » » » 5 weeks ago, # ^ |   0 By definition, the value $L$ is misplaced and wants to participate in some swaps to reach index $L$. If we set $l > L + n$, then there are no swaps that value $L$ can participate in. This is bad, so $l \leq L + n$. You can argue similarly for the $r$ constraint.
 » 5 weeks ago, # |   0 I solved the B problem using two pointers only. During the contest, I was missing an edge case that's why my code didn't get AC. But when I up solved and found the loophole. I managed to get AC using two-pointers.Here is my submission: https://codeforces.com/contest/1973/submission/261450556
•  » » 5 weeks ago, # ^ |   +3 most 2 pointer problem can be solved using binary search, bs on the length of the subarray
 » 5 weeks ago, # |   0 C is amazing! Brilliant round!
 » 5 weeks ago, # |   +7 Hey! Check out my video solutions for the contest. I've covered Problem A-D here: https://youtu.be/owawrSp2ywU
 » 5 weeks ago, # |   0 Thanks for the tutorial, it was really helpful.
 » 5 weeks ago, # |   0 Loved The B Problem.My Binary Search Solution
 » 5 weeks ago, # |   0 in case anybody wanted it:B with binary search: 261420803, without the use of any fancy data structureB without binary search: 261423079, logic
 » 5 weeks ago, # |   0 The number of draws between p2 and p3 should be p2-(p1-(p3-p2))/2.
 » 5 weeks ago, # |   0 D is a very good problem.Interesting.
•  » » 5 weeks ago, # ^ |   0 Can you explain why M will always be a multiple of N(size of the array)?
•  » » » 5 weeks ago, # ^ |   0 M is a multiple of MX(max element of the array)
 » 5 weeks ago, # | ← Rev. 2 →   +4 Round is awesome. But error in Russian statement was fixed only after 5 minutes, and I spend that time solving wrong problem with wrong statement
 » 5 weeks ago, # |   0 can anyone explain me problem A. I could not understand the editorial. I got the -1 part but how do you guys come with such logic in the contest.
•  » » 5 weeks ago, # ^ |   0 You could check my comment in this thread for a detailed explanation of the $O(1)$ solution, and ask me if you have any questions or if you feel like I've made any mistakes. I could get this solution only an hour after the contest ended though :(
 » 5 weeks ago, # | ← Rev. 2 →   0 In problem B why can we say if an array is k-lonely then it is k+1-lonely too??Update: nvm I got it
 » 5 weeks ago, # |   0 fxxk problem B, I use "bin" function many times caused the TLE, fxxk!! After trying for 10+ times, I preprocess the bin of each num, and then accepted! WTF!
 » 5 weeks ago, # |   0 In Problem B, my solution is giving tle verdict while another solution get accepted using my same idea. Can someone help me finding out mistake in my code.Thanks in advance.Accepted Submission
•  » » 5 weeks ago, # ^ |   0 Maybe in solve1 you should pass reference to avoid copying
•  » » » 5 weeks ago, # ^ |   0 yes,it works.thanks
 » 5 weeks ago, # |   -8 can someone tell me why https://codeforces.com/contest/1973/submission/261471081 tle? I think the complexity of it is o(20*n*logn) is there anything wrong with it?
•  » » 5 weeks ago, # ^ |   0 you should only initialize the part of the array you use. (memset part) and you should learn std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr) and stop using std::endl.
•  » » » 5 weeks ago, # ^ |   0 thx bro, its ac now
 » 5 weeks ago, # |   0 I am not able to understand the solution for problem C.It is saying that We can do this by placing the numbers $\frac{n}{2}+1,\frac{n}{2}+2,…n$ at the odd indexes in q, giving the bigger numbers to the indexes with smaller pi, and placing the numbers $1,2,…,\frac{n}{2}$ at the even indexes in p, giving the smaller numbers to the indexes with bigger pi. Then since n belongs to an odd index, then ai for each odd i will be at least n+1 while the ai for each even i will be at most n.Let us suppose $p_3 = 1$ and we choose $q_3 = \frac{n}{2}+2$, then $a_3 = \frac{n}{2}+3$, which is less than $n+1$ and similarly, we can show it for even index.Is there anything that I am missing out here? If someone can help me, I would highly appreciate it.Thanks
 » 5 weeks ago, # |   0 why ai|...|ai+k=(ai|…|ai+k−1)|(ai+1|…|ai+k) is correct ? when I expanded these term, it didn't match.
•  » » 5 weeks ago, # ^ |   0 Because of a property of bitwise-or ($a_i | a_i = a_i$, also note that it is associative): $a_i | ... | a_{i + k - 1} | a_{i + 1} | ... | a_{i + k} = a_i | a_{i + 1} | a_{i + 1} | ... | a_{i + k - 1} | a_{i + k - 1} | a_{i + k} = a_i | a_{i + k}$
•  » » » 5 weeks ago, # ^ |   0 Thanks, I mistake bitwise-or for XOR.
•  » » » » 5 weeks ago, # ^ |   0 | is the symbol for the bitwise OR⊕ is the symbol for the bitwise XOR & is the symbol for bitwise ANDit's always the case
 » 5 weeks ago, # |   0 The Rating Change and Editorial came in like 10 mins... Great Work Authors
 » 5 weeks ago, # |   +1 In problem F the step to calculate "prefix sum" of $P$ and $S$ can also be some in $D(k) \sum D(d_i)$ somehow. Does anybody have some upperbound of this sum? It feels like it's some really small $D^3(k)$ or something.
 » 5 weeks ago, # |   +13 I have some trouble understanding the given proof for the $O(1)$ solution for Problem A. I'll explain how I got that solution. Let us take an optimal solution (i.e., a solution with the max possible number of draws that corresponds to the given values of $p_1$, $p_2$, and $p_3$). The total number of games played is $\frac{p_1 + p_2 + p_3}{2}$. Let $a$, $b$, and $c$ denote the number of draws in the $A_1$ vs. $A_2$, $A_2$ vs. $A_3$, and $A_1$ vs. $A_3$ matches respectively, where the names of the players are $A_1$, $A_2$, and $A_3$. Since this is an optimal solution, the correct answer to the problem is $a+b+c$. Now, if it so happens that more than one of these players had wins (say, $A_1$ and $A_2$ both had nonzero wins — say, $k_1$ and $k_2$) — then, we could have repurposed them as $\min(k_1,k_2)$ more draws in $A_1$ vs. $A_2$ games, and one of them having $\mid k_2 - k_1 \mid$ wins instead, contradicting the optimality of our solution. Therefore, we may assume that only one of these players had wins (if any), say $w$ of them, in our optimal solution.Suppose $A_3$ is the player who had all $w$ wins ($w \geq 0$) in our optimal solution. Then, $p_1 = a + c$, $p_2 = a + b$, and $p_3 = b + c + 2w$. Solving for $a$, $b$, and $c$, we get $a = \frac{p_1 + p_2 - p_3 + 2w}{2}$, $b = \frac{p_2 + p_3 - p_1 - 2w}{2}$, and $c = \frac{p_1 + p_3 - p_2 - 2w}{2}$. Verify that these values for $a$, $b$, and $c$ will be the same even if you assume $A_1$ or $A_2$ won all $w$ games! Note that we get integral solutions for $a$, $b$, and $c$, iff the number of odd numbers in ${p_1, p_2, p_3}$ is even. If this is not the case, we output $-1$, and finish.Now, thanks to $p_1 \leq p_2 \leq p_3$, $w = 0$ (i.e., all games are draws) leads to a valid (i.e., nonnegative integer) solution for $b$ and $c$, and a valid solution for $a$ only if $p_1 + p_2 \geq p_3$. That is, if $p_1 + p_2 \geq p_3$, the answer we must output is $\frac{p_1 + p_2 + p_3}{2}$. The case left to deal with is when $p_1 + p_2 < p_3$. To make the value of $a$ nonnegative, the minimal value of $w$ to be set (we want a minimal value for $w$ as we want maximum draws) is $\frac{p_3 - p_1 - p_2}{2}$. With this setting of $w$, we get a valid solution $a = 0$, $b = p_2$, and $c = p_1$, so that the answer is $a + b + c = p_1 + p_2$. I wrote this solution (sadly, after the contest) and it was accepted.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Very nice explanation,loved it.
 » 5 weeks ago, # |   0 For Problem, C, can someone prove how the upper bound n/2-1 is always achievable, i.e., there always exists a permutation q such that the array constructed by summing individual elements of p and q will contain n/2 -1 local maxima?
•  » » 5 weeks ago, # ^ |   0 Endpoints can't be local maxima, so the possible positions of local maxima is 2..n-1(n — 2 positions)2 local maxima can't be next to each other=> Maximum n/2 -1 local maxima
•  » » » 5 weeks ago, # ^ |   +1 So what? Question is not "why n/2 — 1 is at most value", but "why we can always can obtain n/2 — 1"
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 You see in this case, you can construct a sequence such that: for $i \bmod 2 = p$ you'll have $a_i >= n + 1$ Otherwise you'll have $a_i <= n$ Where p is $0$ or $1$.So then you'll find expect these numbers which is at position $1$ or $n$，you will have $i \bmod 2 = p$ is greater than both on the sides.
 » 5 weeks ago, # |   0 In solution editorial for problem B, the size of array t is log A (not log n). I'm confused so much reading that editorial.
 » 5 weeks ago, # | ← Rev. 2 →   0 for the question B, what am i getting wrong here: any corner cases or something?? or my logic is wrong?https://codeforces.com/contest/1973/submission/261565983 i tried to debug but im unable to
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 here is the testcase where your code failed 1 5 2 3 0 2 1 it's giving 2 unstead of 3
 » 5 weeks ago, # |   0 Here's my O(20n) approach for B https://codeforces.com/contest/1973/submission/261367948
 » 5 weeks ago, # | ← Rev. 4 →   0 For problem F I wonder if it's necessary to swap a[1] & b[1] and solve twice, I think we can record the minimum and maximum cost to achieve a solution case and add the less of minimum cost and total cost minus maximum cost. With this method I can solve some cases but got wa on test 10, and I cannot figure out what is wrong. For detailed implementation here is my submission: 261587221
 » 5 weeks ago, # | ← Rev. 4 →   +5 Correctness Proof for Problem C AlgorithmObservationThere can be at most $\frac{N}{2} - 1$ local maxima (because boundaries cannot achieve this).Constructing $\frac{N}{2} - 1$ Local MaximaEven Positions (excluding $N$ We aim to achieve local maxima at even positions (excluding $N$). We use a greedy approach to place $\frac{N}{2} + 1, \frac{N}{2} + 2, \ldots, N - 1, N$. Assign the larger $p_i$ to the smaller $q_i$. Then $a_{\text{new even}} \geq N + 1$. Next, we place the remaining positions with $1, 2, \ldots, \frac{N}{2}$, assigning the smaller $p_i$ to the larger $q_i$. Then $a_{\text{new odd}} \leq N + 1$. You know that "=" can only occur when $a_{\text{odd}} = N$. Therefore, this is correct for all odd positions where $a_{\text{odd}} \neq N$. Odd Positions (excluding (1)) We aim to achieve local maxima at odd positions (excluding (1)). We use a greedy approach to place $\frac{N}{2} + 1, \frac{N}{2} + 2, \ldots, N - 1, N$. Assign the larger $p_i$ to the smaller $q_i$. Then $a_{\text{new odd}} \geq N + 1$. Next, we place the remaining positions with $1, 2, \ldots, \frac{N}{2}$, assigning the smaller $p_i$ to the larger $q_i$. Then $a_{\text{new even}} \leq N + 1$. You know that "=" can only occur when $a_{\text{even}} = N$. Therefore, this is correct for all even positions where $a_{\text{even}} \neq N$. Since there is only one $a_i = N$, the above discussion ensures that one of the above approaches must be correct.
 » 5 weeks ago, # |   0 259945476Anyone why MLE??
•  » » 5 weeks ago, # ^ |   0 I think the query function is making a lot of recursive calls (O(n * lg (n) * lg(n)) which is a lot. Maybe write it iteratively?
 » 5 weeks ago, # |   0 Problem C (Cat, fox And double maximum) Video Editorial (Audio : Hindi) YOUTUBE CHANNEL LINk :: --Click Here
 » 5 weeks ago, # |   -10 the spoilers make the solutions hard to read
 » 5 weeks ago, # |   0 261627325 Anyone why does it fail??
 » 5 weeks ago, # |   0 For problem E, why the necessary condition is "l<=R+1" and "L+n<=r". I can't understand... What do you mean by "being able to swap L,R with anything"? Under such condition, we can just swap L with [1,n] and swap R with [1,n-R+L]. Can anyone further explain it? Thank you very much.
•  » » 5 weeks ago, # ^ |   0 Sorry, I meant "to be able to swap $L$ and $R$ with at least one other element". The paragraph explaining this was a bit hard to understand, so I rewrote it a bit, hopefully it's clearer now.
•  » » » 5 weeks ago, # ^ |   0 Sorry, I'm still confused. $l\le L+1, r\ge R+1$ should be enough to swap $L,R$ with one other element like $1$, right?
•  » » » » 5 weeks ago, # ^ |   +3 $l \leq L + 1$ is stronger than $l \leq R + 1$, so some pairs $(l, r)$ for which you can sort the permutation may not satisfy your first condition. For example, in the last sample from the statement, the pair $(4, 5)$ doesn't satisfy your first inequality, yet you can still sort the permutation by choosing it. That's why you should look for another set of inequalities to describe the necessary condition.Note that we don't care about $1$ or any other element in particular, we just want to be able to swap $L$ and $R$ with anything else, possibly two different elements.
•  » » » » » 4 weeks ago, # ^ |   0 Thanks for your reply! I just realize it is $l\le L + n$ or $r\ge R+1$.
•  » » » » » » 4 weeks ago, # ^ |   0 It's actually $l \leq L+n$ and $R+1 \leq r$. You need to be able to swap both $L$ and $R$ with at least one other element.
 » 5 weeks ago, # |   0 https://codeforces.com/contest/1973/submission/261664728Can someone check what's the issue with this?? I know I am bad in implementations.
 » 5 weeks ago, # |   0
 » 5 weeks ago, # |   0 Problem AThe last test case 1 1 10. How this is possible ? Question says , first and second friend made two points by two draw with the third friend( One by each) . So the third friend should have made 2 points . How he managed extra 8 points ?
•  » » 5 weeks ago, # ^ |   0 He wins 4 times again first friend
 » 5 weeks ago, # |   0 I think Problem B is high-quality.
 » 5 weeks ago, # |   0 Problem C was easier than B
•  » » 5 weeks ago, # ^ |   0 C was more maths and problem solving based , B relied on knowledge more,i mean anyones who know segment tree or sparse would kill the problem .
 » 4 weeks ago, # | ← Rev. 2 →   0 For Problem C.How did the no.of local maximas are atmost n/2-1?For n=5 We've 2 maximas then how it is n/2-1
•  » » 4 weeks ago, # ^ |   0 Got it n will be always even
 » 4 weeks ago, # |   0 highly recommend this round cuz every problems have step-by-step hints so that we can solve the problem without relying too much on editorials. Wish to see in other rounds.
 » 4 weeks ago, # |   0 In problem B why can we say if an array is k-lonely then it is k+1-lonely? I don't understand why (ai|...|ai+k-1)|(ai+1|...|ai+k) = (aj|...|aj+k-1)|(aj+1|...|aj+k) in the editorial.
•  » » 4 weeks ago, # ^ |   +3 You know that $(a_i| \ldots |a_{i+k-1}) = (a_{i+1}| \ldots |a_{i+k}) = (a_j| \ldots |a_{j+k-1}) = (a_{j+1}| \ldots |a_{j+k})$ if the array is $k$-lonely (it follows from the definition), so then you also have $(a_i| \ldots |a_{i+k-1}) | (a_{i+1}| \ldots |a_{i+k}) = (a_j| \ldots |a_{j+k-1}) |(a_{j+1}| \ldots |a_{j+k})$ , thanks to the properties of bitwise OR.
•  » » » 4 weeks ago, # ^ |   0 I got it know. Thank you very much.
 » 4 weeks ago, # | ← Rev. 5 →   0 Can someone tell me how to solve the bonus2 in B? I'm just interested in it. Thanks.
•  » » 4 weeks ago, # ^ |   +3 I'll leave some hints on how to get to the solution. hint1binary search the answer, you can prove we can do it just like in the original solution. hint2what should be the number you are going to insert equal to? hint3that's right, it should be the OR of all numbers in the array $a$, since that's what every OR of subsegment of length $k$ should be equal to. hint4when binary searching and checking if the array can be $m$-lonely, just greedily insert the new number on the first position such that if you didn't insert it here, the array wouldn't be $m$-lonely anymore (you can find it by going from left to right and keeping an array of size $O(\log A)$ telling us what was the last time we saw this bit in some number in the array), then just check if the array is $m$-lonely.Total time complexity will be $O(n \log n \log A)$.
•  » » » 4 weeks ago, # ^ |   0 Thanks! It helps a lot!
 » 4 weeks ago, # |   0 B was a very good problem. Has a very reusable idea
•  » » 4 weeks ago, # ^ |   0 Yeah I think it's great too，especially the two Bonus. Also D is pretty good, just interesting.
 » 3 weeks ago, # | ← Rev. 2 →   0 I have a weird WA in problem D when I add a line of code in the beginning:if (n == k && k == 1) {cout << "! 1" << endl;continue;}which will output the answer directly when n and k are both 1 and continue to the next testcasefollowing are two submitsions which only differ from the description abovehttps://codeforces.com/contest/1973/submission/263160320https://codeforces.com/contest/1973/submission/263160243Can someone teach me why, I'm new with interactive problems, thanks