### juckter's blog

By juckter, history, 7 days ago, ,

Hi Codeforces!

We are happy to invite you to take part in Codeforces Round #561 (Div. 2). The contest will be held on May/17/2019 18:05 (Moscow time).

You will be given 6 problems and 2 hours to solve them. The round will be rated for all contestants with rating below 2100. As usual, participants from the first division are welcome to join out of competition.

The problems were written and prepared by Jefe and me. We owe a huge thanks to KAN for coordinating the round, to lewin and mohammedehab2002 for testing, and of course, to MikeMirzayanov for the great Codeforces and Polygon platforms.

Good luck and have fun!

UPD: A huge thanks to neal, dreamoon_love_AA, and antguz for help with additional testing.

UPD2: Thanks for participating! System tests have finished. Congratulations to our winners!

Div. 2

Div. 1 + Div. 2:

Editorial will be available soon.

UPD3: Editorial is up!

•
• +334
•

 » 7 days ago, # |   +44 A lot of rounds recently! That is awesome!
•  » » 5 days ago, # ^ |   0 But the next round is after 2 weeks. That is not awesome.
•  » » » 5 days ago, # ^ | ← Rev. 2 →   +3 I suppose next round will be earlier than in two weeks. It just hasn't been announced yet.
•  » » » » 5 days ago, # ^ |   0 That's sounds good.
 » 7 days ago, # |   -20 Hope I become CM after this round.
 » 7 days ago, # |   -57 Hope it will be harder than before
 » 7 days ago, # |   -8 i wish i could solve 2 or more problems this time :)
•  » » 7 days ago, # ^ |   +6 3. Hope you will
•  » » 5 days ago, # ^ |   -10 Did you?
•  » » » 4 days ago, # ^ |   -7 No i was only able to solve first. Although I was so close to second. Still I am looking forward for next competition :)
•  » » » » 4 days ago, # ^ |   0 I hope u will perform well in the next competitions. Good luck!!
 » 7 days ago, # |   +33 hope is a good thing..
•  » » 7 days ago, # ^ |   0 absolutely right . I was waiting from last 6 months to become colorful. Finally i did it.
•  » » » 6 days ago, # ^ |   +36 Grey is a color.
•  » » » » 6 days ago, # ^ |   +50 please try to understand my emotions not my words.
•  » » » » » 6 days ago, # ^ |   -32 ahaHAHAHAHAHHA
 » 7 days ago, # |   0 Great week for Codeforces. Three Contests
 » 7 days ago, # |   0 Good Chance for newbies
 » 6 days ago, # | ← Rev. 2 →   -7 Thank you, i hope it'll be a nice and challenging round.
 » 6 days ago, # |   +29 I Hope the statement will be short and nice like the announcement .
•  » » 6 days ago, # ^ | ← Rev. 3 →   -52 ++
 » 6 days ago, # |   0 Auto comment: topic has been updated by juckter (previous revision, new revision, compare).
 » 6 days ago, # |   0
 » 6 days ago, # |   -26 round done by weeb... ... ..... .. ....... .... ... i am scared to try it!!
•  » » 6 days ago, # ^ |   0 How come you haven't been blocked yet? I intentionally commented about 10 bad comments and Codeforces already threatened me.
 » 6 days ago, # |   +16 Oh Mexico Round SMT new
 » 6 days ago, # |   +6 Is there any plan to announce the scoring distribution?
 » 6 days ago, # |   0 Thanks for div2. I want to be Master.
•  » » 6 days ago, # ^ |   0 That's hurt
•  » » 5 days ago, # ^ |   -8 Everyone wants to be a Master. What's different about you?
 » 6 days ago, # |   -21 I know , U know, what if I told u...
•  » » 6 days ago, # ^ |   -12 Nobody likes my singing except me?
 » 6 days ago, # |   +68 I will try to do screencast with live commentary in English. If everything will go smoothly, you will be able to check it out on my YouTube channel some time after the round. Warning: English will be bad.
 » 6 days ago, # |   +21 So what's the score for each problem?
