Hi Codeforces!

ScarletS and I are glad to invite you to Codeforces Round 803 (Div. 2) which will be held on Jun/28/2022 17:35 (Moscow time). **The round will be rated for participants with rating lower than 2100**. The theme of the round will be *déjà vu*! (Wait, wasn't that already a theme before?)

Thanks to the people who made this round possible:

- errorgorn, for his fantastic coordination of the round;
- MikeMirzayanov, for creating the amazing Codeforces and Polygon platforms;
- KAN, for translation of the statements into Russian;
- antontrygubO_o, AmShZ, Ari, MagentaCobra, AlperenT, satyam343, Vladithur, phattd, fishy15, tenth, Surprise_Me, jampm, Yangster, Il9, ak2006, FionnKimberOShea, Codula, and bakekaga for testing the round, catching any mistakes and providing lots of valuable feedback!

Thanks to NEAR for supporting this round, details can be found in this post.

You will have **135 minutes** to work on (and solve!) **7 problems**. **At most one of the problems will be interactive.** Make sure to read this blog and familiarize yourself with these types of problems before the round!

The scoring distribution is $$$250-500-1000-1500-2000-2500-3250$$$.

Good luck, and see you on the scoreboard!

**UPD:** Editorial is out!

déjà vu ? I've just been in this place before...

(Higher on the street)

And I know it's my time to go

Calling you, and the search is a mystery

What a nice photo！

nice photo

As a problemsetter, each upvote on this comment equals one time I'll roast saarang

Nice but who asked

I and the entire citizen of botswana asked !!!

mine was 145th one excited to know how you roasted :)

happily you got >=0 upvotes, otherwise saarang would roast you lol

Saarang does not have the power to roast me

I just hope I can perform incredibly and get a Candidate Master...

Why do I feel like I've seen this theme before...

As a tester, I’ve been told I get free internet points if I comment

As a tester, I can tell you this round is fire! yall should try it :)

As a tester I can tell problemsetters and coordinators have tried their best to keep the problemset as good as possible.

I Hope you guys enjoy it.

"déjà vu", hmmm, something familiar

Teach me the ways flame :orz:

As a tester, I can assure you really good quality problems. The contest in worth spending time. All the setters and testers have put a lot of work and effort. Good luck everyone !!

Hoping I don't feel déjà vu while seeing my rating changes after this contest

but you had 1725...

I'm referring to the (-109) after said 1725 lol

pheww

On the contest page, duration is shown as 2hrs. Please correct it. flamestorm

Why are there at most 1 interactive problem and not 998244352

I hate Interactive Problems

ok but i don't remember asking it

Me too

Déjà vu theme is a very convenient excuse in case if some of the problems turn out to be well known

We did this intentionally, as it is well-known that all problems are well-known in China

Score distribution is 250 for problem A, means problem A's difficulty level below 800?

It's probably gonna be easy, but I don't think it will be rated less than 800. I haven't seen any problems rated below that even if they are very easy

I think E will be interactive

upd.: happily, it wasn't

As a tester, I can snitch that the discord server icon is a picture of an anime girl.

Not just any anime girl.

Excited!

i am too!

Good luck everyone :)

thank god speedforces

This is my first time,I'm scard

this round is much intresting

8 downvotes. Does this mean Saarang roasted you?

:)

Until you become pupil.

That's funny because I stopped using python for contests after I got out of pupil.

I got to orange in Python but even I gave in eventually

Finally my exam is over. Hopefully I will able to solve 2 problem in this contest.

it's morbing time

hussenberg you seem kinda sus ngl

nah I ain't,I'm just drunk

you sussy baka

Lol, you sound like one of my friends Btw do you have discord or smth?

Maybe he's Hank?

How to attempt D question?

whyl i can't register?

yet, another speedforces round?

Competitive programming = speed + knowledge

I shocked for a sec after seeing 4th problem :)

Took me a long time to debug, though got the approach early.

i didn't attempted *_*, but after seeing so many submissions it's seems easy .

Problem A is a very greedy !!

Does not have any idea on F. Expect fast editorial.

I would say the same for E.

Problem A was a great scam :3

