### ilyakrasnovv's blog

By ilyakrasnovv, 6 weeks ago, translation,

# Thanks a lot!

Hello, Codeforces!

We are glad to invite everyone to participate in Codeforces Round #816 (Div. 2), which will be held on Aug/20/2022 17:35 (Moscow time). The round will be rated only for the second division. You will have 6 tasks and 2 hours to solve them. We recommend you read all the problems.

Round is completely set by winter SIS (Summer Informatics School) students. During the camp we did our best to prepare interesting and creative problems. You can check previous rounds prepared by SIS students: Codeforces Round #815 (Div. 2), Codeforces Round #694, Codeforces Round #612, Codeforces Round #530

We are very thankful to

Scoring distribution will be released before the contest begins

We hope that You will participate in our round, as well as in SIS!

Good luck and have fun!

UPD — Scoring distribution:

$500 - 1000 - 1750 - 2250 - 2750 - 3000$

The contest may contain interactive problems! Make sure to read this post.

UPD 2 — Editorial is out!

UPD 3 — Congratulations to the winners!

Official participants:

All participants:

• +703

 » 5 weeks ago, # | ← Rev. 6 →   +330 UPD: Large text has reached its limit! Good luck on the round!178 upvotes on this comment and the larger large text becomes even larger!57 upvotes on this comment and the large text becomes even larger!
•  » » 5 weeks ago, # ^ |   +73 After getting $998244353$ upvotes... Spoiler
•  » » 5 weeks ago, # ^ |   +9 How about we count the upvotes on the post and enlarge this comment also accordingly
• »
»
»
5 weeks ago, # ^ |
+45

# Large comment

•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +8 SpoilerVery large comment
•  » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +99 SpoilerExtremely large comment
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +21 upd: thanks!Hide it in a spoiler, so as not to complicate the reading of the comments, or idk... You've gone too far
•  » » 5 weeks ago, # ^ |   0 228
•  » » » 5 weeks ago, # ^ |   0 239
•  » » » » 5 weeks ago, # ^ |   0 240
•  » » » » » 5 weeks ago, # ^ |   0 241
•  » » 5 weeks ago, # ^ |   -23 Spoiler:This is dumb.Bold textItalic textinline text code: #include int main() { printf("SlavicG"); return 0; } Username: SlavicG
•  » » 5 weeks ago, # ^ |   +15 There is no limit if you use a bit of CSS :D
 » 5 weeks ago, # |   +69 Big comment text for upvotes
•  » » 5 weeks ago, # ^ |   +63 Italic comment text for upvotes
•  » » » 5 weeks ago, # ^ |   +96 ᵗᶦⁿʸ ᶜᵒᵐᵐᵉⁿᵗ ᵗᵉˣᵗ ᶠᵒʳ ᵘᵖᵛᵒᵗᵉˢ
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +60 Русскоязычный текст комментария для лайков
•  » » » » » 5 weeks ago, # ^ |   +28 sǝʇoʌdn ɹoⅎ ʇxǝʇ ʇuǝɯɯoɔ pǝddᴉʅᖵ
•  » » » » » » 5 weeks ago, # ^ |   +26 Monospace comment text for upvotes.
•  » » » » » » » 5 weeks ago, # ^ |   +23 SpoilerSpoiler comment text for upvotes
•  » » » » » » » » 5 weeks ago, # ^ |   +34 red comment for upvotes
•  » » » » » » » » » 5 weeks ago, # ^ |   +34
•  » » » » » » » » » 5 weeks ago, # ^ |   +98
•  » » » » » » » » » 5 weeks ago, # ^ |   +35 // for upvotes
•  » » » » » » » » » 5 weeks ago, # ^ |   +16 Bulleted text for upvotes
•  » » » » » » » » » 5 weeks ago, # ^ |   +27 ${Latex}$ ${comment}$ ${for}$ ${upvotes}$
•  » » » » » » » » » 5 weeks ago, # ^ |   -8 I knew I would get rickrolled but I went ahead anyways
•  » » » » » » » » » 5 weeks ago, # ^ |   0
•  » » » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -7 $\color{white}{\texttt{White comment text for upvotes}}$
•  » » » » » » » 5 weeks ago, # ^ |   0 SpoilerThere are 38 layers of spoilers on the comment above. Time saved!
•  » » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Spoileri added more ;)
•  » » » » » » » » » 5 weeks ago, # ^ |   0 SpoilerThere's 82 now and holy F the screen is literally a long pyramid
•  » » » » » » » » » 5 weeks ago, # ^ |   0 Spoiler:I am sorry for wasting your time, but I added even more.
•  » » » » » » » » » 5 weeks ago, # ^ |   0 SpoilerSuch a grand sight!
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   -13 hidden comment text for upvotes UPD 1 : there was simple instead of hidden before. UPD 2 : there was not before written on the upper line.
•  » » 5 weeks ago, # ^ |   -23 SpoilerNo comment for upvotes
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Emoji (and other unusual UTF-8 characters) are not supported comment for upvote
 » 5 weeks ago, # | ← Rev. 2 →   +133 As a (supposed) tester, I don't even remember testing this round but it should be good.
 » 5 weeks ago, # | ← Rev. 2 →   0 Same setters for this as well as the previous round, nice!
 » 5 weeks ago, # |   +37 winter Summer Informatics School
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +16 SIS is such a great camp, that it is always the time for SIS.
•  » » 5 weeks ago, # ^ |   -29 fucking cringe
 » 5 weeks ago, # | ← Rev. 2 →   0 As a tester, I don't remember tasks. spoilerAlso I haven't been in SIS winter
 » 5 weeks ago, # |   0 Finally, a round where I can gain rating again.
 » 5 weeks ago, # |   +2 Hope to become an expert!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 !!!!!You Will!!!!!
