### cry's blog

By cry, 13 days ago,

Thanks for participating! Despite the round being unrated, we hope you've enjoyed the problemset. We put a lot of effort into this round :prayge:

I want to give huge thanks to Dominater069 and satyam343 for their heavy contributions to the subtasks of G. If you're participating out of competition, we hope you enjoyed attempting these bonus subtasks. Otherwise, we hope you will enjoy upsolving them!

2009A - Minimize!

Problem Credits: cry
Analysis: cry

Solution
Code (Python) (ntarsis30)

2009B - osu!mania

Problem Credits: cry
Analysis: cry

Solution
Code (Python) (chromate00)

2009C - The Legend of Freya the Frog

Problem Credits: vgoofficial
Analysis: cry

Solution
Code (Python) (ntarsis30)

2009D - Satyam and Counting

Problem Credits: vgoofficial
Analysis: cry

Solution
Code (Python) (ntarsis30)

2009E - Klee's SUPER DUPER LARGE Array!!!

Problem Credits: cry
Analysis: cry

Solution
Code (Python) (ntarsis30)

Bonus: Solve in $\mathcal{O}(1)$.

Code (Python) (Non-origination)

2009F - Firefly's Queries

Problem Credits: cry
Analysis: cry

Solution
Code (C++) (awesomeguy856)

2009G1 - Yunli's Subarray Queries (easy version)

Problem Credits: cry, vgoofficial
Analysis: vgoofficial

Solution
Code (C++) (yash_9a3b)

2009G2 - Yunli's Subarray Queries (hard version)

Analysis: Solution 1: vgoofficial, Solution 2: awesomeguy856

Prologue
Solution 1 (Lazy Segment Tree, Offline)
Code (C++) (vgoofficial)
Solution 2 (Binary Lifting, Online)
Code (C++) (awesomeguy856)

2009G3 - Yunli's Subarray Queries (extreme version)

Analysis: Dominater069

Solution
Code (C++) (awesomeguy856)
• +155

 » 8 days ago, # |   +8 Auto comment: topic has been updated by cry (previous revision, new revision, compare).
 » 8 days ago, # | ← Rev. 2 →   +20 The G2 problem can also be solved by the MO algorithm. My solution is:https://mirror.codeforces.com/contest/2009/submission/279633321
•  » » 8 days ago, # ^ |   0 Can you explain your solution in detail
•  » » » 7 days ago, # ^ |   +10 I've just solved it with mo+sqrt decomposition too. here my 279746467The idea is the following: get array ans from G1 problem. ans[i] means the min number of operations needed in range [i,i+k). Now, for a query (l,r), the problem reduces to find min({ans[l]}) + min({ans[l],ans[l+1]}) + min({ans[l],...ans[r-k+1]}). This is range queries and it can be solved with mo+sqrt by dividing ans in buckets and sorting the queries Your bucket size X = q/sqrt(n) // this is an optimal value, no need to explain here. You can also choose X = sqrt(n) as your bucket size. Sort queries. Say query1 = l1,r1 and query2 = l2,r2. if l1/X == l2/X, then they are on the same bucket and order by r1 < r2. If on different bucket, return l1/X
•  » » » » 7 days ago, # ^ | ← Rev. 3 →   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; } Thanks for Explanation. I understood your solutionI have solved it using Range Min Query and Next Smallest Element in arrayMy Submission : 279798999Time Complexity : O((N+Q)*logK)
•  » » 7 days ago, # ^ |   0 It can also be solved using merge-sort treeSolution using merge-sort tree: https://mirror.codeforces.com/contest/2009/submission/279748718
•  » » » 7 days ago, # ^ |   +3 Can you explain the idea, the code is too messy to read
•  » » » » 6 days ago, # ^ |   +4 from G1 we precompute the answer for every window of k and store it in a new array (c). now answer for query (l,r) will be sum(j=l, r-k+1) min(i=l,j)ci. now we construc a merge-sort tree that stores values in (l,r). lets say sub-array c is like cl,cl+1,cl+2,cl+3,...,cr. this vector seg[400001] in (i,l,r) stores cl,min(cl,cl+1),min(cl,cl+1,cl+2),...min(cl,cl+1,...cr). now lets say query is (l,r), and we are in a segment (gl,gr), we also maintain an int pre_mn that calculates min in (l,gl-1). answer from this seg would be min(pre_mn,cgl),min(pre_mn,cgl,cgl+1),...min(pre_mn,cgl,...,cgr). now lets calculate sum of this values using binary search and prefix sum by finding the index until where cgl+i is greater than pre_mn, as it will become pre_mn.
•  » » » » » 21 hour(s) ago, # ^ |   0 ur merge sort tree is storing cl,min(cl,cl+1),min(cl,cl+1,cl+2),...min(cl,cl+1,...cr).and we need to query min( cl , c(l+1) , c(l+2), c(l+2) ... ) how u did that ?
 » 8 days ago, # |   -32 binary search forces
•  » » 8 days ago, # ^ |   0 Apart from E which question needed Binary Search?
 » 8 days ago, # |   +109 Nice Div. 3 contest !
•  » » 7 days ago, # ^ |   -6 maybe Div.2
 » 8 days ago, # | ← Rev. 3 →   -13 In problem E i used prefix sum and got MLE bruh...
•  » » 8 days ago, # ^ |   0 n<=1e9 binary search will work
•  » » 8 days ago, # ^ |   0 its obvious coz you are taking 10^9 memory
•  » » 7 days ago, # ^ |   0 binary_search is usefulmaxn = 1e9
 » 8 days ago, # | ← Rev. 2 →   0 Can we solve D faster than O(n^2) if xi's were real numbers instead of integers ?
•  » » 8 days ago, # ^ | ← Rev. 2 →   +1 It appears I am wrong. Disregard this
•  » » » 8 days ago, # ^ |   +5 actually, no i think there are other cases, Spoilerany x and y values that stisfy x*y = 1 here will count :proof : a^2 = 1 + x^2 , b^2 = 1 + y^2 and a^2 + b^2 = (x+y)^2 hence, 2 + x^2 + y^2 = y^2 + x^2 + 2*x*y or x*y = 1 .
•  » » 7 days ago, # ^ |   0 I'm interested in your n^2 solution, is it something to do with circles?
•  » » » 7 days ago, # ^ |   0 Even easier (use the fact that left difference times right difference has to be equal to onesee prrof) : iterate over each point where y= 0 name it a , now for each point where y= 1 find its x difference from a say it is d now check if there is a point (1/d,1) and the rest is same as D.
 » 8 days ago, # |   +1 In the C problem, there is a neat way to check whether there will be any other case or not.Following the given explanation, one can see, that if any of the points on the side which contributes 2 points to the triangle are moved, the angle increases, and since we can't get them any closer without falling into Case 1, we can't have any more cases.Another way that can be used is the fact that the slopes of the two perpendicular lines must give a product of -1.So, if the points were $(x_{1}, 0), (x_{2}, 1), (x_{3}, 0)$, then we would have :$(\frac{x_{2} - x_{1}}{1 - 0}) * (\frac{x_{3} - x_{2}}{0 - 1}) = -1$which leads to :$(x_{2} - x_{1})(x_{3} - x_{2}) = 1$And since the differences will always be integers, we have :$x_{1} + 1 = x_{2} = x_{3} - 1$
