Hello, Codeforces!

<almost-copy-pasted-part>

Hello! Codeforces Round #690 (Div. 3) will start at Dec/15/2020 17:35 (Moscow time). You will be offered 6 problems (one of them is split into two subtasks) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 problems and 2 hours to solve them.

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**.

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 trusted participants of the third division, you must:

- take part in at least two 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, then the round will be rated for you.**

The problems for this round were invented by MikeMirzayanov and prepared by me Supermagzzz and Stepavly

Thanks to MikeMirzayanov for platforms and coordination of our work. Thanks to Sho, kocko, brian, Crazy_hedgehog, manta1130, Rox, Gassa for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

UPD: Editorial is published

It seems that the preparation of div3 rounds is less and less fit into vovuh's schedule. It will be great if Supermagzzz and Stepavly work together and they will take the initiative. Please support them!

We need to support the few writers we have, as Div3 rounds do not take place that often.

Is Mike said something else?

sir plz make sure the problem quality is good, otherwise a lot of the times problems are not that good.

stop making new user ids until you perform well :P

vovuh problems are easier though

Such a great pair betweens Supermagzzz and Stepavly. They work together in every contests. Thank you for another div 3 round.

Hey, can you make sure that problem changes are added to the problem page too? An announcement about a problem is just posted on the main page and doesn't appear on the problem page after refreshing.

My chance for becoming expert :D

+1

I see mikasa <3

<3

i see luffy

Congrats! Very glad to you!

haha, ratings not updated yet! let's not count the chicken before it hatches :P

I guess, you didn't know about CF-Predictor extension. Don't worry, you're going to be an expert!

Ohh, great extension. Thanks for the information :)

Finally, the almost-copy-pasted-part joke is back.

My chance for becoming pupil.

your chance for becoming red tbh

Thanks to Supermagzzz and Stepavly for preparing the div. 3 contest.

Hoping that the problem statements would be as short as possible. Also my chance for not to go back to pupil.

Why there are 2 Hello?

Because of almost copy paste.

"You will be offered 6 problems (one of them is split into two subtasks)"

Will the 2 subtasks count as 1 or 2 in the

score?2

you have come a long way...inspiring

Your graph is a true motivation for me

Thank you _believe_ chaudhary_19 ritikagarwal!

Welcome, but really don't know why guys just see the color of the handle and downvote the comments :(

Thanks a lot for this DIV3 contest! Supermagzzz && Stepavly

SpoilerMeanwhile Red Coders in every Div 3 contests be like :

More like completing the round within 45 minutes.

Hoping, that I don't mess this round up with silly and lengthy implementations.

Hoping to see good problems, Supermagzzz and Stepavly, thanks for this round.

Hope difficulty level of problems will increase smoothly.

Having a rating of 1601 is good thing or bad thing before a DIV 3 contest?

Good, atleast u reached

expert:)Good, at least u reached a four-digit rating

Good, at least you have a rating

On the behalf of a person not having any account -> Good, atleast you have an account

The joke is ruined when you explain it

While I like vovuh's div3s a lot, it'll be a breath of fresh air to have new writers! Hope you guys have a nice round prepared for the contestants !

Note the sub-tasks, it can make or break your round. Waiting for the distribution to see whether its C1, C2 or D1, D2.

You can't see before the contest

I can't tell you before the contest which ones will be subtask

Forgot this might not have scoring distribution. So subtasks are profitable to solve first!

i am a newbie and these contests are very much helpful :)

First competetion for me on codeforces can I try ?

yes you should :)

Of course! Everyone started with their first contest.

This contest I will be pupil.

Are you crazy dude?

No.

Please have more Div 3 Rounds!.

This is not just good for beginners since (Div 2 and Edu Rounds can be a bit overwhelming) but also good for Codeforces since the amount of people registering(and participating) in Div 3 Rounds is the highest.

I am agree with you.

So just a doubt regarding the question involving subtasks, if we solve both the subtasks it will be counted as solving 2 separate questions, right? (Since this is a Div3 round so each question has equal weightage, hence the number of solved problems matter.)

Yes if you are confident its better to do the harder one first. That way you will save time, against doing them one by one.

Whenever I see a div-3 round announcement, the first name comes to my mind is vovuh :)

All the best to everyone in div. 3..... Hoping to see good problems, Credits to Supermagzzz and Stepavly!!!!

MY chance of becoming Newbie.

Good luck everyone!

I hope i do better in this round since its division 3 ....i dont know i am just not able to solve the third question in div 2 and sometimes even the second one.....i guess div 3 is for noobs like me and they should organize it more

exicted for the div 3 contest , hope the problems are good

dude Buy some clothes before being excited :3

good luck guys .. happy coding!

Finally, div4

In caseno negativ, just meme :)

While the problems were fine, I think E and F should be more difficult than this.

