Hello, Codeforces! (or as we say in romanian, "Nu renunţ la tine niciodată")
I am glad to invite everyone to participate in Codeforces Round 833 (Div. 2), which will be held on Nov/12/2022 17:35 (Moscow time).
This round will be rated for all participants with rating lower than 2100.
You will be given 6 problems and 2 hours to solve them. All of the problems are authored by me.
I would like to thank the following people, without whom this round would not have been possible:
- IgorI for his awesome coordination of the round and for helping me with problem preparation.
- feecle6418, SSerxhs, Gary2005, RUSH_D_CAT, atodo, BucketPotato, andrei_boaca, hochesh, JohnVictor, valeriu, powergee101, mejiamejia, jampm, alin_gb18, sutekine, tibinyte and ansergeyg for testing the round and providing valuable feedback.
- MikeMirzayanov for the great systems Codeforces and Polygon.
Here is the scoring distribution: $$$500−1000−1500−2000−2250-2750$$$
Good luck & have fun!
Edit 1: The round is over, the editorial can be found here.
Edit 2: Congratulations to the winners:
Div 1 + Div 2:
Div 2:
As a tester, holy fuck 2 romanian rounds in a row and 3 cars of polis wtf romania
How did you write in white font?
<span style="color:white">your text here</span>Wish for a positive delta & Good luck everyone...
I guess you can become pupil in today's round if you solve A and B fast. Good luck!!
Thank you, buddy... Definitely, I will try. :)
Woahh an early scoring distribution OwO
omg no green round
omg no green round
omg no green round
omg no green round
omg no green round
Please stop the chain here, thanks in advance
Omg no green round
omg no green round
omg no green round
omg no green round
omg no green round
Omg no green round
omg no green round
omg no green round
Deleted
omg no green round
omg no green round
omg no green round
omg no green circle
omg no green round
omg no green round
Get a life
omg no green round
omg no green round
omg no green round
omg no green round
omg no green round
omg green comment
OMG no green round
Why everyone writing this line again and again What does it mean?
That's what I want to know too///
omg orange round
omg no green round
Hope everyone good luck! :)
Everyone best of luck,,,,
I am looking forward to the problems of this contest, hoping to surprise me.
down vote me :)
Best wishes for everyone
As a Romanian, I am delighted to see lots of Romanian rounds lately!
We have same rating, stranger!
Haha, really nice coincidence!
Good luck!!!
I want to be a specialist in this round.
All the best everyone.
Hoping to be green in the orange round. Bad luck doesn't allow. Hope so this time maybe i will :)
best of luck everyone. Will meet tommorow.
I hope next round after this one will be green again
unacceptable contest! why can romanians make contests now on codeforces? does no one know how things run among romanians when it comes to programming, especially competitive programming? this is deeply disturbing and I will reconsider whether I want to continue with this website or not. cheers but look into it
No one wanted you to join the contest
He's obviously trolling
unacceptable contest! why can humans make contests now on codeforces? does no one know how things run among humans when it comes to programming, especially competitive programming? this is deeply disturbing and I will reconsider whether I want to continue with this website or not. cheers but look into it
unacceptable contest! why can capybaras make contests now on codeforces? does no one know how things run among capybaras when it comes to programming, especially competitive programming? this is deeply disturbing and I will reconsider whether I want to continue with this website or not. cheers but look into it
unacceptable! why can? does no one know how things run? this is deeply disturbing. cheers
Good luck everyone, hope for Candidate Master
Good luck to everyone!
I intent to become green today!
I can see that you have been consistent for the past few days. Hope you reach green, good luck bro!!
Google Kickstart Round H and Div.2 Codeforces contest at same time... :(
(*P.S. I'll go with Codeforces):))
they literally have a 12 hr gap in their start time...
Damn my mistake..yeah u are right i thought it PM instead o AM
among us
Hey, my neighbour is Romainian, too. Good luck.
What color is your codeforces account? ♫ Tourner Dans Le Vide ♫
why div2 ?
i want div3 or 4 for become pupil
Skill Issue Tbh
gl
Good luck!(or as we say in romanian, baftaaa baaai)
liis Gang!
tourist in parallel universe
Time to be a specialist.
Best of luck Everyone.
Wish for a positive delta & Good luck everyone...
Mathforces with Awesome round :(
how it's unbalanced?
Time to be a pupil.
B is soo tough...
no we are just retarded
or maybe we need to improve ( i mean look at the standing alot of peoples solved it)
Corrected: lot of cheaters solved it.
if you can't solve some problems but a lot of people can
don't call them cheaters make yourself better
Totally agree, but one solution video for B had over 1.1K views on YouTube before the contest was even over.
don't get sad for some cheaters they don't ever get improved but you can
We have skill issue smh
I have never felt more retarded in my life while solving B.
getting WA 3 times because of being a dumbass only
Again leaked solutions on YouTube... (https://www.youtube.com/channel/UChJvx-TFKQ5t-T6YyPf1tsw, https://www.youtube.com/watch?v=0x9kKxfqLr8)
This solution for problem B has 1.1K views and the contest is not even over yet!
Can't solve B lol :((
Unbalanced round.
In problem C, my code with
std::mapgot AC but withstd::unordered_mapgot TLE at pretest 7... WTF??Here you go. https://codeforces.net/blog/entry/62393
so will
mapbe hacked in system tests?No. Very unlikely with the given constraints.
Same got TLE, in python...
Tried collections.Counter, defaultdict and all such, but nothing worked...
It seems that O(n) solutions won't be accepted. Maybe I just need to work out an O(log(n)) solution next time...
Viewing the acceptance rate, it seemed that many people had similar issues.
Okay, seemed that they also had a hash hack test case for Python. Great to learn a new lesson!
Anti-hashing testcases. I was aware of that...
Basically there are some testcases that purposefully break solutions that use hashing.
More details
in the worst case, the time complexity for all the operations in an unordered_map is O(n)
How to solve C ?
Construct a prefix array $$$p$$$. Then you can break the original array into segments based on the positions of
Unable to parse markup [type=CF_MATHJAX]
and ends at the index before the next $$$0$$$. Suppose the positions ofUnable to parse markup [type=CF_MATHJAX]
are $$$z_i$$$, then the maximum score you could get from subarrayUnable to parse markup [type=CF_MATHJAX]
is the maximum frequency of any element in the subarray of $$$p$$$ fromUnable to parse markup [type=CF_MATHJAX]
. I implemented this by using a resetting the frequency count every time I hit a zero, and then finding the maximum among the frequencies when I reached the next zero. Also, anyUnable to parse markup [type=CF_MATHJAX]
that occur before the first $$$0$$$ in $$$a$$$ have to be counted as well. Hope this helps!How is D done? I was thinking some SAT solver possibly but couldn't think of a way to calculate divisibility rules of $$$d$$$ efficiently.
My Solution for D:
Check no solution:Note $$$cal(x)=max(i),2^i|x$$$,if $$$cal(d)>min(cal(a),cal(b))$$$,no solution.
Otherwise,Let's construct the solution.
First,let $$$d»=cal(d),a»=cal(d),b»=cal(d)$$$,calculate the $$$x$$$ for the new $$$a,b,d$$$.When outputting the answer, we only need to output $$$2^{cal(d)}x$$$.
How to construct such $$$x$$$?The key point is make $$$x=(2^{key}-1)+2^{key}X$$$,($$$key=30-cal(d)$$$).
This is actually a problem of solving congruence equations:
Unable to parse markup [type=CF_MATHJAX]
,use ecgcd to get such $$$X$$$.B really shocked many!!!
Was pretest 8 of C a hash hack?
Lol, I rewrote my solution to c++ to pass 8
Didn't even think we could have hash-hack pretests
You're right
Well, It is nice that they included it in pretests I guess.
I suspect it was, I only passed pretest 8 after adding code specifically to stop hash hacks (mainly xoring each value in the dictionary by a predetermined random value)
What was the intended solution for D? I had a solution of
Unable to parse markup [type=CF_MATHJAX]
but it TLed.Edit: Ahh, intended was
Unable to parse markup [type=CF_MATHJAX]
per test.Link: 180645422
how to solve D? i got stuck at the part where you have to find some modulo using some certain bits ;-;
Really good E! I like this problem of dp on cartesian tree.
I normally solve A, B, C, this time I only solved A. All good, go next
How to solve C? I had ideas with dynamic programming but I'm tangled up in my thoughts
The main idea is to split the original array into segments based on the positions of
Unable to parse markup [type=CF_MATHJAX]
and ends at the index before the next $$$0$$$. Then I can perform the operations in such a way that each $$$0$$$ only affects its own segment. Construct a prefix array $$$p$$$ and in each segment, find the maximum frequency of occurrence of any element in $$$p$$$ — That will be the score of that particular segment. Also count allUnable to parse markup [type=CF_MATHJAX]
that occur before the first $$$0$$$ in $$$a$$$. Hope this helps!I understand. Thanks
Problem B can use the enumeration algorithm, this surprised me.
I wish I had time to look at F but B took so long because I didn't realize brute force passes it :(
And here I was thinking that it had to be done using 2 pointer+ sliding window
Then I realized it could be done with brute but was unable to find the maximum times inner loop should work :(
I also thought it was two pointers at first and wasted so much time XD
In my honest opinion it was the hardest Div 2 that I participated, I could only solve 1, and I lost expert :'v, but I will learn new concepts and that it is great
How a simple brute force is getting accepted for B?? what is the time complexity of the solution.
Unable to parse markup [type=CF_MATHJAX]
It seems the intended solution is to bruteforce with one simple observation: By the pigeonhole principle, a substring of length $$$101$$$ would have at least one character with at least $$$11$$$ occurrences. So we only have to check for substrings of length upto $$$100$$$, because lengths above that are guaranteed to be non-diverse.
wow giving contests regularly and upsolving is the best way to learn topics thanks i would never have understood pigeonhole principle better than this time .
Quick system test!
How to solve C . Anyone ?
The main idea is to split the original array into segments based on the positions of 0s. Each segment starts at a 0 and ends at the index before the next 0. Then you can perform the operations in such a way that each 0 only affects its own segment. Construct a prefix array $$$p$$$ and in each segment, find the maximum frequency of occurrence of any element in $$$p$$$ — That will be the score of that particular segment. Also count all 0s in $$$p$$$ that occur before the first 0 in $$$a$$$. That will give you the answer.
I did A. Then looked at B couldn't solve it initially. So I skipped went to C. Tried it for about an hour. Then came back to B, after staring at it for a while saw that there was a pigeonhole principle angle which brought the solution under time limit, so did it that way PH principle: ceil(n/h) is the minimum put in h groups if n values has to be distributed among it. so 100/10 -> 10 and ceil(101/10) = 11 which means there is no substring out there of length 101 that can satisfy the conditions. So you can test the substring lengths accordingly. Worst case it goes to 10^5*10^3 = 10^8 which comes under the 1 second condition, 10^3 because 100 values to be checked and say we check all value counts from 0-10 in that case.
even better: 100 is only 10^2, not 10^3
I counted the time taken for going through the 0-9 count values for every one of substrings. Are you counting that to be constant?
You can also just... Not do that ;-)
My submission
Hi, everyone. I have given this contest( Codeforces Round #833 (Div. 2)) and got a score of 464. But still, I am unrated. Can anyone plz say why I am still unrated?? N.B. I am new in codeforces.:):) Thanks in advance..
It will update soon :)
Thanks, brother. :) :)
My Solution for D:
Check no solution:Note $$$cal(x)=max(i),2^i|x$$$,if $$$cal(d)>min(cal(a),cal(b))$$$,no solution.
Otherwise,Let's construct the solution.
First,let $$$d»=cal(d),a»=cal(d),b»=cal(d)$$$,calculate the $$$x$$$ for the new $$$a,b,d$$$.When outputting the answer, we only need to output $$$2^{cal(d)}x$$$.
How to construct such $$$x$$$?The key point is make $$$x=(2^{key}-1)+2^{key}X$$$,($$$key=30-cal(d)$$$).
This is actually a problem of solving congruence equations:
Unable to parse markup [type=CF_MATHJAX]
,use ecgcd to get such $$$X$$$.D is sooooooo cute!!! (Though there is a gap between C and D)
Unable to parse markup [type=CF_MATHJAX]
($$$?$$$ and $$$1$$$ : $$$30$$$ times).Unable to parse markup [type=CF_MATHJAX]
($$$k$$$ is a positive integer). It'sUnable to parse markup [type=CF_MATHJAX]
. Another representation is, using some positive integer set $$$S$$$,Unable to parse markup [type=CF_MATHJAX]
.Unable to parse markup [type=CF_MATHJAX]
.You can choose a set $$$T$$$ which is a subset of $$$S$$$ s.t.
Unable to parse markup [type=CF_MATHJAX]
is an answer. How to determine the set $$$T$$$ ?This should have been included in the official editorial. I think most of the solutions came from this intuition. Hats off man!
B is run in time O(100*n), beacause all numbers [0:9] as a maximum frequency in one sub-string is 10 if it's frequency is greater than 10, then second loop will stop, because no sub-string will be made as no numbers of distinct numbers from [0:9] will exceed frequency of 10. i like this problem.
Can i ask why in your solution you have used i+228 if 100 is the maximum length of valid substring?
My friend told me of this (i+228), but then i reach the main concept. :)
When you say your friend told you, do you mean during the contest?
or maybe because the video with leaked solution on youtube has i + 228?
This is the problem of taking an hint from a friend during the contest, thank you.
I think thats still considered cheating.
Why did so many people solve C? I solved D and E but didn't solve C. Are there any good ways to come up with the solution?
I learned main idea when study IOI 2002 Batch Scheduling. This problem's main topic is CHT but provides one observation related to the prefix sum. Other implementations were learned while upsolving code forces.
It was quite simple to come up with by looking at the prefix sum array and the zeros ;-)
bro maybe u were just overcomplicating it. C is quite simple as you can probably tell from the editorial (i havent read it yet tho)
180648134 My overcomplicated solution for B which I was restraining myself to implement till the final minutes of the contest.
B was leaked by a youtuber. Here is the link. https://youtu.be/0x9kKxfqLr8
You can clearly see its comments was 1+ hour ago from now. I am giving some screen shots.
https://drive.google.com/drive/folders/15e5mFpLw8ESoqK-0A6WXDSxGgzDqIjTV?usp=share_link
and when i look at the solutions many people are suspiciously using that i+228 logic, is there actually any reason for it to be i+228 or is everyone just copying this video?
NOTE: the solution just needs to be i+100 in the worst case thats why this specific number is quite suspicious
LOL if it is 228 then these subs are from the same sources.
I failed C for mistakenly specifying the wrong type for the map iterator like a complete dumbo. Why live? Please host another competition soon I need to avenge my stupidity.
Btw is there a way to somehow apply for retroactively rejudging solutions in cases like this? I will respect and understand if not, but could be very appreciated!
You can use https://cfviz.netlify.app/virtual-rating-change.html and look what rating change you may have had.
what a nice round! thank you
Congratulations being a fifth place.Jarif_Rahman
thanks
When speaking of B, if I quote Joma Tech : "Because of pigeonhole principle, child's play"
How to solve C ? I read the editorial and I still can't make sense of it, Also does any one know how to start solving C problems this is my 10th round in which I only solve A, B and fail C :(
If there are more than 10 * 10 + 1, we can realise that there is at least one digit that appears more than 10 times. It is because there are at most 10 digits, and if those digits doesn't appear more than 10 times, it means that there are at most 10 * 10 numbers, which contradicts what we are saying. (I think the rest is the most delicious part of the problem, so i won't say it...)
I appreciate the help but I'm asking for C, I've already solved B.
O sorry !
Start with the simplest case:
Unable to parse markup [type=CF_MATHJAX]
.How to determine the value of $$$a[x]$$$?
Case1:make
Unable to parse markup [type=CF_MATHJAX]
,the contribution isUnable to parse markup [type=CF_MATHJAX]
,$$$cnt$$$ is the number of $$$y>x$$$,which makeUnable to parse markup [type=CF_MATHJAX]
.Case2:make
Unable to parse markup [type=CF_MATHJAX]
,the contribution is $$$cnt$$$,$$$cnt$$$ is the max number of $$$y>x$$$,which makeUnable to parse markup [type=CF_MATHJAX]
.Hey, I get too nervous while giving contests. Any tip? I feel like I have enough knowledge to keep on solving A, B, C but I get too nervous while the contest that I mess up.
Awesome problems(at least A-D). But it's sad, that completely stupid 2e9 solution passes pretests and falls on systests. 1e9 is AC
Was C leaked like B and A somewhere? I feel like this C is harder than the usual C div2
B took much longer time than C.I solved B just one second before this contest over.But I still lose a good oppurtunity to become expert.
I believe question B should have been a C and question D should have been an E
In D, is there any reason there are two numbers given (a and b)? I think the problem works with a single number just as well, or am I missing something and it becomes very easy with one number?
I think you're right. If there were an easier way to find $$$x$$$ for only one number $$$n$$$, then the problem can be solved by finding $$$x$$$ for
Unable to parse markup [type=CF_MATHJAX]
?Adding more numbers doesn't increase the difficulty.
Would you please review my C? My code is bad because I am messed up during the contest. Only solve() is meankngful. Others are trash.
Fail at no.4227 at test2. And another failed contest.
https://codeforces.net/contest/1748/submission/180647355
There is a case of cheating in the problem B A solution is available during the contest on YouTube https://youtu.be/0x9kKxfqLr8
Matching solutions:- https://codeforces.net/contest/1748/submission/180650292
https://codeforces.net/contest/1748/submission/180650184
https://codeforces.net/contest/1748/submission/180649269
https://codeforces.net/contest/1748/submission/180646072
https://codeforces.net/contest/1748/submission/180646346
https://codeforces.net/contest/1748/submission/180646263
https://codeforces.net/contest/1748/submission/180646094
https://codeforces.net/contest/1748/submission/180645940
I registered 20 minutes after the contest started will it be rated?
yes
Really unacceptable! Isn't the codeforces rule that only pupil or below can set a round? Why can an orange coder set a round? The experience of this round will definitely be bad! I can't accept it at all!
My solution on C is uphacked for TLE. The cause seems to be the usage of unordered_map. See 180668799 and 180668851. The only difference is that the first one uses map and accepted, while the second one uses unordered_map and TLE.
Is unordered_map really that bad on performance? Am I using it in a costy way?
Weired. I find some benchmark showing that std::unordered_map outperformed std::map on every use case. I have totally no idea what is going on here.
Hmm changing compiler from g++ to MSVC resolves this issue, interesting... See [submission:https://codeforces.net/contest/1748/submission/180670005] which is exactly the same code as the one getting TLE I mentioned before. but accepted with MSVC.
Looks like it's not my fault. Maybe there's something wrong with the compiling flags?
you can refer to this : https://codeforces.net/blog/entry/62393
Ouch, the hash function, of course... Thanks a lot for your reply, and the guy below too.
When we will get rating changes?
When all cheaters are punished. :)
where rating where
Waitforces
Why codeforces don't make any hack phase in the regular rounds about 1 hour or even permit any rate account to uphack any solution ?
below there are huge number of hacks after the end of the rounds.
codeforces round 833
codeforces round 830
Dang I cheated but my rating wasn't taken away...
Well yay my rating got removed
For problem B why do we do (fr[s[j] — '0'] == 1) what does — '0' do here and how will it be equal to 1.
$$$s[j]$$$ is a character and we need to transform it into a number so we can use it as an index for the array, we can transform by subtracting $$$'0'$$$ from $$$s[j]$$$ that will result in the number itself.Take a look at the $$$ASCII$$$ table you will find that the result of subtracting the corresponding $$$ASCII$$$ code for each digit and the $$$ASCII$$$ code for $$$'0'$$$ will result in the digit itself, now we can use that number as an index for the array.
Could you show me an example with the string, "1011101"?
How would subtracting a character with '0' result in the number?
Take for example the character $$$'1'$$$,How can we get the number $$$1$$$ from the character $$$'1'$$$ ?
The $$$ASCII$$$ code for the character $$$'1'$$$ is $$$49$$$,
The $$$ASCII$$$ code for the character $$$'0'$$$ is $$$48$$$,
$$$ '1' - '0' = 49 - 48 = 1 $$$.
This is how we can get the number $$$1$$$ from the character $$$'1'$$$, This can work with any other characters $$$('2','3','4',....)$$$.
Note that this only works with characters and not strings (you can't get the number $$$"1011101"$$$ using this method), instead you can get each character at a time and calculate the number based on its base.
Personally, I think the problems F are not very difficult. They are very good. They do not involve advanced algorithms, but simple thinking problems
good morning :)
..
I got this message from codeforces:
This is probably due to both of us using the PyRival template and the problem being quite simple; how should i resolve this?
By doing precisely what you did! Simply comment on it with all the details, like you did. Your rating should come back soon.
Although it is very sus that the two submissions are less than a minute apart and the code is ridiculously similar... it is too simple to know if you cheated or not.
In the future, be safe and make your own templates.
i got none message and i loss my rating,how can i sovle it ?
my rating someting loss sometime back. what happened?
I think it may just be a temporary roll back caused by either cheaters or wrong cheating detections. I believe that this would be solved in a few hours (or days).
Ok so I submitted 180618741 in 9 minutes, and you have disqualified me for a generic Russian number 228 in my solution? I don't use any cloud IDE, neither do I have a clue why a widespread leaked solution has 228 in it, I lost about 80 pts in that contest, but please be so kind to cancel the disqual
There were only 3 successful attempts on B in my room, and the only locked one was made by a random Indian guy at 00:42:02. I haven't checked completely but looks like every other submission was made strictly after this particular moment. Thus, I strongly believe that my solution had been leaked through locking + hacking, akm07 do you have something to tell us about?
MikeMirzayanov could you also take a look, please?
Why is the rating cancelled?
Hey, I recieved this but obviously it's not me. What happened?
I have received a message that my solution 180643841 to the problem 1748C significantly coincides with solution pqr0xffffff/180627756. But I wrote the code myself, without violating the competition's rules, and I didn't post it anywhere. I have compared both solutions after I got the message, and it is clearly visible that the codes were written independently. The part of code that looks most similar is calculating prefix sums, which is a basic and very commonly used technique, and is written the same way by many people. One more thing that occurs in both implementations is using maps to solve the task, but the most important part differs — my solution uses one map, while the other solution uses two; my solution does some iterations over the map inside the "for" loop, and the other doesn't, etc. I hope that this situation will be reconsidered and I will get correct verdicts to my submissions from the contest, instead of 'skipped'.