•  » » 8 days ago, # ^ | ← Rev. 5 →   0 It's a good explanation for showing there is no other cases. I came up with similar idea using geometric properties of the median in a right triangle. Other than triangles with sides in a vertical line $(x, 0), (x, 1)$, triangles must have sides on a horizontal line. Then the median of the right triangle separate out the two parts $(x - t, k) ,(x + t, k)$ with the last vertex is $(x, k'), k,k'\in \{0,1\}$. Then the median of length m calculated as $m^2 = 1^2 + t^2\$, thus $(m - t)(m + t) = 1$, with similar argument $m$ must be 1. Sides on horizontal line is 2, then $t = 1$
 » 8 days ago, # |   0 ~~~~~~ if(x > y){ cout << 2* ceil(1.0 * x/k) - (ceil(1.0 * x/k) >= ceil( 1.0 * y/k)) << endl; continue; } else { cout << 2 *ceil(1.0* y/k)<< endl; continue; }~~~~~why this fails??
•  » » 8 days ago, # ^ |   0 if they are equal you should not do -1
•  » » » 8 days ago, # ^ |   0 yes actually true, but when i removed that eequality then too it was giving wrong.
•  » » » » 8 days ago, # ^ | ← Rev. 3 →   0 you should not use doubles as vgoofficial mentioned
•  » » 8 days ago, # ^ |   0 We should avoid doubles whenever possible. For ceiling calculation, you may instead use the modulo operator (%) or use (x+k-1)//k
•  » » » 8 days ago, # ^ |   0 okay <3! thank you!
•  » » 8 days ago, # ^ |   0 You should not check for x > y, rather compare the number of steps to complete them.
 » 8 days ago, # |   0 I'm really happy to unrate b/c I'm really mad because I don't submit my code. :)))))
 » 8 days ago, # |   +112 G2 and G3 are not div4 problems. They should only appear in div2 or div1.