Its a very very good round. Thanks a lot to authors and their team for it. Keep going!

My worstround, which Ienjoyed.Great Problems, but I don't know what happened to me or test cases are very tricky. I have tried to solve from A — F but only A and C passed the test case.

What was the idea behind the different input and output in E1 and E2? You could fix k = 2 and m = 3 and still write them into the input, and I find it unfortunate that my solution with modulo didn't work in E1, but did in E2. The last sentence of the problem statement, "You must output the exact value of the answer.", is in my opinion contradicting to "you DON'T NEED to output the answer by modulo.", especially when the word "NEED" is written in caps.

Usually, you can just submit the hard version also for the easy problem.

Edit: I enjoyed the contest besides that, thanks for it!

Great problems

How to solve D?

soryy, it should be D.

You can edit the first comment. UPD(MY EDIT) : The user editted.

if all the elements are equal and the total sum of the array is S, then you can find what all the numbers will be equal to. For any array size N, it will be (S / N). Simulate to check if its possible to convert all of them into (S / N) and print.

Try all the prefix sums possible in the array. Complexity is O(n^2), it works since n is 3000.

E1was available onGFG. Similar idea ofE2damn it why didn't i google

Oh, sorry. I came up with the idea of the problem completely independently. By the way, is there really E2 there?

No matter sir. We enjoy, we learn from the contest , thats great.anyway great contest !!

E2 idea was the same just adding NcR.

On problem E (easy version)

What if the input is all ones (1 1 1 1 ...)

(length 10^5). Choose3 from 10^5would be very huge. Is there something I missed?It just $$$\dfrac{10^5 * (10^5 - 1) * (10^5 - 2)}{6}$$$, around $$$1.6 * 10^{14}$$$ and still fit in

`long long`

.Iterate through the array to choose one element to fix. Notice that there are (n-i) choose 2 ways to pick the other two elements in this case. The answer will just be $$$\displaystyle\sum_{i=1}^{n-2}{n-i \choose 2}$$$, which should fit in a LL.

Nice round, but why don't you just write

`k`

and`m`

in the input of E1 for convenience? It took me about 10 minutes just to realize how I went wrong in E1 although I got AC in E2.Nice contest. I enjoyed the problems very much. Thanks!

Hey. Could someone let me know why I received RE on problem E1. https://codeforces.com/contest/1462/submission/101345065

I tried looking for a mistake but I couldn't find how I received run time error. Everything was correct until this test case. If someone could let me know why that would be awesome :)

Your long long is overflowing. 10^5! is huuuge.

Integer overflow is there in your code while calculating factorial.

In test five, I believe your program is finding $$$\dbinom{200000}{2} = \dfrac{200000!}{2! \cdot 199998!}.$$$ This is probably giving an integer overflow.

You can just compute $$$\dbinom{n}{2} = \dfrac{n(n - 1)}{2},$$$ so there wouldn't be any overflow.

How to approach F? I tried scanline with coordinate compression. Failed test case #2

I did Binary Search and used Difference Array.

Consider each range in sorted order, find how many ranges do not intersect with it on its left (suppose x) and right (suppose y). Minimise x + y.

The problems were so cool !

Thank you for the fun problem set! It felt like an AtCoder ABC :). D was really nice. EF could've been a little tougher.

I found E1, E2 and F easier than I thought.

I had been trying $$$F$$$. First I tried Fenwick Tree, messed with the implementation there. Then I moved to a simple binary search solution, messed there too. Just saw your solution for $$$F$$$, it's along the same lines of what I was thinking during the contest. You've written it pretty elegantly I must say. Thanks.

Just up-solved it, now regretting my stupidity during the contest...

PS: I agree that the complete set was pretty easier than I expected.

Is multiset is too slow for 2e5? or I had something wrong in my code for problem F: Your text to link here...

Actually the problem is with distance function. Check the complexity of distance.

I think this works in log(n).

distance takes constant time for random access iterators, otherwise linear.

`int z = distance(v.begin(), lower_bound(all(v), a[i].fi));`

it is linear here. Also, use`v.lower_bound(...)`

as`lower_bound(v.begin(), v.end(),...)`

will not be logarithmic.Thank you

I have hard coded all the answers for problem C. And then gave solution in constant time.

WOW! Easy but Interesting problems.

Very cool contest, First time I solved five problems.

Thanks, Supermagzzz and Stepavly

I am still not able to solve 5 problems

From the participant's perspective, the differences between E1 and E2 are quite significant. For someone who has just solved E2, they have to spend a few minutes revising their code, removing modulo from all the computations and deleting some lines about reading the input format. On the other hand, I see the value of having this subtask, since someone can solve E1 and not know how to solve E2.

