Hello, Codeforces! Or, as we like to say in Romania: Noi nu spunem asa ceva, Codeforces!
We are proud to finally invite you to participate in Codeforces Round #804, which will start on Monday, July 4th, 2022, 14:35 UTC You will be given 5 problems and 2 hours to solve them. We greatly recommend to read all the problems, statements are very short and straight to the point.
In this round, the theme is not Independance Day related. I know, maybe we should've made the theme "Freedom", but we are not Americans and the puns within the problems were already written.
Joining me on the problem setting panel are:
- Vip-Testers: Um_nik, antontrygubO_o, BlueDiamond, lucaperju, atodo
- Testers: LucaIlie, borgar02, freak93, $$$\,\,\,\,$$$ Ionut_Padurariu, Lemur95, FairyWinx, $$$\,\,\,\,$$$ Brodicico, apostoldaniel854, Kirill22, $$$\,\,\,\,$$$ Olympia, lavish315, Kuroni, $$$\,\,\,\,$$$ caheman, theodor.moroianu, TheScrasse, $$$\,\,\,\,$$$ 244mhq, VladHaivas0205, Tudy006, stefdasca, CaesarPP, Fanurie, elizatoma000w, mat50013, IacobTudor, codrincrismariu, Matteo.Verz, mircea_007, amcbn, mihneacazan, armand09
- Coordinator: Artyom123
Also, we would like to thank:
- intrusiv for not deserving to be publicly named
- tibinyte for being a "codechef carry".
- Gheal for getting order #804 at KFC.
- lucaperju and VladHaivas0205 for inviting some of the testers :)
- Artyom123 for captivating coordination, rejecting only Boring tasks. 9 div2Bs to be precise
- antontrygubO_o for improving one of the tasks!
- TON for supporting this round, details can be found in this post.
- MikeMirzayanov for great platforms, Codeforces and Polygon!
Here is the scoring distribution: $$$500 - 1000 - 1500 - 1750 - 2500$$$.
Good luck & have fun & the third part!
UPD1: Editorial is up!
UPD2: Winners!
Div 2:
Div 1:
As a tester, please upvote the op. The problems were most fun I've seen in a while...
Gheal orz
%%%
I give you face
As a setter, I setted.
as the problemsetter that published the announcement, I did neither problemset the problems in the current contest nor did write the announcement mainly because my problems are too bad lmao skill issue git gud bozo
As a tester, I tested.
As a Vip-Tester, I Vip-Tested.
As a contestant, I registered
Happy 1 year anniversary!
As a tester, I can confirm that the problems were very fun! :D Hope you have fun too!
As a non-tester, considering who are setters, I strongly recommend you participating in #804.
Yes Sir!
As a Mihai fan, does Mihai show up in statements?
sorry sir this i am lame version mihai so no
mihai
Yay! Finally a classic Div 2 with 5 problems :)
same
Hope my friend kozliklekarsky will reach candidate master in this round!
Marinush
And I hope you reach well deserved master :D
No Freeforces then ;D
Haha "noi nu spunem asa ceva" actually translates as "we don't talk like this"
it translates to "We dont say such a thing, Codeforces!"
Love Romania!
Greetings from Greece!!!
Commented so this would stay in recent actions as deserved.
Gheal what was your #804 order at KFC? ;)
If I recall correctly, a hot double booster with a side of medium fries and coke.
I am gonna perform good in this contest.
damn, how'd you discover this?
Inspect Element
Dark mode users:
Darkmode slightly entered the room and sat in a corner without coming into attention of anyone
Why is no-one talking about the colors tester are arranged -- It's the flag of Romania!!
Greetings from Greece!
oh, I just noticed the Blue-Yellow-Red theme! That's really cool.
Also... I kinda saw 2-3 comments about Romania here (in Editorial and Comments), is July 4 something special in Romania? Like ik it's Independence Day for the U.S, but what about Romania?
My birthday is on July 4th:)
Just problemsetters are Romanian.
Good Luck!
I want to be green,crying.....QAQ
I know the pain
I want to get back to blue,but always fail or can't be persistant
I want gulambi
I'm more miserable than you, it's been 3 years and I'm still gray
As a newbie, Hope for some easy and straight forward statements
I first wanted to do some sarcastic insults, but then, I figured there is just no point to it and it isn't even funny. I will leave this anyway
Don't hope so in Codeforces Div2. Try Codechef Div4 instead, it has good problems for beginners
I first wanted to do some sarcastic insults, but then, I figured there is just no point to it and it isn't even funny. I will leave this anyway
Only 5 Problems? Do they have the same difficulty as the problems in the same position in previous codeforces Div.2 Round ? Are you doing this to response to the call in an entry which says not to waste problems since they're too difficult for Div.2 official participants? If so, I think it is a good start for codeforces to search a way to reform the contests.
For some reason I can't take part in this contest , but I hope to see what difference will the new Div.2 round problemset bring to codeforces and participants,wish all of you to have a happy codeforces round!
And thanks to the contest maker for his/her contribution to make the statements brief to save our time.
Short answer: idk
Long answer: I don't think I am allowed to respond to any of your questions before the ending of said contest. I leave this comment as token that after the end of the said contest I will modify my response as to actually give you a concrete answer
So, mainly the way the coordination went vis-a-vis the fact that we only had 5 problems was that the only one that proposing div2Fs was me (which is was a big mistake), and when I found O(N*log(N)) solution in E, most testers found that it sufficed for the difficulty of the contest. As such, the fate of the round was decided way long before we had Olympia considered as a tester, and as such even before her blog.
Hope to get to CM this time! (I think I have just done it!)
Same) Good luck!
Now if someone would tell my crush this , I would bee highly obliged.
I will convey this message on your behalf. Just tell me her name.
acha
super excited!
What is the story about the usual time is 17.35 !!
I also see 17:35 in the blog for some reason. I think it is in Russia time, so it is still the usual time.
Ah yes, editorial mistake. Modified now, we are sincerely sorry for this
This happened as an oversight from my part, as the timezone I live in is UTC+3, so it seemed normal to me to add the time at which it will start for me, ignoring the fact that other countries may exist
Well, now it is just "Monday, July 4th, 2022, 14:35 UTC" (I live in UTC+3). I was really scared
Orange name, I am coming!
It comes and goes.
Just like her
Please do something about the contest start time announcement in the future.
No!I will get 0!
0! = 1
hah，I did A and B,my friend only got A,not sweat
what criteria qualifies you for "vip-tester" over regular "tester"?
Vip-tester: their feedback made a significant change in the problemset.
Good luck & have fun & the third part! this guy is obsessed with 3 some next level
Doing C for the whole contest, getting the right logic (presumably), implementing everything in a large code and fix edge cases and then WA on pretest 2. And you never know what's wrong.
What was the logic for C though?
What i don't get in c is, it is written that the only permutations similar to a=[4,0,3,2,1] are [4,0,3,2,1] and [4,0,2,3,1]. can someone tell me why [3,0,4,2,1] is not a permutation of [4,0,3,2,1]? it satisfies the condition of MEX too
The mex of the last 4 elements isn't equal (4 in original permutation, 3 in your permutation)
If you take just the last 4 elements of those two arrays, then MEX is different.
That is MEX(0,4,2,1) = 3, while MEX(0,3,2,1)=4.
because mex of subarray (0,3,2,1) of a = 4 and same subarray in [3, 0, 4, 2, 1] is (0, 4, 2, 1) for which mex = 3 since mex is different for same subarray, this is not similar permutation
I can totally understand you.
Problems were interesting.
How to solve E lol
lol!!!
IDK. I found B difficult for me .
how to solve C?
How to do Problem $$$D ?$$$ Any hints?
An interval can be completely deleted if it's even length and there is no strict majority element. Using this fact, just do $$$O(n^2)$$$ dp.
How to do the do?
One can think of this problem as choosing the maximum length subsequence with equal elements, such that the interval between the chosen consecutive elements can be deleted completely. It's very similar to a classic LIS problem.
Problem C: https://yukicoder.me/problems/no/1709
(I'm not saying that the writer/tester should have noticed it and rejected the problem. It was used in a small Japanese contest so it is understandable that many people don't know this problem.)
Something similar was on CodeChef too https://www.codechef.com/submit/CONSTMEX?tab=statement, although the problems are slightly different, the idea and hence the solutions are pretty similar
Thanks for the round! I think the problems are interesting.
How to solve D?
I passed the pretests with dp :v.
How to solve C? I spent almost all the time but still have no idea.
First, I saved the positions in array c; Then having a range called l,r with initial values of l = c[0] and r = c[0], I iterated through numbers from 1 to n-1. if c[i] changes l or r, I just updated the l and r; otherwise, multiply the answer by the positions available inside the range.
My submission: https://codeforces.com/contest/1699/submission/162803936
The most difficult Div2 I have participated in recently
unordered_map sucks! In problem D, unordered_map sol > 2000ms array sol = 143ms, 15x faster Why am I always FST?
This Guy Posts Solutions on YouTube in real time. Can we do something about that? He always gets 500 to 600 views during contests
Well balanced contest I guess!
It could've been balanced better, but I'll assume you are joking.
Third best round this year. Waiting for more :yum:
This is the most unlucky round for me ever... Long time ago i missed +70 delta because forgot to write cout << "\n";, and now I missed my CM title because i forgot to change mod 998244353 (from the previous round) to 1000000007, making an incorrect attempt. Now my rating is 1896...
You'll get it next round :p
Thanks, I hope so :D Congrats on getting CM))
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Great contest! I think the problems are great. There's only one small suggestion that I'm gonna give you: The main test for D is not strong enough, as you let some wrong codes to pass the main test, for example, the code with N^3 complexity and some wrong dp which can be Hacked by the following testcase:
1 20 4 4 4 4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
Hope next time when you propose a contest on Codeforces you can strengthen your main test and test more to make a better contest.
Unfortunately, none of our testers had this wrong dp. All $$$n^3$$$ solutions submitted during testing got TLE on pretests. Pretest $$$2$$$ contained all possible tests with $$$n<=10$$$ and I assumed that it would catch any reasonably wrong solutions. The other tests were also (supposedly) strong enough.
I'm very sorry for this issue.
A classic div contest and as a contestant i really enjoyed this one.Thank you very Much.
I enjoyed it a lot as well.
cheating lol!!! Your problem C solution is matches with HermioneGragersBesty even the variable names.. and you added extra for loop for what??
Hey listen,juat throw this false blame on someone,i swear i haven't copied it from someone and why don't you ask Hermione that why he added so many comments in his orogram?...Is he afraid thar he might get caught? Look i have applied my own logic and it may possible that variable names are same and i swear i didn't even know who the hell is Hermione. So just throw this false blame on somebody else...
The contradiction of this statement is that you know they put a shit ton of comments, but then claim you don't even know them...
Nevertheless, it does seem like the two codes are different
Problem A is very similar to my problem XORABC from CodeChef April Long 2022.
hi! I am working hard on problem solving ,,but my rating is constantly decreasing ..can u see what i am doing wrong or should i keep practicing and have patience?
Because you are blaming an innocent,that's why.
if u r so innocent just explain what is an extra loop doing in ur code??
for(int i=0;i<n;i++){
}
lol!!!
It's so easy to explain it that I often do it so when I realize my wrong in my code and modify it quickly to get more pts in contests.
That is only one of the possible reasons.May be he Ctrl+A+V and too lazy to delete other things.So many explanations isn't it?
I am so happy for becoming pupil in this contest by achieving rank 2401.
Congrats :)
Thank You :)
I got -inf but good round!
Better luck next time!
Thanks to the round,make me to green
Hope I won't back to grey again
Same, I also hope so. Because I also became green in this round.
It's bad that 4 of 5 div 2 winners are probably alts
On the fifth sample test case of problem D, originally the question stated that [4, 4] was the only reachable array of 2 elements. I thought that was correct, but the wording now reads "one possible". Possibly a stupid question but what other array is reachable, and how? The only other number it could be is [3, 3], but I cannot see how that could be achieved.
[3,3] can be achieved too.
1 5 2 3 3 3 4 4 4 4 3 3
1 5 2 3 3 4 4 4 3 3
1 5 2 3 4 4 3 3
1 5 2 4 3 3
1 5 3 3
3 3
Yes! How did I miss that. Thank you.
I received a mail after the contest that my solution for Problem C coincided significantly with one solution(My solution — 162794304 other solution ,162779144. This coincidence occurred becoz almost same question already came in Codechef once — Do Not Touch the MEX. I knew that and copied the editorialist solution of that problem Solution. As the solution was already published before the contest, hence there is nothing wrong in copying it. I request MikeMirzayanov to look into this ASAP.
My ratings from this round disappeared! any news?
Oh no
Where did my rating go????
Today I got mail from from codeforces, that my solution 162783009 for the problem 1699B significantly coincides with solutions pallavvarshney76/162777169. Clarification : It was just a coincidence. The logic was very simple and the implementation can match with anyone. In my case, it is just matching with a single person which shows that I have not copied from any source , also I have not used ideone.com . I never got this type of complain earlier. Kindly look into it and do the needfull MikeMirzayanov. Um_nik, antontrygubO_o ,BlueDiamond, lucaperju, atodo LucaIlie, borgar02, freak93, Ionut_Padurariu, Lemur95, FairyWinx, Brodicico, apostoldaniel854, Kirill22, Olympia, lavish315, Kuroni, caheman, theodor.moroianu, TheScrasse, 244mhq, VladHaivas0205, Tudy006, stefdasca, CaesarPP, Fanurie, elizatoma000w, mat50013, IacobTudor, codrincrismariu, Matteo.Verz, mircea_007, amcbn, mihneacazan, armand09 Artyom123,Gheal ,tibinyte, valeriu
If you are greatly in distress (as I can observe), do know that the problemsetting area of any organization of any contest does not and can not interfere with any area of the plagiarism check. As such, don't bother the problem writers into this, let alone the testers.
Can you please tell me how to contact to problemsetting area of Organization. It is very stressful that i again become newbie after working hard.
Aa I said, we do not have tangents with that area. I only assume (as you did initially) that it is managed by MikeMirzayanov .
I feel completely embarrased and frustrated that I did not make it to this list. Although, it seems your loyalty to the OP is greater than I thought-- You took his advice and not mentioned me publicly
Is Problem C Wrong? Like this example: 5 0 2 3 1 4 The answer should be 2, include: 0 2 3 1 4 and 0 3 2 1 4 ? but the testcase show that it should be 1 The testcase number is Test#2 46th
i was wrong