Wanna problem C hint after the contest :(

seem like its hard for me :(

i am hard stuck at C for the entire round. Need to learn how to move on to D.

When you have more than 2 negative or more than 2 positive integers, the answer is NO (think why). Now you can save min(cnt0, 3) zeros and check the condition on array of size less than 10.

I did the same thing, my logic was, answer is YES if there are >= n-2 zeroes (for n-2 case, sum of non zero ones should be zero). Other than that, only for n=3 and 4 answer is possible otherwise no. Can you give a counter example for this logic?

I don't think that only for n = 3 and n = 4 the answer is possible.

-2 -2 -2 you can check this by yourself in submission details.

lets say my array is [1, 2, 3, 6], will be the answer be yes or no ?

No, because 2+3+6=11 and 11 is not one of the elements of the given array

I hate this round

I hate this round!!!

What I did during the round. 1% of the time solving A and B - 99% of the time trying to figure out why C kept on failing.

What was the idea behind D? I know it's a binary search, but non of my ideas on how to exclude segments were correct.

Probably it has to do something with a number of numbers that are in range (l, r) for a particular segment, but I couldn't elaborate this idea.

Query on segments like [1, x].

Let

missbe count of integers between 1 and x, such that they are not present in query result.For even and odd segment lengths, think about what should be the parity of

missif answer <= x and if answer > xExplain it further, please, I have so many thoughts on D now and can hardly imagine anything :)

My solution:

after each ask count numbers that potentially could be 'x'

let it be cnt

if cnt is odd => 'x' is in our half, otherwise — in second half

continue binary search until l != r

If you don't mind — link your solution, please. So I'll exactly see what is what.

Here it is: 162142911

but it is a bit messy so:

SolutionYeah, I see, thanks a lot. Was just a few steps away from observing that

thats great, wish you progress :)

Appreciate that!

binary search in [l, r], set k = (l + r) / 2, then check [l, k], if \sum_{i=l}^{k}[l<=a_i<=k] is odd(number of exchanges in [l, k] modulo 2 equal 1), answer will in [l, k], otherwise [k + 1, r]

Thank you!

-500 incoming

How to solve problem C?

If 3 positive or 3 negative, answer is not possible.

Otherwise, brute force.

I put that logic...still failed..can i show you the code now that the contest has ended?

sorry i didn't know there was a spoiler option. :(

put it in spoiler

Hint:Notice that the number of non-zero numbers must be very small.

3sum-closed array has at most 2 negative numbers, and at most 2 positive numbers. Then reduce zeros to some small value, so we can iterate all i, j, k and check all sums.

C is pretty strange :)

I hope it will passYea should pass, why not

Umm... we can never have more than 2 positive/negative integers?? So if the count of odd or neg numbers is >2 then the answer will be "NO"

His/her brute force will catch it though :)

Yeah, I mean ofc it will pass, I was just mentioning why his solution passed (^^ゞ

I don't know C++ but it looks like he's applying Brute force only if size of array is less than 100 or else he is printing NO ig

Harder Div2, I thought I was accidentally solving some D1Bs and D1Cs during the contest...

wandering here after solving a,b,c :P

How to solve D?

Hintcan u point mistake in my code. Dude I did the same thing but showling TLE

How to solve E lol

Hi! It's my first time for me solving E, i'm very happy, so lemme write my solution;)

Let's notice that if we are given a certain permutation b we can only change a to b when for each element a[i] if j is the position we should move a[i] to, b[j] <= a[i] + s:

If the condition is not true (for example for a[i], if a[i] should be on j-th place) — then we can't move a[i] to its needed place, because if we can, then we do it on move <=i therefore other element we swap (a[j]) has a difference with a[i] no more than s, but a[j] > a[i] + s (contradiction)

If the condition is true for each a[i], notice that we can consequently move a[i] to its needed position on a[i]-th move (legally).

So let's find all permutations which suit the condition:

Firstly, for each a[i] if b[i] is already not -1, then b[i] must be no more than a[i] + s (condition 1), otherwise answer is 0 (same reasons as in 2nd paragraph)

Assume 1st condition is true: lets say that we have c[1] < c[2] < ... < c[x] — elements of array a, under theis indexes in array B stand -1s. And we have d[1] < d[2] ... < d[x] — elements we have to insert in B on places of -1s.

After substracting s from each d[i], a suitable permutation will be when for every d[j] standing under element Y from A, y>=d[j]. (same reasons as in 2nd paragraph)

So for each d[i] we can find under how much elements of C it can stand (when I say stand under, i mean that they have same index, it's just my visualisation that array B stands under array A) using binary search Let's notice that if b[j] > b[i], on every position we can put b[j], we can also put b[i]. So let's choose a suitable permutation consequently choosing a place for d[1], then for d[2], and so on. if we can place d[i] onto z places, then if we already placed first i-1 elements of D, then we can choose a place for d[i] by z-(i-1) variants.

Let's notice that if we can put d[i] on z<i places, then we can place first i elements of D on z<i places (contradiction, so answer is 0) (condition 2)

In the other case, if d[i] can be put on e[i] places, answer is (e[1]-0) * (e[2] — 1) * ... * (e[i] — (i-1)) * ... * (e[n] — (n-1)) (mod 998244353).

Sorry for my bad english, of if you didn't understand something) i hope you will understand me))

With your explanation and code,I get it eventually :) Thank you so much!!

