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

### Pa_sha's blog

By Pa_sha, history, 2 weeks ago,

2008A - Sakurako's Exam

Tutorial
Solution in C++
Solution in Python
Rate the problem

2008B - Square or Not

Tutorial
Solution in C++
Solution in Python
Rate the problem

2008C - Longest Good Array

Tutorial
Solution in C++
Solution in Python
Rate the problem

2008D - Sakurako's Hobby

Tutorial
Solution in C++
Solution in Python
Rate the problem

2008E - Alternating String

Tutorial
Solution in C++
Solution in Python
Rate the problem

2008F - Sakurako's Box

Tutorial
Solution in C++
Solution in Python
Rate the problem

Tutorial
Solution in C++
Solution in Python
Rate the problem

2008H - Sakurako's Test

Tutorial
Solution in C++
Solution in Python
Rate the problem
• +62

 » 2 weeks ago, # | ← Rev. 9 →   +22 Great problem E. I had a little fun and leaked the solution with a useless if statement (that makes no logical sense and that is wrong): if < 2: print(best + 2) and just a bit above that a if n == 1 so that it would still AC even though there is something useless and wrong. This will make it easy to report cheaters. This is a new thing I think we should all do. Leak solutions with easy to spot but hidden watermark for those who don’t understand the algo. https://pastebin.com/VSP4VCnewe just need to crawl all AC and check those with a if n < 2.This is an example of a cheater that would have never been caught otherwise: https://mirror.codeforces.com/contest/2008/submission/279191114 Because he or she was clever enough to really rework my solution. SpoilerRemoving the useless < 2 and + 2 obviously still passes (I took his solution and removed the useless statement) and those who have read the problems will understand why + 2 makes absolutely no sense (and also doing if n == 1 and just after that if n < 2) https://mirror.codeforces.com/contest/2008/submission/279249347
•  » » 2 weeks ago, # ^ |   +1 Great work lmao
•  » » 2 weeks ago, # ^ |   +1 Smart!!!
•  » » 2 weeks ago, # ^ |   +9 however if they have a brain and catch the weird code as they read, they might remove it which gives them a free AC (i guess plagiarism check will catch their solution if its similar but still)
•  » » » 13 days ago, # ^ |   0 If you need help for Div3.E you won't find the weird code. And the goal is to instil fear among cheaters, not to catch them all.
•  » » » » 13 days ago, # ^ |   0 bro why havent the ratings been adjusted yet, any idea?
•  » » » » » 13 days ago, # ^ |   0 In such contests, there are long hacking phases. After them the new test cases from hacking are used to judge the accepted solutions. This is system testing. Once it finishes, there will be the ratings.
•  » » » » 13 days ago, # ^ |   0 Another victim submission
•  » » » » » 12 days ago, # ^ |   0 So they cheated and didn't even manage to get AC, lmfao.
•  » » 13 days ago, # ^ |   0 Instead of that, why not just leak a hackable solution so you don't have to report it—just hack their code?
•  » » » 13 days ago, # ^ |   0 I'm not clever enough to do that unfortunately, but you should do it next contest if you have the IQ to do it!
•  » » » » 13 days ago, # ^ |   +3 Many people leak hackable codes; all you need to do is add a case that is not covered in the pretests and print a random answer for that case. Many dumb ppl fall for this.
•  » » » » » 5 days ago, # ^ |   +1 .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; } I'm going to have to step up and spend some weeks learning how to leak hackable codes because the guy didn't even get skipped lol
•  » » 6 days ago, # ^ | ← Rev. 2 →   +1 The fact that the guy i mentioned didn’t get skipped is sad
•  » » 49 minutes ago, # ^ | ← Rev. 2 →   0 @MikeMirzayanov MikeMirzayanov
 » 2 weeks ago, # |   0 In problem F, I guess it should be "divide" instead of "delete first value by second" :)
 » 2 weeks ago, # |   +14 Great round, I loved G and H very much.Anyways, I read E wrongly during the round and I assumed we can do deleting operation as much as we want. Can anyone solve it? (if you can solve that, you can solve E easily.) Spoiler:I solved during the contest too, all answers are same except "abacba", in that our answer will be 2 because we can erase 'c' and any 'a'.My solution is based on dp (saving minimum number operation for i.th prefix, and our current string length is odd or even) and brute forcing 1st and 2nd char.I added only one dimension for did I used any operation, if we delete that you can solve easily infinity version: 279135317
