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, Sexpert, MagentaCobra, AlperenT, satyam_343, Vladithur, polarity, fishy15, epicxtroll, 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 $$$25050010001500200025003250$$$.
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
which one are you talking about lmao this is the best
Olivia Rodrigo — deja vu
Car rides to Malibu
Strawberry ice cream
One spoon for two
And trading jackets
Laughing 'bout how small it looks on you
(Hahahaha, hahahaha, hahahaha)
Watching reruns of Glee
Being annoying
Singing in harmony
I bet she's bragging
To all her friends, saying you're so unique, hmm
So when you gonna tell her
That we did that, too?
She thinks it's special
But it's all reused
That was our place, I found it first
I made the jokes you tell to her when she's with you
Do you get déjà vu when she's with you?
Do you get déjà vu? (Ah), hmm
Do you get déjà vu, huh?
Do you call her
Almost say my name?
'Cause let's be honest
We kinda do sound the same
Another actress
I hate to think that I was just your type
I'll bet that she knows Billy Joel
'Cause you played her "Uptown Girl"
You're singing it together
Now I bet you even tell her
How you love her
In between the chorus and the verse (ooh) (I love you)
So when you gonna tell her
That we did that, too?
She thinks it's special
But it's all reused
That was the show we talked about
Played you the song she's singing now when she's with you
Do you get déjà vu when she's with you?
Do you get déjà vu? Oh
Do you get déjà vu?
Strawberry ice cream in Malibu
Don't act like we didn't do that shit, too
You're trading jackets like we used to do
(Yeah, everything is all reused)
Play her piano, but she doesn't know (oh, oh)
That I was the one who taught you Billy Joel (oh)
A different girl now, but there's nothing new
(I know you get déjà vu)
Calling you, and the search is a mystery
What a nice photo！
thanks,,,,,,
Why I start laughing?
C++
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 !!!
Thats why your upvotes are 69 at currently.
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
if he do then???????
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
Can somebody please tell me how to be a tester for contests
their will be no perfect rating in this round
yes bro you are right!
a
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 wellknown that all problems are wellknown 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 :)
there will be no perfect rating in this round
My idea
You should start with B
GOOD LUCK
Mysterious score distribution!!
thank god speedforces
This is my first time,I'm scard
this round is much intresting
8 downvotes. Does this mean Saarang roasted you?
What's polygon?
I will try to make at least 3 problems today :)
Python is the best programming language in the world!
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
C is interactive ?
Will have to flush the output buffer for the interactive problem
I really love 250 problems in the contest :)) thanks for that :))
Finally my exam is over. Hopefully I will able to solve 2 problem in this contest.
hope i am lucky this time.
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?
Hmmmmmmmm, why not?
How to attempt D question?
lmao:)))
if the problem is so hard that i can't solve then????
Looking forward to a great contest
Good luck everyone.
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 .
YESSS, I will be newbie again!!!
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
Yup . Just output any no of your choice which is in array. lol
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.
Try for n>10 and observe number of zeros
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 >= n2 zeroes (for n2 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.
Found my stupid little typo, https://codeforces.com/contest/1698/submission/162144366
in n==3 case, i missed one "=" sign and thats what caused WA. corrected it and got accepted
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 miss be 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 miss if answer <= x and if answer > x
Explain 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:
Yeah, 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 nonzero numbers must be very small.
3sumclosed 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.
What in the name of lord was the third question. GODDAMNIT!!
Awesome question but got stuck in C ..Anyone can explain me plzz ?
for n<=4 brute force and for n>4 if number of zeroes>=(n1) its a yes else if number of zeroes=n2 and rest 2 numbers add to zero then yes, else no!
ConstructiveForces
C is pretty strange :)
Yea 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 c
sort the array & see if last three are positive or first three are negative , if anyone above is true then answer is NO . else both the cases are failed means there is zero in between repeatingly so take first three element & last three element & apply brute force
i do bruteforce but wyhout check the 3firsts nembers and 3lasts nembers
How to solve D?
can 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 jth 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 i1 elements of D, then we can choose a place for d[i] by z(i1) 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] — (i1)) * ... * (e[n] — (n1)) (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
wow took me an hour and a half just to solve A lol
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.
Hey could you please help me find the failing test case in 162156403 for yesterday's C problem.
Take a look at Ticket 14998 from CF Stress for a counter example.
Ok I need to know, what was déjà vu in 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?
3SUM 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/twosum/
Yes, but context was about recent div4 because Flamestorm was one of the setters, dude
My bad, I did not know
no problems, congrats with performing great today :)
We have too much dignity to use references to Leetcode problems.
Thank you!
a is 3SUMclosed 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.
For Problem C I tried to observe only one pattern sum of all numbers must be zero. I couldn't further break it down.
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
whats wrong in this code? https://codeforces.com/contest/1698/submission/162151736 in problem c.