•  » » » 5 weeks ago, # ^ |   +1 Thanks,Good luck!!!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 1587 is exactly my highest rating, and the rest is history :rofl. Wish you luck ;)
•  » » » 5 weeks ago, # ^ |   0 Thanks to your best wish!! finally become an expert! Good luck!!!
•  » » 5 weeks ago, # ^ |   0 Me too!
•  » » 5 weeks ago, # ^ |   0 Expert!!!
 » 5 weeks ago, # |   +41 Well, it got my attention. The round better live up to your hype now, that's all I've got to say.
 » 5 weeks ago, # |   +8 Float like a butterfly, Sting like codeforces.
 » 5 weeks ago, # |   0 as a student, I would like to learn from this Codeforces Round #816 (Div. 2) contest
 » 5 weeks ago, # |   0 Waitin
»
5 weeks ago, # |
+4

# Very excited!

 » 5 weeks ago, # |   0 All these Contests back to back, as coders we are just loving it :)
 » 5 weeks ago, # |   0 thanks for contest !!!!!!!!!
 » 5 weeks ago, # |   +3 Good Luck
•  » » 5 weeks ago, # ^ |   +1 wish u luck too
•  » » » 5 weeks ago, # ^ |   0 This fourth question already has 2250 points, this estimated to drop points
•  » » » » 5 weeks ago, # ^ |   0 Lets give it a try at least
 » 5 weeks ago, # |   0 Hope to become pupil(lll￢ω￢)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 goodluck
•  » » 5 weeks ago, # ^ |   0 Me too bro
•  » » 5 weeks ago, # ^ |   0 Same here
•  » » 5 weeks ago, # ^ |   0 ABC only required
 » 5 weeks ago, # |   0 as a participant i will participate
 » 5 weeks ago, # |   +32 I finally found SomethingNew that I have zer0brain, now I KAN participate in this contest :)
•  » » 5 weeks ago, # ^ |   +25
 » 5 weeks ago, # |   0 go go go
 » 5 weeks ago, # |   0 Thanks, SIS! The last contest was awesome. Probably there will be math and binary search or implementation problems again. Good luck everyone!
 » 5 weeks ago, # |   +4 As a student, I will try my best to solve the problems.
 » 5 weeks ago, # |   +16 (* ^ ω ^) comment ʕ ᵔᴥᵔ ʔ with (▽◕ ᴥ ◕▽) cute ❤❤❤ emoticons ❤ (ɔˆз(ˆ⌣ˆc) for (ﾉ◕ヮ◕)ﾉ*:･ﾟ✧ upvotes (◕‿◕)
 » 5 weeks ago, # |   +3 The same but not the same time :(
 » 5 weeks ago, # |   0 Just a random question but if anyone knows about it please reply. Here is the question:I may not be able to participate in today's contest but i saw in the calendar that the next contest is going to be held on the 2nd of September. Do you know if any contests are taking place before that date? If not i might have to cancel everything and participate.
•  » » 5 weeks ago, # ^ |   0 very low or no chance that there will be any contest before 2 sept and after todays contest.
•  » » 5 weeks ago, # ^ |   0 there is no exact answer, everything can change
 » 5 weeks ago, # |   +13 Hoping not to see grid in problem A.
•  » » 5 weeks ago, # ^ |   +17 your wish was fulfilled by the author
•  » » 5 weeks ago, # ^ |   +15
 » 5 weeks ago, # |   0 I hope the problem statements are short, crisp and clear.
 » 5 weeks ago, # |   +4 The contest may contain interactive problems!Hope it doesn't >_<.
 » 5 weeks ago, # |   +16 Ah, that score distribution is looking dangerous.
•  » » 5 weeks ago, # ^ |   +3 Too dangerous !!
 » 5 weeks ago, # | ← Rev. 7 →   -43 .
 » 5 weeks ago, # |   -19 Div 1.5
 » 5 weeks ago, # |   -13 牛哇牛哇 （So EXECELLENT the writers are！）
 » 5 weeks ago, # |   -20 C seems tedious
•  » » 5 weeks ago, # ^ |   0 not much, but i struggled for an hour on what i think was some overflow (WA on pretest 2). At the end i just put ll everywhere and it passed the pretests
•  » » 5 weeks ago, # ^ |   0 get better
 » 5 weeks ago, # |   -33 It's hard for me to imagine what the author's mindset was when he wanted to put that hard tasks to 2C, only to make this LARGE GAP?I know! The large text stands for the large gap, right?Conclusion: gapforces, speedforces.
 » 5 weeks ago, # |   +4 I couldn't see the problems for the past 15 minutes. It keeps saying "Bad Gateway 505". Anyone else?
•  » » 5 weeks ago, # ^ |   +14 same
•  » » 5 weeks ago, # ^ |   0 NOTE: m2 is alive
•  » » » 5 weeks ago, # ^ |   +5 I forgot my login password
•  » » 5 weeks ago, # ^ |   +1 Me too. Unfortunately, I resent two times the same code while refreshing the web, maybe can admins remove my last RE submission 169136909? It's exactly the same as the RE submission 169136355.
•  » » 5 weeks ago, # ^ |   +5 same
 » 5 weeks ago, # |   -29 speedforces
 » 5 weeks ago, # |   -42 I feel that Problem b is more advanced than usual !! (•_•) Speedforces!
 » 5 weeks ago, # | ← Rev. 2 →   -10 [deleted]
