### pashka's blog

By pashka, history, 6 weeks ago,

1921A - Square

Idea: goncharovmike, prepared: pashka

Tutorial
Solution

1921B - Arranging Cats

Idea: pashka, prepared: ikrpprppp

Tutorial
Solution

1921C - Sending Messages

Tutorial
Solution

1921D - Very Different Array

Idea: Vitaly503, prepared: pashka

Tutorial
Solution

1921E - Eat the Chip

Idea: ikrpprppp, prepared: ikrpprppp

Tutorial
Solution

1921F - Sum of Progression

Idea: Vitaly503, prepared: Vitaly503

Tutorial
Solution

1921G - Mischievous Shooter

Idea: Vitaly503, prepared: goncharovmike

Tutorial
Solution
• +111

 » 6 weeks ago, # |   0 nice E and F
•  » » 6 weeks ago, # ^ |   -12 в задаче Е в последней строчке написано Элис хотя должно быть Алиса
 » 6 weeks ago, # |   +12 The problems were nice. I solved A-E in-contest and F about 10 hours later.For some reason I feel like E was easier to figure out than D.Also my F submission is in-queue even though it got accepted earlier (?)
•  » » 3 weeks ago, # ^ |   0 I agree that.E was easier than D
 » 6 weeks ago, # |   +17 prefixsum forces
 » 6 weeks ago, # |   0 Beautiful problems specially a to f Couldnt figure out g in time I misread a,b both which was abs terrible since the penalty I got from both was almost as twice as usual For A I thought that the squares aren't parallel to the Axis so I wrote a function to validate the squares, the i assumed every possible square and find the max Before I code the last part just reread the ! Question and...
 » 6 weeks ago, # |   +3
•  » » 6 weeks ago, # ^ |   0 Why D can use prefix sum without considering absolute value symbols?
 » 6 weeks ago, # |   0 I reached 1000 and I am so happy. Hope to reach pupil soon!
 » 6 weeks ago, # |   0 Finally crossed 1500. Had no idea how to solve F.
 » 6 weeks ago, # | ← Rev. 8 →   +17 I wonder what the intention for the strict limits for F was. The model solution 241944593 runs in approximately 1s, which is around half of the limit, and it consumes almost full memory allowed (1010600 KB).The very same solution reaches very close at the limit just by swapping the array dimensions that leads to a worse cache hit rate: 241946807, which is what my own solution 241780298 exactly did and barely passed.It's quite unfriendly with other slower languages, and with only a few trivially inefficient elements it's easy to exceed the time limit as well as the memory limit. It would've made more sense to set a bit more lenient TL and ML as done in problem G.
•  » » 6 weeks ago, # ^ |   +11 It's always a tradeoff. The problem here is that the optimized naive solution, written in good C++ works about 2.5 s, so we cannot extend the TL any further.
•  » » » 6 weeks ago, # ^ |   0 That's a lot faster than I imagined. Guess you couldn't really do much about the ML as well as Polygon only allows up to 1024 MB ML.
•  » » » » 6 weeks ago, # ^ |   0 Oh, i checked again and I was wrong, we added more tests with many long sequences, and not it works more than 4s, but still pretty close.
•  » » » » » 4 weeks ago, # ^ |   0 indeed the time limit is too tight. same code after converting to c++ by gpt works in 900ms whereas it gives tle on test 3 in java
•  » » » » » » 4 weeks ago, # ^ |   +1 Yes, maps and lists are much slower in Java
•  » » » » » » 4 weeks ago, # ^ |   +1 But there are a lot of accepted submissions in Java, actually. Here is one for example https://codeforces.com/contest/1921/submission/243773379It's sad that you cannot use standard java containers in problems with such strict time limits, but I don't think we can do anything about it. I solved a lot of contests in Java, and at some point I learned how to implement anything using only simple arrays, but it's painful, I agree. That's why I moved to C++ for contests at some point.
•  » » » » » » » 3 weeks ago, # ^ |   0 Thanks for the reply Instead of map and arraylists, I used 2d array and the case which was giving TLE now passes in 450ms
 » 6 weeks ago, # |   +3 Solution for G without prefix sums: 241838352.The idea is very similar to the author's solution with prefix sums over $O(nm)$, but in this solution the recalculation is done over $O(\text{min}(n, m))$. In this solution, I go through all the red squares (from the parsing) and subtract them, and I also go through and add all the green squares.The total time complexity of this solution is $O(nm\ \text{min}(n, m))$.
 » 6 weeks ago, # |   0 E was doable