•  » » 2 weeks ago, # ^ |   0 I solved the same misread on E initiallyIt is straight forward dynamic programming after fixing the alternating string characters
•  » » » 2 weeks ago, # ^ |   0 Can you explain how the misread problem is a dp problem? Even though I misread and can't solve E, I still want to solve the misread version more.
•  » » » » 13 days ago, # ^ |   0 I have such solution. Fix first two characters and use dp for levenshtein distance. But it takes $O((k\cdot n)^2)$ time where k is the size of the alphabet
•  » » » » 13 days ago, # ^ |   +1 https://mirror.codeforces.com/contest/2008/submission/279276801 what I believe is correct.The dp state is the parity of the string taken till now. the transitions come naturally from either deletion or modification or doing nothing
•  » » 13 days ago, # ^ |   0 Brother, what happened to your rating in fall of 2023?
•  » » » 13 days ago, # ^ |   0 Looks like he's trolling.
•  » » 13 days ago, # ^ |   0 Hey, sorry for bothering you, but I'm curious about your dp solution. During the contest, I attempted to solve it with dp but failed. Could you explain your approach a bit more, please?
•  » » » 13 days ago, # ^ |   0 Lemme explain, What MisterReaper has defined is this: dp[i][j][k] = minimum cost to build a k parity array from prefix i, and j is whether you have used a removal operation yet or not.The transitions are better explained by looking at his code directly, but the general idea is to understand that when you want to build an even parity alt string with prefix i, then if: if your current character s[i] is suitable to take the place of the end of the string you are building that that's always optimal. Obviously then you would have to "pull" the rest of the answer from dp[i — 1][j][!k], !k because when replacing the alt string's last char, we would be building the rest of the string of a different parity. It's always a replacement unless we are making the deletion (obv!).Now the "only one deletion" bit is not to difficult to infuse from here, if you trying to figure out the transitions of a state like dp[i][1][j] it can be pulled from two different states actually, which corresponds to whether you have already used up your operation (in which case you will pull from the dp[i — 1][1][!k] state, a replacement) and if you are going to use the operation on the current s[i] itself, in which case you need to pull from a dp[i — 1][0][k] state, note its k and not !k, because deletion will not change the parity of the string we are willing to build, we just need to "borrow" what i — 1 has already calculated. Note that now the problem can be extended even more freely by changing the cost of the operations. Since we are taking care of every transition, adding the cost of deletion whenever we are deleting and similar for replacing and doing nothing (cost 0) is not a very difficult extension to the problem.
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   0 Thank you so much for the clarification! After reading your explanation, I believe I understand the logic behind this. However, I have one more question, we don't need to visit every state like his code, right? For example, when we tried to build the first character of the alt string, we simply needed to visit dp[1][0][0] and dp[1][1][0]. Is that correct? His codevoid solve() { int N; std::cin >> N; std::string S; std::cin >> S; for(int i = 0; i < N; ++i) { S[i] -= 'a'; } int ans = INF; std::vector, 2>> dp(N + 1); for(int i = 0; i < 26; ++i) { for(int j = 0; j < 26; ++j) { dp[0][0][0] = 0; dp[0][0][1] = dp[0][1][0] = dp[0][1][1] = INF; for(int k = 0; k < N; ++k) { dp[k + 1][0][0] = dp[k + 1][0][1] = dp[k + 1][1][0] = dp[k + 1][1][1] = INF; chmin(dp[k + 1][0][1], dp[k][0][0] + (S[k] != i)); chmin(dp[k + 1][1][0], dp[k][0][0] + 1); chmin(dp[k + 1][0][0], dp[k][0][1] + (S[k] != j)); chmin(dp[k + 1][1][1], dp[k][0][1] + 1); chmin(dp[k + 1][1][1], dp[k][1][0] + (S[k] != i)); chmin(dp[k + 1][1][0], dp[k][1][1] + (S[k] != j)); } ans = std::min({ans, dp[N][0][0], dp[N][1][0]}); } } std::cout << ans << '\n'; return; } 
•  » » » » » 12 days ago, # ^ |   0 Indeed for the forst character there are only two possible paths, however in general, all dp states needs to be transitioned properly, a state will automatically end up as "inf" if as you are implying, was unreachable.
•  » » » » » » 12 days ago, # ^ |   0 Thank you, now I got it! Btw, I've just written a code for this problem. Although the time complexity I think is equal, I got TLE somehow. Is it because it has many if else statements in it? 279423444
•  » » » » » » 12 days ago, # ^ |   0 Ahh, so the problem is the language version I chose, I didn't know gcc 13-64 run faster than gcc 7-32. Thank you for your help, I appreciate it! Have a good day man!
•  » » » » » » » 12 days ago, # ^ |   0 you got this!
 » 2 weeks ago, # |   0 https://mirror.codeforces.com/contest/2008/submission/279144095Why this solution get TLE for Problem D
•  » » 2 weeks ago, # ^ |   0 try implementing dfs without funtion may be recurion calls is taking time;
•  » » » 13 days ago, # ^ |   0 yes use for loop , that might help.
•  » » 11 days ago, # ^ |   0 dfs would take time and would give tle, as the number of calls are more, subsequently you are doing additional operations on top of this, try via dsu (the existing structure is already in dsu format), have a look to my solution — https://mirror.codeforces.com/contest/2008/submission/279831257
 » 2 weeks ago, # |   0 In the problem G tutorial there should have been k = k — a2 + a1 + 1 instead of k = k — a2 + a1 — 1
 » 2 weeks ago, # | ← Rev. 7 →   0 In C , Can be solved in $\mathcal{O}(\sqrt{r-l})$ and can be optimized by binary search in $\mathcal{O}(\log (r-l))$ using $\frac{n(n+1)}{2}$, and can be optimized to $\mathcal{O}(1)$ by quadratic equation The maximum length of array $a$ is obtained when the difference of two consecutive differences is minimized ; Thus we set the difference of two consecutive differences is only 1 , For example consider $l=1,r=10$ thus we can consider the following array as the optimal choice $a=[1 \xrightarrow{+1} 2 \xrightarrow{+2} 4 \xrightarrow{+3} 7]$thus the maximum length is $4$ , Notice we can form an $\textbf{Optimal Model}$ , $a$ can be considered as : $a=[l,l+\text{T}(1),l+\text{T}(2),l+\text{T}(3),.....,l+\text{T}(\max)]$since each time we've an element $l$ + Sum of First $n$ integers called Triangular Numbers $T(n)=\frac{n(n+1)}{2}$We want to determine the value of $x$ above i.e. $\text{What's maximum } x \text{ such that } l+\text{T}(x) \le r$We can reverse this with Quadratic Formula : $\frac{n(n+1)}{2}=f \implies n=\frac{\sqrt{8f+1}-1}{2}$Consider $(f=r-l+1)$Since we may have rational part We've to perform ceiling , thus $\max(x)= \lceil \frac{\sqrt{8(r-l+1)+1}-1}{2} \rceil$279123925Overall nice contest Pa_sha orz