Issues involving subtasks seem to be quite frequent, and cause unnecessary trouble. Besides situations where input/output format differ, there are also situations where there is a queue and one has to decide whether to submit to both versions without seeing the verdict of one. There is also an issue if the author does not include all tests of the easy version in the hard version, and you can fail system tests on only the easy version.

If the system was able to give you points for both versions of a problem when you submit only to the hard version, I think this would solve a lot of issues.

Btw Time Limits of E1 and E2 were different, and some people were hacked on E1 not E2 by Tl..

I've now done over 100 successful hacks on E1,E2 and F combined, with E1 being by far the easiest to hack because of the lower TL. Almost all of my hacks come from TLEing solutions with slow IO with the most basic of max test hacks. For some reason E1,E2 and F all had $$$t \leq 2 \cdot 10^5$$$ but there were no test cases with a large $$$t$$$ inside the system.

I really think that allowing $$$t \leq 2 \cdot 10^5$$$ is completely unnecessary to begin with. Having something like $$$t \leq 10^4$$$ or $$$t \leq 5 \cdot 10^4$$$ makes much more sense. But if for some reason the problem setters want $$$t=2 \cdot 10^5$$$ then they should at the very least put in a test with $$$t=2 \cdot 10^5$$$. It really isn't fun to solve a problem, just to have it get TLE hacked because of slow IO.

Worth noting is that this time around I caused

`unexpected verdict`

3 different times when hacking (`unexpected verdict`

means that my hack broke one or more of the internal solutions). So not only was there not a single $$$t = 2 \cdot 10^5$$$ test case in the system, their code also somehow failed for $$$t = 2 \cdot 10^5$$$. So they didn't test for large $$$t$$$ internally either. What even was the point of allowing $$$t=2 \cdot 10^5$$$ in the first place?I am very disappointed about how unprofessionally Codeforces contests were prepared recently. I will switch to competing in TOKI and Codechef.

Why didn't this 101339626 work?

Check the value you assigned to mod variable, it should be "1e9 + 7" not "1e9*7".

Feeling sad for you.

D was the nicest one!

Thanks Supermagzzz and Stepavly for a great contest. I think I will go to Pupil after this contest =))))

This felt like Div 4

Yeah, but the contest seems to be balanced as far as DIV 3 is concerned.

Could someone please tell me why this solution for E1 is surpassing the time limit. In my opinion it should run in O(n). (https://codeforces.com/contest/1462/submission/101338165)

Am I missing something??

You are creating a vector of size 300000 for every test case. 2e5 * 300000 is a lot. It should work if you replace the 300000 with n+1 as it's given that 1 <= Ai <= n.

censored

Can somebody find why my solution to problem E1 link gives TLE

I like this Contest.

What's the hack for E1? I want to know why my O(n) is giving TLE.

Instead of iteration on 1 to n, you could have tried iteration on set of array nos to avoid unnecessary nos which are not present in array...

Initialisation of array of 10^5 size in each test case is wrong..

Oh shit. my bad. Didn't even looked at number of test-cases.

But still it's stated that sum of n over all test cases does not exceed 2.10^5.

Yeah. but I am traversing the whole of the 10^5 array for every test case making it 10^10 in the worst case. I should have traversed only those elements which are in the list.

It's actually your m[] array of 200000 size at the start of each testcase..

Does it matter whether it's 10^5 or 2*10^5?

No...

It's no of test cases × 200000 (Initialising whole array to 0)..

Instead you could have used map to store frequency...

Can anybody plz tell me how to know on which case my submission got hacked?

The tests seem to be kinda weak — many solutions were TLE-hacked

Lots of Python solutions (including mine) were hacked because Python I/O is slow for 2*10^5 test cases.

Yeah same here

This seems like someone is pretty blatantly farming hacks...

There is no advantage of hacking in educational rounds.

Giving this contest made me feel like Div 4's were back on the site.

i have created a fact arrary which stores the factoril of number and I used it to calculate nCR

why this code is giving tle for E2 O(nlogn) solution....string solve(){ // CALM DOWN : — )

ret(""); }

Just change all 200000 with n in solve func

ya i got accepted but i am mot getting one thing that 200000 is not so big to give TLE can u explain plz

You iterate 200000 in every testcase so your complexity is t*200000*c

(c = complexity for every iteration in for loop, t = numbers of testcases)

I solved 2 questions in the div3 contest yesterday. and also this is my first contest my submission list shows that I have submitted 2 questions. but my contest list shows no items and my rating is also null. can anyone help me

The final standings has not come yet. It will be updated soon.

Why F is easier than E2?

i need help with E1 problem. Close Tuples (easy version). I still don't understand why the result is 15 sets? With the number 1,2,3 we can form 10 sets. With 2,3,4 we can create 4 sets. With 3,4,5 we get 1 set and 4,5,6 more. This would give 10 + 4 + 1 + 1 = 16 : (

yes, but one over count....

in case (1 2 3)=10, we count (2,2,3)tuple

in case (2, 3, 4)=(3 not 4);// here double count of (2,2,3) tuple with same position

Why does my O(N) Code in E2 gets TLE?

Is this the power of frequent use of modular and long long type

EDIT: index mistake for the n<m case.

E1 was easier than D problem.But overall we enjoyed solving another good contest.Thanks Mike,Supermagzz and Stepavly.

I streamed my virtual participation of this contest, as well as explaining solutions afterwards: https://www.youtube.com/watch?v=_6nyLsqM5Ec

When the ratings will be updated??

Is this contest rated?

Hello. Is this contest rated or not?

Read the announcement.

Ok. Thanks :)

