Hello Codeforces!
I'm glad to invite you to participate in Codeforces Round 665 (Div. 2) taking place on Aug/21/2020 17:35 (Moscow time). The round is rated for users whose rating is lower than 2100.
All problems were mainly created and prepared by me, and I'd also like to thank:
adedalic for coordinating and reviewing the round,
AmShZ, coderz189, dorijanlendvaj, Osama_Alkhodairy, Mohamed.Sobhy, awoo, kdjonty31, TechNite, BledDest, saurabhyadavz, Retired_cherry, errorgorn for testing the problems and giving feedback,
MikeMirzayanov for Codeforces and Polygon platforms,
All users for participating in the contest!
You will be given 6 problems and 2 hours to solve them. The score distribution will be announced closer to the start of the round.
Good luck, and have fun!
UPD1 : Score distribution is 500 — 1000 — 1500 — 1750 — 2500 — 2500.
UPD2 : Editorial
UPD3 : System testing has finished. We hope you enjoyed the contest :)
UPD4 : Congratulations to the winners!
Div.1 (Out of competition)
- tribute_to_Ukraine_2022
- Egor
- jiangly
- Geothermal
- dlalswp25
- antontrygubO_o
- ashmelev
- Maksim1744
- Sugar_fan
- SSRS_
Div.2
adedalic coordinating round will be great!
35 hours before the contest and this still isn't on the home page. Hmmm...
That's the charm of secondthread.........lol
The blog was running on SecondThread ;)
Finally kdjonty31 become tester. congrats ! :3 link
Yay! Thanks. LMAO.
ᕕ( ՞ ᗜ ՞ )ᕗ
Love it. I keep my fingers crossed for you.
6 заданий на 2 часа и тестеры разных подразделений |=> хорошо подготовленное соревнование.
Спасибо всем, кто принимал участие в его подготовке!
Успешного написания!
6 tasks for 2 hours and testers from different departments |=> well-prepared competition.
Thank you to everyone who took part in its preparation!
Successful writing!
As a Tester, I would like to say that the problems are really interesting, also the statements are short too. Please upvote me now! :)
Love Short Statements
Hope for strong pretests and not shitty problems from blobugh!
Hard to hope for the latter
I cracked so hard and wanted to upvote your comment. But me being a man of culture did not want to destroy the auspicious number of upvotes on your comment :)
it went a little above. Had to downvote it. Sacrifices have to be made for greatness
<Mandatory tester comment./>
Also, the problemset's really nice and concise.
Congratulations..
Thanks lol! ＼(^o^)／
As a tester I would say that a good strategy will lead to positive rating.
i think he meant to say A and B are tricky so try out with C and D.
August:
In India — the month of holidays
In codeforces — the month of contests
We already have six contests and three more to go.
Thanks Mike and codeforces.
Augustforces
.
As a master, I hope you good luck and high rating!
As a master, give me contribution, please.
I gave you contribution.
As a master,saying something is better than contributing something.
WEll, How many contest holds in every month, at least ??
As a tester i advice you to read all problems :)
is it rated?
???
The round is rated for users whose rating is lower than 2100.
Can you read the announcement ?
This round is gonna be an amazing
I can relate xD
I can feel you bro, you can check my profile I've reached 1590+ many times but never crossed 1600, 1600+ rating is still a dream for me
I hope You’ll reach blue after This round
Are you a digon?
Oh boy! so we have a monogon here too it seems
Where do you learn these weird polygons ? I never came across these in my school/college.
But can monogon be also belong to polygon? :P
You are at 1599 right now, coincidentally, your profile picture also has a point on the border of the circle.
I'm in dilemma whether to wish you luck or not. If you cross 1600, your graph will lose the charm.
This same thing happened to me also
I can relate bro, I was closer than you xD
Hope for strong pretests.
protests are really strong these days
what is this meme ?
It's Pretest, not Protest. — the first comment hoped strong protests.
Понять-то они поймут, но здесь не политический митинг.
As a tester, this contest made me lose my will to live.
I hope that doesn't happen to the contestants after the contest..
But it did not kill your craving for contribution.
Glad to see specialists are also being accepted as problem setters. :)
*testers
You were a tester yourself weren't you?
YES Contigo KHALIYAR
Can I ask a question? What type of problems are you best at solving?
I wish I could say "relationship"
)
Korean contest! I love it! 반가워요 :)
오 한국말이 되네요
south or north ?
South! i've never seen North Koreans in codeforces yet
There are north Koreans in the ranking though.
As a tester I recommend you to read all problems and wish you big positive deltas!!!
Thanks, really did helped as I skipped B to solve C first
hey bro nice nick
Let's hope the problem statements can be as short as this announcement.
Am I the only person who finds the username blobugh weird? Its like saying "Hi, I am Anus No. 1373"
P.S No offense intended though
Lets just hope that shit doesn't come out.
All hail to you brother! Keep rocking! kdjonty31
LMAO, Thanks! ;)
[..]
wow! there aren't too many testers...
Not as a tester, give me contribution
I had to post this, for 71 minutes the number of comments hadn't changed, a conspiracy.....???
Haha funi sex number i laughed, came, and had an epileptic seizure upon seeing this post. It is in fact so hilarious that after I showed it to my entire family they nearly died from asphyxiation because they couldn't stop laughing at this quirky post. I am currently at my mother's funeral, and the priest is unable to keep a straight face when he reads about the cause of her death.
I'm just happy my mom died with a smile on her face :)
Just asking, what's the point of the 'x' button if I can't remove them?
Just asking, Why do you want to remove these?
Why not? It's good to have a choice and I'd personally feel better after removing some or all.
You could remove them if you didn't make any submission.
I am scared about 5 page long queue . I hope MikeMirzayanov will fix it before the contest .
UPD — It is fixed now !!
Not 5 pages but hundreds of pages .. no submissions are judges for last 4 hours(which i saw ).
Where can you see the queue?
As a tester, this contest will be interesting and entertaining. Thanks, Codeforces.
надеюсь, ник автора контеста и качество задач не связаны
.
Only two hours left before the contest, score distribution should be published. blobugh
wishing all coderforces family luck and fortune . May god bless you all @Erica
I feel most of the downvotes are from newbies and pupils
.
This meme isn't new(actually, it's common), so it's likely to get downvoted.
WOW! E=F, WILL TRY BOTH!
speedforces
I suppose everyone here wants to learn. So the test cases must help us to think regarding the problem.
This is how you make a round.
When I'm sure my logic is correct but WA on pretest 2 (x4) @@
Problem 4
Problems are good but somehow I choked so hard on B
even i felt C was easier than B
At least you're not choke hard on "D" *IYKWIM
is it educational round or what? why problems havent any idea
What do you mean?
It's most possible boring math problems.
Problem D which decided the rank of majority was standard re-rooting. And I guess problem F was some modification of segtree but I haven't looked very seriously into the problem.
D was greedy and not re-rooting.
Of course it was. But at least in my solution, I used re-rooting to find edge weights.
You could have done it like this-
Ah yes of course.
#Always_ready_to_overkill
+1, I understand that maybe this problems can be Educational for Div2 but they seem uninteresting.. :(
I prefer this problem set. Only one I really thought was too boring was D, but better than having non-diverse round. ABC were even an ur style problems...
For me A was nearly as difficult as D
Will have to check the editorial to understand it lol
Imo C was easier than both A & B.
can you give a hint ?
Just sort the original array and check to see which ones are out of order, if all the ones out of order are divisible by the minimum element the answer is yes otherwise no.
I dont think sorting the array fits under the given constraints ( N<= 10^5 , T <= 10^4)
There is another constraint about max sum of N over all testcases.
SHIIIIIIIIIIIIT
What is wrong in this https://codeforces.net/contest/1401/submission/90583034
You need to compare objects using equals, not !=, even if it is Integer objects.
Thanks bro, But other answers using != are accepted
Maybe they use int[] instead of List ?
Just curious to know why it runs well on 7 5 2 2 4 but not on 1120 707 16
I don't know. Numbers smaller than 128 are somewhat special in Integer class, because Integer.valueOf(int) will return same Object for int<128. Maybe somehow that comes into play.
and I can't solve C, I'm too bad :(
After getting 4 WA in D, here are the cases to take care of.
Don't take mod of last greatest values when m > n — 1 and insert in list because mod might make the value smaller. Instead take product of those and add to our answer ASAP.
While computing how many times edge can be part of various paths, don't forget to take it as long long and also list as long long. And don't mod because again value might become smaller.
oh fuck I think I fell victim to both of these... RIP
Oh wow, I think now I know why my solution get WA
Shit..Too bad I couldn't figure out during the contest :(
for point 1, how about sorting p array first, then assigning the values, that way the array is always in sorted order, and no need to care of mod making the value smaller.
Can D be solved by the greedy method?
Yes
Yes, I think the author's solution bases on Greedy approach
Yep, greedily assign the maximum weight to the most used edge (found using dp to get size of subtrees)
Thanks, so it must be some silly mistake
hint —
DFS + SORT
Don't give hint , either tell full solution or don't , we can wait for editorials .What you are telling everyone knows.
My approach —
find number of times an edge is coming in a path.
(n1 elements)--(edge)--(n2 elements) => number of times = n1*n2 (I found n1 = number of elements in subtree of n1 and n2= n — n1)
and then fill max factor in maximum edge.
my sol — 90611208
I have used iterative DFS, because I thought I might get TLE.
Sorry to hurt you feeling bully....maguire
Completely exhausted after the contest. I got stuck in the 4th problem. There may be some property that will be used. A lot to learn this from contest. A NICE CONTEST with short problem statements!!
How to solve D :(
Wasted all the time with problem D pretest 5, finally I found that i am sorting after taking the numbers module mod :(
Same here :(
At least you realized it during contest ._.
LOL so glad to know I'm not alone
I had the same problem too but wasn't able to notice this. I even solved E mentally and would probably have had time to implement it if it weren't for this mistake. :(
I should have quit it too, but it's really hard to leave a problem solved by about 2K users and go to other harder problem :(
I've done this but still got WA5 90613994 :(
z.push_back((n - s[u]) * s[u]);Overflow will happen here, as both $$$n$$$ and $$$s$$$ are declared
int.lol, thank you!
Thanks for this comment, wasn't able to find the bug in my code until i saw this
ahhhh thanks! after 22 times getting WA on test 5 i just saw your comment. god damn it :(
Problems, at least problem statements, were too mathy/formal to my taste
It was pure math homework contest. I am surprised as how much people seems to like that kind of problems.
WitchOfTruth and spookywooky if you want to be good at competitive programming , trust me soling math problems will help you a lot .
Math problems per se may not be that bad, but here we had A-B-C three math problems in a row, And then D, which was not math, but the problem statement was so dry and full of formulae that it felt like one.
Great contest...
A round with two data-structure problems!!
And both of them will most likely have difficulty 2000+. So for most of the real div2 participants there were no ds problems.
F — press segment tree to win
But how to do? Lazy-tag can't work!!
Maintain left and right childs and a tag for each level if they have to be swapped. Reverse operation is same as swapping at all levels below current level.
Observation — order of the operations doesn't matter, so just write amount of each operation for each k. So when pushing from vertex, just look at the number of operations for the current level k. Swap is just swapping children, and Reverse can be done lazily.
Alternatively, notice that all operations are xoring the indices and segment tree works really nicely with xor.
Is it obvious?During the contest I doubted whether the order matters .:(
What was the logic behind C
Today for the first time I had to implement Segment Tree from scratch lol.
lol!
Yes problem A took me 11 minutes!!
I'm curious that how one would solve C? if the gcd of two element of array is not needed to be the minimum element of array.
I was stuck with this logic. But say array is 2, 8, 4 and you want to swap (8, 4), you can just swap (2, 4) (8, 2) and (4, 2) again.
Basically 4, 8, 2 -> 4, 2, 8 -> 2, 4, 8.
if gcd can be anything (i.e. no conditions on gcd) then according to me its always possible to sort the array, just like swapping every possible pair.
so true..then the problem will not even be considered as prob A
no I didn't mean that gcd can be anything it's like that the gcd should belong to the array but it's not need to be the minimum element of the array.
if you have one element whose gcd is always equal to min with others (like — minimum number) and those numbers if gcd != min are in right position than you can always arrange that array.
ex — 2, 6, 5, 4
if min = 2, and you want 4 to be in 2nd position, but gcd(6, 4)!=min, then you can
swap —
2-6 => 6, 2, 5, 4
2-4 => 6, 4, 5, 2
2-6 => 2, 4, 5, 6
what's wrong in this? https://codeforces.net/contest/1401/submission/90616241 (problem D)
Test case:
Correct answer: $$$1555$$$
Your answer: $$$95$$$
Why the answer is 95? we give the following value: 11*7*5 in the edge between 2-3, 3 in the edge between 3-4, 2 in the edge between 1-2; then answer should be 4*(11*7*5) + 3*(3) + 3*(2) = 1555; Correct me where I am wrong!
Yes, the correct answer is 1555, but instead of do 4*11*7*5 i did 4*11+4*7+4*5
you should consider the cases in which m is larger than n-1.
Like if you sorted after taking mod
I even didn't do that stil got WA. Please help to debug.
UPD: No need i got what i did wrong.
What if m>n-1
Thanks, I wish I would have realized this during the contest.
I kept on getting RTE on test 6 of D. Thanks a lot to python!
https://codeforces.net/contest/1401/submission/90611250
GCD is resounding in all directions ——when i solved D but not C and only 30 mins left
Solved F first and didn't have enough time to debug E :(
solution of C https://codeforces.net/contest/1401/submission/90579190
Without Reverse and Swap last problem is easy to solve)
Thanks for the good samples in F though
Can anybody tell me why my solution for D is failing on pretest 5? It looks like the logic is correct, comparing it to people who got it accepted. Submission link
Alright, so I realised my mistake, one of the arrays I had sorted after taking modulo. I crie. TT
What is the correct approach for problem E? I guess there would be some magical trick.
wingardium leviosa
are you really Dr Vishal Gupta from pilani?
Yes indeed. Why should students have all the fun.
Please help!
Can anyone tell me why I'm getting TLE on problem D? I switched to c++ from python recently and I really thought these things won't happen anymore :<<<
I really feel my solution is perfect.
Is it about memory allocations? Should I have created an array for the adjacency list instead of creating a new vector or something?
One of the submissions: 90617571
I think you should put vvi &adj instead of vvi adj in dfs()
You think that one copy made all the difference? Oh.. As I'm writing this comment, I realize every dfs copies it, because it's recursive :|
Well it was the first dfs problem I solved since switching to C++. There have to be some bumps in the road I guess.
You need to declare vectors given as parameters as references. Here, you copy the array adj each time dfs is called.
For problem D, do we have to greedily arrange the m factors on each edge based on which edge is most visited?
Yes!! But how will we know which edge is visited most? I was stuck in this part only!!
It will be equal to number of times a particular edge xan be used in a path from u to v which will eventually the product of number of elementsin the subtree and other the nodes As that edge will come only if you have a node other than the nodes in the subtree and the other node is in the subtree.
What's wrong with my solution for C? 90603416 I created a copy of the given array and sorted it. Next, for each index, if the elements in the original array and the sorted one aren't equal, I checked if their gcd was equal to the minimum element. If it is different, I print "NO", else "YES".
If the arr is 2, 8, 4, then the sorted array is 2, 4, 8. GCD of 4, 8 isn't 2, but it's still possible to fix this. Swap 2 with 4, swap 2 with 8, swap 2 with 4.
You need to check if it is multiple of min element, because that is enough. Every two multiples can be triple-swaped with each other using the smallest element.
I felt like a math exam, didn't like this contest at all
Amazing round ! Clear statements with no stories, hopefully strong pretests. This has to be one of the least constructive rounds I have seen in recent times on CF :)
EDIT: And fast editorial as well :)
Great contest :) No shitty stories
In C, i just took all elements which were not in the correct place after sorting in another array arr2, and found the gcd of arr2. whats wrong in this??
First: Find minimum element.
Second: Find elements that not in their place.
Third: Notice that we can swap any 2 elements using minimum element as a buffer, BUT, we wont be able to do that, if one of this two elements not divisible at minimum element.
So, u just need to check for every elements that not in his place, if it divisible by minimum element. If all is divisible: "YES", otherwise: "NO"
Query Party!
Stuck in Problem A. Orz
how to solve c????????/ please help
I won't tell you how to solve it directly, but I can give you 3 similar problems to today's C:
1) 432C - Prime Swaps
2) 1365B - Trouble Sort
3) 1148C - Crazy Diamond
my solve: we can never move elements, which are not divisible by min_of_array, so we should check if they are in their "sorted" place. Lets call other elements divisible. after that we can always sort the array with this logic: gcd(min_of_array, any divisible) = min_of_array, with that we can swap for ex min_of_array with the last element and then with min_of_array with max, with that iteration we decreased size of our array to sort by one (we sorted biggest divisble in its right place) and can continue with that logic.
also good problem to practice this kind of thinking is: Replace by MEX — https://codeforces.net/problemset/problem/1375/D
First: Find minimum element.
Second: Find elements that not in their place.
Third: Notice that we can swap any 2 elements using minimum element as a buffer, BUT, we wont be able to do that, if one of this two elements not divisible at minimum element.
So, u just need to check for every elements that not in his place, if it divisible by minimum element. If all is divisible: "YES", otherwise: "NO"
By "swap any 2 elements using minimum element as a buffer" I mean this. U have a1 a2 ... aN . A1 is minimum element (aM), GCD(aM,aX) == aM. So, if we want to swap aX and aY. We can do like this:
[aM,aX,aY]->[aX,aM,aY]->[aX,aY,aM]->[aM,aY,aX]
Could anyone help me,why is my solution for D is TLE. I think my answer is perfect. 90615633
pass the "tre" by reference in dfs function.Because in your code the vector is copying itelf everytime dfs is called
Had the exact same problem. Need to pass 'tre' as a reference (or do like all the experiences ones and declare it as a global variable).
Every time you call 'dfs' you copy the whole vector.
This was the first time I solved 2C and still am able to get a +3 according to predictor. :(
Can someone please tell me why this is giving RTE. link
In dfs function you are using int val = sub[x] * (n — sub[x]); but you shoud use long long int as it (sub[x] * (n — sub[x])) may exceed the limits of int
int is already defined long long in macros :)
Okay, I didn't see that earlier. But now I have found the mistake. for(int i = n — 1; i >= 0; i--){ cal[i] %= mod; factors[i] %= mod; int temp = (cal[i] * factors[i]); temp %= mod; ret += temp; ret %= mod; }
In above for loop you should start i with (n-2) not with (n-1)
okay got it...Thanks. But why my code didnt fail on pretest 1?
I am also wondering, why it was not failing on pretest1. But I didn't came up with any answers.
Can anyone detect why this code gave WA on pretest 2 in problem D , I am not able to understand the issue in it. 90570026
PS:- Finally done , I was missing case when m>n!
Off 5 blue participants in my friendlist 4 did not submit any solution. And the one who did won't be blue next contest.
how to check who took part and didn't submit?
On the contest page you can click the number which shows the participants to get the list of all registered ones. Then there is a friends button.
Same friends button is in standings table.
solved C but got stuck at B :(
Any small hints for problem E?
The editorial is the smallest hint as well as the complete answer .
problem c: n=5. 8 8 4 4 2 why the sample is correct? (this smaple printed "yes" in some codes)
Because 8, 8, 4, 4 are all divisible by 2 (the minimum), so they can easily be swapped to create a sorted array.
ok,i think so.I get it.Thank you.
For C , If input is n = 5
2 12 8 32 24
min = 2, gcd = 4, My ans : "YES" passed, actual ans should be "NO"
Answer is YES. cause using 2 you can swap any element .you have to find just 2 element gcd not all..
Did anybody else feel this contest was so smooth? I mean.. I got my "Wrong answer on pretest 2" the second after I made my submission. Kudos to the platform! Jokes apart, it was nice problem set!! Thanks overall!!
SO, what does the "1-s" mean ??? I didn't get it, so I lose Problem D. Can't you just write directly " 1s " or " '1's " ?
Thank you very much for uploading editorial this fast!!
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Those who are getting WA in D like me m can be greater then n , it have to be considered! I got WA in 2 facepalm!
During the contest, I submitted solution for F, but quickly realized that it works in $$$O(2^n \cdot q)$$$, though it was easy to fix so I resubmitted. But then I submitted initial slow solution after the contest again, and it passed systests! So I quickly hacked it 90619845 But I'm quite disappointed that systest didn't manage to break my initial slow solution(
when my rating was increased in last contest they updated it afer 6 hours or more and today my rating was going to decrease they updated it inside one hour
why?
My screencast of the round, where I start to give up on templates, horribly screw up D, continue my curse of never full-solving, and explain solutions for A-E
I have a new record !!! 2000+,I am waiting for your congratulations!!!!
Congrats!
Congrats!
congrachulasunzz
No announcement for any problems in the round is the best evidence to prove an expilcit and clear round.
It was unrated for me — rating change 0. lol
Same as 72 other people
.
You are saying that it has nothing to do with gcd just because you figured out how to solve it without explicitly finding any gcd?
Please help me why this solution get error out of bound at line 59?
Here is my submision 90686316
if i is max size of your vector, i + 1 will be overflow
Ah thank you so much.
please someone help me. I am getting Runtime error in TC 6 in Q.4("Maximum Distributed Tree"). here is my code in Python 3
Anyone with W/A on Problem D, test case 5, don't take mod while calculating the frequency of edges.
why the rating changes have changed ??
Thanks for the fast editorial. this was my second time to take part in codeforces rounds and I'm very happy that I managed to solve one problem at least.
Could someone help me figure out why am I getting Run time Error in 2nd test-case of Problem D. I have found one mistake of taking mod when i multiply the values and then sort, but that doesn't resolve the run time error[submission:90755994]. Thanks in advance!
Problem D: Maximum Distributed Tree
Can anyone please explain why my code is giving wrong answer on test 5? Please... Solution