•  » » 2 weeks ago, # ^ |   +1 because no one should be solving A like that
•  » » » 2 weeks ago, # ^ |   0 Optimization when not needed Bad solutions when not intended
•  » » » 2 weeks ago, # ^ |   +1 At least I solved C assuming $(1 \le l,r \le 10^{18})$
•  » » » 9 days ago, # ^ | ← Rev. 4 →   0 Ok , I up-hacked some recursion solutions :DHack by the hack of MathModel >_< I'm wondering how the test used in hack MathModel didn't appeared in judging above hacked submissions ?!
•  » » 2 weeks ago, # ^ |   0 I don't think that last linked submission of yours is constant time. It uses the sqrt() function.
•  » » » 2 weeks ago, # ^ |   0 Check time/ standings
•  » » » » 13 days ago, # ^ |   0 It's not constant time. sqrt() is log2.
•  » » » » » 13 days ago, # ^ |   0
•  » » » » » » 13 days ago, # ^ |   +1 But sometimes, they may give wrong answer. So, it is better to use binary search to find sqrt in any case
•  » » 2 weeks ago, # ^ |   0 Hi. Your solution for A cannot pass because it is $O(t\cdot (a+b)\cdot 2^{a+b})$ which is a lot. On maximum tests it is $100\cdot 20\cdot 2^{20}$ which is approximetly $10^9$.For C you are right. In fact, $O(\sqrt{r-l})$ is okey for Div3B, so we didn't take it away.Thanks for your feedback
 » 2 weeks ago, # |   0 please someone explain to me in problem: 2008G — Sakurako's Task. Why the gcd of all numbers is the key, I cant see the idea behind.
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   +9 So there is a basic concept. If I give you 2 numbers like 2 and 3 and say you that you can use 2 and 3 any number of times and you can either add them or subtract them then what are the possible numbers you can generate. Answer :- You can generate any integer from 2 and 3.Reason :- GCD of 2 and 3 is 1 therefore you can use 2 and 3 to create 1 (3 — 2) Now for any integer x you can generate it by using (3 — 2) x times. Now take 2 and 4 for example. Their gcd is 2 so you can generate 2 from them (4 — 2). Now you can generate any even number from its gcd by repeating (4 — 2) any number of times but you cannot make any odd number using it. Go in G after taking gcd of all, suppose gcd is x therefore optimal array to form will be [x, 2x, 3x, ... ]Sorry if I made you more confused by my explanation but if your doubt is not cleared I will try to explain with a different approach.
•  » » » 2 weeks ago, # ^ |   +3 great explanation
•  » » » 13 days ago, # ^ |   0 is there any blog that you can suggest to read for this topic
•  » » » » 13 days ago, # ^ | ← Rev. 2 →   0 Actually there is a concept named Linear Diophantine Equation similar to this. You can look it up on Cp algorithms. Hope it helps.
•  » » » 13 days ago, # ^ |   0 But why this array is optimal... means how is it helping in finding kth mex maximum??
•  » » » » 13 days ago, # ^ |   0 Ok so assume you have 2 arrays [1, 2, 3, 4] and [0, 1, 2, 3] what do you think which one of them will have max value of mex1 Array 1 will have mex = 0 and array 2 will have mex = 4.Intuition :- It is best for us to make array elements as low as possible till zero and all the elements must be unique. This will ensure all the small elements are present in the array so the mex can be as large as possible. Now combining all info above. Let's assume you have an array [6, 2, 6, 4, 18]For this to calculate the optimal array we need to calculate their gcd which is 2.So optimal array looks like [0, 2, 4, 6, 8] if I tell you to find it's mex5 so the answer is 9But we can also form our final array somewhat differently like [0, 4, 6, 8, 10] or [2, 4, 6, 8, 10] and mex5 in both the cases will be 7. Why :- Because we ignored to form 1 more possible small number which minimized our mex value. I hope you can understand this. If this is not clear now also then you can again message me I will try to help as much as I can.
•  » » » 13 days ago, # ^ |   +3 thanks for the explanation! I also remembered that the euclidean gcd algorithm is very similiar to the described process. (Just substract b to a until a turns a % b, and then viceversa)
 » 2 weeks ago, # |   +33 Updating the tests instead of the model seems like the wrong decision to me (i am biased though)The last few cases I remember of a wrong model (but there exists a solution), they fixed the model and rejudged the solution Can you explain why it was not done like that here? I remember an edu round and a div2 round where we got rejudged midcontest after the model was fixed Relevant meme : Situation : Unit tests are failingVladosiya and Pasha : delete the unit tests
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   -24 Also, Why isnt there more discussion on this? Authors fucking changed constraints midway but a slightly too hard div2C gets more hate???
•  » » » 2 weeks ago, # ^ |   +18 You don't need to curse or be rude every time. You're not umnik, and will never be.
•  » » » » 2 weeks ago, # ^ |   -22 you would be pissed off too if you spent 30minutes wondering where your code might go wrong and then it turns out authors cannot write a correct model.I do not want to be a umnik, i want to be myself. Cursing comes naturally to me and I dont see the need to restrain from it.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Dominator orz, please calm down, I can't see my idol frustrated.
•  » » » » » 12 days ago, # ^ |   +21 Hurtful
•  » » » » 2 weeks ago, # ^ |   +10 I think he just accidentally got a little carried away due to his recent rating boosts.
•  » » » 2 weeks ago, # ^ |   0 is the div2C ur talking about from recent div 2? cuz i haven't been active lately
•  » » » » 2 weeks ago, # ^ |   0 just in general, you will find tons of comments complaining about a hard div2C or something.But, there are almost no comments complaining about how constraints were changed mid round...
•  » » » » » 2 weeks ago, # ^ |   +1 i think the reason no one complain about the constraint change in this round's G is because the constraint change does not affect the initial solution for the problem pre-change, and all the change did is probably made some coders mildly annoyed because they had written some edge cases for the problem before the change.i do agree tho that constraints change midway through contest can be fatal
•  » » » » » » 2 weeks ago, # ^ |   +11 You are right that the constraint change isnt the issueThe issue was that the authors wrote the wrong solution, and thus my correct solution was marked as incorrect before rejudging with the changed test data. So it was me who was extra careful, while mostly everyone else wasnt
•  » » » » » 13 days ago, # ^ |   +15 The reason for almost no complaint is pretty obvious imo. There were barely any solves from rated participants at that time. It was even before I submitted it, so I doubt if many people in rated range even read this problem at this point, so most people were unaffected by it.Not saying that this decision was good, but you can see why the community's reaction is very different from the hard Div. 2 C's, and probably the authors also had that in mind.
•  » » » 2 weeks ago, # ^ |   +1 Its probably because its a G, so many didnt even get to it. I personally got to it only after constraints changed, and only realised after contest that anything actually happened. Im not saying this justifies it or anything, just giving an explanation :D
•  » » 2 weeks ago, # ^ |   0 Hi, first of all, I want to say sorry to you for this. For me, it is sad to look at all of this, because, I put the most afford in G among all tasts (I think because it has been changed little before contest).For me, two solutions (your and what we have done) seem like equally good. I mean, if you know how to solve this problem, you should know how to do with that tests. But if we would notice this test before contest, it would be put in the samples, since in other case there would be wa2 everywhere. But we cannot change samples during the contest. So, I think this decision was better in this case.One more time, sorry for inconvinience. We didn't want such think to happend.
•  » » » 2 weeks ago, # ^ |   +1 it was a great contest, and i found G really enjoyable even though i upsolved it 15 mins after the round, thank you very much!
•  » » » 13 days ago, # ^ | ← Rev. 3 →   0 Was the original "main correct solution" wrong with the initial constraints? I mean, that's what they're saying but it looks like some other people just moved on to problem H (implying that they probably didn't get WA in the first place).
•  » » » » 13 days ago, # ^ |   0 It is wrong, i asked a clarification, rhey admitted itIt fails on array = [0, 0, 4, 8] for example
•  » » » » » 13 days ago, # ^ | ← Rev. 2 →   +8 So I guess many others did the same mistake, makes sense. Anyways, most people couldn't even be aware of what actually went wrong before it was fixed, so it's no surprise that this is not being discussed much.
•  » » » » 13 days ago, # ^ |   -18 It failed at tests where was more than one 0, because they cannot be changed.
•  » » » 13 days ago, # ^ | ← Rev. 3 →   -14 But we cannot change samples during contest But you did change samples during contest right....(0s to 1s) also somehow changing tests is fine but not changing samples? they would get wa on 2 I dont see why this is an issue. Not every error gets caught by samples and thats fine. It would have been much more fairer since wrong logic would not get AC.... I got penalized for being more correct, other people did not get penalized despite being wrong. This is just bad. Why did you actually make the decision on G? I think its because you are more afraid of downvotes than being "fair" (even rejudging is sort of unfair, but I think its the less unfair choice since CF doesnt guarantee your results are final). Afterall, you will get more downvotes if people see they are getting wrong answer
•  » » » » 13 days ago, # ^ |   0 Decision wasn't made by me and I don't know who made it is the first place, but I think that this decision is okey. In fact, I was not saying about "fair" or something like this, but I want it to be fair. Also, I don't see how contribution can be involved here. You are the only who says lot of bad staff about this situation. I mean, yeah, it was bad, but you don't need to be rude and write lots of comments like "it is bad, selfish, wrong decision". I see that you have wrong answer, but why you are ready to argue with it in a whole day while bad wa for contest where you are not official takes 30 minutes? I mean, I already said that I am sorry about it and as we saw almost no one get affected, so no one pays attention. Of course, if I will make more tasks in future, I will try to prevent happening such things.To summarize, I was not making decision for G, but I think that it is good decision. It is not about contribution all this things.
•  » » » » » » 13 days ago, # ^ |   -6 Look, there was no announcement about it because almost no one has been affected. I think it can be counted on the fingers the number of people who's solution actually gave another verdict after regudging. In the case you sent, there was already lot of solution on problem D, so it should have been announced. Our case is different. Also, since this discussion is in the comments of the tutorial, I am not making 95% of people not aware of it. No one say that it is not true. And as you see, no one argue about it. I don't think that it is because they are not aware, I think it is because they just don't feel like part of it or something like this.
•  » » » » » » » 13 days ago, # ^ |   +19 It's still an issue, and some people still got affected by it, even though most of them were unofficial participants. I think it would've been fair to at least state that in the in-contest announcements. Also, it's not you who made some people aware of it. It was kept hidden until Dominater069 brought it up here.
 » 2 weeks ago, # |   0 Thank you for fast editorial
 » 2 weeks ago, # |   0 Hi I am a begginer and I really liked your effort on this round thank you for the answers so I can get the clues of coding
 » 2 weeks ago, # |   +10 Very good problem H!
 » 2 weeks ago, # |   0 Could someone tell me ,for problem E , why this submission is giving wrong answer for test case 97 of test 2 . https://mirror.codeforces.com/contest/2008/submission/279256847
 » 2 weeks ago, # |   0 I solved problem E in O(nlog(26)) using two sets.For even ns my solution is basically the same.For odd ns, I brute forced the index of the character to delete. First I deleted the first character from the string and inserted frequencies of other letters on odd and even indexes in each of these sets. Then for other characters, I updated the set of frequencies by erasing, updating and inserting a frequency of character.you can also check my code if you're interested: 279194144