•  » » 6 days ago, # ^ |   0 So what's the score for each problem?
•  » » » 6 days ago, # ^ |   0 Do not copy what I say please.
•  » » » » 6 days ago, # ^ |   -15 Sorry,I want to know it too.
•  » » » » 6 days ago, # ^ |   -15 Do not copy what I say please.
•  » » » » » 6 days ago, # ^ |   +5 .......
•  » » » » » 5 days ago, # ^ |   -8 You were trying to make a joke and you got buried with 23 downvotes. Not the best joke, but 23 downvotes, really CF ?
 » 6 days ago, # |   +3 where is score distribution
 » 6 days ago, # |   0 contest ends after 1st hour for the ones whose rating is below 1600. p.s 4th and 5th question are tough!!
•  » » 6 days ago, # ^ |   0 D (4th) is a nice problem, I spent too much time with little bugs and post my only solution at last 7 secs, WA at TC 5. Perhaps next time I'll able to solve my first D in Div 2 xD
 » 6 days ago, # |   +5 1166C - A Tale of Two Lands remind me of gravity falls :D
•  » » 6 days ago, # ^ |   0 is que. E having a trick!
 » 6 days ago, # |   +1 I was glad that the problems seemed good to me, but actually from my extra registration I can't submit my code, and it just alerts "You have submitted exactly same code before", though I didn't succeed to submit anything... Lost the chance to climb up qwq
 » 6 days ago, # |   0 Good Contest.
 » 6 days ago, # |   +3 TestCase 12 for C?
•  » » 6 days ago, # ^ |   +4 If I'm not mistaken, test case #12 for C is the test where the answer is bigger than 2^31-1.
•  » » » 6 days ago, # ^ |   0 I was handling it. Let me check again. :/
 » 6 days ago, # |   +16 Yay! A chance to be master if system tests won't reject me :P
•  » » 6 days ago, # ^ |   0 congo...
•  » » » 6 days ago, # ^ |   +22 Thx! Took me 3 years :D
•  » » » » 6 days ago, # ^ |   0 I m struggling in green and grey...:'(
•  » » » » » 6 days ago, # ^ |   +9 It has been only 3 months you have been participating! See my rating graph and look how I was struggling in newbie. By the way, I was newbie when I changed to that handle ;)Just choose a good practice way and reaching to expert is really easy after having enough experience and algorithmic skills.
•  » » » » » » 5 days ago, # ^ |   0 Right bro, @PikMike is also good example like you...
•  » » » » » » 4 days ago, # ^ |   0 How are you practicing now?
•  » » 6 days ago, # ^ |   0 You can't even imagine how much I understand you ;)
•  » » » 6 days ago, # ^ |   +8 Well, you also had some time in the very top of CM so I think that means a real potential to be master in the next contests! Good luck!
•  » » » » 6 days ago, # ^ |   0 Thanks XD !!!Hold tight your new rank! ;)
 » 6 days ago, # |   +3 Mathforces???????????????????????????????????
 » 6 days ago, # |   +35 I need proof for E
•  » » 6 days ago, # ^ |   0 How to solve E?
•  » » » 6 days ago, # ^ |   0 Necessary condition for the solution to exists is : Any two days must have a store in common. Seems like, it is the sufficient condition too.
•  » » » 6 days ago, # ^ |   0 This is really intuitive solution, which I came up with in last five minutes: iff there's any element that are contained in all $m$ days, you can make the number extremely big prime so that you will get larger LCM. Is it true?
•  » » » » 6 days ago, # ^ |   0 seems to be false, sorry
•  » » » » » 6 days ago, # ^ |   +1 Counterexample = 2 3 5 with her buying (2,3) (3,5) (2,5) from stores.
•  » » » » » 6 days ago, # ^ |   0 This is true (it's sufficient), but it is not necessary. Other cases can be valid as long as there is no pair of days on which Dora visits two disjoint sets of stores.
•  » » » » » » 6 days ago, # ^ |   0 So it's "if" instead of "iff". I was wrong anyway.
•  » » » » 6 days ago, # ^ |   0 An example that your argument is not holding for "only if" 3 4 2 1 2 2 2 3 3 1 3 4 Valid sequence :7 5 7 2
•  » » » 6 days ago, # ^ |   +13 Check if for any $2$ different days sets of shops Dasha visited have nonempty intersectionBut I don't know how to prove that it's a sufficient conditionActually, I just submitted that because I saw how much people got it accepted, so it has to be something really stupid O_o
•  » » » » 6 days ago, # ^ |   0 I did the same thing... didn't believe it will actually work...
•  » » 6 days ago, # ^ |   +62 Let's take $m$ different primes, one for each query. Start with array of 1, and then multiply all the numbers in one query by the prime of this query. In each query LCM of our numbers will be product of all primes and LCM of all other numbers will lack prime of this query.Of course, this is true when all queries are pairwise intersecting.
•  » » » 6 days ago, # ^ |   -8 Uhh, I am very dumb, thank you
•  » » 6 days ago, # ^ | ← Rev. 2 →   0 If there exist two disjoint sets, answer is obviously no. If every pair has common element we can do the following: First set all numbers to one. Lets consider one set: a1,a2...aS. We may multiplay all numbers a1,a2...aS by arbitrary large prime number. It will guarantee us that this set is correct. On the other hand, we dont make our situation worse, for other sets(days), i think it is clear why ( from definition of LCM).
•  » » 6 days ago, # ^ |   +2 If on any day the set of stores visited by Dora is a subset of the set of stores visited by Swiper on any other day then it is impossible, else it is possible.
 » 6 days ago, # |   +8 ALL THE PROBLEMS WERE BEAUTIFUL EXCEPT FOR C
