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
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...
Tread on me plz!!!（♡▽♡）
strange request.....
Freakyforces
non-Notorious Coincidence
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
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
is it possible to get high rating without an anime PFP?
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
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
Hopefully I can reach Specialist after this round. Good luck for me and for everyone.
StringForces
Forgot to add binary string problem :(
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
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$$$
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
This would work. 295266464
Or
295267641
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
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 \lt =i \lt =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 :')
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.
problem b and c felt really weird
interesting tasks, thx
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
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
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.
how to prove it wont get hacked?
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?
You only need to enumerate 2s in [0, min(cnt_2, 9)] and 3s in [0, min(cnt_3, 9)]
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.
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
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?
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
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?
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
for question D why this code give tle ? can someone tell ?
j<=min(j+9,n)should bej<=min(i+9,n)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$$$.
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?
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 !?!?
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
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