•  » » 13 days ago, # ^ |   +3 I did the same, actually. Couldn't work out all the kinks in time to submit it to the contest, but I had that idea and was able to finish implementing it later on
 » 2 weeks ago, # |   0 very nice idea for problem H. also, the sentence "we need to find the smallest element which has at least $\big\lfloor \frac{n}{2} \big\rfloor$ elements in the array that is less or equal to it" in the editorial for H is kinda confusing since some people might interpret it as "find the smallest element $h$ which has at least $\big\lfloor \frac{n}{2} \big\rfloor$ elements in the array that is less or equal to $h$ including $h$".my suggestion is to change it into "we need to find the smallest element such that it has at least $\big\lfloor \frac{n}{2} \big\rfloor$ other elements in the array that is less or equal to it" or smth along that line. also, i can see that you use translator (probably) to write this edi.
 » 2 weeks ago, # |   0 In the editorial solution for F, why do we dosum=(sum-sumsq+mod)%mod;instead of sum=(sum%mod -sumsq%mod);to the best of my knowledge it is done when we want to take modulo of negative numbers however this doesn't make sense to me here since difference of sum — sumsq can't be negative mathematically , or i may be wrong some where plz help.
•  » » 2 weeks ago, # ^ |   0 The latter is also correct
•  » » » 2 weeks ago, # ^ |   0 This code gives WA on 4 but if i change line int num = (sum%MOD - pairsum%MOD);toint num = (sum - pairsum + MOD)%MOD;it gets AC'ed why so ? #include #define pb push_back #define int long long #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define lb lower_bound #define ub upper_bound #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) using namespace std; #define MOD 1000000007 using namespace std; int modmul(int a , int b , int mod){ return (a % mod * b % mod) % mod; } int fastpow(int a, int b, int mod) { int ans = 1; a = a%mod; while (b > 0) { if (b & 1) { ans = modmul(ans,a,mod); } a = modmul(a,a,mod); b >>= 1; } return ans%mod; } int inv( int a , int p){ return fastpow(a , p-2 , p); } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; vector a(n); int sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum = (sum + a[i])%MOD; } sum = (sum%MOD * sum%MOD)%MOD; int pairsum = 0; for(int i=0;i
•  » » » » 13 days ago, # ^ | ← Rev. 8 →   +3 The reason for this is that in C/C++, the x % MOD operation does not guarantee that the result will be in the range [0, MOD). In fact, when MOD > 0, its range is (-MOD, MOD): for cases where x >= 0, the range is [0, MOD), otherwise, the range is (-MOD, 0]. In your example, sum % MOD - pairsum % MOD can result in a negative number, which would make num fall in the range (-MOD, 0]. This doesn't guarantee that the final answer is in the range [0, MOD), which can cause a Wrong Answer. By using (sum - pairsum + MOD) % MOD, you ensure that the result is always non-negative and within the desired range, which is why it gets AC. This is because when sum >= 0 and pairsum < MOD, sum - pairsum + MOD > 0, which ensures the result is in the range [0, MOD). In fact, I would suggest writing ((sum - pairsum) % MOD + MOD) % MOD instead, as it offers better generality. Regardless of the ranges of sum and pairsum, as long as MOD > 0, you will always get a result in the range [0, MOD). Note that if sum and pairsum have values that are very close to the upper or lower limit of the integer type (usually long long), using ((sum % MOD - pairsum % MOD) % MOD + MOD) % MOD provides better reliability. However, since in most cases sum and pairsum are already results after taking modulo with MOD, and the absolute value of their initial values are usually not large, not doing this is generally acceptable.
•  » » 2 weeks ago, # ^ |   0 Try 1 1 1 1 1 1 1 1000000000
•  » » » 2 weeks ago, # ^ |   0 Thanks!If i understood it correctly then ->sum - sumsq >= 0 but (sum%MOD - sumsq%MOD) might be negative hence will not work.
•  » » » » 2 weeks ago, # ^ |   0 My bad, you are correct it's due to negative, because if it was a + sign between the two,your formula would have worked
 » 2 weeks ago, # |   0 G — Sakurako's Task gives TLE when using Binary Search but succeeds when I use linear search. Can anyone explain why? Shouldn't the binary search ideally take log(n) time?Here are the two solutions -Binary Search — https://mirror.codeforces.com/contest/2008/submission/279260235 Linear Search (as given in tutorial) — https://mirror.codeforces.com/contest/2008/submission/279260712The diff is in last few lines, where I use either binary search or linear search.