•  » » 6 days ago, # ^ |   0 why not C?
•  » » » 6 days ago, # ^ |   +5 All you have to do is just divide into cases and apply long boring deformations. (well maybe I'm stupid enough that I didn't realize clever solution)
•  » » » » 6 days ago, # ^ |   +5 There is an easier solution. Let's assume $|a| \leq |b|$. Then this pair is good iff $|b| \leq 2*|a|$. Now sort the numbers by absolute value and do binary search. https://codeforces.com/contest/1166/submission/54294460
•  » » » » » 6 days ago, # ^ |   +4 You're absolutely right. It was me who was stupid. My comments above SHOULD be downvoted...
•  » » » » » 6 days ago, # ^ |   +1 You can do it in linear time too, with two pointers. If answer is right for |a| |b| pair, it is also right as long as we increase |a|.
•  » » » » » 5 days ago, # ^ |   +5 Simpler solution: https://codeforces.com/contest/1166/submission/54287780
•  » » » » 6 days ago, # ^ |   0 There is no cases. Sign of the number doesn't matter
•  » » 6 days ago, # ^ |   +12 ALL PROBLEMS WERE NICE.Thanks very much problemsetters.
 » 6 days ago, # |   +20 D is hard to implement.
•  » » 6 days ago, # ^ |   +9 Well, I didn't know my solution is $O(k^3logm)$ for each query before submitting it. Time to pray for not getting TLE :PWhat I did was choosing the numbers greedily (the maximum I can put).
•  » » » 6 days ago, # ^ |   +1 I did pretty much the same, but in O(k^2 log m) time...
•  » » » » 6 days ago, # ^ |   0 Yeah, doing in that was is easy but I thought mine solution was fast before sending it :(
•  » » » » 6 days ago, # ^ |   +3 same but in O(k log m). :P
•  » » » » 6 days ago, # ^ |   0 same and in $O(k^2)$ (strange...and it got WA on 6)
•  » » » » 6 days ago, # ^ |   0 Same but in $\mathcal O(k)$.
•  » » » » » 6 days ago, # ^ |   +5 Same but in $O(log(k))$.
•  » » » » » » 6 days ago, # ^ |   +15 Same but in $O(nothing)$.
•  » » 6 days ago, # ^ |   0 And I started with D only, took me 1 hr 40 mins, RIP rating.
 » 6 days ago, # |   +19 Constructforces :v
 » 6 days ago, # |   0 For question C what is going wrong with this approach? https://codeforces.com/contest/1166/submission/54311053 thanks.
 » 6 days ago, # |   0 Sad story!Next time,i will solve more problem
 » 6 days ago, # |   0 Is it just me or was problem A description confusing? I still don't get how three chatty students paired together are considered three chatty pairs, while two students together are considered one chatty pairhow does this generalise for n > 3 ?
