Hello! Codeforces Round 991 (Div. 3) will start at Dec/05/2024 17:35 (Moscow time). You will be offered 6-8 problems 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 of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks. After open hacks all accepted solutions will be rejudged on successful hacks.
You will be given 6-8 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round 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 a trusted participant of the third 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 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.
Problems have been created and written by our team: AVdovin, DanGolov, kbats183, Vladosiya and pskobx.
We would like to thank:
MikeMirzayanov for Polygon and Codeforces platforms.
Vladosiya for coordination.
EgorUlin, qsmcgogo, molney, misorin, vladmart, Blinov_Artemii for yellow testing.
snasibov05, FBI for purple testing.
artcosec, Pslnd, _icy_, Gabbasov, UniversalAdmin for blue testing.
dmit_brit, WahidmShafin, Osama.Rafat100 for cyan testing.
Kaushal_26 for green testing.
Good luck!
UPD: Editorial is out.
yay! Vladosiya round
first comment :D
mamba:)
As an author, I want to admit, that I am an e-girl...
What is an e-girl?
electronic girl
What is an electronic girl?
e girl
xD
edging girl
u got a third leg down there or nah
Don't ask questions, you don't want the answers to...
haha true
Tread on me plz!!!（♡▽♡）
strange request.....
Freakyforces
Good luck
non-Notorious Coincidence
Sad Bad Terrible Day
If I don't become specialist after this round, I'll quit CP.
bro, relax, just enjoy this round like me))
i'm fucked.
why and how?
Well, I used my alt account to submit the question first so that I don't get any penalty, and now here I am. I've learnt my lesson and yeah, I don't deserve to be a specialist.
how does this work
like submitting the same code will lead to both your accounts getting flagged isnt it?
Not both, but the one at which you submitted later.
are you sure about it because
giving out solutions in public is also considered as an offence
codechef flags all the solutions first as well as second
pskobx is this a pose in your pic?
As a user, I wish everybody good luck!
Respect to everyone competing—turning simple fishing into a true test of skill!
Why I'm not given an invite to my email yet?
I would like to thank all of the problems writers and testers for their efforts in order for this round to be conducted.
I am excited to compete and do some brain storming.
I hope y'all enjoy this round and reach the rate you want.
Hoping for the best Div 3 round!
Hoping that there are no interactives in this one
But they are usually very fun
The strange kinds of errors are always beyond me. Extremely hard to test.
Why are there so many yellows testing the round lmao
As a green tester, problems are exciting. I recommend participating, and wish you good luck and have fun.
xD
who knows how to build my Chaska?
is it possible to get high rating without an anime PFP?
look like someone is going to be expert soon good luck buddy
Thanks Mate!!! Best of luck for your conquest towards higher ratings!.....
no
How do you practice codeforces?? I am grinding towards becoming Expert but stil struggle. Please help. Thanks!
i read a problem, and if i dont have an idea within 5 minutes i read the editorial and then try to understand where my thinking went wrong. this way of practicing is how i reached expert so quickly. hope this helps
So you dont give too much time to ponder about the approach. Interesting. Thanks !..
i believe that if i am truly able to solve the problem i will probably get the solution in about 10 minutes. and i dont think its worth it to struggle for hours just to be able to say that you solved without editorial. also often it happens that you just dont know a technique that is key to solving the problem, and i dont understand why i would bother if that is the case
great mine approach is also similar to you
and how much time you devote a day and any specific number of problems you target daily??
I am taking a bit of a break right now, but when i was practicing consitently i used to aim for about 3 problems a day
I think that I can also participate officially :) I am an Expert with a 1600 rating now.
blud really didn't read the next sentence
in div3 the number of problems u solve and how quickly u solve them matters? not which problem A or G u solved ? right ?
yes
Hopefully I can reach Expert after this round. Good luck for me and for everyone.
Congratulations bro!
Thank you!
is it rated for newbies?
Yeah
No
Hopefully I can reach Specialist after this round. Good luck for me and for everyone.
Why has the number of participants on Codeforces decreased compared to a few months ago?
Best of luck! May your hard work and preparation pay off, and may you achieve great success in the contest. You've got this! ;-)
Excited!
just before start...
StringForces
Forgot to add binary string problem :(
thank God you didn't
This contest reminds me of the awoo comment about problems from which you learn nothing. I don’t know what I’ll learn from C and D.
There are problems you learn from, so there should be problems you apply what you have learnt to
Though I truly agree with this mindset and have always followed it, sometimes it's just a matter of whether you can guess it or not—there's no other option. Maybe I'm just mad because of my performance, but I don't know. Sorry.
Edit: I just observed you are one of the authors of this contest, thanks for the contest, I appreciate that. I am mad mb
It's fine, I hope we will make better contest next time :p
how is E not educational for div 3 people wtf? i agree that C is kinda meh, but i dont think its that bad
Is E solved using DP?
yep
Thanks, my initial DP solution gave me a WA on test case 2, I found what makes it fail but couldn't fix it. Anyways, I agree it's a good problem and very educational.
F should be educational too
Why in the world are problems B and C, B and C?
Problem C is a good Problem. I've learned something from it.
I just did dp I assume there is another way around IDK yet so don't spoil it for me
There is a "math" way to do it. At least that's what I did.
Say the original number modulo 9 equals p and there are n 2s and m 3s. Then we have 2*x + 6*y = 9 — p, where 0 <= x <= n % 9 and 0 <= y <= m % 9. So we can enumerate x to get the answer. Is this the "math" way you are talking about?
Yeah, the idea is basically it.
Can u pls elaborate more? I don't get why u use 2 & 6.
$$$2*2 - 2 = 2$$$
$$$3*3 - 3 = 6$$$
Thank You, Sir
I got Runtime error in TC 3. Is there anything I missed that u said? ~~~~~ string str; cin>>str;
ll sz = str.size(); ll sum=0; map<int,int>mp; for(ll i=0;i<sz;i++) { sum+=(str[i]-'0'); mp[str[i]-'0']++; } if(sum%9==0) { cout<<"YES"<<endl; return; } ll num = stoll(str); ll mod = num%9; ll x = mp[2]; ll y = mp[3]; ll mod1 = x%9; ll mod2 = y%9; for(ll i=0;i<=mod1;i++) { for(ll j=0;j<=mod2;j++) { ll a = 2*i + 6*j; if(a==9-mod) { cout<<"YES"<<endl; return; } else if((sum+a)%9==0) { cout<<"YES"<<endl; return; } } } cout<<"NO"<<endl;~~~~~
First of all, when you want to share a code share it like this
string str; cin>>str;
ll sz = str.size();
ll sum=0; map<int,int>mp; for(ll i=0;i<sz;i++) { sum+=(str[i]-'0'); mp[str[i]-'0']++; }
if(sum%9==0) { cout<<"YES"<<endl; return; }
ll num = stoll(str);
ll mod = num%9;
ll x = mp[2]; ll y = mp[3];
ll mod1 = x%9; ll mod2 = y%9;
for(ll i=0;i<=mod1;i++) { for(ll j=0;j<=mod2;j++) { ll a = 2*i + 6*j;
if(a==9-mod) { cout<<"YES"<<endl; return; } else if((sum+a)%9==0) { cout<<"YES"<<endl; return; } }}
cout<<"NO"<<endl;
or like this 295180304
You're probably getting an error because of this line
str has $$$10^5$$$ digits and c++ only allows 19 digits at most .
i see you used num to calculate modulo 9 you can callculate the sum of digits modulo 9 instead
295219248
Actually IDK how to share code in comment. It's my first time.
I fixed how u said. Got WA in TC 3
What i said was to fix the runtime error . But for the WA it's probably mod1 and mod2 because they don't make any sense to me.
This would work. 295266464
Or
295267641
.
hello, could you kindly explain why taking x = x%9 would not work?
295079165
I tried the above using the property where sum of digits of number divisible by 9 -> number is divisible by 9, then applied the logic to increase the sum to a multiple of 9, but unsure why it fails test 3?
The number can't fit in long long as it's length can be as high as 100000, you have to store it as a string.
I see. Then would inputting in a string then summing up with a ll work?
Yup, you can sum up the individual digits from the string and continue with the rest
spent 1 hour in C bc i forgot a (+9) before the %9 could have done 5 or 6 god
it goes for me too, my first observation that just sum of even num can be the answer since 6 and 2 is even:_) how dum of me
I got the right observation "fast" then I coded wrong and thought my logic was off spent 30 minutes just to find the missing +9 lol
My first contest. Solved A, C, D wasted 1h on B .. all wrong submissions:( I think I would be able to solve this modulo queries.... upsolving during the weekend to see ;) Wondering what will be my initial ranking after this contest
Same! B was very hard or has a very weird idea
sometimes, condition problems are easy but this time it needs some observation:_). solved 4 probs, accept newbie this time again:_)
I almost jumped to reroot dp for G.
I was close to AK this contest and it would be my first ever AKed contest, but I couldn't solve $$$F$$$ 😢
can anyone explain how to solve $$$F$$$ ?, thanks in advance ^_^
a is congruent to b modulo m if and only if m divides a-b. so, each query justs asks you to find the gcd of the elements in the range [l,r-1] in the difference array, which can be done with a segment tree or a sparse table
that sir is exactly how i did F.
__gcd over differences of adjacent elements.
i.e., __gcd(A(l+1)-A(l), A(l+2)-A(l+1)..., A(R)-A(R-1))
I did just that, can you tell me why my solution fails?
https://mirror.codeforces.com/contest/2050/submission/295117653
i just ignored same and pre idk what is that. just did if l==r print(0).
I was trying to handle the case when all $$$a_i$$$ for $$$l<=i<=r$$$ are equal and failed miserably at that, for some reason I thought that segment tree will give a wrong answer in that case :(
Thanks though
I did the same mistake thinking segtree (i used sparsetable) would give wrong answer for the case that all elements are same. Then, I implemented mo's algorithm to compute number of distinct elements for all queries and somehow i managed to get AC. (i got hacked)
Try to think of solution, when $$$r-l=1$$$
the answer would be $$$\max({a[l], a[r]}) - \min({a[l], a[r]})$$$
Yeah, now try to extend segment and find how the answer changes
all Ai mod M equal means, for some Li, Ai = M*Li + rem (same remainder when divided by M). suppose take 3 elements, A1 A2 A3. (A1 — A2) = M*(something), (A2 — A3) = M*(something). from this (A1 — A3) = M * (something). so i concluded that if adjacent elements differ by a multiple of M all the pairs will also differ by a multiple of M. (what is the maximum value we can choose ? gcd(all adjacent differences). can be implemented using a segment tree for [l, r]
Segment tree doesn't work ,it has to be a sparce table because of the O(1) query and the time limit.
How would you calc $$$\gcd(x, y)$$$ in $$$O(1)$$$?
no GCD is logarithmic .
sparce table calculates the GCD mostly in prerocessing and once in query so it's $$$O(log(n))$$$ foreach query but segment tree does it log(n) times in query so the complexity of a query in segment tree is "I THINK" $$$log^2(n)$$$ .
Actually, since we are calculating gcd over the calculated gcds, it could be more fun.
Tighter time complexity for GCD
both of them works
segment tree submission
sparse table submission
both of $$$O(n + q)$$$ and $$$O((n + q) * log(n))$$$ solutions are accepted and fits in the time limit
https://math.stackexchange.com/questions/1549709/find-every-k-such-that-arrik-is-equal-for-each-arri
bruh just use gcd(a,b)=gcd(a,a-b) (grade 6 math) and you can solve it :D
Same with me :')
B was so much frustrating. at the end I solved it because I solved something similar before . also C I solved it with dp which should not be the intended solution
Thank you very much for the round. Good problems. Will not be reaching Specialist I guess, that's the only sad part.
how to do D
It is bruteforce. For any $$$i$$$ only the next $$$10$$$ numbers can take that place since others would get reduced to $$$0$$$ before it reaches $$$i$$$ th position.
i am so dumb
Same.
For every digit of the number try swapping it with at most 10 next digits one by one and check which swap makes the maximum digit value.If no swap can make the current digit larger then no swap will be needed at all.At most 10 next digits approach always works because after every swap a digit gets decremented by 1 so after 10 swaps the digit will be converted into the least possible digit(0).
problem b and c felt really weird
Next time try thinking maybe
Thanks for the suggestion..
I am and I just stated facts deal with it
interesting tasks, thx
when do the solutions appear for this contest?
i think A and B were cool and appropriate for their positions, C was a bit too easy if you were able to get the solution quickly, and probably impossible otherwise. D was weird, but it has the same problem as C i think. E was a very educational dp for div3, and as someone who struggles with dp, i found it very fun. i dont think segment tree/sparse table should be included for div 3 contests(althought i might just be salty because i couldnt ak the contest because of those), so i think F was a bit misplaced. and G was amazing, and it was a ton of fun to solve. great contest overall, and i found it very fun to participate. :D
I got the solution for C quickly and spent 1 hour in it bc of a missing "+9" b4 a %9 lmao
Same here. I had to write all the if-else statements because of that shit
lolll you still managed to do 5, i should've skipped it and done other questions instead of spending that much time on this
No i did 4 only. I could'nt solve E in the contest because I suck in DP.
can you explain c please.
For a number to be divisible by 9, the sum of its digits has to be divisible by 9. The only digits you can change are 2 and 3. If you change 2, you add another 2 to the sum, and if you change 3, you add 6 to the sum. You can now iterate over the amount of 2s in the number, and for each fixed amount of 2s, calculate if there is a number of 3s that you can change so that you can get a number divisible by 9. Its actually sufficient to check if adding 0,1 or 2 3s is enough, since the sum%9 will be periodic after that. The complexity is O(cnt2), but it can be done in O(1) as well
Thank you!
My intuition for C is based on the divisibility rule of 9 ( if the sum of digits of the number is divisible by 9, then the number itself is divisible by 9). So If that is the case initially, we don't need to do any thing. Otherwise, we can only convert all 2s in the original number to 4 (+2 to the total sum) or convert all 3s in the original number to 9 (+6 to the total sum) or convert some of the 2s and some of the 3s and each time check if the resulting sum is divisible by 9.
I thought the exact same thing...add +2 and +6 to the intital sum...but i was just too dumb to implement it and code it.
I just wrote all the cases and it was so dumb that took me almost 20 minutes.
will you reach specialist in this contest? genuinely asking cuz i have seen your comment in a lot of contest blogs and i would personally feel good if you reach specialist,personally i am trying to reach atleast 1000 pts but i always choke!!!
No I won't. Not in this contest. Look what delta I got in previous contest 💀
Keep practicing more 900-1100 problems and you'll reach 1000 in no time.
ohh no...well good things take time lets keep going:)
that's correct!
how to prove it wont get hacked?
Why would it get hacked? The rule is correct that in order for a number to be divisible by 9, its sum of the digits must be divisible by 9. Now, if the sum is not 9, then look what is the minimum required number adding which will make the sum divisible by 9. Notice that you can only change digits 3 and 2 only. The greedy solution would be to process 3-s first then 2-s, because subtracting 6 (3 * 3 — 3) now would make more room for 2 (2 * 2 — 2).
It is the brute force solution, so it is not missing any cases
i thought this could lead to tle, since we are iterating on frequency of 2 and 3, but frequencies can be high, as per constraints. What is time complexity of this code?
Yes, worst case of (counts(2) + counts(3)) can't exceed size of n, so the number of operations is linear to the size of the digit. Anyways, I guess this is not the best way, there is a better way using modulo.
You only need to enumerate 2s in [0, min(cnt_2, 9)] and 3s in [0, min(cnt_3, 9)]
man wtf... Sometimes I just can't solve a problem during contest, but 0.0001 secs after contest ends, I immediately know the answer for some reason?? Anyone else experienced this? It happens to me pretty often, wtf is up with that
Happens pretty often
Same here, honestly! I think it's because when the contest is about to end, we go into overdrive, speed-running and giving it everything we've got. It's like our brain hits peak performance under pressure. And then, right after the contest ends, all the clarity suddenly floods in. It’s wild how that works sometimes!
Damnnn it was too easy...
is it a string round?
I honestly did not enjoy the earlier problems being so implementation heavy. I had much more trouble doing A-E rather than F,G.
I do not know how I solved b. I guessed my way to AC. Can anyone please explain why this works? This is my submission 295089033.
for the numbers with same parity you can always redistribute them in any way you want so if you can redistribute even numbers and odd numbers in a way that every number is equal the answer is "yes"
you can not transfer any amount between indices of opposite parity
you can transfer any amount between any indices of same parity
use above two facts to figure out solution.
I am sorry I don't understand what you mean. Can you explain in a bit more detail please?
assume there is a queue of alternating men and women
a men can give money as well as take the money from any other men
same goes for women
let $$$M$$$ be the total money men's have and $$$W$$$ be the total money women's have
so if average money for men ($$$\frac{M}{no \ of \ men}$$$) and women ($$$\frac{W}{no \ of \ women}$$$) is equal then answer is yes
Can someone find the mistake in my below code for G?
https://mirror.codeforces.com/contest/2050/submission/295071112
Perfect div3 doesn't exi.. Nevermind
Has anybody done D with segment tree?
I think this is a speedforces. ABCDE — normal, but F is very easy on his place. I think, F maybe to move on D-place or E-place. G — cute task, but i cannot to debug my code....
problems were very satisfying to solve. Great div3 despite being bit tougher than avg div3.
I have a question who soled B. Did u guys seen this kind of problem before and that helped OR u came up with the solution in the contest?
I guessed it from the sample test cases and solved it during the contest.
Usually in these types of "applying operation" problems, it is useful to think of some invariant which will not change after applying the operations or changes in a more "simpler" way which is easy to tackle. For example, in this case, the sum at odd and even indices does not change.
I thought of the whole array sum that will not change so the number at the end must be (sum/n) if sum%n !=0 print NO otherwise I convert each number from left to right to (sum/n) by doing the operation and then check the whole array
You solved the problem for the case when the operation is applied on index i and i+1. Tweak it a little bit and you can get this one too.
For G
5
2 1
3 1
4 3
5 2
Here if we remove vertex 2 and vertex 3 , we end up having 3 connected components , but the ans for this test case is 2. Where m i going wrong ?
You don't just remove vertices 2 and 3 but all vertices on the path from 2 to 3. In this case, removing that path leaves just 4 and 5 in disconnected state. Hence, 2 components.
My fault . I misread the problem
How unfortunate that problem F is literally the same as this problem: https://mirror.codeforces.com/problemset/problem/1549/D (P/S: I don't intend to criticize anyone because having the same idea as the old problems isn't rare, it is just that I really want to point this out)
agreed +1 upvote =))
Well they were not exactly same but had the same idea. I could solve F yesterday as the earlier problem, which I solved earlier, instantly clicked after reading the statement
I spent over 40 minutes on C trying out different logics and debugging my code because it was getting WA on test 3. It's only at the very end that I realized that the intended input type for n was string because it wasn't explicitly mentioned in the problem.
Why isn't it being submitted for integers? When I test the cases in my editor, everything works perfectly. I don't understand. Could you please explain?
I didn't read the question properly during the contest. The length of n (number of digits) is specified to be a maximum of 1e5 whereas int can handle a maximum of 32 bits number (roughly around 9 digits) and long long 64 bits which are way below the possible value resulting in WA for bigger numbers. The samples given fit in int that's why it gives correct output.
During contest I got Idleness limit exceeded on test 1 verdict 295079719. That is weird because it's the first time I have that error on a non interactive problems. I think the problem is the case where n == 1, because the difference array will have length 0. But the more weirder thing is that it works on my local machine.
So my question, is it because the difference array is empty, or is there another problem with my sparseTable that cause the error?
i dont know about sparse table but, code running locally but not on cf server happened to me many times and that was mostly because of indexing errors.
what you guys think will be the rating distribution on the problems? B a little bit hard to be a 800/900 right?
may be 1000, just need some observation
G was best :)
Thank you for the problems
is the standing table based on the total penalty score ? or other things involved ?
for question D why this code give tle ? can someone tell ?
j<=min(j+9,n)should bej<=min(i+9,n)Yeah got it
man i got stuck in problem B.im fkd
StringForces???
uhh..GPTforce actually, Like this one
Why are you sure it's a GPT-code? seems pretty natural
His initial submission on G His initial submission for the G problem differs significantly in coding style from the code I provided, such as whether there are spaces around assignment statements or the way variables are named. Either he used a tool like GPT, or someone else wrote the code for him. In any case, I believe he is cheating.
Problems of contest are so interesting also not pure math.I enjoyed
pskobx Vladosiya, the validator for D doesn't match the problem constraints. The problem doesn't specify that the given string must be a valid integer, but the validator denies strings like "01". The problem is about making lexicographically largest string, so it has no reason to be a valid integer by itself at all.
Although I can't see the full validator message I assume the full regex is about accepting valid integers only. I hope it gets changed.
You're right, strings should be considered as strings here. All hacks with verdict "incorrect" will be rejudged soon.
Thank you. Also maybe consider adding a test with several such cases?
Actually, the Russian statement specifies that the string does not have leading zeroes, so the validator was designed to check this. In this case, we need to revert the validator to a stricter version and update the English statement accordingly.
Well, that makes me sad. Can't be helped though.
how so solve g? i think its dp but i dont know how to do it
Notice that the value of (a,b) is just $$$(\sum\limits_{x\in Path(a,b)} deg_x-2)+2$$$.
Good content
Look at the submissions by Dima393SF and cemenkovich_kloun. Them submissions are very equvalent. I think, they are cheating. Please, ban them.
Sorry, my English is very bad.
Wtf. Why no reaction?
Yesterday I gave the codeforces div 3 contest and I did 1 question but I don't get any rating for that question.
It takes time to update it will be updated
How much time it generally takes for update
Well for the past contests that I have given none of them took more than 1-2 days so u can expect it to be updated till tonight
Thnx for reply
I hope participants like KMO will be banned cause solving A in 1 minute and C in 1 minute right after this is not impossible, it is hilarious considering the history of his participations in previous contests.
How on earth does someone go from 2000 to 1 in 3 days !?!?
System test is finished but why my solutions are still in queue?
It took me 36 contests but I've finally reached Pupil. Let's go!!!
Greatest div 3 of all times
What should be the difficulty level of E? I do not trust Clist.
its standard dynamic programming. 1400-1600.
Ahh..so good to see so much progress!!
remains leet
div 3 or 4 doesn't worth anything for a pupil or a newbie because of this, either you aim for div 2 C which can sometime place you in top 2000 or you need to AK div 3 and 4 there is no in between
blud really didn't read the next sentence
295391659
for problem C why is this giving WA on TC 3.
Possibly cause you are taking input in int n; take input in string and count the number of twos & threes, I have done this here: 296303837
Dear @MikeMirzayanov,@Kaushal_26,
I have received a plagiarism notice for my solution to problem 2050D in Codeforces Round 991 Div 3. I was surprised to see my submission flagged, as I wrote the solution independently and based on my own understanding of the problem.
I would appreciate it if you could kindly review my case and clarify why my submission was flagged. If necessary, I am happy to provide additional details or evidence to support that my solution was original.
Thank you for your time and consideration.
Regards, [_shrink]
Is there any contest in Division 3 with in two days