•  » » 6 weeks ago, # ^ |   +4 Fr but never thought E would be just if elses lol
 » 6 weeks ago, # |   +2 i also had same intution for D as editorial ,but so much less confidence in contest .can anyone please justify why the greedy approach(same as editorial) will work.@authors
•  » » 6 weeks ago, # ^ |   0 Always, the difference between minimum and maximum is the max possible to get... Wym
•  » » » 6 weeks ago, # ^ |   +1 it is maximum diff now ,but by taking out maximum such element,we might be reducing maximum difference for second smallest element. you are saying local optimum decision will lead to global optimum(that is exactly greedy),i am asking why it will always result in optimum answer
•  » » 6 weeks ago, # ^ |   0 Usually proving that swapping any two elements doesn't improve the answer is enough.
•  » » 6 weeks ago, # ^ |   +3 See my submission first before reading the proof.The greedy approach can be neatly summarized as choosing the pair that gives the largest absolute difference and then we can pop the two corresponding elements and then we can continue doing the greedy.We need to prove two things:(1) That the largest distance is either abs(a.front() - b.back()) or abs(a.back() - b.front()).Proof. Note that any selected pair a[i] and b[j] have an associated direction from a[i] to b[j] in the number line (either right or left). If the direction is right, we can make the difference larger if we change a[i] to a.front() and b[j] to b.back(). The case is similar to if the direction is left. (2) Choosing the largest difference is optimal.Proof. Without loss of generality, assume that abs(a.front() - b.back()) gives the largest difference. Assume that the two pairs are (a.front(), b[j]) and (a[i], b.back()) (other cases like when a.front() or b.back() is not paired is trivial). Then by swapping, it's easy to visualize that (a.front(), b.back()) and (a[i], b[j]) is not worse.
•  » » » 6 weeks ago, # ^ |   0 can u pls elaborate (2) choosing largest difference is optimal "Assume that the two pairs are (a.front(), b[j]) and (a[i], b.back())" what are we assumingThen by swapping, it's easy to visualize that (a.front(), b.back()) and (a[i], b[j]) is not worse. After swapping what is not worse than what?
 » 6 weeks ago, # |   0 The Solution Code of D may meet some display problem?On my view, there are some — in the brackets of abs(), they look like: c[i] = b[m — n + i]; s += abs(c[i] — a[i]); I don't know if it's an issue with my browser.
•  » » 6 weeks ago, # ^ |   0 actually the &mdash is the minus sign -
•  » » » 5 weeks ago, # ^ |   0 what does that line mean c[i] = b[m — n + i]; is it b[m-n+i] or what is it
•  » » » » 6 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; } Yup
•  » » 3 weeks ago, # ^ |   0 Me too! It's confusing!!!
 » 6 weeks ago, # |   +10 Can someone explain why are we taking d=sqrt(q) ?
•  » » 6 weeks ago, # ^ |   +23 We want to minimize $nd + qn/d$, When we increase $d$, the first part will increase, and the second part will decrease, and the minimal point will be when they become equal: $nd = qn/d$, from that we can get $d=\sqrt{q}$.
•  » » » 6 weeks ago, # ^ |   0 We can also sort queries by $(d,s \mod d)$, and for all queries with same $(d,s \mod d)$, we preare the prefix sum using items : $a_{s \mod d}, a_{d+s \mod d},a_{2 \cdot d+s \mod d}, \cdots$, which are $\frac{n}{d}$ items in total. For some fixed $d$, $d$ queries would be needed to make prefix sum calculation cover the whole $n$ array. Worst case is when $1+2+3+ \cdots + x=q$, get $x \approx \sqrt q$ , so the total time complexity of prefix sum preparing is $n \sqrt q$.
•  » » » » 5 weeks ago, # ^ |   0 I get really stuck when it comes to understanding the problems so deeply with respect to constraints.
 » 6 weeks ago, # |   +4 Can Problem D be solved with dynamic programming approach? dp[i][j] = maximum diff when a[i] is paired with b[j].transition: dp[i][j] = abs(a[i]-b[j])+max value from dp[i-1] (other than dp[i-1][j] as jth element is paired with current element.)return max value from dp[n-1];is this approach correct?
