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!
A lot of rounds recently! That is awesome!
But the next round is after 2 weeks. That is not awesome.
I suppose next round will be earlier than in two weeks. It just hasn't been announced yet.
Hope I become CM after this round.
Hope it will be harder than before
i wish i could solve 2 or more problems this time :)
3. Hope you will
hope is a good thing..
absolutely right . I was waiting from last 6 months to become colorful. Finally i did it.
Grey is a color.
please try to understand my emotions not my words.
ahaHAHAHAHAHHA
I Hope the statement will be short and nice like the announcement .
++
Auto comment: topic has been updated by Ari (previous revision, new revision, compare).
(https://imgflip.com/i/316rg9)
round done by weeb... ... ..... .. ....... .... ... i am scared to try it!!
How come you haven't been blocked yet? I intentionally commented about 10 bad comments and Codeforces already threatened me.
Oh Mexico Round SMT new
Всех с праздником
Это конечно хорошо, 21 век на дворе и так далее, но к чему это на этом сайте? или это тонкий юмор?
о каком юморе идет речь?
так и я не знаю, очевидно что-то мне непонятное с кф-ом? ибо как объяснить положительный рейтинг комментария ни коим образом не относящегося ни к этому посту, ни к этому сайту. Будем флудить разными поздравлениями дальше?
так ты же гей.................
Is there any plan to announce the scoring distribution?
Thanks for div2. I want to be Master.
That's hurt
I know , U know, what if I told u...
Nobody likes my singing except me?
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.
So what's the score for each problem?
So what's the score for each problem?
Do not copy what I say please.
Sorry,I want to know it too.
Do not copy what I say please.
.......
where is score distribution
1166C - A Tale of Two Lands remind me of gravity falls :D
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
Good Contest.
TestCase 12 for C?
If I'm not mistaken, test case #12 for C is the test where the answer is bigger than 2^31-1.
I was handling it. Let me check again. :/
Yay! A chance to be master if system tests won't reject me :P
congo...
Thx! Took me 3 years :D
I m struggling in green and grey...:'(
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.
Right bro, @PikMike is also good example like you...
You can't even imagine how much I understand you ;)
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!
Thanks XD !!!
Hold tight your new rank! ;)
Mathforces???????????????????????????????????
I need proof for E
How to solve E?
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.
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?
seems to be false, sorry
Counterexample = 2 3 5 with her buying (2,3) (3,5) (2,5) from stores.
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.
So it's "if" instead of "iff". I was wrong anyway.
An example that your argument is not holding for "only if"
Valid sequence :
7 5 7 2
Check if for any $$$2$$$ different days sets of shops Dasha visited have nonempty intersection
But I don't know how to prove that it's a sufficient condition
Actually, I just submitted that because I saw how much people got it accepted, so it has to be something really stupid O_o
I did the same thing... didn't believe it will actually work...
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.
Uhh, I am very dumb, thank you
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).
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.
ALL THE PROBLEMS WERE BEAUTIFUL EXCEPT FOR C
why not C?
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)
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://mirror.codeforces.com/contest/1166/submission/54294460
You're absolutely right. It was me who was stupid. My comments above SHOULD be downvoted...
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|.
Simpler solution: https://mirror.codeforces.com/contest/1166/submission/54287780
There is no cases. Sign of the number doesn't matter
ALL PROBLEMS WERE NICE.
Thanks very much problemsetters.
D is hard to implement.
Well, I didn't know my solution is $$$O(k^3logm)$$$ for each query before submitting it. Time to pray for not getting TLE :P
What I did was choosing the numbers greedily (the maximum I can put).
I did pretty much the same, but in
O(k^2 log m)time...Yeah, doing in that was is easy but I thought mine solution was fast before sending it :(
same but in O(k log m). :P
same and in $$$O(k^2)$$$ (strange...and it got WA on 6)
Same but in $$$\mathcal O(k)$$$.
Same but in $$$O(log(k))$$$.
Same but in $$$O(nothing)$$$.
And I started with D only, took me 1 hr 40 mins, RIP rating.
Constructforces :v
For question C what is going wrong with this approach? https://mirror.codeforces.com/contest/1166/submission/54311053 thanks.
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 consideredone chatty pairhow does this generalise for
n > 3?Number of (unordered) pairs of
nelements:n * (n - 1) / 2. That's a well-known formula :)From three students A, B and C, we get three pairs which are — (A,B), (B,C) and (A,C).
how to solve E?
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.
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.
Problem C. Testcase:
4
1 1 2 2
What is the answer?
All of the potential values are guaranteed to be distinct, so this is an invalid case.
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.
The second line contains n pairwise distinct integers...
Thanks, I see. It should be part of problem, not "Input" part then. I think, input is for constraints on sizes, not number properties.
Thanks, Codeforces for another good round! Although, unfortunately, it will take a long time until the next round...
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 :)
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.
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
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.
Aren't you people talking about C ?
just found it was small mistake on bound ,modify it then got AC
thx 4 fast testing)
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.
What is the point on setting too much math problems? >:(
Do you think that implementing boring algorithms is better than nice, math problems with short and clean code?
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
Did anyone else solve E by constructing a DAG based on subsets, and checking for existance of topoloical order in that graph?
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.
ba iharke Paron Pashinyan
Barev, Robert Qocharyan. Inchqan el zarmanali chi xosqi uxix imastov :DDD
Barev, lav es?
Kayfot:D
My first contest after a loooong time! Hello again Codeforces! ^^
Can someone tell me why I got WA on tc 20 for C 54289806
Sorry, i cant understand java code completely, but did you count pairs {0,0}? It seems like not
All numbers are pairwise distinct. {0, 0} won't appear.
Collections.binarySearch() is of no use when finding index if there is repetitions.
When both you and the problem setter do the math wrong...
How come in problem C for the test case 3:
The answer is 1? Shouldn't the answer be 0?
The answer is indeed 0.
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
I did the same thing :D 54300556
Моё решение по задаче А: link
Задача А из данного раунда имеет довольно простую идею, поэтому реализации разных участников могут совпадать или выглядеть, с точки зрения системы, довольно похоже: (link — author — MK_99).
Могу заверить, что свой код я не выкладывал в публичный доступ. (смысл сообщения — сообщение от системы о списывании)
I recommend you two pointers method for problem C. In my opinion so easier way than binary searches.
Auto comment: topic has been updated by Ari (previous revision, new revision, compare).
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.
It’s a pity that I didn't become winner of div.2 qaq~
Auto comment: topic has been updated by Ari (previous revision, new revision, compare).
I suggest from now on everyone who cheats to get last place in the contest as punishment, like i did and got -181.
Codeforces must fix at least 1 contest every week. If possible 2-3 would be great!
The second test case for D problem is wrong as it is clearly mentioned in the question that ri>=1
juckter
how is it wrong? The sequence only has one number so $$$r_i$$$ is not relevant.
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
You shouldn't mix
scanf/printfwithcin/coutif you're usingios_base::sync_with_stdio(false);, removing that line would fix it. Also, this blog post is for round #561, not #560.yes, thanks so much for you fast reply
Me during the contest:
(for those who don't know, they are pinyin for the Chinese words "yes" and "no" and I speak Chinese as a native language)