•  » » 5 weeks ago, # ^ |   -12 so sad, but true
•  » » 5 weeks ago, # ^ |   0 And why is it always C :(
•  » » » 5 weeks ago, # ^ |   0 not always tho
•  » » » 5 weeks ago, # ^ |   0 One of the most worsest observational problem for C :(
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   0 Not sure it's that big gap I solved C it doesn't need any data structures but it wasn't easy for sure
•  » » » 5 weeks ago, # ^ |   0 I've heard that sb. used Treap / Splay Tree in C. Initially my solution have used Old Driver Tree but I gave up debugging it. so maybe a lot of people used some too complicated data structures :)
•  » » » » 5 weeks ago, # ^ |   +3 I used array and if else XD
 » 5 weeks ago, # |   +1 This round reminds me of Educational Codeforces Round 133 (рейтинговый для Div. 2).
•  » » 5 weeks ago, # ^ |   0 The C of this round is nowhere as hard as the C of edu round 133
 » 5 weeks ago, # |   0 Nice round!No mutitestcases! C is a little difficult,but interesting!
•  » » 5 weeks ago, # ^ |   +6 A had multiple TCs*
•  » » » 5 weeks ago, # ^ |   0 I mean CDE
•  » » » » 5 weeks ago, # ^ |   +6 well yes C~E were nice
•  » » 5 weeks ago, # ^ |   0 I become Master again! thx D! I solved it quickly on 00:11
»
5 weeks ago, # |
+6

# Large Gap

to make you get negative rating change.

•  » » 5 weeks ago, # ^ |   0 Don't underestimate your opponent, ejjii!
 » 5 weeks ago, # |   +14