•  » » 6 weeks ago, # ^ |   0 I also thought about dp but finding max value from dp[i-1] takes O(m) or I can not come up with better way to do it, overall it will be slow. Personally I solved it by sorting both arrays and using two pointers on each of them and taking values by greedy approach.
•  » » » 6 weeks ago, # ^ |   0 I thought something like this .We will need to keep 2 largest values from the dp[i-1] array . As mostly we will use largest value and if the currently chosen index is equal to index with greatest in dp[i-1] then we will use the second largest value. We can maintain this values in such array maxValue[n][2] and update it while processing dp states.
 » 6 weeks ago, # |   -9 почему моё решение 241780647 использует multiset но в тегах не было добавлено структуры данных?
 » 6 weeks ago, # | ← Rev. 3 →   0 Editorial is not attached as "Tutorial" in problem statement page yet. May it would be fixed.. UPD: Fixed Now..
•  » » 6 weeks ago, # ^ |   0 bklode
 » 6 weeks ago, # |   0 F Video editorial + Live Coding (English): https://youtu.be/mJVq_nW8iQk
•  » » 3 weeks ago, # ^ |   0 Thank u man, really helped me
•  » » » 3 weeks ago, # ^ |   0 Welcome
 » 6 weeks ago, # |   0 Can someone help my find out why my submission to E gives WA?: expected: 'DRAW', found: 'BOB'
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 why you are doing wins==true in if(w — ya — 1 <= dh /2) and in else aslo ? in else there will be draw
•  » » » 6 weeks ago, # ^ |   0 Thank you! What a silly mistake...
 » 6 weeks ago, # |   +19 who setted this problem G and why
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +19 Sirs teaching Englishs. 😂 So spreading the awareness xDset is an irregular verb and isn't followed by "ed" in past tense
 » 6 weeks ago, # | ← Rev. 2 →   0 After 18 contests, I've finally reached specialist, and so far, the only active specialist in Seattle! :)
 » 6 weeks ago, # |   0 I have an alt. sol for F that uses memoization.Suppose we split the array into $d$ subsequences of increment $d$ for every $d$ from $1$ to $n$.Ex: Original array is $[1,2,3,4,5]$$d = 1: [1,2,3,4,5]$$d = 2: [1,3,5],[2,4]$$d = 3: [1,4], [2,5], [3]$ (You get the idea)If we can generate both the prefix sums and the partial sums of the values multiplied by their index (eg $[1,3,5]$ becomes $[1\cdot1, 1\cdot1 + 3\cdot2,1\cdot1 + 3\cdot2 + 5\cdot3] = [1,7,22]$.We can use these two precomputed arrays to evaluate the queries efficiently. However, precomputing all of these will be too slow, instead, we can create them and store them as we process queries since we don't need to precompute every subsequence.To store them, we would just need something like a map, the key would be a pair $(d,s\%d)$ where $d$ is the increment and $s\%d$ represents the first element's index of the subsequence.The worst case is that for every query, we have to create both types of prefix sum arrays for the largest, not-yet-computed sequence. It should be clear that given array of size $n$ and $n$ queries, the total iterations should be around $O(n\sqrt{n})$ (or plus a log factor depending on which map).My code: 241999941 (which uses custom hash + unordered map)
 » 6 weeks ago, # | ← Rev. 2 →   0 In problem c, doesn't the phone lose charge at 0 moment and also will the phone lose charge after it sends a message or before? could someone explain?
 » 6 weeks ago, # |   0 Can please tell me why is this submission giving a TLE for Problem F? (Time complexity: $O((N + Q) * sqrt(N))$)