•  » » 2 weeks ago, # ^ |   0 if (k > (n - 1) * (gcd - 1))Potential int overflow here.
 » 2 weeks ago, # |   +7 imo you should have made l and r constraints on C 10^18, so that linear search doesnt pass, and it would have to be binary search, but great contest nonethelesz
 » 2 weeks ago, # |   0 how to derive the second expression for problem F ?
 » 13 days ago, # |   +8 Can someone explain how we are able to get every multiple of gcd in problem G? I understand that after doing operations whatever number we get, will be a multiple of the gcd. But after doing one operation we are also replacing the number. How can we prove that we will be able to get all the multiples 0, g, 2*g, 3*g, ... ?
•  » » 13 days ago, # ^ |   +8 Step 1 : First get gcd. You can follow Eculidean Algorithm for all pairs of adjacent elements in order and in the end you will have atleast 1 element = gcd. Step 2 : convert every other element to gcd. We can just subtract gcd from each element while they are > gcd Step 3 : make one elememt go to 0, make one stay at gcd, and make the others go up to i * gcd for i >= 2. We can always vhoose to add the element that we keep constant at gcd.
•  » » » 13 days ago, # ^ |   0 In the problem, we are allowed to add/subtract smaller array element to the larger one. I can't understand how your Step 2 is doing the same, like the operations. We are not allowed to directly subtract the gcd itself, right?
•  » » » » 13 days ago, # ^ |   0 Take a look at arr=[5,2] for example. You reduce 5 to 1 by using the 2, and then you reduce the 2 to zero using the 1.
•  » » » 13 days ago, # ^ |   0 Looks like I misread step 1 to just calculate the gcd of the whole array, lol. Got it know, thanks.
 » 13 days ago, # | ← Rev. 2 →   0 Can you please clarify some of the samples, copied below, from 2008G - Sakurako's Task? Input: 2 10 1 1 Output: 11 Query: Can we not generate every positive number from 1 and 1? How can there be any mex other than 0? Input: 3 1 1 2 3 Output: 3 Query: Can we not generate every positive number from 1 and 2? How can there be any mex other than 0? Also, 3 is part of the input array. We can choose to operate only on the 1 and 2, always leaving the 3 in the input array. How can it be a mex? Input: 3 2 1 2 4 Output: 4 Query: Similar to previous case.
•  » » 13 days ago, # ^ | ← Rev. 2 →   +8 Read the problem statement again and notice why $k$ exists in the input.Also, you don't 'generate' numbers. You can only 'change' the numbers.
•  » » » 13 days ago, # ^ | ← Rev. 2 →   0 Consider the initial array (1, 1). As per the rules, the following is possible: (1, 1) -> (1, 2) -> (1, 3) -> (1, 4) -> (1, 5) -> (1, 6) -> (1, 7) -> ... Every positive number can thus be obtained.Sorry if I am overlooking something trivial.
•  » » » » 13 days ago, # ^ | ← Rev. 5 →   0 The problem wants you to find $mex_k$ on the array. Thus, being able to 'obtain' such numbers doesn't mean anything. For example, if $k=3$, $mex_k$ on the array (1, 7) is only 3. $mex_k$ on the array (1, 9999999999999...) is still only 3. One of the possible arrays you need to make in this case is (1, 2), so that $mex_k$ becomes 4.Read the definition of $mex_k$: mex_k is the k-th non-negative integer that is absent in the array. If you don't know what 'absent' is, it means that it should NOT exist in the array. So making large number is meaningless, because that number "exists" in the array, while you want it to "not exist" in the array.
•  » » » » » 13 days ago, # ^ |   0 Thank you for explaining patiently.
 » 13 days ago, # |   0 is this hackable ???[submission:https://mirror.codeforces.com/contest/2008/submission/279192059]
 » 13 days ago, # | ← Rev. 2 →   0 Just a Newbie question, here in Problem C what is the maximum time complexity solution which will definitely pass. Though I've have used solution which takes O(sqrt(n)) or O(log n)(not sure about the time complexity of the c++ std sqrt() function) per test case and I think a solution with complexity greater than this might not pass. Anyone ?Also can anyone explain how can we just by looking at the constraints here , which is 1<=t<=1e4 and 1<=l<=r<=1e9, guess the time complexity of a solution which will pass ?