•  » » 8 days ago, # ^ |   +7 On the contrary, they cannot appear in div2 or div1They are far too standard for both of them.They were never meant to be solved by actual participants, A — G1 is the actual div4 round. They are meant to educate higher rated people.
•  » » » 8 days ago, # ^ |   +17 so why have div 4 :/
•  » » » » 8 days ago, # ^ |   -9 wdym? why have these "bonus" tasks in div4? or why have div4 at all? why have these "bonus" tasks in div4? how does it hurt you? Ignore it if you want to. It is not fit for a div2 or div1 clearly, why not have it here incase someone finds it useful? why have div4 at all? Because we have an abundance of easy tasks and an abundance of low rated people? D
•  » » » 8 days ago, # ^ | ← Rev. 2 →   +22 clearly not div4, admit your mistake instead of making baseless points.Dominater069 orz thanks for admitting it
•  » » » » 8 days ago, # ^ | ← Rev. 2 →   -9 They were never meant to be solved by actual participants i admitted it lol.Not every task exists has to exist for intended participants. Authors (and me) wanted to add bonus educational tasks for high rated participants. I really dont understand how the intended audience was affected
•  » » » » » 8 days ago, # ^ |   +41 I appreciate the extra tasks. G2 is fairly new to me, and G3 was totally new to me. These were good tasks for learning.
•  » » » » » 7 days ago, # ^ |   0 Yesterday I was feeling extra confident for some reason so i started from G2 and got destroyed. Luckily it went unrated. So that's how I intended participant got emotional damage LOL. Anyway I'll try to understand editorial.
•  » » » » » 7 days ago, # ^ |   +7 honestly, based from previous div 4s, i think G3 (or maybe also G2 idk) should be a bonus question that appears in the editorial, as a challengealthough it's probably gonna be dismissed by lots of people, it'll be consistent with other rounds where in the editorial, they mentioned that they thought of harder constraints of the problem but not actually inserting it inside the problemset to make the round somewhat consistent.
•  » » » 8 days ago, # ^ |   +28 Why Div.4 have to educate Master or Grandmaster? I cannot understand.I think that that an overwhelmingly difficult problem is standard so can't put it in Div.2 doesn't mean that it can plugged in Div.4. I want a good problem must to be placed where a more people can solve it.
•  » » » » 8 days ago, # ^ |   -11 Why Div.4 have to educate Master or Grandmaster? It doesnt have to, but isnt it good if it does? Who did it harm smh? Experts who want to be able to AK every div4 round. welp sad for themAuthors tried to do a nice thing by including extra tasks (something which they didnt have to do and still would be paid the same) I want a good problem must to be placed where a more people can solve it. except G3 or G2 aren't good problems. Educational? sure. But educational problems should not affect rating.
•  » » » » » 8 days ago, # ^ |   +17 I hate you so much
•  » » » » » 8 days ago, # ^ | ← Rev. 3 →   +14 I think it's more like "it could've benefited more people in a higher division" rather than "it harmed those people."While I see your argument, and it may be true that it won't be very good to be in a Div. 1 round, I honestly don't think there would be many solves even if it was in a Div. 2. I agree that standard problems shouldn't heavily affect ratings, but I think the benefits are far bigger to have this problem in a Div. 2 round instead of a Div. 4 round.See how many of the 'target' people for these problems have actually participated in this round. If you want to attract those 'target' people and educate them, it needs to be rated for them to be motivated. Candidate masters won't expect a Div. 4 round to actually educate them, so there is little reason for them to even register for the contest and read the problem. It's not like having a few official solves ruins the whole authority of the rating system. It's way more important to motivate the fitting people to read and try the problem.Also, G2 was actually an interesting problem for me. It may involve only a few standard techniques, but I don't think such standardness necessarily made the problem bad.
•  » » » » » » 8 days ago, # ^ | ← Rev. 2 →   -24 i agree with you that it would be on the edge of being fine for div2 because its hard enough so affecting only small number of people But you cant easily port a problem in between rounds, or decide the division based on one problem even if it doesnt affect much, i dont see many div2 coordinators who would accept G3 as a d2F (even though it would be somewhat fine imo) there was a high likelihood that G3 existed on the internet since it is a very natural problem, and indeed it's max variant existed on hackerrank. https://www.hackerrank.com/challenges/little-alexey-and-sum-of-maximums/problem (somebody solved it using this too)
•  » » » » » 8 days ago, # ^ |   +48 Oh, you think G2 and G3 aren't good problems... Then why they are in contest? Isn't it wierd? Is it OK that not good problems in Div.4? But educational problems should not affect rating. Then why Educational CodeForces (Div.2) exists? Just do plug all Educational CodeForces problem in Div.3 or Div.4. But there is reason that Educational CodeForces exists.And why you're saying like that? Nobody said "I want to solve all of them!"I'm just saying that problem must be its suitable position, so it can teach more people. If you do not think so, then I'm sorry. But I believe every problemsetter and coordinator, tester knows that Div.4 is not for Master or Grandmaster, but for Newbie or Pupil.
•  » » » » » » 8 days ago, # ^ |   +11 you think G2 and G3 aren't good problems From problem solving perspective, it is mostly standard and implementation for me.From eudcational perspective, it is useful as a problem to teach you the power of sweepline algorithms. There can be educational value in a problem despite it not being a "good" problem. Then why Educational CodeForces (Div.2) exists? It's fake educational and has been for a long time.years before, it used to be unrated and containing actually standard tasks. Now, it's just slightly more standard than average div2, but the name stuck. This change happened almost solely because they became rated rounds. I'm just saying that problem must be its suitable position, so it can teach more people But it comes at the cost of affecting people's ratings. Who likes to lose rating to a standard problem? I certainly don't
•  » » » » » » » 7 days ago, # ^ | ← Rev. 2 →   +3 just to be clear, does "standard" mean a problem that's solvable using ONLY well-known algorithms and methods?
•  » » » » » » » » 7 days ago, # ^ |   +3 like everything it is a spectrumA problem is more standard the more well known algorithms and methods as opposed to thinking about the problem.so something like ratio of well known stuff : thinking needed gives you an idea about how standard a problem is
•  » » » 7 days ago, # ^ |   +39 Without a doubt, this problem cannot appear on Div1, but it is actually fine as Div2F (we definitely had worse and more standard d2F).The following only applies to unofficial contestants:the mild complaint I had is that I participated in a div 4 round, expecting div 4 difficulties and “div 4 level resistances” only to find that this is not the case. Div 4 to me had been a “quick and easy AK and funny internet speed test with no verdicts for 10 minutes and so every penalty is worth 25 or more”. In fact, div2/3/4 (and obviously also div1) have distinct feels to it, so I am not so sure in general making it feels like div2, which is what happened when G2 and G3 we’re included.This only made sense under my belief that this problem can totally be used on D2F as is.
•  » » » » 7 days ago, # ^ | ← Rev. 2 →   0 G3 is probably not fine as 2F either, as there is a square root solution which is trivial to think of (no sweepline or monotonic stacks or rectangle queries) but annoying to implement (279798653).
•  » » » » » 7 days ago, # ^ | ← Rev. 2 →   0 Can you explain it in more details? I fail to see anything sqrt that isn’t a reinterpretation of a rectangle queries, it doesn’t seem like your solution is MO’s based.it is also worth noting that G3 is also trivial if you have segment tree beats (range chmin, historic sum). Implementation is at least half of the problem.
•  » » » » » » 7 days ago, # ^ |   0 I have solved it by processing queries offline.I iterate over the leftbound $l$ of the query in decreasing order, while maintaining two arrays $p$ and $q$ through my square root structure.When at a certain $l$, $p$ and $q$ are defined in the following manner: $p_i = f[a_l, \dots , a_i]$ $q_i = \sum_{j = l}^{j = i - k + 1} {f[a_j, \dots , a_i]}$ So the answer for any query $[l, r]$ simply becomes $\sum_{i = l + k - 1} ^ {i = r} {q_i}$.To maintain this array, my square root structure needs to be able to perform the following kinds of queries: $p_i \leftarrow x, \; l \leq i \leq r$ for some $[x, l, r]$ $q_i \leftarrow q_i + p_i, \; l \leq i \leq r$ for some $[l, r]$ Compute $\sum_{i = l}^{i = r} {q_i}$ for some $[l, r]$. which can be done.
•  » » » » » » » 7 days ago, # ^ | ← Rev. 2 →   +14 Your solution is identical to the intended one (Edit; after a slight more read on the intended solution it may have some subtle differences, nonetheless, it is identical to mine). It is just that you happens to choose to implement it via sqrt structures.This task could be completed by (lazy) segment tree too (no beats). I would say this is just difference in preference and the fact that it is passable by sqrt does not make it easier. Perhaps, this task is more standard/widely known to be doable by sqrt. In this case, then the task would be more standard than what I initially thought.
•  » » » » » » » » 7 days ago, # ^ |   -31 why??
•  » » » 7 days ago, # ^ |   0 me, who on;ly solved A-G1 :(
•  » » » 7 days ago, # ^ |   0 I agree but I think it would be a better fit for a Div.3. Div.3 contests still contains standard questions
•  » » » 7 days ago, # ^ | ← Rev. 3 →   +3 Ye G2 and G3 educate me, I don't know why the problem like this can't appear in div2 or div1, only observe problem can. It would be nice if Codeforces Div 2 mix observe problem and standard problem :)
•  » » 8 days ago, # ^ |   +26 I can see G2 barely being on the edge of a Div. 3 but G3 is straightforward way too difficult. It's maybe a harder one even for a 2F.
•  » » » 8 days ago, # ^ |   0 G3 is definitely below d2F level
•  » » » » 8 days ago, # ^ |   +3 I think it's more like most of the other 2Fs are too difficult in general, but okay.
•  » » » » » 8 days ago, # ^ |   0 if most 2F are more difficult then that’s the 2F difficulty level lmao
•  » » » » » » 8 days ago, # ^ | ← Rev. 2 →   +3 You can say the same thing to this: if we keep having these kind of problems in 4G, then this becomes a 4G level problem. However, that would be far from what I'd expect from a 4G, and 2F is kind of such state already.
•  » » » » » » » 8 days ago, # ^ |   0 I agree that G2/3 are beyond div 4 level but I think it’s clear that they’re not intended to be solved by div 4 participants
•  » » » » » » » » 8 days ago, # ^ |   +13 But they are in a DIV4 contest
•  » » » » » » » » » 8 days ago, # ^ |   0 It's an extra problem to be upsolved for education value. What harm did putting these questions here do? Did it affect anyone? No. Only 1 trusted user solved G2 and G3.
•  » » » » » » » » » 8 days ago, # ^ |   0 Maybe my opinion is stupid but when you say a DIV4 contest, I expect a contest that contains problems that a DIV4 participant can solve or upsolve. Similar logic for other divisions. But it is fine. Feel free to put a Div1F in the next DIV4 contest.
•  » » » » » » » » » 8 days ago, # ^ |   +34 How many people in division 2 can solve F you think? What about the old div 4 G about 2-sat? Do you think newbies and pupils have a chance of inventing that on the fly without seeing 2sat before? Almost every final question on each round is far too hard for its division. We only included G2 and G3 because they follow quite naturally from G1, and if is impossible to port questions between rounds.
•  » » » » » » » » » 7 days ago, # ^ |   -13 I never said the past div4 rounds were perfect. Also, I said I expect the target participants to be able to SOLVE or UPSOLVE the problems. So, because every final question on each round is too hard for its division, every round should follow this pattern? Anyway, it is your round, do as you want.
•  » » » » » » » » » 7 days ago, # ^ |   +3 "Also, I said I expect the target participants to be able to SOLVE or UPSOLVE the problems."Ok? isn't that the purpose of G2 and G3? For div.4 participants to upsolve? Of course, you don't have to upsolve it right now. You can always come back when you're better. The problem doesn't disappear.I don't see any harm in contests with a harder final problem than its intended division. It gives strong participants of the intended division something to think about for the rest of the contest (instead of doing nothing), and makes more of a competition for higher rated participants.
•  » » » » » » » » » 7 days ago, # ^ | ← Rev. 2 →   +26 do you really think that average div 4 users are gonna be able to understand the editorial for G2 and G3 just so that they can upsolve it hours or days after the contest? the point of upsolving a round that is consistent with your division is so that you can get AC on all of the problems by understanding what the editorial said shortly after the round ended. this is why most difficult problem in div 4s is usually around 1700-1900ish (that 2-sat 2100 problem doesn't count), because although most div 4 users cannot come up with the idea during the contest, the authors knew that some (not very small group of) div 4 users will understand the editorial given for the problem so that they can upsolve it immediately (or after some short period of time)also, "makes more of a competition for higher rated participants" ok but the intended target for this round are pupils lmao
•  » » » » » » » » » 7 days ago, # ^ |   -6 If you can’t understand G2 or G3, you can pretend those problems never existed, and move on. Alternatively, you can note their existence down and return later. It’s up to you.A-G1 already makes a complete div 4.
•  » » » » » » » » » 7 days ago, # ^ |   +3 so basically G2 or G3 is equivalent as the Ex problem in abc, where sometimes it's so hard it's not even intended for users who partake in abc
•  » » » 7 days ago, # ^ |   0 I don't know if G3 is really div2. F level. I just brute-forced my G2 solution with a random optimization and it got AC (after the contest). Here's my Submission.If anyone is interested, try to hack me!
•  » » » » 7 days ago, # ^ | ← Rev. 2 →   +3 Hacked, brute forcing with a G2 solution would result in $O(n)$ per query in worst case. Hence, if there are many instances where $ind = i + 1$, you are not skipping much numbers and therefore TLE.
•  » » » » » 7 days ago, # ^ | ← Rev. 3 →   0 I also knew that it would give TLE on a case where my array ans[] had consecutively increasing elements. But I was not able to think of such a case.Not sure how it managed to pass all the pretests.Btw, thanks for hacking.
 » 8 days ago, # |   +41 Sharing my video of winning the round along with explanations of my solutions: https://www.youtube.com/watch?v=JhL-oPzptlI