•  » » 5 weeks ago, # ^ |   0 Don't declare vectors(prefix sum) for every test case, make them of fixed size [10^5+1][320]
 » 6 weeks ago, # |   0 I have a nice greedy solution to D which just selects the largest possible distance at every iteration until all elements in $a$ have been paired, but I don't have a proof.Code: 242031960Can anyone prove it?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 I have also used this method during the contest.In sorted $a_1, a_2, \cdots a_n$ and sorted $b_1,b_2, \cdots b_m$ , WLOG, let us assume max diff value is $| a_1 - b_i |$. Obviously $i$ could only be $1$ or $m$ . If $i=1$, when $b_1 < a_1, |a_1-b_1|<|a_n-b_1|$ , when $b_1 > a_1, |a_1-b_1|<|a_1-b_m|$ , so $i \neq 1$. If $i=m$, when $b_ma_1$ . Assume in optimal solution, $b_j$ paired with $a_1$ , if $b_m$ is not paired with any value in $a$, we can move $a_1$ from pair with $b_j$ to $b_m$ to get a better solution. If $b_m$ is paired with some $a_k$ , since \$a_1
•  » » » 5 weeks ago, # ^ |   0 Thanks. You motivated me to prove it myself. I came up with a not-so-elegant proof with the same outline as yours
 » 6 weeks ago, # |   0 Not able to figure out whats wrong with my solution https://codeforces.com/contest/1921/submission/242087071
 » 5 weeks ago, # | ← Rev. 3 →   0 Don't understand the equations in F at all. Feels like editorial has been written for someone who already understands the solution."The key idea is that we know how to calculate the sum (i−l+1)⋅ai for l≤i≤r fast – we need to calculate all prefix sums i⋅ai and ai for 1≤i≤k, then take the difference between the r-th and (l−1)-th of i⋅ai and subtract the difference between the r-th and (l−1)-th multiplied by l−1"This certainly could have been explained in a better way.
 » 5 weeks ago, # |   0 Thanks for the editorial!
 » 5 weeks ago, # |   0 Can somebody explain solution of problem E to me? I am just gonna type what I understood so somebody else won't have to type much.From what I understood, Alice can only win when the distance is odd and vice versa(This part was intuitive). Draw happens when loser tries to dodge winner in the game as he knows he is gonna lose. So to draw losing player can run to either extreme left or right and If there's enough distance in either left or right they successfully dodge the winner.Is this correct or am I missing something? Beside calculating all of this is too much as well.
•  » » 5 weeks ago, # ^ |   0 Correct. They will meet on some row which is predefined. At the meeting junction if its alice turn then bob has to run for draw or alice win or vice versa.It has comments
 » 5 weeks ago, # |   0 I can't understand what is the code doing in problem D like why are you using this code with some define lines that are not even written , please don't forget that there are some beginners here I can't figure out what is mdash