•  » » 13 days ago, # ^ |   0 if you use binary searc, where k is the answer then r can not be greater than l+(sum of first k-1 natural numbers. So the max number of searches you need is sqrt(r-l) or sqrt(10^9)
•  » » 13 days ago, # ^ |   0 It's not O(long n) .It's O(log(n)) log for logarithmic . Also the c++ sqrt function is O(1) as mentioned by this comment
 » 13 days ago, # |   0 This contest rated or un rated??
 » 13 days ago, # |   0 https://mirror.codeforces.com/contest/2008/submission/279229487 can someone please tell me what I am missing here, thanks a lot
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 Not sure but i had the same problem . This is how i fixed it . tot=(n * (n — 1)) *inv(2); Or just multiply it at the end
 » 13 days ago, # | ← Rev. 2 →   0 There's a $O(nB+q\frac{n}{B}\log(\frac{n}{B}))$ solution in 2008H - Sakurako's Test.279266745(I can't tell the min value of the time complexity.In the submission,$B=2\times \sqrt n$,Welcome to hack.)
•  » » 13 days ago, # ^ |   +8 I think it is exactly the intended solution except that you precalculate the answers for $x \le B$. It is $O(nB + n \log^2 n)$ and is intended solution if you set $B = 0$ and don't recalculate the answer for same $x$.
 » 13 days ago, # | ← Rev. 2 →   0 Submission to D problemWhy is this submission giving a TLE? I am using DSU to solve and according to my analysis it shouldnt give TLE. Can anyone point out what might be going wrong?
•  » » 13 days ago, # ^ |   0 You're visiting every components in the cycle for every node, it'll take n^2
•  » » » 13 days ago, # ^ |   0 Thanks for replying, but that wasnt the case actually. My friend pointed out what exactly was wrong and i was able to fix it. i was creating the array black of size N = 1e5 for all test cases t = 1e4 which was creating a complexity of O(1e9) and hence i was getting TLE. Plus i wasnt clearing my global vectors after each test case which was again leading to wrong answers
 » 13 days ago, # |   0 Was only able to solve 3 problems. Got stuck in the first one :(. Got nervous because I am contesting after long time
 » 13 days ago, # | ← Rev. 2 →   0 H. Sakurako's Test Why do we have to precompute answer for every x in 1..n? Max number of queries is the same as max n, so should be same amount of work even without precomputation.
•  » » 13 days ago, # ^ |   +4 It's because the time complexity of the Check function of the binary search has different time complexity depending upon the value of $x$. For $x = 1$, it works in $O(n)$ For $x = 2$, it works in $O(n/2)$ For $x = 3$, it works in $O(n/3)$ Therefore, if you query all $x$ exactly once, then it works in $O(n + n/2 + n/3 + \dots) = O(n \cdot log(n))$But if all queries contain $x = 1$, then it works in $O(n^2)$.
•  » » 13 days ago, # ^ |   +3 You don't really need precomputation. You just need to save the answer for each query, and reuse it when you encounter the same query again. Precomputation is just a way to make these answers in advance so that you don't need to make any decision on actual queries (just print the precomputed answer always).
 » 13 days ago, # |   0 AC 6 problems but only +12 expected delta... I want to be pupil.
 » 13 days ago, # |   0 good problem G and problem H
 » 13 days ago, # |   0 My E's solution passed with O(N * 26 * 26) ..... I'm praying, please system test doesn't burn me :(
 » 13 days ago, # |   0 Problem A The tutorial explains the concept well, but there is something that i could not understand in the python code. if a=4 and b=5, the output through the python code is "YES", but i am unable to figure it out how?(1,1,1,1) and (2,2,2,2,2)4 ones will cancel out 2 twos, then there will be remaining 3 twos which does not give 0 in any way by adding +/- operations.
•  » » 13 days ago, # ^ |   0 lets take 3 pluses and 2 minuses for b, the value will now be 2, we can subtract 2 using two 1's from a, then we can add 1 and subtract one, making the final value 0
•  » » » 13 days ago, # ^ |   0 Yeah, I got it. Thanks!
 » 13 days ago, # |   0 why are the ratings not updated?
 » 13 days ago, # |   0 Typo in the editorial of B, it should be first character of the 'second' line
 » 13 days ago, # | ← Rev. 2 →   0 My solution for E had TLE when submitted twice in C++ 17 during the contest, but it got accepted when submitted in C++20 after the contest!
•  » » 13 days ago, # ^ |   0 Perhaps the reason is not using fastio?
 » 13 days ago, # |   0 mathforces
 » 13 days ago, # |   0
•  » » 12 days ago, # ^ |   0 Python has a recursion limit, it cannot handle deep recursion. Your dfs function probably got called over 1000 times deep, which made it RTE. You can set it by using sys.setrecursionlimit() but it is still capped and you shouldn't rely on it. For workarounds, see https://mirror.codeforces.com/blog/entry/80158.
•  » » » 12 days ago, # ^ |   0 Thanks!!
 » 13 days ago, # | ← Rev. 2 →   0 I am new to codeforces, it's my first contest, was that a rated contest ? if yes when the rating will be published ?
 » 13 days ago, # |   0 first time solved 5 problems in div.3!
•  » » 13 days ago, # ^ |   0 did the rating changed for you ?
•  » » » 6 days ago, # ^ |   0 no,this round is an unrated round due to the poor network
 » 13 days ago, # |   0 Thanks for the round!Does the condition $a_i \ge a_j$ in problem G affect anything in the current version of the problem? I feel that's the root cause of the issue; having unnecessary details (from the perspective of the model solution) can introduce unexpected cases.
 » 13 days ago, # |   0 do I get any rating for solving 4 questions here? m a newbie and had no idea that there are penalties. If anyone can clarify this it will be greatful.