•  » » 6 days ago, # ^ |   0 Number of (unordered) pairs of n elements: n * (n - 1) / 2. That's a well-known formula :)
•  » » 6 days ago, # ^ |   +3 From three students A, B and C, we get three pairs which are — (A,B), (B,C) and (A,C).
•  » » 6 days ago, # ^ |   0 for 3 chatty students pairs would be (1,2),(2,3),(1,3)..
 » 6 days ago, # |   0 how to solve E?
•  » » 6 days ago, # ^ |   0 The answer is possible if and only if there exists no pair of days on which Dora visits two disjoint sets of stores.The proof that no other cases work is trivial; the proof that all of these cases do is less so.
•  » » » 6 days ago, # ^ |   +5 Proof by construction -> for each set have unique prime and multiply all values visited on that day by the prime. Values start with 1 on day 1. Because each set contains its own prime and all primes of others, LCM in it will be maximum possible. On the other hand, if there is some value between stores that this set did not touch and its value is maximum possible, then it must contain all primes (I mean, number stored in it is divided by all those primes) and so each set contains it, contradiction, we said it was outside some set.
 » 6 days ago, # |   0 Problem C. Testcase:41 1 2 2What is the answer?
•  » » 6 days ago, # ^ |   +13 All of the potential values are guaranteed to be distinct, so this is an invalid case.
•  » » » 6 days ago, # ^ |   0 It never said they are distinct. "unordered pairs formed by two different elements", does not specify that, are two numbers distinct if they have the same value or different index? I went for the solution that counts such case just and it got accepted.
•  » » » » 6 days ago, # ^ |   +1 The second line contains n pairwise distinct integers...
•  » » » » » 6 days ago, # ^ |   0 Thanks, I see. It should be part of problem, not "Input" part then. I think, input is for constraints on sizes, not number properties.
 » 6 days ago, # |   +1 Thanks, Codeforces for another good round! Although, unfortunately, it will take a long time until the next round...
 » 6 days ago, # |   0 IMHO, problems D and E should have been valued equally. I didn't solve E, but I can see in the comments that there is a simple idea behind the solution (and more people solved it than D). On the other hand, D was a rather implementation-intense problem, it took 40 minutes to code the solution :)
•  » » 6 days ago, # ^ |   0 I came up with Idea for E but did not submit it, it looked too easy. Seems I had right solution tho. I'd not say the idea is simple, but implementation really is.
 » 6 days ago, # | ← Rev. 2 →   0 for problem D isn't is hold? Any number between lower bound and upper bound form by current state a solution can be find ,i just did binary search by this but failed
•  » » 6 days ago, # ^ |   -13 My solution to D relied on the fact that through messy casework, we can prove that two numbers x and y with |x| <= |y| form a valid pair if and only if |y| <= 2|x|. I thus created a vector containing the absolute values of all the datapoints, sorted this vector, and then did two pointers.
•  » » » 6 days ago, # ^ |   0 Aren't you people talking about C ?
•  » » » 6 days ago, # ^ |   0 i think u have just explained problem C..
•  » » 6 days ago, # ^ |   0 just found it was small mistake on bound ,modify it then got AC
 » 6 days ago, # |   +2 thx 4 fast testing)
 » 6 days ago, # | ← Rev. 3 →   +8 I read comments, many users have solved problem D with greedy algorithm. My solution is constructive, works in O(k^2) per query. I missed couple of minutes to submit:(((, but I believe I have a proof for my solution. Has anyone else solved it with a not greedy algorithm?UPD: It turns out that my solution was wrong :( sometimes it doesn't find any solution), which is a pity as my solution was quite beautiful.
 » 6 days ago, # |   -9 What is the point on setting too much math problems? >:(
•  » » 6 days ago, # ^ |   +6 Do you think that implementing boring algorithms is better than nice, math problems with short and clean code?
•  » » » 6 days ago, # ^ |   0 Yes. Precisely building your answer through hard thinking and combining algorithms is much prettier than just solving an inequation on paper and then passing it to boring code. This is not IMO but ICPC
 » 6 days ago, # |   0 Did anyone else solve E by constructing a DAG based on subsets, and checking for existance of topoloical order in that graph?