•  » » 6 days ago, # ^ |   +10 Thank you very much for an explanation for G3! Took a long time to implement solution on my own but this was worthy.
 » 8 days ago, # |   0 E was great !
 » 8 days ago, # | ← Rev. 2 →   0 I tried solving E by interpreting it as a function and using the quadratic equation, but it keeps giving the wrong answer for n = 1000000000, k = 1000000000 typedef int64_t ll; ll n, k, sk; cin >> n >> k; sk = gauss(k - 1); // starting k : the gauss sum of the numbers before the start of the series ll max = gauss(k + n - 1) - sk; // quadratic equation // pref = gauss(n) - sk // pref = (n^2 + n)/2 - sk // where does 2pref intersect max? (because we want pref = max-pref) // n^2 + n - 2*sk = max // n^2 + n - (2*sk + max) = 0 // a = 1, b = 1, c = -(2*sk+max) // delta = 1 ^ 2 - 4 * -(sk+max) // delta = 1 + 4 * (2*sk + max) ll delta = 1 + 4 * (2*sk + max); // x1,2 = (-b +- sqrt(delta))/2*a // = (-1 +- sqrt(1 + 4 * (2 * sk+max)))/2 ll x1 = round((-1 + sqrt(delta)) / 2); ll x2 = round((-1 - sqrt(delta)) / 2); ll x = min(abs(x1), abs(x2)); ll ans = 2 * (gauss(x) - sk) - max; cout << abs(ans) << '\n'; 
•  » » 8 days ago, # ^ |   0 I also used the same logic. You probably have to use unsigned long long. I was able to pass the cases using that.
•  » » » 8 days ago, # ^ |   0 But wouldn't a <= sqrt(D). so, a — sqrt(D) will never be a solution since it is negative why are u checking it ??
•  » » 8 days ago, # ^ |   0 was stuck in that for some time, but then used unsigned long long and it worked.. But came to the comments to see that it can be done by using binary search, need to see how they are applying it to the V curve, i mean ternary can work but binary.. no intuition honestly
•  » » 7 days ago, # ^ |   0 In the end, I had to use Java, because the delta's value was 999,999,999,940,000,000,001 in the n = 1000000000, k = 1000000000 test case.Here's my accepted submission: 279807077
 » 8 days ago, # | ← Rev. 3 →   +4 For G1: There's a mathematical logic behind "ai — i". Let's say we have a sequence "(C, C + 1, C + 2, C + 3 + ...)". Any 'ith' element ai will be equal to "C + i — L", where 'L' is the starting index of the window. So (ai = C + i — L) => (C — L = ai — i). This (C — L) is a static part, which means we have to find the maximum occuring "ai — i".
 » 8 days ago, # |   0 You can think of E as an inverted mountain array and look for the minimum point using binary search
 » 8 days ago, # |   0 I think G1 can be solved by finding the longest increasing subarray for each query in O(logN)Ans will be (right — left + 1) — longest;
•  » » 8 days ago, # ^ |   0 counter example: arr = [1, 4, 9].f(arr) = 2, while your method returns 0.
•  » » » 8 days ago, # ^ |   0 Longest *consecutive... Correction
•  » » » » 8 days ago, # ^ |   +5 counter example: arr = [1, 10, 3].f(arr) = 1, while your method returns 2.
•  » » » » 8 days ago, # ^ | ← Rev. 3 →   0 counter example arr = [1 2 5 4] here l = 1, r = 4, your answer = 4 — 2 = 2. but answer should be 1
 » 8 days ago, # |   0 My solution 279640569 of F, is giving correct output as 13 on my local and online compilers but wrong answer as 12 on codeforce's judge for following test case:15 14 8 3 2 47 10Can someone explain it?