•  » » 13 days ago, # ^ |   0 The ratings have already been published, so I think you have already got your answer, but just to clarify, looking at your submissions, failure on the first first (aka sample tests) or a compilation error doesn't count as a penalty, so you only got one penalty for question A, which can be seen here: https://mirror.codeforces.com/contest/2008/standings/participant/190613374#p190613374
•  » » » 12 days ago, # ^ |   0 okkk thnx mate
 » 13 days ago, # |   0 E was harder that F and G
 » 13 days ago, # |   0 Problem F. Wrong.Test 3 5 1 2 3 4 5All pairs: (1,2+3+4+5)=14 (2,3+4+5)=24 (3,4+5)=27 (4,5)=20 SUM = 85 AMOUNT OF PAIRS = 10 So the expected value is 8.5 Can be shown as 17/2 -> P = 17, Q = 2Now the fun part: Q^(-1) = 1/2 So P*Q^(−1) = 8.5 (mod 10^9+7) = is still 8.5Okay, it can be a mistake and we wanted to output P*QP*Q = 34. How. We. Get. 500m. ?I guess it's me who is in wrong here, because many contestants did the task. But unless i see normal explanation how we get 500m here, i will continue to claim that the problem is wrong. I see that solution uses division by modulo, but here you have a simple test, that doesn't need it. And it's seems to be wrong.
•  » » 13 days ago, # ^ |   +7 its unfortunate that author did not tell what $Q^{-1}$ means especially because this is div3$Q^{-1}$, defined for $0 < Q < 10^9 + 7$, is the unique integer in $(0, 10^9 + 7)$ such that $Q \cdot Q^{-1} = 1$. In this definition, you can check that $2^{-1}$ is $5 \cdot 10^8 + 4$.$17 \cdot 2^{-1}$ is thus $17 \cdot (5 \cdot 10^8 + 4)$. You can verify this comes to $500000012$
•  » » » 13 days ago, # ^ |   -17 Stop whining about the author in every comment. First, check your own rounds on CodeChef — your samples are unclear and ambiguous. If you are too much concerned about a beginner than look your codechef rounds you expect someone to understand the problem by looking at 2 samples and that to with n = 1 or 2. And if you think you are providing the feedback than learn how to give feedback like this by djm03178. No one had any problem with this round and just you are shouting and you are getting frustated because no one cares about your opinions and this is also shown by the downvotes you received on this posts.Just because you had a decent showing in a recent contest doesn’t mean you should start acting superior. You’ll always be a kid of um_nik.
•  » » » » 13 days ago, # ^ |   +5 i dont want to reply to a unlinked account but i am curious. You’ll always be a kid of um_nik. This is the second time someone mentioned um_nik and how i will never become him. Why lol? I am genuinely curious. Is it just because of that one comment?
•  » » » » » 13 days ago, # ^ |   -23 you don't want to reply to an unlinked account because you don't have any points to counter and reply. It is what it is. This account is registered 2 years ago which is same as your account.um_nik started acting rudely after winning multiple div1s and created his personality just like that and most of the time he does it in a funnier and sarcastic way. but you are trying to replicate the same behaviour of um_nik without even getting in top 10 in div1. even if you don't agree on this but all your comments about this round are just like that.
•  » » » » » » 13 days ago, # ^ |   +2 i think i have every right to such comments when author messed up model solution and DID NOT EVEN ACKNOWLEDGE IT (this is the bigger issue). I dont care whether you think my comments are right or not, because they are right to me.
•  » » » » » » » 13 days ago, # ^ |   +19 One can always argue about how criticism is communicated, but the core of Dominater069’s argument is 100% valid. The authors should not have changed the problem mid-round, but instead should have been open about their mistake and should have corrected their own solution. The impact was limited this time around as it mainly impacted higher-rated participants who were out-of-competition, but it probably robbed neal of a first place and the same handling of the issue in a division 1 or 2 contest would have resulted in a lot more noise.
•  » » » » » » » » 13 days ago, # ^ |   0 thanks, i agree that maybe i was overly rude and etc. I was frustated and author did not want to admit they made a mistake, which only piled onto it.
•  » » » » » » 12 days ago, # ^ |   +13 You must be my biggest fan, because I myself cannot remember when I "started acted rudely" or "created my personality", and whether it was after I won multiple div1s. Probably because I was "rude" (which is a word people use when I'm technically correct but not polite and not quiet about it, and they can't actually argument with me, so they have to dismiss me in a different way) long before I even registered on Codeforces.Now about Dominater's comments on this round. Some comments are just chatting with others or helping newbies with questions. Actually, the comment that started your unwarranted crusade is exactly this: a person asked a question, and Dominater answered the question. Yes, with a reasonable remark about the fact that in div3 there should be a definition of inverse element modulo $P$. What troubled you, other than the fact that you wanted to vent, — I don't know.And all other comments are about (mis)handling the situation with a wrong model solution. Some might not like the tone, but he is 100% in the right.
•  » » » » 13 days ago, # ^ | ← Rev. 2 →   0 you expect someone to understand the problem by looking at 2 samples and that to with n = 1 or 2. I dont usually expect people to look at samples to understand the problem. Can you send the exact problem you are referring to? I usually dont put only n = 1 and 2 in samples. No one had any problem with this round A problem had a wrong model solution, and worst of all there was no information on it. you dont think thats an issue? shown by the downvotes you received on this posts. I dont care about contribution, please downvote me more. And if you think you are providing the feedback I am not providing feedback. I know how to provide feedback thank you very much. I was frustated and I was expressing my frustation. If you reply, I will continue in DM. I don't want to spam blog even more especially on an unrelated thread.
•  » » » » » 13 days ago, # ^ | ← Rev. 2 →   +7 I dont usually expect people to look at samples to understand the problem. Can you send the exact problem you are referring to? in this problem, the problem statement is a bit lengthy and contains a story, yet there are only two sample cases with n=2 and n=3. The problem is rated 1269, which falls under Division 4. Among the 19 Division 4 rounds held to date on Codeforces, there hasn't been a single problem with just two sample cases for n=2 and n=3. While an experienced participant might understand the problem statement just by reading it, a beginner often relies on sample cases to ensure they've understood the problem correctly. And this is just one of many examples. A problem had a wrong model solution, and worst of all there was no information on it. you dont think thats an issue? I'm not saying that the wrong model solution isn't an issue—the author openly admitted his mistake. What more could you ask for? The nature of problem-setting is prone to errors, and sometimes these can be overlooked. Has CodeChef never had issues with their problems? They definitely have, and many times problem statements have been changed without notifying anyone. I dont care about contribution, please downvote me more. When did I say that you only care about your contribution or are doing this for upvotes? I pointed out that you're getting downvotes on this, which basically means that the community disagrees with you. If a red coder is getting downvotes, it means that they're writing something stupid that others consider incorrect or nonsensical. I am not providing feedback. So you're saying that I'm not giving feedback, which implies you're just trolling the author. Learn to be patient in life—you're not a president somewhere and things should go exactly according to your wishes or opinions. If you reply, I will continue in DM. Feel free to continue this in DM—my DMs are not closed like yours.
•  » » » » 11 days ago, # ^ |   0 Polygon advices (This is official codeforces guide often shared by coordinators). If some of the following items could be used in your statements, copy them. Output <...> modulo $998\,244\,353$.Formally, let $M = 998\,244\,353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.
 » 13 days ago, # |   0 can someone help in figuring out why my E fst'ed? https://mirror.codeforces.com/contest/2008/submission/279235492
 » 13 days ago, # |   0 https://mirror.codeforces.com/contest/2008/submission/279123663whats wrong with this my rank dropped from 600 to 2k after system testing
 » 13 days ago, # |   0 Why this gives WA for 5th test case in Fhttps://mirror.codeforces.com/contest/2008/submission/279369074
