Hello, Codeforces!

ognjentesic, wxhtzdy, OAleksa, AndrewPav, Acanikolic73 and I are glad to invite you to the Codeforces Round 900 (Div. 3).

It starts on Sep/26/2023 17:35 (Moscow time)

You will be given **7 problems** and **2 hours and 15 minutes** to solve them.

Note that the **penalty** for the wrong submission in this round is **10 minutes**.

Also note that there will be a **12 hour open hacking phase** after the round.

Remember, that only the *trusted participants of the third division* will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participant of the third division*, you must:

- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, the round will be rated for you.**

Problems have been created and prepared by AlphaMale06, ognjentesic, wxhtzdy, OAleksa, AndrewPav, Acanikolic73, and Vladosiya.

We would also to thank:

- Vladosiya for the amazing coordination and help with preparing a balanced problemset, and for giving us the opportunity to create a Div. 3 round.
- MikeMirzayanov for the amazing Polygon and Codeforces platforms.
- JovanB, abc864197532, sevlll777 for red testing
- NemanjaSo2005, n0sk1ll, allllekssssa, Alexdat2000, misorin, Hyperbolic for yellow testing
- DAleksa, ljuba, alex.kudryashov for purple testing
- MihailoT, SashaT9, ELDRVD, Chrisedyong, tryptophan for blue testing
- Andrijanikolic73, Mihajlo18, UrosNedic, Klaus26, Escaquejant, smax294, max0n for cyan testing
- Budimmm for gray testing

Also a very special thanks to the most dedicated tester I have ever seen, NemanjaSo2005.

I wish you luck, and hope you like the problems and learn from them.

Update: Editorial is out.

Congratulations to the winners:

Unofficial:

Official:

As a coordinator, it was fun to work on the contest in English for the first time!

As a problem setter, I'm proud to have made the first (mostly) Serbian Div. 3 round :)

Best of Luck Guys . Surely this would be fun .

Serbian div 3, orz!

Best tester ever, orz!

"Throughout heaven and earth I alone am the honored one"

now he is the honored two

is it rated?

The answer is !(do you know how to read)

!false

I can teach you how to read but I won't as I don't know either

yes

As an author i didn’t make any tasks.

As a tester, I hope you to enjoy the contest and read all the problems. Good luck!

As a tester, problems are well balanced and really interesting. Hope you will enjoy solving them and get positive delta!

I will be taking part after reading this statement and having faith in your words :). I don't have any rating hopes as I am more interested in enjoying the round :).

Will give my review after the contest !!

Good luck!

As I said I will give my review and it is as follows — I liked the problem set , problem D and E should have been swapped then it will be balanced in correct order. Unfortunately I was not able to debug my code for D but I am happy to take part in today contest . Good job to team.

Zoves u kasne sate

trazis opijate

As a tester I can confirm that NemanjaSo2005 is a tester any author would wish to have. orz.

Same goes for you :)

Happy 9th centennial! 100 to millennium!

100% SERBIAN BESTEST ROUND!!! SERBIA!!!

yes , bestest

As a special tester, the problems are good and test data should also be good!

As a tester, the problems were interesting. I hope all of you enjoy this round.

As a tester, I recommend you to read all the problems.

Sorry but shouldn't the 900th contest be rated for whole community. I think 901st and this round should be swapped.

Don't really see why it should? It's just a number. Maybe if it was 1000th.

As a tester, I hope you to enjoy this round, because the problems are interesting and balanced. Good luck!

As a late one tester I wish you all good luck!

Screwed up the edu round, hopefully this will make up for it!

I promise it will :)

900! damn i feel old

2h and 15 mins Is Little time for 7 problems

but the question is

Spoilerwill you solve all 7?

900! Sounds good :)

This will be my first official Div.3 contest in 5 months

Hope it is the last one too :)

ًWish i get green

will there be 12 hour hacking phase round??

of course

It is not mentioned that's why I asked

Round #900 hope to be special for me <3.

Cool

Do we get 10minutes less if we submit a wrong submission??