it works fine. can you give the input example?
got it thanks
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 nonzero numbers(saym
), 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.
same happened w me, there are many testcases
So do I
3a a a a
Replace a with a, this isn't a new case.
More tricky than interesting... shortcuts on A, B, C made my completely moronic solveofsomethingtrivialthatisn'ttheproblem for D seem way too plausible. Even had the usual binary search thought and how the constraints fit... but was already locked in on the stupid. OH well.
A smarter me would retire until end of daylight savings... even if I successfully carve out time, I still rush in anticipation of getting interrupted... results have been less than comical.
Why does the presence of this line give idleness limit exceeded?
Run your program with and without it and you will see
I wish I could run but the wait for the system test is killing me.
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/
Thanks. Understood it now. I thought adding "fflush(stdout)" will flush the output but it didn't. Is it because of "\n"?
because they are not the same stream. use cout.flush() instead or remove the iosbasesync with stdio null line... this line is responsible for temporal aligning of c and cpp buffers
for ref. https://stackoverflow.com/a/41777103/
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.
he he
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.
As xor of whole array is zero, you can pick any element to be the xor of rest other elements. So it can be any element, not just element 0
it is not the first element.. it is any element lol
say XOR of n1 is $$$a$$$, then XOR'ing the XOR of n1 elements with $$$a$$$ means $$$a\oplus a=0$$$. Now, when you are given n elements, you can literally pick any element say "k" and the XOR sum of the remaining n1 elements is guaranteed to be "k" because $$$x\oplus y=0$$$ iff $$$x=y$$$
I feel this was a perfect contest. Also problem A feels like a troll problem.
How to solve b TT
If k==1, then you can increase alternate elements to any height except 1st and last element. So answer = (n2 + 1)/2
else: if k>1 then if you apply operation on any range, then it would not be useful as it will also increase the count of adjcent element. So the answer is the tall piles without any operation.
oh i got it now thank you very much <333
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.
Okk thanks got it now.
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.
there is a hint in the editorial, but imo it kinda sucks.
Sort B based on the order of A
Iterate over 1 to N. Where can each of them go in the (customsorted) array B?
Can anyone explain why I should use Bsearch in problem D? TIA
First of all notice the constraints. n is upto 10^4 and maximum no. of operations is 15. Observing this, it is clear that the solution has to be in log(n) and hence binary search is the best approach (as far as I thought of it).
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.
You are right, I did not read the statement well, thank you.
See the announcement during the round.
You are right, I did not read the statement well, thanks
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.
UPD2. 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?
I did, but announcement wasn't for me, i knew that it should be true for every i,j,k index
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
Why does this contest is unratted in my profile ?
my solution for problem d is giving different output's on my pc and on online compiler (https://codeforces.com/contest/1698/submission/162170632)
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
The round teach me to be more carefully,i must be stronger after some trainings
So many people got many wrong answers to problem C. The main issue with everyone was that they thought, they could solve it by just observing some test cases. I, myself got 6 WA in C. Hope I will do better in upcoming rounds.
C made me feel so dumb with 10 wa
预警糖
it's so hard being a rookie.
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
Codeforces Global Round 21(Question C)
Can anyone please please help me...like where I'm wrong in this code? 162330458
I have been trying to resolve it. But it's been two days and I am not able to find any clue, any help. Please help!
Take a look at Ticket 14997 from CF Stress for a counter example.
Thanks bro..Finally i solved it.
deja. Vu? Hmm something familiar!
I have been using a template for this contest which I found from an opensource, 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 Closure
The skipped solutions have the same implementation as the problem was pretty straightforward in this case you can see hmm
Hi, my contest has been skipped for code similarity at 1698B  Rising Sand. After I got the message i looked at the other guy's code and i saw that they are similar 162137682 162082266, but it was an easy problem with straightforward solution. I demand to get back my contest result back. flamestorm ScarletS MikeMirzayanov errorgorn
is it rated?