Hello Codeforces!
mesanu, flamestorm, MikeMirzayanov and I are glad to invite you to Codeforces Round 827 (Div. 4)! It starts on Oct/13/2022 17:35 (Moscow time).
The format of the event will be identical to Div. 3 rounds:
- 5-8 tasks;
- ICPC rules with a penalty of 10 minutes for an incorrect submission;
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
- by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).
We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.
Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them),
- do not have a point of 1400 or higher in the rating.
Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.
We would like to thank:
pashka, keta_tsimakuridze, Gheal, AlperenT, KrowSavcik, Sho, badlad, qwexd, Phantom_Performer, haochenkang, _Vanilla_, sandry24, jampm, tibinyte for testing and great feedback!
TimDee for helping with russian translations!
- badlad for helping with a problem!
We suggest reading all of the problems and hope you will find them interesting!
GLHF!
UPD: Editorial
As the one, who translated statements, I promise, Timur has legs!
Scuza
Scuza
Scuza
I request Marinush to confirm this fun fact.
kozliklekarsky
bleahbleah
What do you want from me? Leave me alone.
bleahbleah
What do you want from me? Leave me alone.
bleahbleah
I hope you're right!
Maybe that was support for people who hasn't legs, that codeforces loves everyone
I got pinged lol
Finally, MY FIRST UNRATED ROUND >:D
Nice
As a tester, SlavicG orz
As a tester, I suggest while(true){ if(time != contest_time) continue; else return write_contest; }
That code uses 100% of CPU Thread, use something like std::this_thread::sleep_for(std::chrono::milliseconds(1)) to avoid that.
There were no Div. 4 rounds before. There were times...
Love to see haochenkang testing! Gl everyone!
As a tester, I'm really happy to be a part of this contest :)
waiting for long time...Finally div 4 come ..very exited ...
Best Div. 4 round I've tested so far!
Trust me bro
I hope this is my last rated Div 4 :>
As a tester, I just wanna say the G in SlavicG stands for top G.
How do you become problem setter, tester, helper or any of such things?
And also do these people get paid or they do it for fun?
setters do get paid, there's a blog in the catalog about that. in the meantime, testers either get contacted from setters directly or from other testers, and don't necessarily get paid.
No, testers do not get paid.
I like being a div. 4 tester because i can't wait for div 4 problems XD
and also because I am slavicG's #1 fan
If you want to prove that you are SlavicG's #1 fan, then you should change to my profile pic to show your loyalty.
Please read this, it's about becoming a problem setter.
You can become tester if your friend is the author/coordinator/another tester, they'll invite you. Note that authors need to be very careful who to trust, because they don't want to get the problems leaked.
Also, testers don't get paid unlike authors and coordinators. We do it for free because it's fun :)
I think it's unfair, testers should get paid with at least an autograph from SlavicG himself. You already got plenty of autographs but us the average testers never get to taste an autograph >;((
What an excellent suggestion, I also want autograph from SlavicG! But he didn't invite me this time, so I have no right to claim it unlike you :(
Oooof right, you know what, let's go on a strike if he doesn't invite you next time, or if he doesn't pay us with juicy autographs
I can't believe that I have 2 more rating than the maximum to participate in this contest as rated contestant, I wish I had waited a few minutes before submitting the last problem in the previous contest. -_-
This is harsh. I have used codingblocks.com online compiler and have not copied any text from anywhere and done it on my own. This is just a coincidence and nothing else. https://codeforces.me/submissions/code_vishal18# https://drive.google.com/file/d/1xTv1xVGfwwAsr0OIcfZEwf4nqu2GZLF9/view?usp=sharing. Please roll back my ratings. This is really frustrating and demotivating.
SlavicG
mesanu flamestorm
Marinush
kozliklekarsky
MLGlolalol
Hi, I'm a Chinese student, my English is bad. So, I want to Make frinends to learning it. After reading the previous words, you can also find that my English is not good. We can also progress on algorithms together. Thanks to you read my words.
"to learning" should be "to learn".
yes, thank for your help
能不能给这个hack div4点个upvote？https://codeforces.me/blog/entry/107979
点赞了hh，看来你的英语不错，我很菜，一直在学习
Some users with rating 1400+ create new accounts and participate in such contests and it affects us low rated users. I hope they stop doing this. This happens in div 2 contests as well.
Finally, I can increase my rating :)
Just the opposite for me.:p
OmG My FIrsT UNofficIAL ROunD!!!!!!
rp++！
Good luck to you
Hope it won't be queueforces.
Unfortunately, the queue is very long.
It may because there are too many testcases.
And that's how you jinxed it.
Very long queue !!
I keep seeing "Oops! Codeforces is broken"
Servers down O_o
Div 4 became so popular...
stresstestingforces XD
As an unrated participant, I really enjoyed the contest. Good job slavicg and team.
Why don't div3/div2 contests have similar problems? :sad:
Great contest for a div 4, covered a lot of basic concepts, for the first time I was able to solve the whole set of problems, enjoyed it thoroughly.
Imagine submitting a solution and after 30 min long queue getting wrong answer on tc 1.
That was happened with me after 20 min WA on 1 ;)
Exactly !
Thank div4 for making me feel less useless, first time full AC without any WA :(
I'm so tired for waiting.
Deleted.
What's the issue with C++20's gcd function? Let me know so I can mention it next time I cover it on STL in CP
You are invoking undefined behaviour by sorting empty vectors. Gcd is in no way invalid in c++20
I am impressed by how many different explanations there are for why your code is wrong. Check the test case that you failed on. You mistakenly assumed that if the GCD of the entire array is $$$1$$$, then there exists a pair of elements that is coprime. You fixed it by initializing $$$\mathrm{ans}$$$ to $$$-1$$$ instead of $$$0$$$. Everything else was fine.
Yes that's true, Thanks
Why was site down all the time! It was frustrating.
it was SO annoying
Is it just me who think that E has way more right submissions that it should have?
Dude, $$$E$$$ was easy, I actually solved it before $$$C$$$ and $$$D$$$ !
So I guess it has a simple solution that I didn't think of
It's because of Um_nik everyone knows how to Binary Search
how to solve G?
Video Solution for G.
Only first 30 elements are important.
Use a mask. Initialize it as the max element in the beginning. Add this to the answer and mark it as used. Then, for each unused element update the element with a new key of (original value with the masked bits cleared). This is the key. The value is a vector of the original values. Use the largest key and sort the vector of the original values. Take the max. Add to answer and mark it as used. Repeat the above until key is 0. Add all unused elements to the answer.
176046217 I submitted 5 minutes after contest ended.
Let the max element of the array to be the beginning of the sequence, since it has the highest lexicographical order. Then we try to find the element that results in the highest OR value, then update the prefix OR and mark that index as used. At one point where the higher OR value cannot be found, we fill the rest of the sequence with unused elements.
Since a[i] <= 1e9, which is less than 31 bits, the time complexity is O(N).
POV : You missed red and blue being horizontal and vertical specifically
And after getting WA2 wonder if this problem is even solvable.
Is there any more efficient way to check coprime than generating all in O(1000^2 * log(1000)) time.
they can be generated in 1000^2 operations by memoizing eucledian gcd
Problem E Why my solution is giving TLE for test case 4 176003168 176020081 176037934
pass the vector by reference
approach for F?
Only two things matter:
number of 'a's in the string
does the string have any character other than a?
I'd like to expand on tsuu's explanation.
1) Both strings 's' and 't' contain only the character 'a': Eg: aaa vs aaaa => we can see that the one with lesser frequency wins
2) String 's' contains many different characters, while string 't' contains 'a' only Eg: aaab vs aaaaaaa => S will never win aaab vs aa => again, S loses
3) Both 's' and 't' contains many different characters Eg: abcde vs aaazxy => Just pick 'a' as the starting character in S, and any character other than 'a' in t Here we pick a**** vs z***, so S wins
About the 3rd case, both strings are 'a' initially so if string T has different characters, S will win because we can make S starts with 'a' and T starts with anything other than 'a'.
Yes, thank you.
https://codeforces.me/contest/1742/submission/176025562 Why this is not passed any counter exam ple
1 6 1 1 3 1 2 5 4 3
Output should be 1+3+1+2 = 7 but it considers 5 as well and wrongly prints 12
Can anyone provide me a stress test like wa2 for my submission[submission:176043362]
176043362
Here's your counterexample, found in tests. Answer should start with
12 3. On your code it starts with12 6.I wasted 1 hour getting WA on Problem C, because, I thought each row or column can be painted with both red or blue colour! Then I noticed, only columns can be painted blue and rows can be painted with only red!!
A similar thing happened to me in the past, a few extra seconds spent reading problem statements are worth it.
How to solve D
Note that numbers are only up to 1000.
As the numbers are up to 1000 it's a good idea to save the number's indices. Then Iterate from 1 to 1000 and for each number find the numbers that are coprime with it, Then get the maximum sum of indices of both numbers, and in the end print it.
Please, share why this code getting TLE. Problem E time limit is 3 seconds. is q*n more than 3 seconds?
include <bits/stdc++.h>
define forn(i, n) for (int i = 0; i < int(n); i++)
define forN(i, n) for (int i = 1; i <= int(n); i++)
define ll long long
define nl cout<<endl;
define vi vector
define vl vector
define pb push_back
using namespace std;
int main() { int t; cin>>t; while(t--) {
int n,q; cin>>n>>q; ll arrN[n],arrQ[q]; vl v; forn(i,n) cin>>arrN[i]; v.pb(arrN[0]); for(int i=1;i<n;i++){ ll x = v[i-1]+arrN[i]; v.pb(x); } forn(i,q) cin>>arrQ[i]; vl ans; for(int i=0;i<q;i++){ int c = -1; for(int j=0;j<n;j++){ if(v[j]<=arrQ[i]){ c++; if(j==0) arrQ[i]+=v[0]; else arrQ[i]+= (v[j]-v[j-1]); } else if(v[j]>arrQ[i]) break; } if(c>=0) ans.pb(v[c]); else ans.pb(0); } for(auto i : ans){ cout<<i<<" "; } nl }}
q*n=4*1e10,it need more than ten seconds.
Thought in E we rearranged both s and t in the lexicographically least arrangement and then compare, wasted about 30 mins there, then re-read the question again and understood it properly, my ADD is really messing up with my performance, maybe it's time to cut down insta reels and tik tok ;(
i increased my performance 3x just by cutting porn.
Will 827div4 be unrated?
no definitely not
SlavicG
Is something wrong with the checker of problem F? I tried to hack and kept getting "Unexpected verdict" result.
Same Issue here. I find many people using int to store the number of characters. When k and q are large I created a set of data to overflow the counter back to 1... But the hack gives me "Unexpected verdict".
Sorry for the inconvenience, it should be fixed now.
C was the biggest anti-speedforces bait I've ever seen.
C still needed weak testcases for full effect ;) The number of FSTs would probably set an all time high record if the testcases were weak.
Can anyone tell why I am getting wrong answer on test case 2 of problem E.. It is because of wrong implementation or because of wrong logic. Submission link
This is the first round that I AK :D
Imho problem F was easier than E and D
editorial?
if you want, I can explain you any problem from this round
In problem C, you have to check whether "RRRRRRRR" is present in a row or not? Is that a wrong logic? because i wasted an hour on that and I couldn't find out what am i missing.
I found your problem. You should cin>> all lines, but if you found answer you break from cycle and for the next iteration you cin old lines from other test.176113641
Omg thanks
BTW implementation with regex: 176204006
It was a cool round. The last assignment is a lot of fun to underestimate why you can write n^2 code with one break and it will be accepted.
Overall this contest was good.
This contest taught me to read the problem statements very carefully.
By getting WA on C and D and correcting it after 1 hour :)
Can anyone tell me why there are so many hacks on F?
hacks in F because some people didn't read the first line in the statement
How to do F, if s and t are initially empty ?
they will never become empty ...initially, they are a = 'a' , b = 'a' ;
GEO THERMAL WROTE IT a newbie sadly
I had a problem accessing the page.
How can I not panic?
I hope this div not reflected in my rating.
Is the contest declared unrated?
The contest is shown under the 'only unrated' tab..
It takes time to update rating. Until the rating is updated, the contest is shown under unrated tab only.
Oh sorry, I wasn't aware of this, thank youu.
Wtf how is my F solution wrong, even some Gms had it wrong
temp*y can be greater than 2e9. so you should use long long
I'm an idiot i knew it should be long long and set the size variable to long long but the mul operation variables were integer.. Short sad story
Is it possible to solve E this way without getting TLE in test case 9? 176125836
q*log(n) is right.q*n is not enough.you can see my code.It only needs 467ms.176015222
Yeah but that's binary search. I was asking that can I do some improvement in this code only and get the job done? Or binary search is a must to reduce it to q*log(n)?
of course we need binary search.q*n=4e10,it will need more than ten seconds
Guys, I mistakenly resubmitted my own code for problem D, and CF sent me this:
Attention!
Your solution 176041980 for the problem 1742D significantly coincides with solutions tllwtg/176009167, tllwtg/176041980. 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.me/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.
Dose that mean my account are going to be blocked? :(
the same for me, also round somehow became rated for me
Thats strange. I guess the rating will soon be rolled back. lol
It's just a warning. But In case of repeated violations, your account may be blocked
fine... and thanks
same here. I wrote a blog post here. I did not cheat, and I don't know how they matched those 2 solutions as a "significant coincidence" case.
I ranked ~400 in the round (~95 officially) but I found I was disqualified and I am accused of cheating. I wrote a post here. Please help by upvoting.
Something strange happened to me. For problem B, I used "goto" in my code, and the judge gave me WA ( 175907076 ) though the code works well in my computer, when I replaced it with "flag" , I got AC.( 176139742 ) Could someone tell me whats going on with "goto" in this problem? that would help me a lot, thanks : )
It's because you don't read the input correctly. You are breaking early while reading the input so the values for the next test case start from the array of the previous test case, so all future values are just messed up.
Ohhh! I see. thank you so much!
https://codeforces.me/contest/1742/submission/175924333 https://codeforces.me/contest/1742/submission/175959376 I don't know why my code for this problem in 827div4 has been repeated by other's code. I don't know the people at all and if you see the links of code above , you could find that the codes could certainly made by different people. And the problem D , the solution I solved was right and simple. I can't really understand that this code could be repeater by others. Attention!Your solution 175924333 for the problem 1742D significantly coincides with solutions 0x4c/175924333, alitarekkk/175959376. 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.me/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.
My English is not good, so some of them are translated.
D guarantees that n is greater than or equal to 2, but they have n is equal to 1 in their data.
The first solution get Accepted. https://codeforces.me/contest/1742/submission/176077405
The second solution adds assert(n! =1) Then it gets Runtime error on test2.
https://codeforces.me/contest/1742/submission/176155308
MikeMirzayanov SlavicG I have been submitting my Java solution for problem E div4 827, and getting judgement failed verdict continuously. This happened at the time of contest as well. Kindly check.
Attaching the submission links : 175975446 176169782 176170045
Try renaming your class, con is a restricted filename on windows.
Why Problem D coprime in Codeforce round 827(Div 4) is retesting
Because of this. Testcases contained invalid input.
Hi everyone,
As a contestant I found that the test in the probem F wasn't good enough. I have all the prestest passed, but then somebody hacked me, so I checked what was the problem with my code and it was the size of a variant. I needed to put long long int and I used int, I think that it should give me wrong answer in a pretest, but it didn't.
Help me for find my mistake. I don't understand. https://codeforces.me/contest/1742/submission/176450420
This is Problem C