Hope i can color upgrade ヾ(⭐▽ﾟ)ノMe too.. missed by 12 pts last round:(

how do some coders start their journey from 1400 rating? how ?? you are one of them, i'd like you to answer

The codeforces ELO was initialized to 1500 at that times (2018 prob go search yourself idc).

Codeforces rating actually starts from 1500, but a few years ago they made some adjustments so a fake rating is shown for the first few rounds (e.g. your rating is 1400, but 500 is shown). The adjustment becomes less and less, and after like 5? rounds it disappears.

good luckI also hope to become at least green

Round 900......Seems GOOD

900 sounds good. Hope the color change occurs in this contest.

Just a comment to get some contribution:)

All the best to everyone...

I hope the questions are good because this is the div number three I joined.

first div3 as out of competition :)

Hopefully I also get to this point someday ^_^

Finally an Alpha Male Round :D

Can anybody explain what 10 min of penalty means

As you take more and more time to get to the answer, Points get deducted

For example a guy who solved a problem in 10 minutes would get better rank than guy who solved at 20 mins(Assuming both solved it correctly in the first submission itself)

But if the 10 mins guy made an incorrect submission before his accepted answer, 10 minutes worth points will be deducted from that problem's points, So in this particular case both 10 and 20 minutes guy will get same points even tho 10 min giy solved it earlier

In Codeforces, you usually lose 0.4% of the task's points for every minute between contest start and submission time, plus 50 points for every failed attempt, the penalty caps out at 70%. Here, the failed attempt penalty is 4% of the total points rather than flat 50 points.

He asked about exICPC penalty rules. Not Codeforces rules.

You're right, I forgot ICPC rules are used for Div3+ rounds (for those who don't know — there's no points, first sort key is total problems solved, second key is the sum of deltas of submission time and contest start + 20 minutes per failed attempt, except here it's 10 minutes instead).

Best of luck everyone :D

If I couldn't start with the div on time and perhaps joined mid-contest before it ends, will it be rated for me? and can I even join?

Yes, it will be rated for you

if you register earlier. But it is not a good decision to attend a contest at the end moment. Every second matters.If you are late anyhow, you can give a virtual contest later.

I hope there will be a lot of problems on MEX

do not have a point of 1900 or higher in the rating.Shouldn't it be $$$1600$$$?

That's for Div. 4

SpoilerNo the rating limit of Div.4 is $$$1400$$$.

Oh yeah, sorry, I forgot

You didn't understand what that part means. Read this.

As we all know, div3 is more difficult than div2

Why always in queue :(

A B C E easy. D crazy hard.

Nice.

It was meant to be

I though I wouldn't solve

F, but after I spend some time. I finally did it. And I love itLe authors:I think u should just stop founding problems in others and focus on getting better. U are responsible for every problem in ur life bro :)

just use treap)

I really liked your ordering of D and E.

QueryForces!

I love number theory too. Thanks for this problem ^_^could you please explain your reasoning behind F? The only one that came to mind was counting divisors in N^1/3 but couldn't proceed from there?

HintThe answer is yes only when $$$d(n)$$$ divides $$$n$$$

Thank you for the reply. I get it now since the gcd(a,n)==1, if I may ask the method of counting diviosrs is the same as this [N^1/3] or is there an easier way (https://codeforces.com/blog/entry/22317)

factor the number given in the input and just maintain stuff on a map

HintUse the sieve of erathostenes to be able to factorize numbers in $$$O(logn)$$$, now you can maintain all prime factors and the number of divisors in a map or array, then you can calculate the number of divisors using the formula for the number of divisors via prime factors

Thank you for the reply, and the excellent problem set as well, hopefully, I reach blue this time :)

Thank you :)

Answer is "yes" when n is divisible by d(n).

Reason:lets say if we prime factorize $$$n$$$ then we get: $$$p_1^{a_1}*p_2^{a_2}*p_3^{a_3}*...*p_k^{a_k}$$$

so $$$d(n) = (a_1+1)*(a_2+1)*(a_3+1)*...*(a_k+1)$$$

let $$$x = \frac{n}{d(n)}$$$. so we need to multiply $$$d(n)$$$ with $$$x$$$.