You are welcome! I'm glad somebody understood me;))

interactive = binary search

I learned three lessons from this contest

Read the problems carefully !

Read the problems carefully !

Read the problems carefully !

I misread the problem C, I thought one fulfilling pair was enough.

Me too. I misread problem C until the problem setter made the announcement. And, I misread problem E again. I solved problem E immediately after the contest.

Ok I need to know, what was

déjà vuin this contest?I think that the problems had classic prototypes like:

A — xoring to find the unique number

C — 2Sum or 3Sum problem

F — reversing an array via Implicit Treap

I am not sure though whether knowing about these prototypes can help you solve today's problems faster :)

Oh ok, I see. Thanks

come again?

3-SUM was reference to recent div4, PermutationForces was reference to one of recent problems too (don't remember the contest), pretty much sure all other problem names you could've meet before.

3Sum and 2Sum are old problems: https://leetcode.com/problems/3sum/, https://leetcode.com/problems/two-sum/

Yes, but context was about recent div4

because Flamestorm was one of the setters, dudeMy bad, I did not know

no problems, congrats with performing great today :)

We have too much dignity to use references to Leetcode problems.

a is 3SUM-closed if for

`all integers`

..... anyone missed the all integer part like me.. That's created the problem more hard :'( even is that possible with the same constraints ?What else would it be? For even one such $$$i, j, k$$$?

how u find there have at least one i,j,k as if a[i]+a[j]+a[k] also exist in array. ?

one hour is wasted on that thing, I really gotta read the problem statement carefully the next time.

I solve F while using only 2n operations. And I don't have any idea why the limit is n^2.

it's very sad that your rating is 2100, not 2099

I actually use sjcsjcsjc for Div1 contest.

2100 isn't my real rating lol.

(Sorry for violating the rules :( )

ded after looking at ur real rating.

I waste too much time because of misreading the statement of E so that I didn't have time thinking about G.

Anyway, the problems are very impressive and a bit more difficult than normal Div2. Really like this contest.

It would be nice if someone could look at my submission for the interactive problem (Java). It was my first interactive problem and I think I did something wrong with the queries / flushing, my submission didn't do anything (my testing did work, think the solution was correct). 162145333

I liked problem D. Thanks to the authors for the contest.

Good problem..but number of queries was a direct hint to binary search..If number of queries were hidden,it would have been a even better problem.

If they hid number of queries, one would just get WA without knowing why?

For

`C`

, there can be atmost 4 non-zero numbers(say`m`

), for the given condition to satisfy.For,

`m=4`

, there can be only 2 forms of numbers — a,-a,b,-b and 3a,a,-a,-a. Can there be any other kind of arrangement?Thanks in advance :')

Failed systest because I didn't see the 3a, a, -a, -a case. :(

:'(

I was taking different cases for proving that there isn't any arrangement of 5 numbers possible and stumbled upon this case. Although, I skipped its implementation and applied a general implementation for

`n=4`

. Implementing different cases separately wasn't necessaryYea I didn't include the m=4 option at first and WA'd, then by messing around, found the -b, -a, a, b case and just submitted it and passed pretests so I didn't bother looking at it again.

So do I

-3a -a a a

Replace a with -a, this isn't a new case.

Why does the presence of this line give idleness limit exceeded?

Run your program with and without it and you will see

It shouldn't, however if you defined "endl" as "\n" it will because \n does not flush the stream and you were explicitly asked to flush your streams.

however, if you remove that def, the streams are flushed automatically https://stackoverflow.com/a/31165481/

the problem statements robbed me (" _ ")

As a tester, I'm very glad to participate this contest,which tell me i am lacking for training

Problem D:

Binary Search: Bro.

Interactive Problem: Yea, bro.

Binary Search: Close your eyes, bro.

Interactive Problem: Ok, bro.

Binary Search: What do you see, bro?

Interactive Problem: I see you, bro.

Binary Search: Broo!!

Interactive Problem: Bro.

For A why is it always first element? Although I used brute force after long time by seeing the constraints

You can print any of the elements

I think it can be any element

WHY???!!!

Let the xor of original array = $$$x$$$. After adding $$$x$$$, xor of the new array = $$$0$$$. Therefore for all inputs the xor of the array equals $$$0$$$.

So, now you want to find any $$$x$$$ such that $$$x$$$ = [xor of the rest of the array]. This is true for any $$$x$$$ present in the array because $$$x$$$ xor the rest of the array is $$$0$$$. Hope that helps.

I feel this was a perfect contest. Also problem A feels like a troll problem.

I spent even more time on B or C than D...

And I get many "WA 2"s

For anyone wondering why they got TLE on test 13 of problem C, I suggest reading this and noting that

`A[0] = 107897`

— commiserations if this is you and you've never heard of this phenomenon before; I guess you won't make that mistake again.Can you elaborate a lil?

I don't know specifically what's changed from GCC 17 to GCC 20, but I can make an educated guess. From the blog I quote:

`It turns out the right prime depends on the compiler version: for gcc 6 or earlier, 126271 does the job, and for gcc 7 or later, 107897 will work. Run the code below in Custom Invocation and see what output you get.`

I suspect that the hash function for unordered map / unordered set has changed from GCC 17 to GCC 20, and now in order to hack it a different prime is required.

I love problem D and E, they're quite nice. I enjoy the feeling of finding an interesting conclusion and solve the problem without a long code. However, I think B is not so good because of the weak samples. A k=1 sample can really help a lot. Anyway, love this round very much!

My code for 3rd problem got accepted in C++20 but shows tle for the same code in c++17 I lost nearly 18 points due to this. What should I do?

dont use unordered map

Any hint for E? Spent more than an hour. Don't wanna ruin it by directly reading the solution.

Hint 1Sort B based on the order of A

Hint 2Iterate over 1 to N. Where can each of them go in the (custom-sorted) array B?

Can anyone tell me why the testcase: n = 6 ar = [1,2,3,4,5,6] the answer is NO in the problem C? if 1 + 2 + 3 == 6

Because (for example) 4 + 5 + 6 = 15, and 15 is not in the array.

See the announcement during the round.

If problem C change the statement from "all (i,j,k) pairs must satisfy" to "one (i,j,k) is enough". What is the most optimal time complexity? Can this problems solve by O(n), O(nlgn) or O(n^2)?

It's possible to solve it in $$$\mathcal{O}(n ^ 2 \log n)$$$ with std::map or $$$\mathcal{O}(n ^ 2)$$$ with std::unordered_map.

Iterate from the end. In the map $$$cnt$$$ for each possible $$$s$$$ store the number of pairs $$$(j, k)$$$ such that $$$j < k$$$, $$$a_j + a_k = s$$$ and $$$j > i$$$ where $$$i$$$ is the current position. Then, bruteforce $$$l$$$. If $$$cnt_{a_l - a_i} > 0$$$, print YES. If we haven't found such pair print NO.

UPD1.

CodeUPD2. You can use bitset of size $$$2 \cdot 10^9$$$ instead of unordered_map and get better constant factor.

Has anyone solved C just after the announcement during the contest?

the third problems was wrong and how it impossible with 2e5 and t <= 1000 ??

Did you notice in last line of input format: "It is guaranteed that the sum of n across all test cases does not exceed 2*10^5" Its common in codeforces

did you check testcases in problem C? there is t equal to 1, if t will be 1000 and each n will be equal 2e5 i sure that all solutions will be TLE)))