Hello . Good job ! when will the ratings change ? 19 hours have passed since round 690, but the ratings have not changed yet. and it's so bad...

The logic of question D is easily available on Internet. So I haven't cheated, I used the code of dividing the Array into K subarrays such that all subarrays have same sum and than iterated K fron n to 1 and this was my logic. Any sort of matching in the code is completely a coincidence but I am not a defaulter and have hiven test with complete honesty. So I request Codeforces to give me my points back for this contest

I hope the rating changes are brought about faster in this round! Thanks Mike.Expect more of Div 3 rounds!

Hey, can anyone help me with realizing how this solution can be TLed https://codeforces.com/contest/1462/submission/101328873. Is it because of Java sort , or i just made a mistake ? Thanks for attention/

Hi, I got a message that my solution AAAwesome/101289887 to problem B of the contest is similar to that of sul3/101270264 and asmans/101276379 and that is why I have been disqualified from the round.

My solution was pretty simple. I just coded it so that my code just checks that if the digits of 2020 are in the end or the start or a few in the start and a few in the end. My code would give the output on that basis. I could have probably thought of a much better implementation, but because it actually had a pretty small number of combinations of arranging the digits of 2020, I went with my code.

I am not surprised that other people thought of implementing their code in a similar way. After getting the message, I saw that the others had used different functions for their implementation for the same, so there is no way I copied them and also there is no way for me to check someone else's code while the contest is still running.

I request Codeforces to count my submissions because I haven’t cheated.P.S.: I don't know if this is the right place to post this, if this isn't then please tell me where I should.This is the message I received: Attention!

Your solution 101289887 for the problem 1462B significantly coincides with solutions sul3/101270264, asmans/101276379, AAAwesome/101289887. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I too got falsely accused for the natural solution to problem B in python!!

Respected Codeforces, I have valid proof that the basic code for Question D was published prior to the contest on gfg. I have not cheated by any means and I request to code forces to recheck my submission and give me my valid ratings Here I attach the link to that gfg problem, https://www.geeksforgeeks.org/check-if-it-possible-to-partition-in-k-subarrays-with-equal-sum/ You can refer it by yourself and confirm that I have not cheated and the source was freely available on the Internet and the match with other contestants is just a coincidence.

Thank You

Hello, I received a message saying my solution to Problem D 101301240 and Targas's solution 101299306 to the problem are quite the same. And thus we both have been disqualified.

Both Solutions might be very close, but we don't share the same exact code. I didn't share my solution anywhere, neither Targas did. We also don't know each others, so we don't have any way to communicate. We're not even friends on codeforces(I will add him after this coincidence as he thinks in the same way I do).

I think it's unfair to accuse people for cheating just for thinking in the same way and writing codes that are similar but not the same.

Your efforts for making the checker of copying are appreciated but I just figured out it needs some more work.

Thanks for the great round and problems!

Your solutions look very similar. In addition, you already participated out of competition. Let's not do anything. Unless you are a cheater, lightning rarely strikes the same point twice. You are unlikely to encounter such system behavior.

I did not receive a message for rating update, as earlier i used too. Can someone explain this? I am new to Codeforces.

You only receive messages for rating update if you get 100+ rating points.

"Attention!

Your solution 101277221 for the problem 1462B significantly coincides with solutions soham_mittal/101273272, complexroots/101277221. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."

This was such a direct question which just involved some if/else statements checks. Also I used Python and this could be the reason for two or more similar answers. I have NOT done any violation or any illegal activity.

What do I do now?

MikeMirzayanov Please look into this.

Vaibhav Garg

I don't see much common between GeeksforGeeks implementation and your and Piyush_7399 codes. But your and Piyush_7399 codes look the same.

I received messages from codeforces that my solutions for problem B and D match with solutions of some other contestants. I did not adopt unfair means. Also I am pretty sure there was no leakage of code. The similarity may be found because of the templates I used which are readily available in internet. Hopefully I did not violate any rule of Codeforces by using them because they were available in the internet even before the contest. Please look into this matter.

Thank you.

Hmmm what about this and your submission to D