Hello, Codeforces!

We are excited to invite you to Codeforces Round 641 (Div. 1) and Codeforces Round 641 (Div. 2). This round will take place on May/12/2020 15:35 (Moscow time). In both divisions, you will have **2.5 hours** to solve **6 problems**. **Please notice the unusual time.**

Problems of this round were prepared by Rebelz, A.K.E.E., mydiplomacy and me BlueSmoke.

We would like to express our sincere gratitude to:

300iq, for responsible and interesting coordination;

WZYYN, Elegia, fsy_jiaxun_when, vintage_Vlad_Makeev, fpdqwq, wangziji, Suika_predator, wrg0ababd, AcF-_-FcA, Shuba_Buba, duyiblue, xiaolou0411, LiM_256, Hazyknight, need_some_change, djq_cpp, little_waxberry, for their hard-working testing and suggestions;

fantasy, for giving suggestions and support throughout the whole preparation of this round;

Glamorgan, for proofreading and polishing our statements;

MikeMirzayanov, for excellent Codeforces and Polygon platform.

We have made an effort to create interesting problems, strong tests and clear statements. Wish all of you good luck and have fun! Since the round **is rated**, we also wish you guys have huge positive $$$\Delta$$$ in this round!

**UPD: Tester list updated.**

**UPD: Tester list is updated again. Apart from that, score distribution is here:**

Div.1: $$$500+1250+1250+2000+2500+(1750+1750)$$$

Div.2: $$$500+1000+1500+2250+2250+3000$$$

UPD: Hey, it seems that Div.1 is really hard and has bad discrimination. And also, in some problems pretests are weak. We are sorry about our mistakes, and hope you will like these problems after reading editorials here: https://codeforces.com/blog/entry/77284

**UPD: Congratulations to the winners!**

Div.1:

Div.2:

Hope you have a nice day! Also you can view a blog by our tester Hazyknight about his opinions of this round: https://codeforces.com/blog/entry/77276

Since the round is ratedDon't jinx it.

Yes! For now, the round is rated. Round #639 participants and Monogon will get what I'm trying to say... xDxDxD Hopefully, the queues are short .... xDxDxD

I'm sorry, but I didn't find this comment funny.

Again seems like it was more of Mathforces competition!

Also, problem statements could be improved! They were confusing at first!

absolutely agree

Literally! We need to point out negatives and positives about competition.

It can't be one way! So, better point out negatives too! But I don't know when people will understand that, instead of downvoting.

Downvote if:

Its irrelevant

Its bullying someone

If something is unrequired and just for sake of upvotes.

But if it's a constructive argument (Be it negative or positive) Appreciate it!

This will be the first div 1/2 after a difficult period. Imagine the frenetic jubilation and the incredible tension of thousands of enthusiastic participants! I look forward to it.

As one of the testers, I believe that this round will be quite successful! :D

EI /qq /qq

By the way, color combination of the problem setters looks great, hoping the problems to be the same :)

Red and Orange make the folks happy !!As a tester，I would say that problems are awesome. There are no ugly geometry and big data structures! I bet you'll be really enjoyable after solving these problems. Even if you failed to solve that during contest, you'll learn a lot after reading the tutorial.

Care to DM me any more details about the problems? ;)

Sorry that's all I can say, hope you enjoy..^_^

There are no ugly geometryNumber Theory:

Allow me to introduce myself..Joking aside, the problems were interesting.

The main reasons why geometry is widely considered ugly are precision issues and edge cases (and the second one can be reduced by developing good habits). The less important reason is that because everyone hates geometry, noobs will also start hating geometry and people will learn geometry less.

Number theory has neither of these problems.

In fact, after your testing we have changed some problems. But I think that you'll also like these new ones. XD

I don't think it's legit to say anything about the problems nature even if it was that little. I know it won't probably make a huge difference, but I'm afraid it opens the door for testers to say more later.

It all started earlier with testers recommending to enter the contest and saying it has interesting problems, and now we are talking about problems' topics.

I agree, I prefer to know nothing about the problems at all so it doesn’t bias my thinking (but of course thanks to the testers for testing, I am sure the problems will be very interesting)!

Problems were very good anyways. Thanks for the contest!

Thanks

That'd be unfair for those who have no gain from it. Most people are comfortable with these timings and that's probably one of the reasons why CF Rounds are held regularly around 16:35 CET (20:05 IST).

He asked because this contest starts at unusual time. Its not 20:05 IST but rather 18:05 in Indian time.