•  » » 7 days ago, # ^ |   0 Use C++ 20 while submitting the code.
 » 8 days ago, # |   0 import java.util.*; public class one { public static void main(String[] args) { java.util.Scanner sc = new java.util.Scanner(System.in); int t = sc.nextInt(); for (int i = 0; i < t; i++) { long x = sc.nextLong(); long y = sc.nextLong(); long k = sc.nextLong(); long jumpsX = (x + k - 1) / k; long jumpsY = (y + k - 1) / k; long moves = Math.max(jumpsX, jumpsY) * 2 ; if (x>y) { moves--; } System.out.println(moves); } sc.close(); } } why wasnt this AC for the frog and freya question?
•  » » 6 days ago, # ^ |   0 compare jumpX and jumpY, not x and y when doing moves--
•  » » » 6 days ago, # ^ |   0 oh my god how did i miss that....gosh thank u for replying
 » 8 days ago, # |   0 can somebody explain how they used binary search for E? i found the function to be unimodal and hence i applied ternary search to find the point of minima, i dont get the intuition for binary search (i dont see monotonicity)
•  » » 8 days ago, # ^ |   0 There is a V formation, check my solution. To find minima just use formula of summation n there are different cases where mid will lie
•  » » 8 days ago, # ^ |   0 Just look for the point where current_sum > (total_sum)/2. The correct answer is nearby there. .
 » 8 days ago, # | ← Rev. 2 →   +6 The entire universe is against me for becoming pupil. Was doin super well today until that announcement appeared, L cry, L servers... MikeMirzayanov I think its time to add a new god damm server.
 » 8 days ago, # | ← Rev. 2 →   +24 I miss SlavicG,mesanu,flamestorm ... (╥﹏╥)
 » 8 days ago, # | ← Rev. 4 →   +3 Here is a clean(er than the edi) solution to C and a unique solution to D.For C we can see that Spoiler$\lceil \frac{x}{k} \rceil$ + $\lceil \frac{y}{k} \rceil$ + $|\lceil \frac{y}{k} \rceil-\lceil \frac{x}{k} \rceil|$ — ($\lceil \frac{x}{k} \rceil$ > $\lceil \frac{y}{k} \rceil$)This is because note that x goes first, and at some point we will have to use 0 for some turns once already at the coorindate for x or y.Firstly, lets imagine we do not take more steps for x than we do y, it would go x,y,x,y and continue until we are all done, therefore we do not need to add 1. However if we were to take more steps for x than we do y, it creates a pattern x,y,x,y,x which requires an extra x, ys would simply become 0 after y is reached which is where the absolute value part of the problem comes from. x.As for D, which I found much more interesting, though do note I misread it and as such overcomplicated it. SpoilerThere were 2 main cases, 1: The right angle is rotated some multiple of 90 degrees from 0, and 2: The right angle is some (45 + 90x)%360 degrees, I saw the latter as a way to be able to use the x,y -> s,t transform used in geometry. This transform essentially turns x,y coordinates into coordinates of the y intercepts of slope y=x+b and y=-x+b. By doing so, we can create s,t = {x+y, x-y} though a bit of algebra. Using this transform, we have essentially rotated by 45 degrees making the last case trivial (I did not read that it was only 0 or 1 so I had not thought about the x+2 y^1 thing.) After this some basic map spam gives AC, do note that as long as the X is equal we can just add n-2 due to all points being on 0 or 1 on the Y.If you are wondering the simpler solution to D for case 2 is that it simply has the points x,y x+1,y^1, x+2,yHere are submissions for both, hope that puts these problems into a bit of a different perspective! C: 279561294 D: 279622363This contest had quite a few issues with the queue and pages loading, however I still enjoyed the problems and I hope you did too! I would have gotten plus VE if this contest was rated however instead of complaining I had fun solving these problems even if I did overcomplicate D a bit, however it would give insight to a possible harder version of the problem if it was not only 0 and 1 on the Y.
• »
»
3 days ago, # ^ |
Rev. 5   0

### I think this one is simpler 280325230.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int32_t main() {
int tt = 1;
cin >> tt;
while (tt--) {
ll n;
cin >> n;

set<ll> a, b;
int x, y;
for (ll i = 0; i < n; i++) {
cin >> x >> y;
if (y == 0) a.insert(x);
else b.insert(x);
}

if (a.size() < b.size()) swap(a, b);

ll ans = 0;
for (auto &it : b) {
if (a.count(it)) ans += (a.size() + b.size()) - 2;
}

for (auto &it : b) {
if (a.count(it - 1) && a.count(it + 1)) ans++;
}

for (auto &it : a) {
if (b.count(it - 1) && b.count(it + 1)) ans++;
}

cout << ans << "\n";
}

return 0;
}


 » 8 days ago, # |   +1 This was a good round, sad that it got unrated.
 » 8 days ago, # |   +1 thanks for writing, issues not your fault!
 » 8 days ago, # | ← Rev. 2 →   0 I have a different solution for G2. Use a set and a map to get the minimum moves for the window of size k starting from every index. Then use a stack to build a vector to store the index of next smaller number. Then use jumps to next smaller number to compute answer for every range. Code#include #include #include using namespace std; using namespace __gnu_pbds; #define intt int64_t void solve() { intt n, k, q; cin>>n>>k>>q; vector v(n); map mp; for(int i=0;i>v[i]; v[i]-=i; } set> s; for(int i=0;i ans(n-k+1, 0); auto it = --s.end(); ans[0]=k-(*it).first; for(int i=k;i0) s.insert({mp[v[i-k]], v[i-k]}); mp[v[i]]++; s.insert({mp[v[i]], v[i]}); auto it = --s.end(); ans[i-k+1]=k-(*it).first; } vector next_min(n-k+1, 1e9); stack ck; for(int i=n-k;i>=0;i--) { if(ck.empty()) ck.push(i); else { while(ck.size() and ans[i]<=ans[ck.top()]) { ck.pop(); } if(ck.size()) next_min[i]=ck.top(); ck.push(i); } } while(q--) { intt l, r; cin>>l>>r; intt i = l-1; intt p =0; while(next_min[i]<=r-k) { p+=(next_min[i]-i)*ans[i]; i=next_min[i]; } p+=(r-k-i+1)*ans[i]; cout<>t; while(t--) { solve(); } return 0; } 
•  » » 7 days ago, # ^ |   +1 Hacked, your solution runs in O(n) per test case. Since in worst case, next_min[i] is just i+1, and you would be just jumping a number at a time.
•  » » » 7 days ago, # ^ |   0 Nice! Thanks for this!!
 » 8 days ago, # |   0 Nice Div3 Contest !!!
 » 8 days ago, # | ← Rev. 9 →   0 My code is failing in case of- 1000000 100000 10 givng me answer- 200000 !! Can someone point the mistake ?? Thanks #include using namespace std; int main(){ long t; cin>>t; for(long i=0;i>x>>y>>k; while(x>0 || y>0){ int result_x=min(x,k); x-=result_x; int result_y=min(y,k); y-=result_y; count+=2; } cout<