•  » » 6 days ago, # ^ |   0 This argument is valid, but I think you will need additional observations for dealing with memory issues (to make sure not too many subsets are being considered) It is enough to ensure that there are no conflicts — i.e, there are no set A and B of given sets, such that $A \subset B^c$. What you said is equivalent to this, but using some unnecessary subsets.
•  » » 6 days ago, # ^ |   0 ba iharke Paron Pashinyan
•  » » » 6 days ago, # ^ | ← Rev. 2 →   0 Barev, Robert Qocharyan. Inchqan el zarmanali chi xosqi uxix imastov :DDD
•  » » » » 6 days ago, # ^ |   0 Barev, lav es?
•  » » » » » 6 days ago, # ^ |   0 Kayfot:D
 » 6 days ago, # |   0 My first contest after a loooong time! Hello again Codeforces! ^^
 » 6 days ago, # |   0 Can someone tell me why I got WA on tc 20 for C 54289806
•  » » 6 days ago, # ^ |   0 Sorry, i cant understand java code completely, but did you count pairs {0,0}? It seems like not
•  » » » 6 days ago, # ^ |   +3 All numbers are pairwise distinct. {0, 0} won't appear.
•  » » 6 days ago, # ^ |   0 I have same approach and got WA on TC 20 too. I thought getting absolute values before sorting might cause a problem. Now testing with random small cases but haven't met a wrong answer. Only differences with not taking absolute values happens like that: For -3 3 our range is (0,6), but it should be (-6, 0). I'm not sure this might cause an error.
•  » » 6 days ago, # ^ | ← Rev. 2 →   +4 Collections.binarySearch() is of no use when finding index if there is repetitions.
•  » » » 6 days ago, # ^ |   0 That's it! I just put a condition for next item and it got accepted, and I met that same problem in another contest too. Hope next time I'll remember it
 » 6 days ago, # |   +79 When both you and the problem setter do the math wrong...
•  » » 6 days ago, # ^ | ← Rev. 2 →   0 How come in problem C for the test case 3: 2 0 1 The answer is 1? Shouldn't the answer be 0?
•  » » » 6 days ago, # ^ |   0 The answer is indeed 0.
•  » » » » 6 days ago, # ^ |   0 Never mind, it's my bad, my code is throwing an error.
 » 6 days ago, # |   +12 Did you guys know that a = b.flip() on bitsets changes value of b??? I guess I'm lucky to catch that bug while participating out-of-contest :D
•  » » 5 days ago, # ^ |   +5 I did the same thing :D 54300556
 » 6 days ago, # |   0 I recommend you two pointers method for problem C. In my opinion so easier way than binary searches.
 » 6 days ago, # |   0 Auto comment: topic has been updated by juckter (previous revision, new revision, compare).
 » 6 days ago, # |   -16 I cheated this contest and i am sorry for my behaviour, but i am still in the official list of participants and i think that i don't deserve to be in the official standings.
 » 6 days ago, # |   +23 It’s a pity that I didn't become winner of div.2 qaq~
 » 6 days ago, # |   0 Auto comment: topic has been updated by juckter (previous revision, new revision, compare).
 » 6 days ago, # |   0 I kinda turned into genuis the last couple of rounds, it seems that the strategy solve C first seems to work.
 » 6 days ago, # | ← Rev. 2 →   +25 I suggest from now on everyone who cheats to get last place in the contest as punishment, like i did and got -181.
 » 6 days ago, # |   -16 Codeforces must fix at least 1 contest every week. If possible 2-3 would be great!
»
6 days ago, # |
Rev. 3   -17

The second test case for D problem is wrong as it is clearly mentioned in the question that ri>=1

# juckter

•  » » 5 days ago, # ^ |   0 how is it wrong? The sequence only has one number so $r_i$ is not relevant.
 » 4 days ago, # |   0 Un Poco Loco.
 » 4 days ago, # |   0 Can someone please tell me why my codeis giving runtime error the only thing i did was to replace the first scanf for no. of test cases to cin
•  » » 4 days ago, # ^ |   +1 You shouldn't mix scanf/printf with cin/cout if you're using ios_base::sync_with_stdio(false); , removing that line would fix it. Also, this blog post is for round #561, not #560.
•  » » » 4 days ago, # ^ |   0 yes, thanks so much for you fast reply