Oh, my bad, sorry. I didn't notice and assumed 16:35 CET. Yeah, it's pretty unusual then. There may definitely be a reason, none that I know of, to start the contest earlier.

Thanks too, you saved me from missing the contest! :)

The author are chinese. So this unusual time is chosen to provide a comfortable time to chinese i think.

Yeah, It will start at 20:35 in China, instead of 22:35 as usual.

Have a comfortable contest then. 22:35 is really tough time i think specially if someone has to join class or work in early morning. But i am going to miss the contest due to unusual time :(.

Most people are comfortable with this timing?? really nigga??

Yeah. I don't see a high number of people crying about the timings of contests on the few rounds I've participated here. So, looking at the facts of not more than 4-5 people reporting timing issues to Mike, 16:35 CET seems to be okay usually. It's not a comfortable time for me too (as it clashes with dinner) but if it's a good time for a greater lot of people, I'm okay with having my dinner earlier or later.

Back to the OP: I see your problem now. The issue is that this contest is earlier that usual timings and might be problematic for some people (but it's always going to be problematic for a certain time zone, sadly nothing can be done about it). leafvillageninja conveys exactly what I wanted to say in their comment below. Hope you take care of your health during your fast!

I've been complaining about all contests being at 6am in my timezone for 8 years and no one cares. Other people with the same problem probably gave up or never started CF.

That's so cute. You probably do the contest while on the school bus.

Not everyone is Kid my friend.

That's sad :( But let us not forget that no matter what the time is, it'll be inconvenient for at least some people. Nevertheless, having the problem-setters available during the contest is generally helpful so they can answer queries and give announcements during the contest. With the usual timings, the contest will end at 1:05 AM in problem setters' timezone, which of course may not be convenient for them. So I think it is unfair to request a change in the timing.

Hope no unrated again.

Warm Welcome Div 2 :)

This it a meaningful contest.It represents the end of last week's $$$(NOT)_serious$$$ problem.

Wow djq_cpp! /se

Finally a Rated Div.1 contest！ I see many familiar faces！Hope everything goes well and I can realize my dream for this year — being a Grandmaster！（Actually, if the last Div.1 Round wasn't unrated, maybe I'm a Grandmaster now）

But you got FST on B last round

Actually, I got FST on B because there was a stupid bug in my code. (I fixed it after the contest and got AC) And my solution of C was close to the editorial but I didn't want to improve it anymore after that round was unrated.

Well, I performed badly in the contest so I even had to say goodbye to the International Master. But after I discovered the secret of Div.1B, I thought the solution was really beautiful.

Because of the unusual time. All the Muslims in Bangladesh won't be able to take part in the contest. It's Ramadan time and the contest will start when the fast will be broken! ;(

It's scheduled at a nice time since I will go to school and I can't stay up late to compete at Codeforces. I'm a Chinese student. Thx for the great arragement.

Why do you go to school, sir? Isn't there lockdown in China?

The epidemic was almost controlled in China actually. The lockdown of Wuhan had been already terminated and some schools opened under good preparation.

You guys have found a cure for Covid? In your country, the curve has flattened and out of the 82k infected, 78k have been recovered. I mean, seriously, what other steps did you guys take along with lockdown? In India, it is exploding like anything.

The fact is if all patients get well placement in hospital, most of them will recovery from disease, just by the working of immune system, and the rate of death won't be too high. We hope that everyone will no longer suffer from the epidemic, and in case we find a cure, we will definetely help other countries in the world ^_^

We haven't find a cure yet. What we do is preventing the virus from spreading too fast. Yes, there indeed exist one or two cases some day but all people who met with that guy recently are tested and quarantined. Also, Chinese civilians know the importance of social distancing. We always wear masks when we go out and take extra care about our personal hygiene.

Will Newbies and Pupils be giving this contest? I mean they have their own contest type now.

This is racism based on colour. @Mike

Please do not take this as a racist comment. My worry is if the long queues don't come back. Even we are not allowed to give Div 1 but that doesn't mean it is racist right? Since Div 4 is exclusive to newbies and pupils, it would be much better if they participated in their own division just like we do.

You can use the term ratist.

![ ]()

Or... I am once again asking for clear statements.

I am once again asking for short queues...xDxDxDxD

I think Qs don't affect if you are unable to solve a single problem.

Any special reason for this unusual time schedule ? :(

Probably the problem setters are all from China so they want to set the starting time earlier. It is actually 08:35 pm in China.

" interesting problems, strong tests and clear statements." Love this quote.

Someone told me that queues are one of the important ones in STL . These days I dont use them....Thanks to CF..

Mike needs to

`.pop()`

the queue more frequently ...:-D . Love queue fear long queue.And Is there any container called Long queue in STL?

If answer is yes,fear that container . And, you should feel free to use queue. :-D

You can always switch to priority queues ;)

Hope no unrated again

we live in present so be happy for present. don't worry for future. #RatedForAll

We're afraid we will not change time for this contest. It is very sad that whenever the contest will begin, there will always be some people feel uncomfortable. Apart from that, all writers are from China, and it means that the contest already ends at 23:05 in our timezone, so further delaying would be very uncomfortable for those in our country. We are very sorry for this arrangement, especially for those must perform the Maghrib prayer. We respect everyone's faith, and hope you can understand us.Have any contest in codeforces been delayed because of someone requesting in the comment section. If not then why are people still complaining?

I'm in Korea and usually the contest ends in 01:35am or even 02:05am sometimes. And yes, we do have class on the next morning. I have some friends living in other countries even have to enjoy contests at 4am or 5am. However, we have never complained about the time zone. Some people get the convenience most of contests and complain about the rare unusual starting time.

I don't get what you are sorry for, and it's pretty ridiculous that some people complain regarding it because even for Muslims, they are in different timezones, and e.g. for me, this timing is much better than the usual one because the usual one conflicts with the Maghrib time, and I don't believe you should have commented regarding that. Anyway, it's not like the usual timing is perfect for all people all over the world.

I believe there should not be a fixed timing anyway, but rather different timings to give a chance for everyone.

Notice the unusual start time.

I think maybe I should add an extra notice.

Pieliedie as in the Swedish dota pro player?

Yes.

SpoilerLakad Matatag, Normalin Normalin.

xD

This is the most colorful contest I've ever seen in an advertisement

The writers are great OIers in China, this must be a successful round!

.

ldq101!

That will be great (although I'm not sure whether I'll have a positive rating change or not...)

The writers are famous and great OIers who has much experience. I'm looking forward to a great time the day after tomorrow ^_^

(Hope the writers have prepared strong pretests and clear statements!)

Hazyknight I love your profile picture, i saw once a similar picture quoting djikstra(shortest path between you and me) Can you please tell me the source :D

I’m so sorry that I can’t find the sourse. I find this picture somehow on the Internet years ago...

Here they are: Link.

I saw them before, and they instantly caught my eye, all well-designed and inspiring posters.

And particularly this is the Dijkstra one.

I've noticed some comments that are not so friendly. In my opinion, discussing or arguing politics on Codeforces is definitely a bad idea, because this platform is built for communication of knowledges and getting improvement through those problems. My suggestion is, no matter what opinion you have, give up your bias, and enjoy the beauty of Competitive Programming whole-heartedly. Mike will be glad to see that.

Hopefully, some of the testers of this round will listen to you.

the coordinator has taken a lesson from previous div 2 round and hasn't included any FAQ this time..

strong tests and clear statements instead of word 'clear' it should be 'short' then we all will be double happy....!

You will know sometimes for "clear" we need to give up being "short"(but not meaning extremely long and obscure) XD But anyway, most of problems have short statements, don't worry.

codeforces has passed very difficult period like dark night. We hope, after the night, this round will be the guide of light.

Lol, so many peeps whining over here about the contest time being pulled back to 12:35 UTC, and under the radar the Div2 after this one is scheduled at 11:35 UTC. Ecksdee. #HowToReduceQueueforces (Jk. I totally understand that this is due to otherwise inconvenient times for the authors.)

I like the new timing tho !!

Sad about the contest time! Collides with Iftar time in Dhaka.

Please change the contest time. As It is "Ifter" time in Bangladesh. 30 minutes delay would be fine.

I'm a Muslim too, but I don't think that the problem setters and authors and contest organizers should consider us. There are also a lot of people that the contests time don't fit with them, consider yourself one of them.

Also, if you want to participate, participate and eat your Iftar after the contest. (That's what I do usually in Ramadan).

Cant you just move the "Ifter" for an hour?

That makes no sense. After 30 minutes its iftar time in India. If you delay it two hours, still its iftar time in somewhere else. My suggestion is to take a 10 minutes break during the contest.

Can't wait to participate, I hope this round will be successful without technical problem! :"D

What has codeforces done different from the last (unrated) round? Has the problem been fixed? Is there something we as participants can do? Just curious..

We hope too that the problem has been fixed and as they successfully conducted 2 rounds with different pattern of submission and we noticed no bug this time.

Yes, lets hope that this contest gets successful and rated and all the queue problem has been solved.

Let's pray to god to complete this round rated this time successfully

This will be rated round after a long time.XD

Lets Pray for it!

And my dinner goes wooooosh

plz, change the time, make it 8PM or any time after 8PM.

Dear Codeforces, In Bangladesh the time you set for this round is 6:35 and as a Muslim country most of the contestants will be busy taking their iftar. If it is delayed by half an hour it would be great. Please consider this. Hope you understand... Message for the users: Don't downvote this :) i just stated our problem. If you don't find it helpful you can just ignore it.

I can't participate this contest for iftar time but making it delay is not a good decision. If it is 30 minutes delayed then it will conflict iftar time in india. If choose another time then it will conflict somewhere else. Someone has to sacrifice. Some days,we have to sacrifice too. So we should respect the time fixed by author according to their comfort.

Except the delayed contest, this must be the earliest announcement of Scoring Distribution :o

I was part of a comment thread started by Ashishgup :>

Div2D/Div1B is missing!

Why is it always delayed at the last minute?

A meaningless fact: this announcement used LaTex for "score distribution" instead of just bold.

can you held the contest an hour later (i mean 20:35 utc+7 lmao) ?

Sorry for disturbing, but 18:35 utc+7 is 1 hour

earlierthan the original time.I think one reason this round is held earlier is that its writers are from rdfz, Beijing, China, so it follows the Chinese time.

Nice meme

So, when someone share their problems with unusual time, you react with down votes? I always respect this community for the friendly behaviour. Today, your reaction with down vote really has disapointed me! Have a good day! Best of Luck everybody. :)

brother those comments got down votes just because the organizers already answered the problem but still there are comments mentioning the same problem again and again..

stO rdfzer Orz --from a very vege OIer one street from your school

I'm from Brazil and I'm very happy with the unusual time.

I think CF contests should have a time rotation so that everyone around the globe can compete, at least once in a while, in a comfortable time.

Looking forward to have a great time with this contest. Wish you all the best.

How can a sequence of 'n' integers be partitioned into 'k' partitions such that the total sum of the squared sum of all 'k' partitions is minimum? n<=10000 1<=k<=min(50,n).

Have u solved the 4 disjoint subsequence problem and if so could u explain ur idea?

for that, we can generate all possible cases, that is- dp[sum1][sum2][sum3][sum4]; this dp table stores true and false only depends on whether we can reach that state or not. sum1<=60,sum2<=60,sum3<=60,sum4<=60.

after that, we have to select the one that satisfies the given condition. i.e,

Thnxx

Can u explain one thing that if we try to compute all possible cases then there would be 4^n possible cases as we assign each i into one of four subsequences ?

as all the cases are bound by DP state, so it can not exceeds O(60^4)

I mean to precompute the dp table we need to go to all possible cases

You both are discussing about which contest ?

yesterday, there was a contest on the scaler academy. solutions are not open even after the contest.

I hope this "technical work" doesn't leave a bug that impacts the contest xD

why there are less registrations this time

The time, I guess. But at least the risk of a queue is less as well XD

We got long queue again :(

how

Check status of all submissions!

holy molly, hope it doesn't happen in today's contest

Thanks for the starting time :).

Is it possible to extend the start time of 30 minutes? Cause In Bangladesh, India region it's Iftar time.

add: minus contribution for asking a question! RIP people :) As a contestant, I don't want to miss any contest.

No, it is not possible to extend it.

If you want you can skip the contest, it will great for CF community as queue will be small.

being anrab XDXD

The normal CF rounds are in the same time as Iftar in Iran :).