•  » » 5 weeks ago, # ^ |   0 you already spoke*
 » 5 weeks ago, # | ← Rev. 2 →   +9 I TLEd on 2 different problems using Java and passed in C++. Not sure if it has something to do with my implementation, but I never encountered this on CF before. I liked the problems though.
 » 5 weeks ago, # |   0 So sad, that i solved C too late. Could've solved 20 minutes faster, if i would've not been wasting time on E. At least now it's my bad. Thanks for contests, SIS! Was glad to participate in all of them! Hope to see more contests of yours!
 » 5 weeks ago, # | ← Rev. 2 →   0 regardless the round being unbalanced and speedforces and not being able to solve c, i see that c is an opportunity to introduce low rated people to new topics ( if i have the right idea). ps : after the round finished do we need lazy propagation in this problem?
 » 5 weeks ago, # |   +3 Can somebody explain C? For me it is much harder than D
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Let's say, you know the result for the initial array. Try to find how changing one value will affect the result.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 ok, its easy to observe that, but how do you store data? do we need to have length of every block stored?
•  » » » » 5 weeks ago, # ^ |   +1 No, you don't have to store the length of every block.If you are updating index i, then ans will only change depending on its adjacent indexes (i-1 and i+1).My Submisson: 169128778
•  » » » » 5 weeks ago, # ^ |   +1 You don't need to store anything. Once you find the awesomeness of the initial array, it is straightforward to calculate the change in the awesomeness if one value is changed. You only have to keep track of the current awesomeness and the array itself.
•  » » » 5 weeks ago, # ^ |   0 Is this about writing $998244353$ if statements or is there a clean way to do it?
•  » » » » 5 weeks ago, # ^ |   +3 See my submission — 169125556.
•  » » » » » 5 weeks ago, # ^ |   0 Really neat. Thank you.
•  » » » 5 weeks ago, # ^ |   0 I tried, but couldn't come up with something fast
•  » » 5 weeks ago, # ^ |   0 Though it took me a lot of time to solve this, general idea for any such problem is, we want to know, if there is something with a[i-1],a[i] and a[i],a[i+1], when we do an update on index i.You can check that our summation for a given array of size n = (n*(n+1))/2 + sum of (n-1-x)*(x+1), where 0<=x
•  » » 5 weeks ago, # ^ |   0 Individual contribution of each index to the whole. So, if all numbers are distinct, then each index contributes (i + 1) * (n — i) to the total sum. When you modify a number, check if it is equal to the left or right index. If it is, then subtract its individual contribution from the sum. If it was equal but now different, then add its individual contribution to the sum. The exact individual contribution formula is weird and just takes a lot of time to find. (Ex. it's different if it's the same as the left neighbour vs the right neighbour, different for the first element, middle elements, and the last elements etc.)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 I tried writing an explanation but I found I was unable to explain it clearly. Nonetheless I have left the explanation in case it helps.First, how to calculate answer overall? Calculating prefix of blocks is simple, and all subarray s contianing the first element must sum all these. Then just iterate from left to right and if you find a new block, subtract (length remaining — 1), otherwise subtract -1. Answer is sum of all this.To be clear: suppose you have 1 2 2 3 2 4 block_prefix = 1 2 2 3 4 5 answer for v[0] = 5 + 4 + 3 + 2 + 2 + 1 = 17 answer for v[1] = 17 — 5 (remaining numbers) — 1 = 11 answer for v[2] = 10 (since it's the same block, we only remove 1 from the answer) // and so on final answer is sum of all these.So now we know how to find the initial answer in O(n). How would it help us find the answer?After a query: we have 4 caseseither this element begins a block on the left or begins a block on the right or breaks a block on the left or breaks a block on the rightIf it begins a block on the left, we subtract 1 from all the elements to our left. If it begins a block on the right, we subtract a 1 from all the elements to our left including us. We just reverse this if it breaks a block. for(int d=0;d>i>>x; --i; int l = n — i; if(v[i] != x) { // Case 1: We are breaking a block on the left hand side if(i != 0 && v[i] == v[i-1]) { s += (l*i); } // Case 2: We are breaking a block also on the right hand side if(i != n-1 && v[i+1] == v[i]) { s += (l-1)*(i+1); } // Case 3: We are creating a block on the left hand side if(i != 0 && x == v[i-1]) { s -= (l*i); } // Case 4: We are creating a block also on the right hand side if(i != n-1 && v[i+1] == x) { s -= (l-1)*(i+1); } } v[i] = x; cout<
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 You just need to understand how often subarray of length 2 appear in array.For exmp:1 2 3 4 5Currently ans = 35. Lets say we want to change 3rd (pos = 3) element (1-indexed) to 2, so it became this:1 2 2 4 5Now we consider 2 things:was a[pos] equal a[pos + 1] before and if it is equal now. If it was equal and now it isn't, we just need to decrease ans by how many times does this subarray appears. In this exmp it appears 6 times: {2, 2}, {2, 2, 4}, {2, 2, 4, 5}, {1, 2, 2}, {1, 2, 2, 4}, {1, 2, 2, 4, 5}. So, now ans = ans — 6, so it is equal to 29. Else we increase ans by this number.was a[pos — 1] equal to a[pos] before and if it is equal now. (Do the same as this 1st case).
•  » » » 5 weeks ago, # ^ |   0 Thank you very much! I realized my main mistake was thinking and writing some long and difficult formula. But now I see the solution was quite clear
•  » » 5 weeks ago, # ^ |   0 Try to think of a way to calculate the contribution of each index in O(1) time. Any number affects only the numbers just after and before it. Then the problem is simple. Whenever any number is changed, subtract the contributions of the 3 numbers(before, after and itself). Then add the new contributions after a number is changed.As far as calculating contribution, think of it this way — All numbers in a block except one are useless.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 First calculate maximum answer (i.e when all elements are distinct)Let B[i] = arr[i] == arr[i+1] with length n-1. Then subtract from maximum answer the sum of all subarrays of B (which can be done in O(n)). Answering queries can be done by extending the idea of sum of all subarrays: update can only change 2 values of B and it's easy to recalculate new sum of B.
•  » » 5 weeks ago, # ^ |   +4 Meme
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Assuming we have an array $pref$ where $pref[i]$ is the number of elements with indices $k\leq i$ where $arr[k]\neq arr[k-1]$. For a given $[L, R]$ segment, its awesomeness $=pref[r]-pref[l]+1$. Hence, the answer is $\dfrac{N*(N+1)}{2}$ + $\sum_{i=1}^{n}{\sum_{j=i}^{n}{pref[j]-pref[i]}}$ $=$ $\dfrac{N*(N+1)}{2}$ $+$ $1*pref[1]+2*pref[2]+...+n*pref[n]$ $-n*pref[1]-(n-1)*pref[2]-...-1*pref[n]$.So, whenever $arr[i]$ changes, it can can add $\pm 1$ to $pref[i]$, $pref[i+1]$, ..., $pref[n]$ (if the equality between $arr[i]$ and $arr[i-1]$ changes) and can add $\pm 1$ to $pref[i+1]$, $pref[i+2]$, ..., $pref[n]$ (if the equality between $arr[i+1]$ and $arr[i]$ changes.The effect of adding or subtracting $1$ to all prefix values in some suffix corresponds to adding or subtracting arithmetic sums to the answer, e.g, if we add $1$ to all the prefix values in the suffix starting at $k$, this corresponds to setting $ans$ to $ans+\sum_{i=k}^{n}{i}-\sum_{i=1}^{n-k+1}{i}$.Hence, we can process each query and modify our answer accordingly as needed then print the modified answer.Submission
•  » » 5 weeks ago, # ^ |   0 The initial answer is easy with DP. Then for every update at position i, you consider all segments including i, you check how their contribution change. To make life easier, you can classify segments into 3 types: 1. ends at i 2. starts from i 3. i is neither end nor start. That's the basic idea.
 » 5 weeks ago, # |   +2 Thanks for the extra 15 minutes!
•  » » 5 weeks ago, # ^ |   +4 I can see you solved C, can you please explain your approach !
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I guess there are already good explanations in other comments, but to come up with the idea, you should notice that even without any query, since n<=10^5, you already need around O(n)/O(nlogn) approach to find the initial beauty. Once you figure out the formula to calculate beauty in O(n) it's easier for you to handle queries in O(1).
•  » » » » 5 weeks ago, # ^ |   0 Got it thanks, will try to implement
 » 5 weeks ago, # |   0 Did anyone solve D with Python? I got TLE on pretest 4 :(
 » 5 weeks ago, # |   0 Yet another "speedforces" contest
 » 5 weeks ago, # |   +1 can someone point out what's wrong with my submission for div 2 C?spent basically the entire contest failing to figure out my mistake
•  » » 5 weeks ago, # ^ |   0 x will be compared with arr[i-1] and arr[i+1] and not arr[i].
•  » » 5 weeks ago, # ^ |   0  for (int i = 0; i < n; i++) { You know, subs += (n - i) * i; overflows because i is int.
•  » » » 5 weeks ago, # ^ |   0 is it the (n - i) * i expression overflowing? because subs is already a 64 bit integer
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 C++ evaluates (n - i) * i as int because all variables are int, and then adds result to subs. It doesn't care about context of expression
•  » » » » » 5 weeks ago, # ^ |   0 thanks for your ans ORZ
•  » » » » » 5 weeks ago, # ^ |   0 ty, it passed now.. just mad that all i had to do was change an int to an ll......
 » 5 weeks ago, # |   0 bet many have made silly mistake in problem B
 » 5 weeks ago, # |   0 Any hint for D?
•  » » 5 weeks ago, # ^ |   0 You can $and$ all the $x$ values of the triplets $l, r, x$ with $l = i$ or $r = i$ to find out which bits can/can't be placed at $a[i]$.
•  » » 5 weeks ago, # ^ |   0 First consider the case of $i = j$ in a statement.Then find all bit positions that MUST be 0. Then find all bit positions that MUST be 1. After this, you can greedily construct the lexicographically least array by deciding on the bits that are still unknown.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 Denote $unset[i]$ as the mask representing bits that must be unset in $arr[i]$, this can be known from the unset bits in $x$ values which are the result of an $OR$ operation with $arr[i]$.So we can calculate first the array $unset$ and then iterate on the queries. For the $qi^{th}$ query, for every bit set in $x$ and must be unset in one of $arr[i]$ and $arr[j]$, then we are sure we must set it in the other element. This has to be done before any further processing to ensure no extra unneeded bits are set somewhere.What is remaining is those $x$ values where some set bits in them can be set in either $arr[i]$ or $arr[j]$. Assuming $j\geq i$, let's sort first the queries in ascending order of $j$, then process the queries in that order, and whenever we find a set bit in $x$ that is still unset in $i$ and $j$, set it in $j$.The reason for that latest sorting done on queries is to handle the case when we have queries ${i, j, x_1}$ and ${j, k, x_2}$, where $i •  » » 5 weeks ago, # ^ | 0 If i-th bit of x is 0, then i-th bit of a[l] and a[r] must be 0. After that consider all queries where l = 1 (1-indexing). If i-th bit of x is 1 and i-th bit of a[r] must be 0, then we have to set 1 at i-th bit of a[1]. After considering all queries where l = 1 we can do it one more time, but now if i-th bit of x is 1 and i-th bit of a[1] is also 1, then we don't have to set 1 at i-th bit of a[r]. Now we do the same for all 2 <= l <= n  » 5 weeks ago, # | ← Rev. 2 → 0 Any Hints for Problem F? Can we solve the 1-d version (farm's top-right corner being (100,1)) in 3 steps? •  » » 5 weeks ago, # ^ | +5 If my solution passes system tests, then...5 queries seems to be a red herring. In factYou can do it in two queries. (Maybe even one, but I'm not sure). A way to beginTry to solve the 1D version in just 1 query. Continued...Make one triangle connecting (0, 0), (0, 1) and (N, 1). What will the answer to this query tell you?Then simply expand this to two dimensions. •  » » » 5 weeks ago, # ^ | ← Rev. 2 → 0 Oh nice! Yeah got it for 2-d too in 2 queries, 1 for getting the y (dividing into 100 such triangles...more or like zig-zag trapeziums) and next query for the row y, y+1...beautiful  » 5 weeks ago, # | 0 How do you update values of blocks optimally for each query? This got me stuck hard on C •  » » 5 weeks ago, # ^ | 0 You don't need to — the length of the blocks is immaterial, the only thing you care about is if a block is created or not. •  » » » 5 weeks ago, # ^ | 0 Could you explain it a bit more? •  » » » 5 weeks ago, # ^ | 0 Actually, nevermind, I saw your solution up in the comments, ty. •  » » 5 weeks ago, # ^ | 0 i don't know if there is an easier solution but either u use segment tree with lazy propagation or using BIT ( binary indexed tree) •  » » » 5 weeks ago, # ^ | 0 I thought about both, not familiar with lazy version of segTree, but couldn't get a grip on any of the two.But I agree with the above comment, I knew there was some kind of calculation possible to pretty much calculate everything after each query. Couldn't find it either, lol •  » » » » 5 weeks ago, # ^ | 0 i was thinking the same as u in the contest i get an idea for a possible solution but get stuck at range updating and imn't familier with this topic even when i searched for templates for range update query couldn't use it xD  » 5 weeks ago, # | +2 SpoilerExtremely large gap  » 5 weeks ago, # | 0 How could I get TLE in task C if I only have five "for i in range(n)" (no nested loop)? :( •  » » 5 weeks ago, # ^ | 0 same here  » 5 weeks ago, # | ← Rev. 2 → -10 jjj  » 5 weeks ago, # | -10 How to solve G?  » 5 weeks ago, # | ← Rev. 2 → 0 Can anyone give me a counterexample for my submission for B?I thought it covered all kinds of special cases but it gets stuck at pretest 2. •  » » 5 weeks ago, # ^ | 0 nvm, I found it myself.  » 5 weeks ago, # | 0 Speedforces and this is me on B; -100 delta incoming  » 5 weeks ago, # | +38 Why would you put 1.5sec for D, just why... You made such a good problem and then you screw it with a shit TL... •  » » 5 weeks ago, # ^ | +5 or stop using shit language ;)  » 5 weeks ago, # | 0 When you get "WA on #4" on C in the last 5 minutes  » 5 weeks ago, # | +1 Me who used multiset of structures to solve C and understanding the intended solution now.. •  » » 5 weeks ago, # ^ | +1 i used segment tree and i got a "beautiful" wrong answer which is really annoying  » 5 weeks ago, # | +4 This round is neither bitforces nor mathforces, i like it !, Codeforces should have more rounds like this •  » » 5 weeks ago, # ^ | 0 stfu, not everyone is lucky enough to do good in this trash type of contest.  » 5 weeks ago, # | ← Rev. 2 → -22 . •  » » 5 weeks ago, # ^ | 0 Agree. Very standard and bad problem C. Which cause me fail to solve E in time.  » 5 weeks ago, # | 0 Can someone please explain what's wrong with my code for B?https://codeforces.com/contest/1715/submission/169117875 •  » » 5 weeks ago, # ^ | 0 u can also give k-1 to a1,i.e. a1 can be at max k*b+(k-1)  » 5 weeks ago, # | ← Rev. 2 → 0 Could Anyone Explain How to Solve Problem B I am Struggling in it :( •  » » 5 weeks ago, # ^ | 0 The minimum$s$is if$bk$if each$a_i$is divisible by$k$. There is no way to decrease$s$because reducing any value of$a_i$will reduce the overall beauty.On the other hand, if$a_i$is divisible by$k$, then you can increase$a_i$by up to$k - 1$without changing the result of the floor division, i.e., beauty contribution remains the same. Therefore, the maximum$s$is$bk + k (n - 1)$. So we can start by putting$bk$in the first (or last) element to secure the beauty of$b$. If we still haven't reached our target of$s$, we can add up to$k - 1$in each element (including the first/last!) to reach our target of$s$without altering the beauty. •  » » 5 weeks ago, # ^ | 0 One idea is to build an array with correct beauty, in example by setting a[0] to b*k.Most likely then the sum of a[] is smaller than s. But we can see that we can up to k-1 to each element in a[] without changing the beauty. So we update elements in a until the sum of the elements conforms to s.  » 5 weeks ago, # | 0 I'm so glad I NOPE'd at C so fast and moved straight to D, which I felt was much easier than C. Even after I returned to C (after solving D), I couldn't even figure out how to compute the initial awesomeness value for C in sub-quadratic time... •  » » 5 weeks ago, # ^ | 0 Was D some graph theory problem or what? For me it was harder, than C •  » » » 5 weeks ago, # ^ | 0 Not so much graph involved, just some basic knowledge of connected components imo •  » » » 5 weeks ago, # ^ | ← Rev. 2 → +4 Nah, you just need to think about how bitwise OR constrains the values and then greedily construct the array. If$i = j$for a statement, then$a_i$is exactly equal to the result. Each statement is essentially 30 statements, each involving the OR of two bits.For bits$p$and$q$, the statement$p \mid q = 0$means$p = q = 0$. So now we only need to worry about statements where the result is 1.For bit$p$, the statement$p \mid 0 = 1$means$p = 1$. After this, all that's left are$p \mid q = 1$statements where neither$p$nor$q$are fixed.Now we can greedily construct the lexicographically least result: start with$a_1$, clear all of its uncertain bits to$0$, and check all$p \mid q = 1$statements that involve an$a_1$bit, setting the other bit to$1$. Repeat for$a_2$, and so on.  » 5 weeks ago, # | +12 How to solve E? •  » » 5 weeks ago, # ^ | +8 Relevant ProblemSuppose$distance[i][v]$gives the minimum distance of node$v$from node$1$on using atmost$i$flights.Do standard dijkstra to find$distance[0][v]$Now repeat this process for$i(1 \leq i \leq k)$Suppose you use some flight. So find$distance[i][v]$on using values of$distance[i-1]$(use Convex Hull trick) Transition state is$distance[i][v] = minimum(distance[i-1][u]+u^2 - 2 \cdot u \cdot v) + v^2(1 \leq u \leq n)$Do standard dijkstra to update$distance[i][v]$•  » » » 5 weeks ago, # ^ | 0 How to calculate minimum(distance[i−1][u]+u^2−2⋅u⋅v) quickly? •  » » » » 5 weeks ago, # ^ | +5 You can use CHT to do that. Kind of similar to this. •  » » » » 5 weeks ago, # ^ | ← Rev. 4 → +20 you can also use divide and conquer :D, which i think is more approachable than cht(i dont know how to do cht). Lets say you already have the minimum distances to all nodes if you use$f$flights. I'm gonna denote the distance to node$a$from source vertex$1$if you use$f$flights as$dist_{a,f}$. If you find the answer for some node$v$, which can obviously done in linear time by brute forcing all possible flights to$v$, you can find the optimal$u$to minimize$dist_{u,f}+(v-u)^2$. Notice that, for any$x$where$xu$. Note that disproving this statement suffices for a proof, since we will check all$t$where$t \leq u$anyways. If the inequality from before is true, then it will contradict the statement$dist_{u,f}+(v-u)^2 < dist_{t,f}+(v-t)^2$, since$(x-t)^2-(v-t)^2 > (x-u)^2-(v-u)^2$, since$t>u$and$xv$, too. In that case, we don't need to check any$t$where$t
 » 5 weeks ago, # |   +3 when will the editorial for this round be available?
•  » » 5 weeks ago, # ^ |   0 usually it comes in an hour or so it will come probably in an hour or two !!
•  » » 5 weeks ago, # ^ |   0 it's out :)
 » 5 weeks ago, # |   0 Can anyone pass problem C in python? My solution is in O(n) time complexity, yet TLE on problem C.https://codeforces.com/contest/1715/submission/169148981
•  » » 5 weeks ago, # ^ |   0 import sys input = lambda: sys.stdin.readline().strip() try to add these two lines before your codes and submit again
•  » » » 5 weeks ago, # ^ |   0 Thankyou so much
 » 5 weeks ago, # |   0 How to solve question c
 » 5 weeks ago, # | ← Rev. 2 →   +9 Solved Div2 D for XOR instead of OR :'(
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Code for anyone who did the same#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair p32; typedef pair p64; typedef pair pdd; typedef vector v64; typedef vector v32; typedef vector > vv32; typedef vector > vv64; typedef vector > vvp64; typedef vector vp64; typedef vector vp32; double eps = 1e-12; #define forn(i,e) for(ll i = 0; i < e; i++) #define forsn(i,s,e) for(ll i = s; i < e; i++) #define rforn(i,s) for(ll i = s; i >= 0; i--) #define rforsn(i,s,e) for(ll i = s; i >= e; i--) #define ln "\n" #define dbg(x) cout<<#x<<" = "< void swp(T&a,T&b) { T temp=a; a=b; b=temp; } // Useful Funcs // smallest prime divisor // int smp[100001]={0}; // void calcPrimes(){ // forn(i,100001){ // smp[i]=i; // } // ll ct=2; // while(ct*ct<100001){ // if(smp[ct]==ct){ // for(ll j=ct*ct;j<100001;j+=ct){smp[j]=ct;}} // ct+=1; // } // } ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;} // Recursive function to calculate gcd long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b,a%b); } /* Iterative Function to calculate (x^y)%p in O(log y) */ long long modex(long long x, unsigned int y, long long p) { long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res; } int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not // present in array return -1; } // STL binary search functions // binary_search(start_ptr, end_ptr, num) // returns true if element present, // otherwise returns false. // upper_bound(start_ptr, end_ptr, num) // returns the first index having value // greater than num. // If there is no such index, then returns // length of array. // lower_bound(start_ptr, end_ptr, num) // returns the fiirst index having value // not less than num // Subtract v.begin() or a(in case of array) to get index. // Pointers // for array-> a, a+x // for vector-> v.begin(), v.begin()+x, v.end() const ll MOD = 998244353; const ll mod = 1e9+7; void solve(){ ll n,q; cin>>n>>q; vector>> v(n,vector>(30)); vector>> v1(n,vector>(30)); forn(i,q){ ll a,b,c; cin>>a>>b>>c; for(ll j=0;j<30;++j){ if(c%2==0){ v[a-1][j].pb(b-1); v[b-1][j].pb(a-1); } else{ v1[a-1][j].pb(b-1); v1[b-1][j].pb(a-1); } c/=2; } } vector> ans(n,vector(30,-1)); for(ll j=29;j>=0;--j){ vector vis(n,0); for(ll i=0;i q; queue q1; q.push(i); vis[i]=1; while(!q.empty() || !q1.empty()){ if(!q.empty()){ ll x = q.front(); q.pop(); // cout< ansf(n); forn(i,n){ ll el = 0; for(ll j=29;j>=0;--j){ el*=2ll; el+=ans[i][j]; } ansf[i]=el; } forn(i,n){ cout<> t; // for(int it=1;it<=t;it++) { solve(); // } return 0; } 
•  » » » 5 weeks ago, # ^ |   0 Code for OR. Turns out it is way easier than the XOR counterpart. Its always XOR. Why Codeforces OR now? :‑| Code for Div2 D#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair p32; typedef pair p64; typedef pair pdd; typedef vector v64; typedef vector v32; typedef vector > vv32; typedef vector > vv64; typedef vector > vvp64; typedef vector vp64; typedef vector vp32; double eps = 1e-12; #define forn(i,e) for(ll i = 0; i < e; i++) #define forsn(i,s,e) for(ll i = s; i < e; i++) #define rforn(i,s) for(ll i = s; i >= 0; i--) #define rforsn(i,s,e) for(ll i = s; i >= e; i--) #define ln "\n" #define dbg(x) cout<<#x<<" = "< void swp(T&a,T&b) { T temp=a; a=b; b=temp; } // Useful Funcs // smallest prime divisor // int smp[100001]={0}; // void calcPrimes(){ // forn(i,100001){ // smp[i]=i; // } // ll ct=2; // while(ct*ct<100001){ // if(smp[ct]==ct){ // for(ll j=ct*ct;j<100001;j+=ct){smp[j]=ct;}} // ct+=1; // } // } ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;} // Recursive function to calculate gcd long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b,a%b); } /* Iterative Function to calculate (x^y)%p in O(log y) */ long long modex(long long x, unsigned int y, long long p) { long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res; } int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not // present in array return -1; } // STL binary search functions // binary_search(start_ptr, end_ptr, num) // returns true if element present, // otherwise returns false. // upper_bound(start_ptr, end_ptr, num) // returns the first index having value // greater than num. // If there is no such index, then returns // length of array. // lower_bound(start_ptr, end_ptr, num) // returns the fiirst index having value // not less than num // Subtract v.begin() or a(in case of array) to get index. // Pointers // for array-> a, a+x // for vector-> v.begin(), v.begin()+x, v.end() const ll MOD = 998244353; const ll mod = 1e9+7; void solve(){ ll n,q; cin>>n>>q; vector>> v1(n,vector>(30)); vector> ans(n,vector(30,-1)); forn(i,q){ ll a,b,c; cin>>a>>b>>c; for(ll j=0;j<30;++j){ if(c%2==0){ ans[a-1][j]=0; ans[b-1][j]=0; } else{ if(ans[a-1][j]==0){ ans[b-1][j]=1; } else if(ans[b-1][j]==0){ ans[a-1][j]=1; } else if(a==b){ ans[a-1][j]=1; } else{ v1[a-1][j].pb(b-1); v1[b-1][j].pb(a-1); } } c/=2; } } for(ll j=29;j>=0;--j){ for(ll i=0;i=0;--j){ for(ll i=0;i ansf(n); forn(i,n){ ll el = 0; for(ll j=29;j>=0;--j){ el*=2ll; el+=ans[i][j]; } ansf[i]=el; } forn(i,n){ cout<> t; // for(int it=1;it<=t;it++) { solve(); // } return 0; } 
 » 5 weeks ago, # |   +19 the pretests at the last two contests were really terrible
 » 5 weeks ago, # |   +30 in problem F, I submited this code and got Wrong Answer during the contest. So I submit another code after that. But the first code should be AC because of the wrong checker.It makes me lose scores by resubmission. I hope my score could be be back :-( don't skip my code and give me the correct score, thx.
 » 5 weeks ago, # | ← Rev. 2 →   +1 I hate pretests On your contests They're very bad It's really sad XD
 » 5 weeks ago, # |   0 Can someone tell on which test case my solution for Problem B is failing. https://codeforces.com/contest/1715/submission/169148352
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 For example：2 2 2 6the answer should be 3 3but not 1 1 4(if it is wrong, just ignore it~
 » 5 weeks ago, # | ← Rev. 2 →   +30 I apologize that there were technical issues during the round today. Ratings updated preliminarily. We will remove cheaters and update the ratings again soon.
•  » » 5 weeks ago, # ^ |   0 Thanks for your work. btw, some people submit problem F again during contest because of technical issues of checker. I suggest recalculate their scores if it is possible, thanks again.
 » 5 weeks ago, # |   0 hey guys, can someone please tell me what was wrong with my C submition? https://codeforces.com/contest/1715/submission/169155228
•  » » 5 weeks ago, # ^ |   0 Take a look at Ticket 16062 from CF Stress for a counter example.
 » 5 weeks ago, # |   0 Hope I get an increase after rechecking
•  » » 5 weeks ago, # ^ |   +3 Wishing for those +3 points just like you.
 » 5 weeks ago, # |   -11 I do not pass F on protests, although I solved it on testing)))))))))))
 » 5 weeks ago, # |   +14 Hello MikeMirzayanov,When CF was down in the midway, I submitted the exactly same solution twice (submission1 and submission2). One from codeforces.com and second from m1.codeforces.com as I was not able to see status. I still got first submission skipped and penalty for resubmission. Can you please look into it?
 » 5 weeks ago, # | ← Rev. 2 →   0 okay got it
 » 5 weeks ago, # |   0 thanks for the amazing problems in this and previous round, definetly would like to see more contests like this
 » 5 weeks ago, # |   +3 Can someone explain me why these 2 solutions have 2 different verdicts :thinking:? https://codeforces.com/contest/1715/submission/169136307 and https://codeforces.com/contest/1715/submission/169166978
 » 5 weeks ago, # |   -13 Problem E is very nice
 » 5 weeks ago, # |   +20 Really don't like this round, for : Task AThe statement is very confusing and I solve it by observing samples. Task CFind it very hard to implement with many special cases in my solution . Used 30 minutes implementing and debugging. Task DIt is easier than C. Also the samples are weak (got wa on 4 for 10 times) and the tests are also weak. (see the uphack area) Task EI do not expect Convex Hull Trick in div2s...
•  » » 5 weeks ago, # ^ |   +1 Very agree.E is the worst problem, it does not have any thinking content but only needs boring algorithms.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 I don't agree with "boring algorithms", cht/lichao tree are quite interesting as a concept
•  » » 4 weeks ago, # ^ |   0 I think that task was fit for div. 2, but maybe not for div. 1, since it's quite standard and a lot of div. 1 users would solve it without much thinking.
•  » » » 4 weeks ago, # ^ |   0 Well but this trick is too high level for div2 contestants. And also everything besides this trick is quite standard
 » 5 weeks ago, # |   -9 The system tests for problem D are too weak. Please retest it.
•  » » 5 weeks ago, # ^ |   0 Are up hacks included in the System testing?
 » 5 weeks ago, # |   0 C time constraints are too tight for python :/ my linear solution TLE'd during the contest but a C++ translation worked
 » 5 weeks ago, # |   0 How do you create a grid in a note at problem A? Thank you.
 » 5 weeks ago, # |   +3 Trash contest
•  » » 5 weeks ago, # ^ |   0 you're on codeforces, what do you expect
•  » » » 4 weeks ago, # ^ |   +3 ?
•  » » » » 4 weeks ago, # ^ |   0 it's common knowledge that codeforces is anarchy, there are no regulations and they just serve us bad contests but there's nothing we can do about it
 » 5 weeks ago, # |   0 Anyone just now got the email notification for this?
•  » » 4 weeks ago, # ^ |   0 yes
 » 3 weeks ago, # |   +8 I feel sorry for whomever had to write the interactor for problem F