•  » » 7 days ago, # ^ |   0 Because for this case in last iteration the count should be += 1 instead of += 2, because we reached (x, y) by doing the x operation only so why count y operation too.
•  » » 7 days ago, # ^ | ← Rev. 2 →   0 the count after your process is always an even number. Note that at a moment when (x == 0 && y == 0), you should break the loop immediately.
•  » » » 7 days ago, # ^ |   0 Tried that it is giving one less the actual output!! but nvm this solution is only good in smaller testcases + it is a bruteforce solution !!
•  » » 7 days ago, # ^ |   0 Moreover I tried this solution earlier , This will give you TLE
•  » » » 7 days ago, # ^ | ← Rev. 2 →   0 Yes i know, it is only good if testcase are small !! Before this contest, I don't know ceil formula of ceil function !!
 » 8 days ago, # |   +1 I loved the HSR and Genshin references. Please do continue naming problems on our favourite characters. Thank you!
 » 8 days ago, # | ← Rev. 4 →   0 I have implemented the same logic as the solution above for 2009D - Satyam and Counting, but keep getting Wrong answer on test 2: wrong answer 7th numbers differ - expected: '100', found: '99' I cannot see the corresponding input.Can anyone please tell me what I am missing? https://mirror.codeforces.com/contest/2009/submission/279654100
•  » » 8 days ago, # ^ |   0 I spotted one mistake but that does not fix the Wrong Answer above. The mistake is that each array should have size n+1 instead of n because each 0 <= x <= n. I also fixed the ranges accordingly. But, as mentioned, the Wrong Answer stays the same.
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 I figured it out. Because of my confusion with the range of x, the code decrements x. That maps x=0 to x=-1, which does not result in an error but in undesired behavior when used as a list index.
 » 8 days ago, # |   0 We can use binary search to search for the greatest i such that a1+⋯+ai≥ai+1+⋯+anIsn't the solution for E wrong? If the above statement is the correct solution, the greatest i is just len-1 no?
 » 8 days ago, # | ← Rev. 2 →   0 In problem E's editorial ... We can use binary search to search for the greatest i such that a1 + ⋯ + ai ≥ ai+1 + ⋯ + an . Note that here, the positive difference is minimized. If we move to i+1 , then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases. It should be a1 + ⋯ + ai ≤ ai+1 + ⋯ + an because we want to minimize the difference.cry (ignore the formatting)
•  » » 8 days ago, # ^ |   +8 ahh oops, thanks for letting me know
 » 8 days ago, # |   0 Can't understood editorial solution for G2
 » 7 days ago, # |   0 G2 can also be solved using sqrt decomposition in $O(Q*N/B*log(B))$ where $B=\sqrt{N}$.For each query, maintain the answer from left to right. If the current minimum is greater than the current block's minimum, we can use a binary search to find where the current block's first minimum is.Submission: 279662760
 » 7 days ago, # |   0 Can we use ternary search at the problem E, though we need to find the minimum here?
•  » » 7 days ago, # ^ |   0 We can. Submission: 279662737
•  » » » 7 days ago, # ^ |   0 yes. It is more intuitive to me.
•  » » » 34 hours ago, # ^ |   0 I have applied ternary search during the contest but got wrong answer. could you help me finding the problem.
 » 7 days ago, # |   -10 anyone mind to explain solutions of G3?
•  » » 7 days ago, # ^ |   +3 i wrote a really long solution as you can see above in the editorial :(Any specific queries in it?
 » 7 days ago, # | ← Rev. 2 →   0 Can someone suggest a testcase where this will fail for C? It fails on testcase 2.wrong answer 862nd numbers differ — expected: '2', found: '1' Spoilervoid solve() { int x, y, k; cin >> x >> y >> k; int ans = 0; if (y >= x) { ans += (y / k) + (y % k > 0); ans *= 2; } else { ans = 2 * (x / k + (x % k > 0) - 1) + 1; } cout << ans << endl; cerr << endl; return; } 
•  » » 7 days ago, # ^ |   0 Cannot compare x and y. You should compare ceil(x/k) and ceil(y/k) instead.Countercase: x=9, y=8, k=3. Your solution prints 5 but correct answer is 6
•  » » » 7 days ago, # ^ |   0 thanks for this case!
 » 7 days ago, # |   0 279728269can someone pls tell me why is this failing
 » 7 days ago, # |   0 The solution to A talks about choosing c and then talks about "distance". The solution to Problem D doesn't even mention (let alone prove/sketch) that the mentioned right-angled triangles are the only ones.
•  » » 7 days ago, # ^ |   +4 Thats because people who read the editorial for A and people who read editorial to D are different audiences. Obviously more experienced people need less intermediate steps to understand a solution. Look at any div 1 F solution and see how fast paced they are.I remember the general guidelines is to keep solution to every problem approximately equal lemgth.
•  » » » 7 days ago, # ^ |   0 What? My objection to A was not that it had too much fluff, but that it makes absolutely no sense.
 » 7 days ago, # |   0 You can just say that G3 is range sum of history sum(
 » 7 days ago, # |   0 last 3 problems G123 were actually suitable Div2DEF I think since many red & orange people couldn't solve G23.
•  » » 7 days ago, # ^ |   0 As G2/G3 have been discussed above, I’ll just say G1 is absolutely not a div2 D.
•  » » » 7 days ago, # ^ |   0 you mean too hard to belong div2 D right?
•  » » » » 7 days ago, # ^ |   0 No, I think it’s too easy.
•  » » » » » 7 days ago, # ^ |   0 agree, D2C at mostalthough G2 is definitely harder than my normal encounter of D2D lmao
 » 7 days ago, # |   0 Why my C wrong? 279562541
»
7 days ago, # |
0

this is code of frog jumping problem c of 971 what is wrong with this code ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# include