now we can just multiply $$$n$$$ with $$$a = p^{x-1}$$$ where $$$p$$$ is a prime number not contained in $$$n$$$. Thus $$$d(n*a)$$$ will be $$$d(n)*x$$$

ps:I replied to my own comment by mistake lolCF was lagging as hell today!!!

Problem B solution:

Spoilerahahahahaha its amazing)

9 also randomly worked

just print any odd sequence of length n

Yeah, but this one also fits the restriction of a_i <= 3 * 10^5 =)

Do we really need to know splay tree to solve a div3D? or there is easier solution.

Btw, problem is same as: https://www.hackerrank.com/contests/w7/challenges/helix/problem

No...

It's just counting the number of reversals that cover each index (because the reversals are symmetric wrt the segments, the order doesn't matter), so it can be done with a "sweep line" sort of thing (idk if it's technically a sweep line).

There is a simpler solution.

Also https://cses.fi/problemset/task/2073

Explains so many solve counts!

Even easier can be done with Treap. Implementation is very simple, so you might as well learn it if you haven't already. Here is my 30-line template, if somebody wants it:

SpoilerPractice Problems:

Cool round! D,E,F are good (even i solved D&E with segment tree lmao)

can you please explain your approach for problem D

I believe this is not the intended solution, but we can solve D using Splay(or other BST).

This trick is a well-known template on a Chinese OJ called Luogu. There are also similar problems on many other OJs.

We can maintain the reverse operation in $$$\log n$$$ time. So just copying one template code and simulating the requested operation is enough to get AC.

__gnu_cxx::rope also offers this functionality. However, the 1s TL is too stringent, causing it get TLE due to large constant factor.

Of course it's not the intended solution.

HintSplit the string into substrings from $$$l_i$$$ to $$$r_i$$$ for each $$$i$$$, now you can solve a much easier problem

Wrong answer on test 7 in problem F when there was only 2 minutes left :((

I got TLE in problem D on test 10 :((((((

Similarly i too got a TLE in D and E.

Because yours solution is $$$O(n^2)$$$ lol:)

I have solved problem E using sparse table and binary search, but it feels like an overkill. Is there an "easier" solution?

Fairly sure that is the intended solution, you can't precompute because the value of k varies. Anything else that involves solving bitwise seems much more overkill to me than sparse table / binary search.

I did it using prefix concept and binary search.

You can have a look at the solution https://codeforces.com/contest/1878/submission/225351971

Yeah, you will see once the editorial is out

If you fix l and iterate over r, then AND will change atmost 32 times. You can precompute the next index at which it changes

Please help how to decrease TC in my code thanks :)

Problem E

The time complexity of your code is O(n*q) which will be around 10^10 operations. This will definitely not pass. I did this problem using square root decomposition but I am sure their is a much simpler solution.

can someone tell me why am i getting TLE submission . terrible div 3 BTW

Don't use memset, because you will get unnecessary reset when the number of test case is high. Just use for loop to reset the value of "pre" array instead.

.

i removed the memset still TLE submission

the inner loop, j will smaller than n, not N (n here is the number of element in the array, not the N = $$$2 * 10^5$$$ you defined)

yeah i saw that silly mistake. fixed it and the solution is AC NOW. i really wanna kms again

It's because you're using memset in each test case which resets the whole array with size $$$N$$$ not size $$$n$$$.

انا هقتل نفسي بجد. هنقص عشان الغلطة الهبلة دي :)

اديك اتعلمتها بالطريقة الصعبة مش هتنساها تاني بعد كده

Is it really div.3

Problem G seems cool. Is it use LCA + Binary Lifting + Ternary Search the Answer?

It is LCA + binary lifting. I don't see how ternary search could be applied, though.

My solution may or may not be wrong (feel free to hack because I feel like it's probably wrong and/or too slow and/or too memory inefficient) but what I did was to sweep line on the first/last occurrences of each bit. Implementation requires binary lifting as you said.

From what I observe (still not sure) for a path of $$$p_1, p_2, ..., p_k$$$ I notice that the results forms a parabolic function and we need to pick an optimal $$$i$$$ so that the result is maximum

But I'm still not sure about it tho

ternary search does not work because: 1. too slow (log^3) 2. wrong because the function of the answer is not not strictly increasing

We can unroll the path into an array and create segments for each bit, which range from the first occurrence of that bit to the last occurrence. The problem is then reduced (with some extra details) to finding a point covered by the maximum number of segments. AFAIK, ternary search doesn't work here.

LCA + binary lifting don't really seem like a Div. 3 approach, do they?

It appeared in round 881 problem F2, which barely anyone solved ;)

are you sure ternary search would work? I think binary searching for 30 places. where bit count of left side is exactly i (i from 1 to 30).

can you please explain how would you do ternary search??

Nah I'm still not sure. Just a hunch. What about yours?

i think we can binary search 30 times like this ->

for each i from (0<=i<=30) we can search binary search for first index j (vertex) from left where OR from first vertex to j vertex has bitcount of i then current value = bitcount(0 to j) + bitcount(j+1 to last). this way left and right will be divided 30 times, then max over all 30 values.

Wow this one's pretty neat. Cool approach. Thanks

I used the same idea in my implementation. It gives TLE as its complexity is O(N*log(N) + Q*30*log(N)*18). 225432018

SecretThis was not Div

3.so what was it

I actually think it's a good div3. Not too easy to be speedforces but not too hard to be div2

gap between C and D

True DE should have been swapped but my point still stands

Yeah, we had to change D in the last moment, the initial D was actually good enough for div3D.

Also I think E is too hard for div3D

Yeah dude, problems are ones of the best i've seen in div3, enjoyed them a lot

does G have a better solution than $$$O(q\cdot log^{2}n\cdot log(max A_i))$$$?

Yes. My solution is $$$O(n \log n + q \log n \log (\max a_i))$$$

How is your approach for G?

problem B was required some focus and analyze the trick to solve the problem in O(N) time complexity

Nice Tech Stack , Goes down whilst a contest is going on!!

Pretty sure E can be done in $$$ O(q * log ^ 2 n)$$$ . Just had not enough time to accomplish it.

E also can be done in $$$O(q\cdot\sqrt{n})$$$ 225365334

I did it in

using some prefix computations 225410652O(32*Q)it can be done in q*log(n) using sparse table and binary search.

Right

I hope i can reach LGM after sys test

How to pass E so fast? Right! use ACL! 225318799

If someone prefers video explanations or interested in knowing how to think in a live contest or reach to a particular solution.

Hereis my live screencast of solving problems [A -> E] (with detailed commentary inHindilanguage).PS: Don't judge me by my current rating :(

Actually, you have been a master LOL

Can someone explain why E cant be done with for loop iterating over array and performing & with every array element from l to r and checking if it is smaller that k. When I did this all and operations over array gave the first element... what am I missing?

it will give u a tle ,u need to find f(l,r) in more efficient way ig otherwise time complexity will exceed o(q)

A good contest QueryForces :)

Python is pretty slow for E (drawbacks of using python I guess...):

https://codeforces.com/contest/1878/submission/225408163 This submission TLEs

However when I change bits to 31 instead of 32, it passes:

https://codeforces.com/contest/1878/submission/225409398

Yeah, my C++ 32 bits kept TLEing, but 30 bits passed; I'm such a clown made 4 TLE submissions because of that.

It is ur problem using 32 instead of 30 bits.

I solved F successfully after 2hrs + 5min but didn't submit as i thought round was of typical 2hr duration.Clown moment for me.

someone tell how to reverse the string from a to b in o(n) time when q queries are given .it is easy if q queries are of the form i to n-1-i but here its i to j ig and its not symetric

It is symmetric for each interval separately, because they are disjoint

u are saying that i need to calculate no. of reversals for eacj index and if its even leave it as it is and if its odd take that character to n-1-i th position?

No, but you can basically treat each l, r as a separate test case and then solve a much easier problem

what do u mean by l,r?those are arrays in the question...

Yeah, you can basically divide the string into substrings from $$$l_i$$$ to $$$r_i$$$ and solve a easier problem for all $$$i$$$

What will be the efficient time complexity for the problem D?

O(N)

I had fun today. Thanks for the Contest. Hope we will get more of these kind of contest..

StructureForces

Structures are beautiful :)

Also E required prefix sums and that's the only structure on the whole contest lol

Isnt D also?

No

E is pref sums or segtree or sparse tables. If pref sums is structure than using arrays is also structure.

D and E were extremely cool problems. First time getting to use segment trees in an actual contest :)

i have never used segment tree in any of my contest ever.

You don't have to use segment tree for D and E

i know.

worst contest i have ever seen in my life ... the level was suddenly increased .... a request to mike that do not allow people like them to make contests

my bro you got bullied by the internet lol

Idfc bro!!

lmao

Dichotomy combined with segment tree, what a nice problem E!

The solution for E was available on geeksforgeeks (pre-written code).Tho it's not a complete solution( u need to apply binary search for answer) major part remains same. Here is the link : https://www.geeksforgeeks.org/queries-for-bitwise-and-in-the-index-range-l-r-of-the-given-array/ Since it's a pre-written code ig cf will consider this before plagiarism check.

Funny Solution for B

Spoiler[5, 5 + n[

Too many data structure problems can be solved by using template, and the questions are so long that the reading experience is poor. May D is too difficult for Div.3.

wdym, only E is a data structure, and even that can be solved using prefix sums

D can be solved with treap or splay tree tho

Why would you do it that way tho...

problems are all nice, its just can be solved by using template. Whaterver, I just say that D is not easy to fast get meaning for me non-native English speaker

Womt prefix sum give tle?

It's $$$O(Q \cdot logn \log(maxA)$$$ so it's not

how prefix sums??

For each bit, build prefix sums (if the bit is present in $$$a_i$$$ then add 1 else don't add anything) now we can check for each bit if it exists in the whole subsegment $$$[l,r]$$$, if $$$pref_r-pref_{l-1}=r-l+1$$$

My B's solution is completely random, I just picked three primes and created the array, checked for some random N <= 100 then submitted. Can someone try hacking it? Btw, overall nice round! Good problem set, except D, which was googlable.

Mine also random lol put even numbers 2,4,6.. if condition violates do a(i+2)--.

Your B won't be hacked cause your code is absolutely correct

https://codeforces.com/contest/1878/submission/225409196 WHY THIS SOLUTION IS GIVING TLE ON 10TH TEST CASE?

Because it is brute force (O(NQ))?

Reversing string has a complexity of $$$O(N)$$$ fyi

Had got the logic for question D. messed up by using lower bound instead of upperbound. Got AC on D after the contest

Something similar happened to me. I was using the lowerbound on the 'l' array and therefore there were some edge cases on which the solution was not working and I got WA 3 times. Right after the contest I submitted it using lower bound on the 'r' array and it got accepted. I wasted a lot of time on this.

Superb contest. Educational and fun to solve

Thanks

yes!!

In problem D, I just wrote brute force, I was not able to handle time complexity. Can anyone help me to reduce the time complexity of this program?

`**Submission Link**`

https://codeforces.com/contest/1878/submission/225389151

There are $$$q$$$ updates, each one of which will reverse a string of length $$$n$$$ (in the worst case). Reversal of a string of length $$$n$$$ if $$$O(n)$$$ and thus, your code is $$$O(nq)$$$.

Yes, I understood you. But I cannot reduce it. Can you help me to reduce it?

or if possible you can edit my code.

Hint 1You can notice from the description that each index has a counterpart (e.g. if $$$l_i = 3$$$ and $$$r_i = 10$$$, then the pair of counterparts are $$$(3,10), (4,9), (5,8), (6,7)$$$

Hint 2Reversing a substring means that all characters within those substring are swapped with their counterparts

Hint 3Reversing a substring even number of times is equivalent to not reversing at all

Hint 4If you know how many times an index is swapped then you can easily determined whether that index is swapped with their counterparts or not

Although I wrote poorly in this round, I know it is my own problem, and I hope I can learn from it and strive for a higher score and ranking in the next round

Why are O(n) solutions to C getting hacked? Isn't it guaranteed that the sum of n <= 2*10^5. If you didn't want O(n) why don't you just increase n?

You kinda just admitted you can't read the constraints

Yup, we allowed precalc for gauss sum because not everyone know the formula, we even bolded it lol

Lol, I just read again after I saw this. I guess muscle memory made me see "it is guaranteed it doesn't exceed" Still why not just increase n to maybe 10^9 or something.

Answered that in the comment above

Well, yeah I kinda agree on that. Like, it's a Div3C, you are usually expected to know the formula.

Actully, it isn't)))

Read again: Note that the sum of n over all test cases

mayexceed 2⋅105 .Great contest hope to become expert after it

First time using Square root decomposition in a contest (for E). Took a lot of time to debug it but got AC!

That was so unnecessary

Learning From The Contest: A C++ map may return a garbage value for an entry that is not present instead of 0. Costed me an AC on F(was pretty simple acc to me. D >>> F ) :(

WAbec didn't check if the entry is not there in the map 225417281ACjust after adding a check 225413613However it is not the intended behavior, can anyone confirm?

D isn't harder than F, you can divide all intervals and treat them like separate test cases basically so it becomes much easier

Ikr. The substring reversal thing was kind of a good observation I would say to apply in the merged intervals to avoid repetitions and it got framed into a really nice problem where pairs of positions were just getting swapped.

It may be possible but personal opinion I found F pretty standard. Like we need to do what exactly is told. (And regarding the division which is to be done by Prime Factorisation is also a pretty standard technique)

Yeah, but F is kind of weird in a sense where if you know basic number theory you will probably solve it and if you don't you are doomed

I don't know, but I have always assumed that map and unordered_map always return the default value for int(which is 0) when the key is not present, and I have never encountered this issue before, which is quite strange. In fact, my solution to F relies on this behaviour.

I agree D>>F

Accessing mpp[x] where x isn't in the map will return 0, but it also inserts x into the map so the other check (mpp.count(dn)) would then return true for values that shouldn't be in the map.

Got it.

definitely didn't create the same segment tree Q times on E :(

Does this relation always hold true? a&b=a+b-(a OR b) physics0523

(a XOR b) + 2*(a & b) = a+b is famous. Try to proove it from this.

actually I saw somewhere on the internet that (a XOR b)=(a OR b)- (a AND b) . So, on combining both equations ( I mean the other is which you have told) I got the equation which i have asked in first comment.

can we prove in C that we can make every number b/w (k*k+1)/2 and (n + n — k + 1)/2 ?

For example $$$n=10$$$ and $$$k=3$$$.

$$$\{1,2,3\} , \{1,2,4\}, \{1,2,5\},\dots,\{1,2,10\},\{1,3,10\},\dots,\{1,9,10\},\{2,9,10\},\dots,\{8,9,10\}$$$ generates every number between two bounds.

how this solution pass ? link

Maybe some optimization in the compiler. I tried to kill this but somehow it's fast enough.

That's why.

read this line again, "Note that the sum of n over all test cases may exceed 2e5"

You're right, my bad. This should be hackable for t = 1e4 and then n <= 2e5, k = n — 1 for all t. But not getting hacked for some reason.

You are right , this is a nice way to think of the sequences. Thanks ! (i wonder if we can prove it using formulae)

We can prove that it is possible to get any sum between the minimum possible and maximum possible sum.

hmm , can you share the proof if you have (or else i'll wait for editorial :D )

Induction, it will be in the editorial

Cool, thanks !

How would one go about proving this?

Induction

Too bad, my C incorrectly used O(k) algorithm, which should have caused TLE, in fact my friend made a mistake once for this reason and corrected it, but my commit somehow passed the test case and got hacked:(

Discovered logic of E without Binary Search might be useful

225421215

What is the purpose of writing such line in Problem C?

Note that the sum of n over all test cases may exceed 2⋅105I thought the convention is not to write this statement if it's true. Maybe I should disable the Dark mode to avoid missing the Bold text.

Anyway, Thanks for the contest.

It's because people often don't read that and assume that it's true, that's why it's bolded.

We also allowed that because some people don't know the formula for the sum of first $$$n$$$ numbers, and we allowed it so they can precalc it.

Silly of me to just come up with a solution for "C" using pick and not pick recursion. I need to follow Constraints. Can anyone explain the "C" here?

It can be proven that the answer is YES if $$$x$$$ is between the minimum and maximum possible sum.

you can make any number between range [k*(k + 1)/2, (n + n — k + 1)*k/2]

Do we get any points for successful hacks ?

Authors, where is systests for sum of n exceed 2 * 1e5 in task C? I made a stupid mistake because of speedforces and fast-reading of easy task. Why didnt you cover this obvious case? Please cover such tests in the next rounds.

Note that the sum of n over all test cases

may exceed2 * 1e5I read it as not exceed

We actually tested that case and most testers codes failed, so idk maybe you just made it optimized but not optimized enough?

My solution complexity is sum of k

No, it's $$$O(k \cdot t)$$$

k <= n

Yeah, but the sum of $$$n$$$ can exceed $$$2 \cdot 10^5$$$ and therefore the sum of $$$k$$$ can too.

I tried to hack O(n) solutions with more than 900ms runtime on Problem C but getting more unsuccessful hacks..

the compiler strongly optimizes problems such as C. There are O(k) solutions which passes also a maximal stress test.

Solutions were leaked during the contest and many people cheated. Requesting CF to filter them out and update the ranking accordingly.

Many People have same segment tree solutions on Problem E...

Yes. i hope they run the rating rollback thing and update it

Yeah, because it's one of the intended solutions?

yeah because it was available publicly before the contest (here gfg link) which is legal according to CF rules :)

you can also do prefix sum + binary search

Holeee newbies in comments using stuff like treaps, splay trees and idk what not and complaining. Like do people not think that perhaps this is too much? Why would you even learn all that at this level kek?

i fake it till i make it

only downvotes for you using alt account

nooooooooo pwease dont downvote :(. lol do it

Tbh I haven't even learn that so far lol

mala ga lomi

sija mi ko kristal na dejtoni

Video Editorial For problem A to F.

I think the questions belong to Div2

I can see how D would be done with trees. How would D be done without trees? Would appreciate a general explanation of the overall strategy.

1) we observe that the k segments are independent of each other so we can solve for each segment and then append them to get the full answer

2) we observe that to solve for one segment ,a range(a,b) in a query is always in the middle of that segment (because it is either from x to r-(x- l) or from l+(r-x) to x ) i.e we can say that each element is either mirrored about the center of the segment or not.

Now to solve this we can use Difference array to easily perform range updates of +1 to each element in range(a,b) (indicating that letter getting mirrored) .At the end we get the resulting array and for each A[i] that is odd we mirror that letter.

here is my python solution

ah, step 1 is what I was missing. thanks!

Solved problem 1878D - Reverse Madness during the contest in time $$$O\left(n \cdot q\right)$$$ by performing all operations by its definition here 225330103 and here 225334036 in

`889 ms`

UPDHere is non-hacked $$$O(n\cdot q)$$$ submission 225577099Petition to ban pragmas

Petition to all problemsetters to make sure unintended optimized $$$O(n^2)$$$ doesn't pass. Although this can be difficult if slower languages also need to pass.

Hacked!

If the TL was 2s, I think it will pass the systest...

Thanks!

Here is a small trick: I solved in $$$O(n \cdot q)$$$, then solved problem E, then solved problem F, then re-solved problem D in right asymptotic.

In ICPC-like format the first non-hacked solution is used by the system for determining the score. In codeforces-like format the last solution is used.

So, I still have my +1 score for problem D.

Do you want to hack mine $$$O(n^2)$$$ solution as well (it just uses Rust's regular

`reverse`

method of the slice)? 225437815Rust

`reverse`

is fast enough, because it's unhackable with my hack TC.I got same runtime for reverse in C++ here 225577099

About problem C I use loop to computa the series, i think it can't TL, but how can you hack me, please tell me why, thank you

Look at the constraints again...

Holy shit, it turns out "may exceed 2e5", not "does not" Interesting

Can someone share to me segment tree solution for E?

https://codeforces.com/contest/1878/submission/225372322

read this blog for implementation:

https://codeforces.com/blog/entry/18051

Thanks for the help!