Good Evening Codeforces! ^_^
This round is unrated; please read this to know why.
I invite you to participate in Codeforces Round #682 (Div.2) taking place on Nov/13/2020 17:35 (Moscow time). The round, authored by Anti-Light and me, is rated for users rated less than 2100, while other users can participate non-competitively.
The round features six problems, and you have 2 hours to solve them. There may, or may not, be an interactive problem; regardless, you should know how to deal with them.
I would, now, like to thank–
- antontrygubO_o for coordination.
- AwakeAnay and AsleepAdhyyan for helping me solve one of the problems.
- BRCode for making 3b1b-style video editorials of the problems!
- knightron00 for helping with preparation.
- Devil, Dragnoid99, far_from_NOOB, IaMaNanBord, Osama_Alkhodairy, prabowo, taran_1407, Tarrus, Tathagat_shah, TheOneYouWant, Utkarsh.25dec, Vivek1998299, _Aaryan_, aryanc403, dorijanlendvaj, coderz189, hugopm, kshitij_sodani, ltc.groverkss, nishkarsh, Roham, shash42, socho, talibmohd, thenymphsofdelphi, Monogon, Ari, 300iq, AmShZ, errorgorn, tejas10p, solvemproblr, DumbbAlgo, aujasvit_datta, TeaTime, stack_overflows, manik.jain, namanbansal013, Gur27, and DarkCraftPlayz for testing!
- MikeMirzayanov for Codeforces and Polygon platforms– Polygon is still remarkable!
We will announce the scoring distribution shortly. The scoring distribution is 500–750–1250–1750–2250-3000.
Good luck, and stay safe!
UPD: Editorial
For students in high school or below—
Participants who are currently in high school or below are eligible to win prizes — 25 USD gift cards to 5 random participants who solve at least 3 problems. Prizes are sponsored by Athena Education and are NOT related to Codeforces. To be eligible, please fill this form (it will be closed after the round ends). If you're interested in participating in other technical events, such as Machine Learning and Computational Linguistics, please head over to exunclan.com.
Registered participants on round or those who filled the form?
Those who filled the form; I have edited the blog to reflect this. Thank you!
Hmm, it would have made sense if there were cash prizes for top rankers + random people, or only top rankers. But to have prizes only for random people is a bit weird.
Expecting a Good Problem Set. Because it's SleepyShashwat
Omg Indian round! So excited
Hope you weren't sleepy while writing problem statements.
He lost a lot of sleep due to problem statements, that's why he's sleepy now.
.
Seems like first time we are seeing Monogon loosing contribution
I'll have to find a new source of dopamine now
Seems like you already found one, But sadly I have to loose some of my contributions because of above comment. Though I don't care about it(but who doesn't like green++).
Edit:Also I can see realnimish gaining +47 because of my username, thats interesting. I think people should atleast appreciate my username, if they don't like the comments XD.
Its a trap
Its a trap
You just see he will reply to the comments like yours and get 1k upvotes.
intresting problems.
such a boy !
I'm currently in high school but over 2100, so this round will be unrated for me. Will I still be eligible for any prizes?
Yeah, you are.
One prize gone
And here I am , Btech Final year and still switching between green and cyan.
Cyan and Green? Let just leave the conversation
Here I am, Btech 3rd year and can't even climb up to green.
As a tester these problems were very interesting!
yea codforces should provide more contests :,)
[Your text to link here...](
)
I am telling you that cute little face had no idea that round would be unrated.. Though had fun first 10 minutes of rounds..
Finally!
Wow that's a whole lot of testers!
Now I am more excited about the 3b1b-style video editorials!!
lol, 1 week without contest,
It was difficult, MikeMirzayanov
please we request don't take 10 days gap for codeforces contest
These 10 days made me realise the plight of div 1 users. Guys hats off to your patience (all div 1 users)
Is that the polish eagle? Makise_Kurisu
No, it is a phoenix ig
yo 3b1b type videos? that's sick
Finally a contest now :)
It seems that there are much more people testing for the contest. So I think this Div.2 would be an excellent one :)
Oh no, it became an unrated contest becuase of B :-(
I think I would like to delete my comment :-(
Picture below shows how I feel when I saw the announcement that the contest is unrated...
Finally something to cheer about
Waited)
)
Wow, there is Anti-Light in writers too!!
I guess this round is going to be awesome.
Happy Diwali :)
They say it's an Indian contest but it isn't just an Indian contest, it's an Indian_Iranian contest. Because Anti-Light is Iranian. So... it means it's gonna be so good.
I didn't finish the form which to prove i'm a high school student. Could I finish it now?
Happy Diwali Everyone !!
problems are very sexy 10/10 would bang
Is it rated?
is rated for users rated less than 2100, while other users can participate non-competitively.
so, Yes!
Update: Not rated D:
no(
Nope :(
happy diwali to everyone out there
this diwali i pray to god so that your code gets compiled and accepted at one go(mine too :) ).
happy diwali happy coding
Every body holds his hat XD
registered already but showing need to register to submit
queue?
I submitted a source code before they changed N and T, and got WA for no reason, very cool.
what's going on. is that really unrated?
I don't get it
What was wrong with B?
same here, i also saw the correct constraints after submitting A in 2 minutes(they said constraints were wrong for 10 minutes)
Got a round after so many days and that too became unrated :(
felt same. :(
Friday the 13th
When I will tell my granchildren that we had rated contests on CodeForces, I bet they wouldn't believe me.
After waiting for so many days, we got unrated round... :-(
Why unrated? I was really fast in ABC, so sad :/
So sad that this is unrated! It's first time I pass the D
The problems are really good!
It's a pity that so many testers and no one caught the issue with constraints on B :(
What was the issue? I didn't get it !! Were the constraints low or high?
It's too low, so the chance to get RTE is high
I believe the actual constraints were initially 2e5, but displayed as 1000-2000, then midcontest, the constraints were changed, and then again constraints were reverted back with updated TCs.
Picture with updated constraints
Too many chefs spoils the food
Agree the problems were quite good could have been a great round.
I don't want to say too much, but this isn't the fault of testers.
It is neither author's fault nor testers'. I guess it's contestants' fault that they couldn't guess the correct Constraints.
How about let's try to understand the situation better instead of making pointless sarcastic statements that no one actually implied.
There are more people involved in contest preparation than just author and tester. Several times accidents have happened because things are changed (and sometimes, need to be changed) at last minute, when most testers have already completed their job.
And often in real life, taking the blame isn't as easy as "it is person X's fault". There are often cases where something is shitty but no one actually really did anything wrong. Of course something has to change but it isn't as simple.
Okay, sorry for that but if things are changed at the last minute, then it is better is postpone the contest and have it tested again. It's better for everyone.
don't get me wrong but if the above comment was by Monogon you must have laughed and upvoted too.
Maybe they don't even know if the constraints are right or not, so it is not appropriate to put the responsibility on the testers without thinking about it, I think.
You know . when you make round unrated half of participants are happy and half not !. im in unhappy group . also when the reason of that is just a bit change in limits!!!!
when u finally get <2k rank but round becomes unrated :(
Luckily I didn't use array with constant space in B
40 testers and noone used
assertwhile testing to check the constraints??? Seriously what did all these testers do? Felling sad for the authors :(Don't you know, testers job is to ask for contributions?
Actually, testers could not get any contribution.
It's writer's job to add validator and validator tests. And coordinator's job to check if the author did it.
I know, I was involved in preparing and testing many contests (Not Codeforces rounds). Usually while testing
assertshould added every where, to check the constraints and all other conditions.Very disappointing. 3 questions inside 25 mins and on track for CM status, and then it's unrated because the constraints were wrong.
I sympathise with the writers and am grateful for the effort that is put in. How did the testers not pick this up?
What was the mistake(in constraints) in B ?
The correct constraint is $$$2 \leq n \leq 1000$$$, but at the beginning of the contest it was $$$2 \leq n \leq 2 \times 10^5$$$. Now the constraints have been fixed.
I think it is the other way. The tests where with arrays of size up to 2e5, but the statement stated n<=1000. Then they changed the statement, then the tests, then the statement again to be like it first was.
I am not sure what the testers are supposed to do but confirming the constraints seems like one of the first things to do. Anyways, the problems were nice. Also, I think there should be a gap between different tests in sample. Makes it a lot easier to read.
.
There are still prizes so please don't discuss.
No, you can't
It's a shame the round is unrated, the problems are quite beautiful. The issue with constraints on B was not the fault of authors, so please don't downvote the blog out of anger.
ok,We will downvote your comments from now on
Downvote me for being supportive of the setters who had nothing to do with the cause of it being unrated? Okay, then I'm proud of those downvotes
Ok I had some slightly bad information at the time I made my comment, but I still stand that people shouldn't downvote the announcement or comments before understanding how the error happened. Still just wait for an explanation of what went wrong.
I don't think it's a wise move ...
I know you're angry for the contest, yes, we are all disappointed, but no matter how the contest is, it's not the fault of these users who write their comment, I think. So it may be a better choice to delete what you say just now.
No offense to anyone.
Feeling Sad for SleepyShashwat !!! Problem set were really good !!
(
)
This is the first time i solved a problem with in 60 seconds i got 500 points but sadly the contest became unrated :(
Even though it's unrated, don't discuss the problems, please, before the end of the contest. Writer is still going to give prizes
One request to codeforces if round is unrated please use bold letters so we don't get a blow after a while
Div 2 people should not be allowed to complain about contest frequency.
It's a joke mate
[Deleted]
B positive
The tasks were really very interesting.
When you solve 3 problems in 12 mins finally, after consecutive blows in previous contests, and the entire universe conspires to screw your rating!
hahahaha....reminds me of SRK's dialogue from Om Shanti OM !!
to bad ;)
Damn I couldn't get C but solved D and climbed to rank 18 for a moment. And now I am like bruh
Actually,B doesn't really need an array.
Thank you. I love Codeforces!
If you got the idea of problem B, it didn't matter the constraints. And the notification of the correction was done with plenty of time to review the problem for any player. I don't think the effect to the score would be stronger than what happens when hidden tests fail at the end of the round after pretests passed. In my opinion, the round shouldn't be unrated...
I can feel that feelings, guy.
Hold on for the contest on Sunday!
How did you solve problem C? Can you explain your approach?
explaned this here
came to read comment section just to be sure that It's unrated.
I was supposed to lose 73 points... and then the round became unrated.
Anyways, I still think it's a pity that the round is unrated because problem B was nice (even though I couldn't solve it). Based on comments, the remaining problems were also nice.
well i think i found solution to C but its way too hard for C and takes too long to code ... D was really easy for me on the other hand maybe im a potato :/
C is easy: You just have to make the parity of a[i][j] the same as i + j.
yeah i found it rn lol glad its unrated
Well, you could make some elements even, and some elements odd. After actions your matrix mod 2 should look like:
So the algorithm is:
Today maybe it was my best performance , and it got unrated .In the next contest it will be rated and I will get a minus 50. Cause that's life.
But it'll not change the fact that it is your best performance today isnt. Don't put a number tag on everything , life will be beautiful.
what is wrong with this idea for $$$D -$$$ If n is odd $$$or$$$ (n is even and there is no odd frequency element) then $$$YES$$$ else $$$NO$$$
If all elements xor =0, then n is even will still be possible
It should be : if n is odd or (n is even and the xor of all the elements is 0) then Yes else No !
Try this testcase: 4
4 1 7 2 Answer is: YES
1
1 2 3 because: 4 XOR 1 XOR 7 = 2
What is wrong with my code(problem D) https://codeforces.net/contest/1438/submission/98320619
Dear division 1, the short interaction between you and me was nice. Now, we have to part away.
dont worry its unrated xD
Now, I'm out of 1700 in an unrated round where many participants left the contest. I'm raging even more now.
.
for each i and j, ensure that inp[i][j] + i + j is even (or odd). then adjacent numbers will have opposite parity, making sure that adjacent numbers are different.
Try to arrange elements like ,
where 0 represent an even number and 1 represent an odd number. Of course you can always change the parity of a number by adding 1 to it.
I have seen that most of the people have done it by using dfs also.
Well it was Friday the 13th. Coincidence? I think not :)
Can someone explain how to solve problem C?
https://github.com/actium/cf/blob/master/1400/30/1438c.cpp
.
3blue1brown styled Video Editorials:
Problems A+B: https://www.youtube.com/watch?v=Z0JKnlmhVOc
Problem C: https://www.youtube.com/watch?v=A3GVI-nxjLM
Problem D: https://www.youtube.com/watch?v=e1TylJJr6Bw
Problem E: https://www.youtube.com/watch?v=wR_qg1XwAg0
Problem F: https://www.youtube.com/watch?v=KC6S5txBsdE
Awesome explainations man! I really hope you continue doing them for other rounds.
looks like i supercomplicated B and C. :(
Really nice and quick realisation! Do you have a public repo where the code for the videos is published?
did you also overcomplicated solution for B or are you normal?
expected solution was if all elements are distict print "NO" else "YES".
.
So in D, I constructed solution for odd n and couldn't get the x-or = 0 thing for even n, foolishness 100. Just got it now.
for n-odd i think the solution is xor between all numbers and that's all. So you just have to print 1,2,3 1,4,5 .. 1,n-1,n for n-even i think you don't have solution if : all numbers have the same bit 1 or xor between all isn't 0. WA on test 4
Same thing.
Did anyone else use 2-SAT for C? xD
twf using dfs for C
Pfft, you aren't a real programmer if you don't solve 2-SAT by putting it into your own hyper-optimized (exponential but still super fast) 400-row general SAT solver.
Nobody did any hacking, interesting XD
It's okay that the round is unrated. It happens.
However, I hope the announcement would emphasize the fact that it's unrated when it's unrated. I saw only the first two sentences of the announcement, and I didn't read the rest of it because I saw that it was talking about problem B and I already passed it, so I thought there is no need for me to read it any further.
Exactly. I just now came to know that the round is unrated :(
Can anyone explain why my dfs solution for C is giving wrong answer on pretest-2 here's my Submission.
I've tried it on some other test cases and unable to find any mistake. Can anyone help?
Basically, it's possible for your code to increment the same value twice.
My solutions:
Answer=[1]*n
Painfully try to squeeze in random modulo, ehm... 2 equal b[i]s --> answer = YES, otherwise = NO
Try to satisfy "non-equal-neighbors" condition modulo 2
If we color odd bi-s black and even bi-s white, then b table will be colored like a checkerboard. Hence the solution: b_ij%2 needs to be equal to (i+j)%2
Observation 1: xor or all ai-s is an invariant (because (ai+aj+ak) == (ai+aj+ak) + (ai+aj+ak) + (ai+aj+ak))
Suppose that in the end we end up with a final array == ([u] * n), then the xor of the final array is 0 (if n is even), or u (if n is odd)
If n is even, and xor of or all ai-s != 0, then the answer is NO (due to invariant)
If n is odd, then the answer is YES (I'll use example with n=7, here a123 = a1+a2+a3)
[a1, a2, a3, a4, a5, a6, a7] ->
[a123, a123, a123, a4, a5, a6, a7] ->
[a12345, a123, a123, a12345, a12345, a6, a7] ->
[a1234567, a123, a123, a12345, a12345, a1234567, a1234567] ->
[a1234567, a1234567, a1234567, a12345, a12345, a1234567, a1234567] ->
[a1234567, a1234567, a1234567, a1234567, a1234567, a1234567, a1234567] ->
If n is even, and xor of or all ai-s == 0, then the answer is YES (I'll use example with n=6)
[a1, a2, a3, a4, a5, a6] ->
[a123, a123, a123, a4, a5, a6] ->
[a12345, a123, a123, a12345, a12345, a6] ->
[a12345, a12345, a12345, a12345, a12345, a6]
Notice that a12345 == a6 because xor of or all ai-s == 0 (a12345 + a6 == 0)
420+4-2-0 times do the following: pick three different numbers u, v, w and put query(u, v, w) to array.
With very high probability (>= 1/2 * 1/2 == 1/4 ???) result = either left or right child of root.
Pick 2 most frequent labels of this array (call them child1, child2).
For n-2 other labels x: if query(child1, child2, x)==x, then return x as resulting root.
Note that because a[i]>0, then a[l+1]+...+a[r-1] > 0, so a[l] xor a[r] >0, so there should be at least one 1 in binary representation of a[l] xor a[r]
Lets suppose that most significant non-zero bit of a[l] xor a[r] == b. Lets also suppose that b-th bit of al is 0 and of ar is 1: bit(a[l], b)==0, and bit(a[r], b)==1 (we can handle the case bit(a[l], b)==1 and bit(a[r], b)==0 by reversing array b).
Lets iterate over all possible choices of l and b: - find r1 == smallest i>=l+2, such that bit(a[i], b)==1; (O(1) with preprocessing) - find r2 == smallest i>=r1+1, such that bit(a[i], b)==1; (also O(1) with preprocessing)
Check if [l, r1] and [l, r2] are valid segments (O(1) with prefix sums) Note that there are no more segments [l, r] for fixed l and b, that is, r cannot be > r2.
Why? Because if r>=r2+1, then a[l+1]+...+a[r-1]>=+a[r1]+a[r2]>= 2**b + 2**b == 2**b+1, but this also contradicts our assumption that most significant bit of a[l] xor a[r] is b.
As a corollary: answer <= 30 * n * 2 * 2
Video Editorials https://www.youtube.com/watch?v=RXJOWUEQz7k
Finally 13 th November. It's Unrated,still intrigued with some great problems....
Can anyone please tell me as to why this solution to B was wrong?
98288806
Try this testcase
1
5
2 2 2 2 2
Your programme will not take all of the inputs.
Thanks a lot!
Never keep a contest on Friday the 13th
Is it unrated now?
Isn't that obvious?
Video Editorials https://www.youtube.com/watch?v=xxAr1ytqWhs
We want one more rated contest in this week as this contest became unrated
agree
And there is one on Sunday :)
Why this solution doesn't work 98303387, but this solution works 98327745?
Because in the first one when i=n-1, a[i+1] is out of bounds.
Important test case is missing from D. I submitted what should be an incorrect solution, and later resubmitted a correct solution. However, my incorrect solution also passes.
The test case in question is where N = 4 and the answer is YES, e.g. N = 4, A = 2 2 2 2, or N = 4, A = 1 1 3 3
My incorrect code printed out "N-4" as the the number of steps, which gives an output: steps = 0, ops = 1 2 3
Clearly this is incorrect, and I corrected my code to output: steps = 1, ops = 1 2 3
However the test cases are not currently sufficient to identify this bug.
I think it's checker's job to check the correctness of your output
The checker reads the number of steps. Because it's 0, the checker doesn't read any operations and your output is correct. CMIIW
0 would be an incorrect number of steps in the case N = 4, A = 1 1 3 3
Yeah you're right, I didn't test your program with the last input
some please point the mistake in this Problem C solution solution_link
try this testcase 1 2 3 2 2 4 2 2 3
Easy solution to problem E:
Notice that if $$$a_l \oplus a_r = a_{l+1} + a_{l+2} + ... + a_{r-2} + a_{r-1}$$$ is satisfied, then $$$a_l + a_r \geq a_{l+1} + a_{l+2} + ... + a_{r-2} + a_{r-1}$$$ is also satisfied.
Assume we fix the position of the rightmost element $$$r$$$. Now let $$$l$$$ be the index of the first element to the left of $$$r$$$, so that $$$a_l + a_r \geq a_{l+1} + a_{l+2} + ... + a_{r-2} + a_{r-1}$$$. The sum of $$$a_l ... a_r$$$ is at least twice as large as the sum of $$$a_{l+1}...a_{r-1}$$$. Lets denote the sum $$$a_{l+1}...a_{r-1}$$$ by $$$x$$$. Notice that the element at the next valid left endpoint will have to be at least $$$x * 2$$$, the next one at least $$$x * 4$$$ ... Hence there are at most $$$log(maxA)$$$ candidate left endpoints for a single $$$r$$$. We can check all of these subarrays $$$O(N \cdot logN \cdot log(maxA))$$$ time using range queries or set (the solution works with a very small constant factor).
Hello, a newcomer here.
I was trying to use pypy3 to do F, and I got a lot of TLE's. I tried many ways to go around this, but I wasn't able to find a not-very-dodgy solution: I had to do it in "batches"
https://codeforces.net/contest/1438/submission/98332683
Is there a not-very-dodgy way to do this with pypy?
Here are some of my failed attempts: https://codeforces.net/contest/1438/submission/98331404 https://codeforces.net/contest/1438/submission/98330796
I agree with this. I can't find a way to fit the solution within the time limits using pypy either.
can anyone explain code from jiangly
If
(a % 2 != (i + j) % 2)this statement is true it will add 1 with a . And the statement means -->> a odd and (i+j) even -OR- a even and (i+j) odd.how does this syntax works << " \n"[j == m]; ?
That's the equivalent of saying:
if (j == m) cout << '\n';
EDIT: Think of it this way:
You are given a string of two characters ' ' and '\n', which is represented as " \n". Take the character at index [j == m]. Keep in mind that j == m yields either 1 (true) or 0 (false).
Hope it clears it up.
if j==m it will print a new line otherwise a space
upvote this comment if you too think today's contest was mainly based on simple observations only.
[please don't downvote to pull my leg]
That's the case with most Div2 rounds nowadays, which is by no means a bad thing. In fact it's only true with A, B and C problems. Give D, E and F a go and you'll be proven wrong very easily. People of all levels get 1 problem to play with, while others stay far below/above their current level and in my opinion that is very well balanced.
Problem solving is all about logical thinking and making observations, maths and algorithms are really the tools to execute the idea.