Hi Codeforces!

We are happy to invite you to take part in Codeforces Round #561 (Div. 2). The contest will be held on 17.05.2019 18:05 (Московское время).

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.

That's sounds good.

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. Hopeyou willDid you?

No i was only able to solve first. Although I was so close to second. Still I am looking forward for next competition :)

I hope u will perform well in the next competitions. Good luck!!

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

Great week for Codeforces. Three Contests

Good Chance for newbies

Thank you, i hope it'll be a nice and challenging round.

I Hope the statement will be short and nice like the announcement .

++

Auto comment: topic has been updated by juckter (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

Is there any plan to announce the scoring distribution?

Thanks for div2. I want to be Master.

That's hurt

Everyone wants to be a Master. What's different about you?

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.

.......

You were trying to make a joke and you got buried with 23 downvotes. Not the best joke, but 23 downvotes, really CF ?

where is score distribution

contest ends after 1st hour for the ones whose rating is below 1600. p.s 4th and 5th question are tough!!

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

1166C - A Tale of Two Lands remind me of gravity falls :D

is que. E having a trick!

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...

How are you practicing now?

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://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://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://codeforces.com/contest/1166/submission/54311053 thanks.

Sad story!Next time,i will solve more problem

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 pair`

how does this generalise for

`n > 3`

?Number of (unordered) pairs of

`n`

elements:`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).

for 3 chatty students pairs would be (1,2),(2,3),(1,3)..

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 ?

i think u have just explained problem 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.

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.

Collections.binarySearch() is of no use when finding index if there is repetitions.

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

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.

Never mind, it's my bad, my code is throwing an error.

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

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 juckter (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 juckter (previous revision, new revision, compare).I kinda turned into genuis the last couple of rounds, it seems that the strategy solve C first seems to work.

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 least1 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.

Un Poco Loco.

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/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.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)