•  » » 5 weeks ago, # ^ |   0 Somebody in comment already said that its just minus. Here's the link.
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 did you understand the code because I'm trying for more than 5 hours and reached nothing and I feel so tilted, the idea is so complicated , or maybe I'm just so dumb
•  » » » » 5 weeks ago, # ^ |   0 There's a youtube video for this entire contest. It's in english by some master or cm. Link.NO, I couldn't understand the solution they have given in editorial.I'll try to explain how I did it.Look from array b you want to choose n integers and arrange it in a order such that diff is maximum as stated in problem.Now for every position if you think about it there are only four options.First this is something for sake of notation. min of array a = mna, max of array a = mxa min of array b = mnb, max of array b = mxbNow just create all 4 pairs using above numbers let's say d1 = abs(mna — mxa), d2 = abs(mna — mnb) and so on.Now you just have to pick whatever is maximum.So if you keep both a and b sorted and create 4 pointers each pointing to above mxa, mxb, mna, mnb. You can increment decrement pointers based on which one is maximum.
•  » » » » » 5 weeks ago, # ^ |   0 nice explanation thanks but there should be no point of trying (mna-mnb) and (mxa-mxb) and the other two will be enough right ?
•  » » » » » » 5 weeks ago, # ^ |   0 Yeah those two cases are useless.
 » 5 weeks ago, # |   0 how did so many people solve D ,like is there any standard problem for it or I'm just bad at this because even after reading editorial and tracing almost 10 different codes I still don't think that I can come up with this my self at all, and with the problem being 1100 it's more frustrating
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 DP/greedy problems are usually difficult to prove but the solutions are rather intuitive and rely largely on observation. After solving lots of DP/greedy problems, you will start to observe the patterns in these types of problems.Basically the solution herein lies in the fact that we know the maximum sum is formed by using the largest/smallest elements in b.To maximize the sum, greedily we want to pair largest b elements with smallest a elements, and vice versa because doing so, we get larger absolute differences.The first idea is to greedily pair elements one by one such that their absolute difference is the largest. However, you may have noticed this solution does not always work. The reason lies in the non-greedy structure of this problem, pairing something affects the maximum sum of absolute difference of remaining pairs in the future, and another pair which is not chosen greedily may be better.Rather than forming the maximum sum, we could instead bruteforce over all possible maximum sums and update ans = max(ans, s). We know we could form the maximum sum by pairing elements of a with k largest elements and n-k smallest elements in b, for some k.For simplicity's sake, we will use words and slowly transition into using variables.After sorting a and b, we have.. a = smallest, smaller, .., smaller, .. largest b = largest, larger, .., larger, .. smallest Let's start by pairing a with the n smallest elements in b. There are many ways to arrange these in some order such that we get the maximum possible sum, but we can easily observe that the optimal order is always to pair the smallest with largest, for each element. |smallest - larger| + .. + |largest - smallest| >= |smallest - smallest| + .. + |largest - larger| thereby using the corresponding indices, |a[0] - b[m-n]| + .. + |a[n-1] - b[m-1]| >= |a[0] - b[m-1]| + .. + |a[n-1] - b[m-n]| With similar logic, we iteratively form the next sum by replacing the pair a[0],b[m-n] with a[0],b[0] and so on. We can easily calculate this updated sum in O(1) using S = S - |a[i]-b[m-n+i]| + |a[i]-b[i]|Thus we form the possible maximum sums as such, S[0] = |a[0] - b[m-n]| + .. + |a[n-1] - b[m-1]| S[1] = |a[0] - b[0]| + (S[0] - |a[0] - b[m-n]|) S[2] = |a[1] - b[1]| + (S[1] - |a[1] - b[m-n+1]|) . . . S[n] = |a[n-1] - b[n-1]| + (S[n-1] - |a[n-1] - b[m-1]|) and thus, ans = max(S[0], S[1], .., S[n]).
 » 5 weeks ago, # |   0 Hello everyone. I am having trouble with problem F. I understand that its a standard problem but the part where we need to hop by d steps is making it hard for me to understand.I have a scenario can someone please explain on this. d = 5, k=6, s=3Here the sequence required is: a3 + 2a8 + 3a13 ... 6a28I have 2 series which can be computed in O(1): S1 = a1 + a2 + a3 ... an S2 = a1 + 2*a2 + 3*a3 ... n*anHow can I get the required sum if someone is available to dry run it.
•  » » 5 weeks ago, # ^ |   0 Precomputed prefix sums starting from index 3 with step size 5:ps1 = a3 + 2a8 + 3a13 + 4a18 + 5a23 + ... ps2 = a3 + a8 + a13 + a18 + a23 + ...Let's say you want to compute the sum for 3 elements starting from index 13:a13 + 2a18 + 3a23 = (3a13 + 4a18 + 5a23) -2*(a13 + a18 + a23) You can get get these two parts from prefix sums ps1 and ps2.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 There's a youtube video for this entire contest. It's in english by some master or cm. Link. Actually he just explains brute force approach so don't waste your time on it.Brute force approach is easy to figure out but I am not able to understand editorial. All I understand is they are multiplying it by some value in order to reduce time complexity when running the queries. What is even the intuition behind the solution?Can somebody explain the intuition or Is it just way above my level so I should leave it?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Maybe putting summed indexes this way helps: 1 2 3 4 5 6 2 3 4 5 6 3 4 5 6 4 5 6 5 6 6 If you need sum from 4 to 6 then you have to subtract triangle 1..3 and rectangle of top 3 lines which is (4+5+6)*3 = (sum without multiplication) * (s/d)After some optimisations you get answers quite fast.
 » 4 weeks ago, # |   0 243976867 that was tight
 » 11 days ago, # |   0 Can problem D be solved with using two pointers?
 » 6 days ago, # |   0 c[i] = b[m — n + i]; anyone???
 » 4 days ago, # |   0 247587440,the solution of D,You can use a two-pointer to solve this problem