It's in BD (BDT+6) Ramadan Iftar time :(.

firstly change your profile picture plz then only i will support you

The queue which has formed right now scares me about the future of this contest too.

Dear MikeMirzayanov, Kindly look after the technical issues before starting the contest as there is a long submission of queues.

UPD : Anyway, i missed previous time related requests. I am so sorry for posting about it again. But, i really don't get the point of behaving rudely or showing arrogance to others. It was so frustrating to see those hate comments getting upvotes.

Is it possible to reschedule the contest starting time or at least postpone it for 30+ minutes? it is almost clashing with IFTAR* time here in south asia. Due to this, a lot of Muslim participants may not be able to participate on time. *IFTAR is the evening meal with which Muslims end their daily Ramadan fast at sunset.

Just shut up. Its enough now.Once you have been told that its not possible to extend then why you are forcing them?

i wasn't forcing anyone. If you don't know how to beahve politely, then you better learn them at first.

Your brothers have already asked for the change in the timings. They denied it. Then whats the point of asking it again and again. If you want to do iftar go and do it, please dont spam here.

Well, you could have typed the same thing before. Showing arrogance or disrespect is not a good habit. Try to be polite next time, it won't cost you. BYE

I do not understand why you do not want to move the iftar.

People showing arrogance are getting up-votes and positive contributions