•  » » 11 days ago, # ^ |   0 You can't directly do f/2, instead you have to do f*binpow(2, mod-2) using fermat's little theorem just like you did below it
•  » » » 10 days ago, # ^ |   0 Thanks for pointing out...I forgot to do modulo inverse for 2 also since I thought it wont be required
 » 13 days ago, # | ← Rev. 2 →   0 I have slightly different solution for 2008B - Square or Not than the solution given by authors: It's clearly mention that the string s is derived from a beautiful matrix, so if it has to be squared two conditions are suffices:Initially we count how many ones and zeros are present in the mentioned beautiful matrix, It's pretty easy, right? Number of ones = r + r + c-2 + c-2Number of zeros = n * n -Number of ones Length of the string should be a perfect square and, count of zeros and ones are exactly as same as we count for beautiful matrix. And It works!!Here is my submission: 279088062
 » 13 days ago, # |   0 Can anyone help me in debugging G, though i changed my approach and got AC but still no idea whats wrong there. Submission
 » 13 days ago, # |   0 why do we need to calculate inverse modulo of 2 in n * (n-1)/2? Can we just divide upfront and then take the inverse modulo of the quotient ?
•  » » 12 days ago, # ^ |   0 No need take inverse modulo of 2, Yes you can, n or n-1 is even hence it's divisible by 2!! just take inverse mod of (n * (n-1)/2) % mod And it works!!My submission: 279251237
 » 12 days ago, # |   0 Solution of problem D using DSU(Union-Find). https://mirror.codeforces.com/contest/2008/submission/279404607
 » 12 days ago, # | ← Rev. 2 →   0 Can anybody Tell me why this submission of mine for D using map, give TLE. Map takes log(n) times for performing insertion and extraction operations, but that has never happened before with me that using map gave TLE and array solution for storing key worked fine.
•  » » 12 days ago, # ^ |   0 You have linked the wrong submission, but I found the code which gave you TLE anyways.You need to replace if(mp[i]) with if(mp.contains[i]) and there wouldn't be any TLE. You can check this blog out to understand (TL;DR: Use std::map::find or std::map::contains and not std::map::operator.)
•  » » » 12 days ago, # ^ |   0 sorry for the wrong link but thanks ser!
 » 12 days ago, # |   0 Hey guys I'm in doubt about 5th problem alternating string if we have test case like "aaaaaaabab" having n=10 if(n%2==0) { vectorv[2]={vector(26),vector(26)}; for(int i=0;i
•  » » 11 days ago, # ^ |   0 aaaaaaaaaa is actually alternating because they didn't said that characters in even position cant be the same as odd ones
 » 12 days ago, # |   0 For B they have given this code. int id = 0; while(id
•  » » 4 days ago, # ^ |   0 The string is always the result of writing out the strings of a beautiful matrix.I took it from the input section of the task B. Your matrix isn't beautiful.
 » 12 days ago, # |   0 Solution of problem B is wrong as it will give yes in case of example like 9 111100000 or 9 111101110
 » 12 days ago, # |   0 All the problems were fun, this is the most I've enjoyed any contest. Thanks!
 » 12 days ago, # |   0 For H, when we are finding the count of elements between say 0 — m, x — x + m, 2x — 2x + m... isn't there a possibility of overcounting if the segments overlap? (oh wait m is always < x... since it's the result after % x)
 » 8 days ago, # |   0 In H, I didn't understand why we have to calculate it for all k, like we already had the number of elements less than or equal to x using prefix sums then why we are calculating for all k?. Does this have anything to do with the range that m (with which we are taking mod) can span within n and then basically calculating for all these spans?
 » 7 days ago, # |   0 Hello there, In Problem E, it is specified that the sum of n across all test cases shouldn't exceed 2e5. On test 3, n = 2e6.
 » 4 days ago, # |   0 In problem G, it's impossible for $g$ to be 0.
•  » » 4 days ago, # ^ |   0 What is g?
•  » » » 4 days ago, # ^ |   0 in tutorial $g = gcd(a_1,a_2,....,a_n)$
•  » » » » 4 days ago, # ^ |   0 Yes. It is impossible. There was nothing about it
•  » » » » » 3 days ago, # ^ |   0 There is, he said in the editorial if the g is 0 print k, and in both codes he checked whether g is zero or not.
 » 3 days ago, # |   0
 » 3 days ago, # |   0 problem H: ~~~~~ 6 2 2 2 5 1 1 6 ~~~~~ when x = 6, I can only operate on i = 6, then it will be 0 1 1 2 2 5, why can I get answer = 1? thank you!
•  » » 3 days ago, # ^ |   0 I got it wrong, sorry.
 » 3 days ago, # |   0 In problem H, the fact that the values of $x$ can be repeating among the queries feels unnecessary; the requirement to precompute/store the answers in an array could be omitted. Although a very good problem!