If t will be 1000 and all n be equal 2e5 then sum of n over all test cases will be 2e8 which is not possible due to constraints

worst contest i have ever entered because the third problem's solution not logical

Why do you think the solution is wrong / not logical?

Wow, what a great round! I really enjoyed the problems, especially E))

It's my first time solving div2 E (and getting a master performance)! I'm so happy I spent my time on it, trying to think of the solution, which in fact is really beautiful

Really a great contest. Statements are obvious and clear. Thanks all writers and testers.

To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!

Pretests for C are so weak. How can this code pass pretests ?

As a beginner, i'm glad to take more Contests

Look at this guy's code. He is probably using his crush's name(Ayushi) as variable name. XD.

https://codeforces.com/contest/1698/submission/162129130

C made me feel so dumb with 10 wa

My rank after system testing increased by 1000. This is unbelievable and I'm so happy about that.

problem E, why the same code in GNU C++17 got tle, in Clang++20 Diagnostics got ac??? ac: https://codeforces.com/contest/1698/submission/162327659 tle: https://codeforces.com/contest/1698/submission/162327699

deja. Vu? Hmm something familiar!

I have been using a template for this contest which I found from an open-source, a few days back, and I believe that many other people might be using that code template, and thus it might have been plagiarised, and I confirm that the code for this problem was done completely by me. Please look into this matter. If required I am also ready to share the template that I used. 162153992 1698C - 3SUM-замыкание

The skipped solutions have the same implementation as the problem was pretty straightforward in this case you can see hmm