People showing respect are getting down-votes and negative contributions

Due to the unusual timing, I can't participate in the contest. RIP rating.

SpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerIs it rated?

Yes, it is rated.

The previous "Bad Gateway"-Error 504 is still a issue for codeforces.Hope so,it'll resolve before the contest.

Chinese problem setters and 2.5 hours... perfect combination! I wish i will be Candidate Master today.

So this guy DreamL0lita is participating in today's div2 again with a fake account created minutes ago. He always makes a new account named dreamlolita (with variation ofc) for every div2 and ends up in the first page of standings. Why? i wonder.

Hope your account is not fake

i hate people who do that

My last submission has been in a queue for last 5 minutes. Hopefully this contest won't be like the last one.

Please reschedule the time. At least +30 minute.

It will be quite impossible to attend in time for Bangladeshi contestant due to Ramadan.

Brother, it has been discussed above. They won't change the time. Hope, you meet better rating soon.

Hey bro. I think , you should start practice to read previous comments before commenting something .

It has been already asked and answered.

delaying by 30m is a really good idea also for our Chinese, I end up extra class at 8:30...

1533 codeforces virgins registered for the contest.

Imagine being insecure about being able to lose rating on Div 4 so much that you call everyone who puts in effort to do well in something they are passionate about a virgin. I enjoyed this comment very much.