using namespace std; int main() { int t=0; cin>>t; while(t--){ int x,y,k,ans,d=0; cin>>x>>y>>k; if(x<=y){

d=y/k;

if(y%k!=0){ d=d+1;} ans=2*d; } else if(x>y){ d=x/k; if(x%k!=0){d=d+1;} if((d-1)*k>y){ans=2*d-1;} else{ans=2*d;}

} cout<<ans<<endl;

} return 0; ~~~~~~~~~~~~~~~~~~~~~~~~~

 » 7 days ago, # |   0 Nice div3 so im sad for urt
 » 7 days ago, # |   0 My submission to problem E was exactly the bonus solution mentioned in the editorial. I spent around 1 hour debugging during the contest but the last sample case was failing. After the contest I submitted the same solution and it passed. I believe there is some precision bug in Apple clang. Can anyone else try this on the last sample test?** Please ignore the excessive use of long double. I was getting panicked :) **
•  » » 7 days ago, # ^ |   0 facing same issue on the last sample
 » 7 days ago, # |   0
•  » » 7 days ago, # ^ |   0 pls highlight the error in my code
 » 7 days ago, # |   0 In D, how do we prove that there will be no other cases? Also, can someone share how did they arrive at those 3 points (last case)?I eventually realized that those 3 points made a right triangle during contest, but it took me a long time.
•  » » 7 days ago, # ^ |   0 in all other cases one angle will become obtuse :)
 » 7 days ago, # |   0 Hi guys I'm new here. When a solution is provided in C++ does that imply that the time constraint for the problem is not achievable using a language like python?
•  » » 7 days ago, # ^ |   0 No
•  » » » 6 days ago, # ^ |   0 Thanks.
 » 7 days ago, # | ← Rev. 2 →   0 firefly queries(f) #include #include #include using namespace std; using namespace __gnu_pbds; #define ll long long #define pb push_back #define pll pair template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; template using ordered_multiset = tree, rb_tree_tag, tree_order_statistics_node_update>; #define endl "\n" #define vpll vector> #define vvll vector> #define vll vector #define sec second #define fi first #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define repr(i,n) for(ll i=n-1;i>=0;i--) #define rep(i,n) for(ll i=0;i c(n); for(ll i=0;i>c[i]; //-------Seive of Eratosthenes--------------------------------------- const ll MOD = 1e9 + 7; const ll N = 200100; vector factorials(N + 1), inv_factorials(N + 1); vector is_prime(N, 1); void seive(){ is_prime[0] = is_prime[1] = 0; for (int i = 2; i * i <= N; i++){ if (is_prime[i]){ for (int j = i * i; j <= N; j += i) is_prime[j] = 0; } } } ll lcm(ll x,ll y){ return x*y/__gcd(x,y) ; } ll bin(ll x, ll n, ll mod) { ll ans = 1; x = x % mod; while (n > 0) { if (n % 2 == 1) { ans = (ans * x) % mod; } n = n / 2; x = (x * x) % mod; } return ans; } void precompute_factorials(ll n, ll mod) { factorials[0] = 1; for (ll i = 1; i <= n; ++i) { factorials[i] = factorials[i - 1] * i % mod; } inv_factorials[n] = bin(factorials[n], mod - 2, mod); for (ll i = n - 1; i >= 0; --i) { inv_factorials[i] = inv_factorials[i + 1] * (i + 1) % mod; } } ll ncr(ll n, ll r, ll mod) { if (r > n || r < 0) { return 0; } return factorials[n] * inv_factorials[r] % mod * inv_factorials[n - r] % mod; } vector getfactors(ll n){ vector ans ; for (int i=1; i<=sqrt(n); i++) { if (n%i == 0){ ans.pb(i); if (n/i != i) ans.pb(n/i); } } return ans ; } void solve() { ll n,q ; cin>>n>>q; geta(a,n); vector pre(n); pre[0]=a[0]; for(int i=1;i>l>>r; l--,r--; ll q1=l/n,r1=l%n; ll q2=r/n,r2=r%n; // q1+r1-1 -->n && 0-->q1-1 //q2 --> q2+ r2-1 ll ans=0; if(q1==q2){ ll st=q1+r1; ll len=r-l+1; if(st+len-10) ans-= pre[st-1]; } else{ ans += sum-(st>0?pre[st-1]:0); ans += pre[(st+len-1)%n]; } } else{ ll st1=(q1+r1); if(st10?pre[st1-1]:0); if(q1>0) ans += pre[q1-1]; } else{ if(q1>0){ st1%=n; ans += pre[q1-1]-(st1>0?pre[st1-1]:0); } } ll ed2=q2+r2; if(ed20?pre[q2-1]:0); } else{ ans += sum-(q2>0?pre[q2-1]:0); ed2%=n; ans += pre[ed2]; } if(q2-q1-1>0) ans += (q2-q1-1)*1ll*sum; } cout<> t1; while(t1--) solve(); return 0; } can anyone check the error in my code getting output: wrong answer 247th numbers differ — expected: '4', found: '-165885590936472'
•  » » 7 days ago, # ^ |   0 which problem ?
 » 7 days ago, # |   0 from math import ceil for i in range(int(input())): x,y,k = list(map(int, input().split())) if y>=x: print(ceil(y/k)*2) else: print(2*ceil(x/k)-1) why does this not work for C
 » 7 days ago, # |   +10 Great problems G1,G2,G3! It's nice to have bonus educational problems like these, although I feel like these problems could've also been placed in a div 3 round, since more higher rated participants take part in div 3 rounds than div 4.
 » 7 days ago, # |   0 kindly explain quadratic eq approach to E
•  » » 7 days ago, # ^ | ← Rev. 2 →   0 The function that we're minimizing is abs(quadratic). Imagine the graph of a quadratic — on taking absolute value, the part below x-axis goes above x-axis. Now, the minima occurs at one of the roots, because everything else is positive. Graph is symmetric around both roots, so we need to check one of them only.However, the root may not be an integer. Say, the root of our quadratic is equal to 1.22. You need to check at both 1 and 2 for minima because your range, in this question, is integers only. That is why he takes min(f(i), f(i+1)). At least, this is my understanding of the solution.
•  » » » 7 days ago, # ^ |   0 I am also trying the quadratic formula method but can't find what I am missing. Can anyone point out what I am doing wrong 279810011
 » 7 days ago, # |   0 an anyone explain why from here ∑rj=l+k−1f([al,al+1,…,aj]). we can associate to here Let ci=f([ai,...,ai+k−1]). ∑r−k+1j=l(minji=lci)I mean supposed we caculate the answer for interval [l, l+k] then if we take min(c[l], c[l+1]), it could be smaller than the answer. For example: [l, l+k] is already consecutive, so the answer for it would be k+1, but if we take min(c[l], c[l+1]), it will be only k.
 » 7 days ago, # | ← Rev. 2 →   0 Nevermind. Understood
 » 7 days ago, # |   0 1 2 2 1 3 2 1 2Is this a valid test for G1?
 » 7 days ago, # |   0 Can someone help me with problem Ehow is val1 in the solution equal to (mid+k-1+k)*mid//2 ?from what I understand val1 is the sum of integers from k->k+mid, and for that I did this, sumof k->k+mid = sumof 0->k+mid - sumof 0->k-1 = ((k+mid)*(k+mid+1) - k*(k-1)) / 2 = (k^2 + mid^2 + 2*mid*k + k + mid - k^2 + k) / 2 = (mid^2 + 2*mid*k + 2*k + mid) / 2 = (mid*(mid+2*k) + 2*k+mid) / 2 = (mid+1)*(2*k+mid) / 2 this is where I arrive at and cant relate this with how the equation from the solution came
 » 7 days ago, # |   0 I think I found a mistake on problem D. My intuition is that there exists a Pythagorean Triplet (a, b, c) such that a belongs to triplet (m, n, a), and b also belongs to triplet (x, y, b). It is proven that such triplet exists. For example, (15, 20, 25), where 15 is also a hypotenuse of (9, 12, 15), and 20 is also a hypotenuse of (12, 16, 20). Then I drew these three triangles and got five points: (0,0), (0,12), (25,12), (25,0), and (9,0). It can be shown that there exists 7 right triangles among these 5 points, however, the answer given by the solution is 6. This is because the solution did not count the triangle (15, 20, 25).
•  » » 7 days ago, # ^ |   0 I just realized a mistake, I forgot the y value is between 0 and 1.
 » 7 days ago, # |   0 Dominater069 Test cases of Problem G3 are too weak.
 » 7 days ago, # | ← Rev. 2 →   0 In problem G2 binary lifting solution, what does w(h, i) mean?
 » 7 days ago, # |   0 why my solution in G1 wrong :<. my solution did i forgot to reset something?
•  » » 7 days ago, # ^ |   0 check mine out, maybe you can figure out what's wrong (the one i submitted during contest)
 » 7 days ago, # |   0 Hi folks,I'm trying to solve 971, task D.for this example9 1 0 2 0 3 0 4 0 5 0 2 1 7 1 8 1 9 1I get answer 9, but the task output says it should be 8. Can you confirm if the answer is really 8?
•  » » 7 days ago, # ^ |   0 ...and if the answer is really 9, how did over 5200 people solved an unsolvable task? Hmmm.... :)
•  » » » 7 days ago, # ^ |   0 I got it. It is 8 indeed.
 » 6 days ago, # |   0 G3 binary lifting almost the same as G2.
 » 6 days ago, # |   0 Why one code is giving TLE other not can anyone explain advance thanks **Problem G1** void ram() { int n, k, q; cin >> n >> k >> q; vector a(n); vector ans(n - k + 1); for (int i = 0; i < n; i++) { cin >> a[i]; } int j = 0; multiset st; map mp; for (int i = 0; i + k <= n; i++) { int end = i + k - 1; while (j <= end) { if (mp[a[j] - j] > 0) { st.erase(st.find(mp[a[j] - j])); } mp[a[j] - j]++; st.insert(mp[a[j] - j]); j++; } ans[i] = k - *prev(st.end()); if (mp[a[i] - i] > 0) { st.erase(st.find(mp[a[i] - i])); } mp[a[i] - i]--; if (mp[a[i] - i] > 0) { st.insert(mp[a[i] - i]); } } while (q--) { int l, r; cin >> l >> r; l--; cout << ans[l] << endl; } } **Other Code Problem G1** void ram() { int n, k, q; cin >> n >> k >> q; vector a(n); vector ans(n - k + 1); for (int i = 0; i < n; i++) { cin >> a[i]; } int j = 0; multiset st; map mp; for (int i = 0; i + k <= n; i++) { int end = i + k - 1; while (j <= end) { if (mp.find(a[j]-j)!= mp.end()&&st.count(mp[a[j]-j]) != 0) { st.erase(st.find(mp[a[j]-j])); } mp[a[j] - j]++; st.insert(mp[a[j] - j]); j++; } ans[i] = k-*prev(st.end()); if (mp.find(a[i]-i)!= mp.end()&&st.count(mp[a[i]-i]) != 0) { st.erase(st.find(mp[a[i]-i])); } mp[a[i] - i]--; if (mp[a[i] - i] != 0) { st.insert(mp[a[i] - i]); } } while (q--) { int l, r; cin >> l >> r; l--; cout << ans[l] <
•  » » 6 days ago, # ^ |   0 Both code are same only changes in if codition if (mp.find(a[j]-j)!= mp.end()&&st.count(mp[a[j]-j]) != 0) { st.erase(st.find(mp[a[j]-j])); } other: if (mp[a[j] — j] > 0) { st.erase(st.find(mp[a[j] — j])); }
 » 6 days ago, # |   0 Can someone please explain problem F? I can't understand the editorial.
 » 6 days ago, # |   0 Anyone facing issues viewing their submissions? Whenever I click on my submission to check test results I get 403 Forbidden error.
 » 6 days ago, # |   0 I have an easier way to solve D with an array and 2 for. Here is my submission 279941542
 » 6 days ago, # |   0 Can anyone kindly tell why this approach is wrong towards E- KLee's super duper large array submissionI am starting from k and ending at n+k-1 as my high. Then for each mid value, i am finding the prefix sum till that and suffix sum and finding absolute difference. Whichever gives us minimum is the answer.
•  » » 5 days ago, # ^ |   0 change if(tillmid<=mid1&&tillmid<=mid2){ `cout<
 » 5 days ago, # |   0 The Solution of E written by the mathematical method is so beautiful. Thoroughly calculate the sum function of |a1+a2+...-an| , then find the zero position for this sum function, awesome math!
 » 5 days ago, # | ← Rev. 5 →   0 In fact, I built a tree to solve G2.First, just like G1, I worked out the $f([a_i,a_{i+1},\cdots,a_{i+k-1}])$ for all $i$ such that $1\leqslant i\leqslant n-k+1$, then let $w_i = f([a_i,a_{i+1},\cdot,a_{i+k-1}])$.Link an edge $i \xrightarrow{w_i\times(j-i)} j$, such that $j$ is the minimum that satisfies $j > i$, $w_j < w_i$ (if such $j$ doesn't exist, then let $j\leftarrow n-k+2$).It can simply prove that these edges consitute a tree, and the root of tree is $n-k+2$.Let $dis_i$ denote the distance from $i$ to the root.When querying $[l, r]$, we need to do a binary search to find the shallowest $p$, such that $p$ is an ancestor of $l$ and $p \leq r-k+1$. Therefore, the answer is $dis_l - dis_p + w_p \times (r - k + 1 - p + 1)$.This algorithm runs within $O(\log^2 n)$ time for each query. (if you use the "longest chain separation" to calculate the k-th ancestor within $O(1)$ time, it can be optimized to $O(\log n)$)You can find my code here: https://mirror.codeforces.com/contest/2009/submission/279915573.But now I have difficulties in using the same thought to solve G3.Please help me. Thanks a lot.
 » 5 days ago, # |   0 Can someone explain why my submission is giving wrong answer?
»
5 days ago, # |
0

# Can someone explain the bonus solution of problem E

 » 4 days ago, # | ← Rev. 2 →   0 https://mirror.codeforces.com/contest/2009/submission/280117676 can anyone help me with this java code.. why it is wrong?? this is G1
 » 26 hours ago, # |   0 Can anyone state the approach for O(1) solution for E?
 » 24 hours ago, # |   0 can someone explain the lazy segtree solution for G2 in more detail please?