+1 to you, good sir.

almost all top 10 legendary masters have registered except one guess who. Even though the timings are suitable for Chinese participants this time.

4/10 is "almost all top 10 legendary grandmasters"? (At least, that's what I assume you meant.)

300iq can't participate and apiadu has also not registered so.... you now i think you get to know what i meant

Lol, you are right in pointing out that the top 3 chinese participants are not registered.

However, in general, the time zone is a bit more favourable to chinese people, since for once the contest doesn't cross midnight for them.

why MIFAFAOVO never participates in any rated round after gaining first position in cf .

So that you can comment if he takes part regularly in rounds retaining top spot will be difficult.

From my point of view, problem description is not good enough.

100th try submitting solution for Div2-B, never gonna give up!!!!1

pretest Case 2 :-(

MathForces returns !!!

you mixed something.... http://mathforces.com

After div4, we have Codeforces Round #641 (div. 0.75) and Codeforces Round #641 (div. 1.75)!

This is the best round I've ever tested

Then I guess you can tell how many problems you were able to solve in Div1 during VC?

More complicated mathematics than multiplication and exponentiation: *appears*

Green coders:

mAtHForCeSand cyan coders

and blue coders

RIP rating bois!

Amazing tasks! tho the difficulty gap between d1C and d1D seems to be way too huge...

What's the point of adding a lot of unsolvable problems to div1?

We are sorry about gaps, maybe the behaviour of testers made us underestimated difficulties of DEF.

I guess F has ok difficulty (for div1F), but DE are overkill. What were the things you intended D to contain or basic skills it should test? I mean, if you were to explain it while trying to avoid giving me any hints about the solution?

You may need some methods or special views to understand and calculate expected value. Unfortunately, maybe it is in fact too tricky, and we have underestimated the difficulty.

Ok, after solving it, I can see where the problem lies. It's not that it requires some hardcore trick or theory. It's that there are so many paths that seem viable but require working with equations on paper with no guarantee that what you're doing will lead to a fast enough solution.

The idea from the editorial is very similar to what I started with. An experienced contestant can quickly notice both that the solution can focus on the final person and that it can be expressed as the simpler "reach an end state without stopping at the first end state" minus a correction term. Here's the first question: is the expected value of this simpler number of steps finite? Such details are pretty common and need you to basically proceed in a direction with confidence that it's the right direction.

What if you don't see that it leads to a solution? You might abandon the right solution and try something else that seems more doable. When should we sum over $$$i$$$ and what should we obtain from it? How about modifying the problem by allowing giving a token back to the same person? It leads to some more symmetry, after all. What sort of math is expected, how about some matrix algebra? (When it looks like simpler things don't work, you try other, more complex things.) How about separating cases where some token doesn't move (which makes the person who wins obvious) and where it does move? There's a lot of paths you can try to take towards a solution.

How to compute the constant $$$C$$$ in the editorial? The expected time of reaching "$$$i$$$ has everything" from "$$$j$$$ has everything" without reaching "$$$i$$$ has everything" before can stop someone because it looks like it has states (number of tokens of $$$i$$$, number of tokens of $$$j$$$) which is $$$O(sum^2)$$$. It's possible to miss the realisation that it's actually simple. There's a lot of such things and it's actually quite common that a problem has a simple solution, but it's super hard because of many other non-solutions.

It's a nice problemset and a nice problem, which can be said about a lot of superhard AGC Fs.

Your opinions are quite incisive. Indeed it is hard to determine the proper approach to calculate the answer in this problem, I had realized that before the contest. But I had also, at least, come up with the relation between $$$E_x$$$ and $$$E'_x$$$ , and I thought this would solve the problem, before reading the tutorial. So personally I had underestimated the real difficulty all the time. Another reason is 300iq thought we could use this problem as div1D. And also, as what I've mentioned, top(GM ~ LGM) testers solved this problem fluently during virtual participation, and they don't think the gap is way too large. So in my view the main part is to come up with the transformation of summations. It requires much inspiration, and makes it like an AGC problem. But also this kind of inspiration is the reason we like it.

An interesting fact is, because of the possibility of making hacks by making something divided by $$$0$$$ (in the earlier standard code), 300iq has once advised to remove this problem and $$$\textrm{swap(E,F)}$$$. Don't know what will happen with standings if we did so.

Last but not least, thank you for your in-depth discussion.

Div2 B was really a 1000 score!?? That one is really tough :(!

it was preety easy

how to solve it?

Let input is stored in arr[i]. Now the minimum answer is 1 as we can purchase one item every time. Initialize an array of ans[] with 1. Now a loop from i=2 to i=n, for each 'i' check at its factor indices if the value(arr[factor of i]) is smaller than the value at arr[i] or not, if yes then just update the ans[i]=max(ans[i],ans[factor of i]+1) for each factor. Finally the max value of ans[i] for all i is the answer. Its something like you're finding longest increasing subsequence with given constraints.

Aah! How easy that was! I couldn't solve during contest time.

Now upsolved it. Couldn't solve C too. But C was an interesting problem. Just have Upsolved it now.

Today was not my day. Problems were nice.

Reason behind half memory limit in C -

People avoid

`long long`

and read p as`int`

and get WA.Well played BlueSmoke

No. That's not my original idea for setting this memory limit. Please improve your own solution.

What was the original idea? Bad memories from 2 contests ago made me more careful, but still it seems hard to imagine a solution that works with 256 but not with 128.

A tester used bitset<1000> f[2000][1000] to get accepted, and since it is hard to larger the constraints to make it TLE(amount of input will be huge), we decided to make it MLE.

I'm sad I thought so hard and still can't find anyway to solve C :/

Codeforces Div.1 is not just for grandmasters.

Grandmaster here, doesn't help. There are only a handful of people that can solve DEF.

I solved ABC and I'm proud of it!

Even more than half of the grandmasters only solved 3 problems! Wondering why they added them

This round is ridiculously hard!

It seems that you are right, especially in Div.1.

Div2 D should not be more than worth 2000 points as it increases the difficulty gap so much.

Today i realized , my maths is extremely weak , even though i used to score good in school tests.

May be because , i never prepared for any mathematical olympiad .

Errichto words guided me to solve B

It's also true for Div.2

Oh, it's very good, if you solved ABC(((

Good Number Theory Round

Nice math-forces round. Increase hack-forces when the problems are that much hard, please.

You know stuff is f-ed up when tourist can't solve beyond Div1C.

Guess my opinion.

The queue worked this time.

You couldn't solve more than D1C :), as tourist.

Which edge case did Pretest 10 covered in Problem B (Division 1) ?

I guess something like this: 3 3 1 1 1 2 and you have to make everything to 2. Basically you start to make everything 3 (from left) except 2. and after everything 2 (from right).

Does your code works for this test :

4

3 2

2 1 3

3 2

3 1 2

3 2

3 1 3

3 2

2 1 2

all the answers are "yes" except third one.

It was some typo in the test cases.

1

6 3

4 1 4 1 1 3

If you have solved using my approach (which was also getting WA on test 10), this case might be helpful for you:

The expected output is yes.

Too much Math

With the amount of testers I suspect the testing approach was quite informal, because I doubt these people managed to solve DEF in any reasonable time. To get an unbiased idea of the difficulties of the tasks, you'd want people who have never seen them to attempt to tackle them under time constraint rather than giving people the analysis and asking them if it seems okay. My only explanation for the difficulty today is that the latter approach was used more rather than the former.

Ignoring how difficult the problems were, I actually enjoyed them a lot and I find E, D quite interesting, even if I can't solve them. Could've easily been used as Es/Fs for multiple rounds.

The round really needed me as a tester :(

Most of them used virtual participation as testing. However, maybe because of some testers counting skills are too strong, we have wrongly estimated the difficulty gap.

div2 D is to find subarray of length>=2 with median k ??

I did the same thing. But, getting WA on pretest 9

Not really, since there might be a test like this:

6 3

3 1 1 4 2 5

where there's no subarray of length >= 2 with median k, but the answer is yes (you can transform into 3 1 1 4 4 4 -> 3 4 4 4 4 4 -> 3 3 4 4 4 4 and so on).

can you tell me the approach to do D ?

yes, but there is an evil test case I forgot about

you should convert it to

then it's possible to change it to 1s

maybe find subarray of length>=2 with median>= k , also remaining array as at least one occurrence of k?

In fact, you only need to find a subarray of length 2 or 3 which has median >=k and that's all. And ensure that k exists in the array at least once.

What was pretest 10 to Div2D/Div1B? I kept getting WAs

Try if this test is

`yes`

:How come?

First make everything 6 except the five with operations of length=3, then you can make everything 5 by performing operations of length=2.

5 1 1 1 6 6 1

-> 5 1 1 6 6 6 1 // operate [4, 6]

-> 5 5 5 5 5 5 1 // operate [1, 6]

-> 5 5 5 5 5 5 5 // operate [1, 7]

try this

n= 8 k= 3

4 4 4 4 1 1 1 3

answer should be yes

How??

4 4 4 4 1 1 1 3

4 4 4 4 4 1 1 3

4 4 4 4 4 4 4 3

4 4 4 4 4 4 3 3

and so on

Because you can turn 4 4 4 4 1 to 4 4 4 4 4, when you get 4 4 4 4 4 4 4 3, the remains is obvious. I also made this mistake by thinking I can only turn values into k but, we can also turn values into x which is greater than k.

Eratostene's sieve for the win!

exactly. one solution for A, B, and C

We don't need that n<=1e5 :)

Is E just so implementation heavy, or am I missing something?

O(n) is a bit complex,but it seems that O(nlogn) is much easier.

Maybe you miss some details.

you should create problems on mathforces, not codeforces.

why you dislike? oh, i forgot, it is because i am not red.

I cant's support you more!

кремлеботы минусуют гады

я лайк поставил а он на дизлайк поменялся кремлеботы гады весь интернет перевертели чтоб мой лайк забрать

НУ ДАВАЙТЕ НАПАДАЙТЕ, СТАВЬТЕ ДИЗЫ ГА А ШО

А НУ ДА ГО ТЕПЕРЬ ЛАЙКИ

да мы не специально сори(((

(нас заставили)

How to solve problem Div2-B if we swap indices with Sizes

f(a) = max( 1 + all( x : x is i *a (i>1) and arr[a] <arr[x])) it is similar to sieve technique

final answer is max(f(a) : 1<= a <= n)

you didn't get my Question guys consider the same problem statement but swap sizes with indices it will be different problem then how to solve it ?

There is a dp with $$$O(n^2)$$$ complexity. Instead of looping through multiples of the current index, loop through the array to find multiples of current value

How did you solve div2 C ?

how did you solve div2 b?

Let input is stored in arr[i]. Now the minimum answer is 1 as we can purchase one item every time. Initialize an array of ans[] with 1. Now a loop from i=2 to i=n, for each 'i' check at its factor indices if the value(arr[factor of i]) is smaller than the value at arr[i] or not, if yes then just update the ans[i]=max(ans[i],ans[factor of i]+1) for each factor. Finally the max value of ans[i] for all i is the answer. Its something like you're finding longest increasing subsequence with given constraints.

man i was so close to solve it, thanks for explanation

Sorry for the previous announcementfor any two adjacent models => for ANY pair of ADJACENT models, this should hold**** I misread the announcement and considered s2>=s1 for every sequence instead of s2>s1. Took me 5 wrong submissions to realize that XD.How to solve Div 2C?

1 Prime factorize all given numbers with their prime powers!

2.Check which prime numbers appeared >=(n-1) times

3 For these prime numbers find if they appeared n-1 times then for a particular prime $$$i$$$find its minimum power across all its occurences except 0.

4 For these prime numbers find if they appeared n times then for a particular prime $$$i$$$find its second minimum power across all its occurences except 0....

< 5 and lets say a prime $$$i$$$

have power $$$j$$$ in above algo then multiply (ans with $$$i$$$^($$$j$$$))finally print the answer

see lcm as Union , see gcd as intersection and then simplify set operations , you can do it O(nlog(n))

GCD is log(A[i]) and not O(1)

im sorry , youre right.i forgot that

Since array t contains all possible lcm of pairs from input, We just need to find the product of all prime numbers that divide atleast n-1 numbers of the input.

Since its hard to explain I'll give an example on how the algorithm proceeds:

input= [10 24 40 80] , n=4 ans=1; //initially

// 2 divides all the numbers so divide all by 2; array = [5 12 20 40]; ans=2

// 2 divides n-1 numbers so divide those n-1 numbers by 2; array = [5 6 20 40]; ans=2*2=4

// 2 divides n-1 numbers so divide those n-1 numbers by 2; array = [5 3 10 20]; ans=4*2=8

// 5 divides n-1 numbers so divide those n-1 numbers by 5; array = [1 3 2 4]; ans=8*5=40

// the algorithms iterates through rest of the prime numbers and outputs the answer=40

Here's my code

Can you please explain the time complexity of your code? if you are looping from (1 to n) inside (2 to 100000) how is it not O(n^2) ?

Notice how i have a break statement the moment it encounters 2 numbers not divisible by i. This and also considering the fact that any element(<=200000) in the array cannot have more than 17 prime divisors (2^17=131072) tells us that the worst possible time complexity is O(200000 + 17*n).

So basically what i mean to say is the second forloop will only be looped at worst case 17 times.

Edit: It may loop more than 17 since different elements have different prime factors, but its still insignificant and is definitely not more than 100

Yeah now I get it. Thanks Sharath :)

How to solve DIV2B? Is it like a dfs? So far I have written this code but couldn't figure out....

Codef(a) = max( 1 + all( x : x is i *a (i>1) and arr[a] <arr[x])) it is similar to sieve technique

final answer is max(f(a) : 1<= a <= n)

state dp worked perfectly. For every i, check for its multiples and update dp according to conditions. then max(dp) world be the answer.

For Div 2B: https://sahilbansal17.github.io/Competitive_Coding/2020/05/12/cf-641.html

Its really nice to see it organised at that precision.

Wow thank you! Are you regularly making this kind of upsolving blog?

I will try to do so, for atleast one contest a week.

In Div2B, since the sum of n over test cases is atmost 10^5, you can apply following dp

Let dp[i] denote maximum length of beautiful sequence ending at i. (Initialise all values as 1)

For each i, go through all divisors (say div) of i (proper), if s[div] < s[i],

update dp[i] = max(dp[i], 1+dp[div])

Overall time-complexity is O(n*sqrt(n)) per tc

Plz help, I use all time to D and cannot get anything

same :(

Another LGM unable to solve more than D1C $$$\dots$$$

Good that you were good enough to solve everything.

Sorry if my English is bad and it made my words offensive, i meant that lots of pros couldn't solve more than D1C and it means the round was unbalanced.

It definitely was unbalanced, I even think that it was perfectly unbalanced for one other website xd

Does that mean that you've accepted my apologize? :D, After all the problems were very nice.

I was joking, don't worry. Yep, problems separately were very interesting.

Unrated?

Same here :(

Spent all the time only to find the answer seems $$$n^m - 1$$$ for $$$a = (m - 1, 1, 0, \ldots, 0)$$$. HELP ME!

Isn't it just (almost)850F - Радужные шары?

I had the editorial for 850F open during the contest, and it led me to an incorrect solution :(

We cannot assume that if a person loses all their biscuits, they'll never get any biscuits again (they can actually even win the whole game)... So we cannot do these shenanigans like "for each person, we count the expected number of turns involving them until either they get all the biscuits or lose all the biscuits". But maybe there's a way around it? I don't know.

https://arxiv.org/pdf/1610.09745.pdf

How to solve div1.B/div2.D?