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, skip2004, vintage_Vlad_Makeev, fpdqwq, wangziji, Suika_predator, wrg0ababd, AcF-_-FcA, Shuba_Buba, duyiblue, xiaolou0411, LiM_256, Hazyknight, Sad_reacts_only, djq_cpp, little_waxberry, for their hard-working testing and suggestions;
Rewinding, 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.me/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.me/blog/entry/77276
Since the round is rated
Don'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 geometry
Number 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.
Lakad 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 earlier than 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.
Is 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: mAtHForCeS
and 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 longand read p asintand 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 announcement for 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....
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)
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 - Rainbow Balls?
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?
Is it true that in E $$$i$$$-th ($$$0$$$-indexed) player with a black hat just adds $$$n - i$$$ to all values and decreases $$$i$$$-th value by $$$1$$$?
Hello guys we are excited to invite you to HandForces Round #228!!!
(imho tasks are pretty good but there is a huge complexity gap between ABC and DEF)
How to solve div2D/div1B?
comment was accidentally posted
It's the answer of div2.B, not div1.B.
oops
if there's no element valued k in the array the answer is obviously "no", so we assume there is such element, and it's index is i. if n==1, all elements are already equal to k, so the answer is "yes".
case 1: let's notice that if one of adjacent to i elements is not less than k, we can apply our operation to these two elements and they both will equal to k; after that, we can "expand" this segment so it will cover all the array.
case 2: if adjacent to i elements' values are less than k, we can take such j < n that a[j]>=k and a[j]>=k, similarly to case 1 expand this segment so one of it's element would be adjacent to i. then we have case 1.
case 3: if cases 1 and 2 are not performed, we can find such 1 < j < n that a[j-1], a[j+1] >= k, then apply operation to [j-1; j+1] (if j+1 or j-1 == j, the median will also be a[j]); then we have case 2.
let's notice that if no one of these cases is performed, answer is "no" (because any operation will set some value that is less than 1).
Anyone 4th?
i got the idea but my solution failed on the 10th pretest
try n=5 k=3 a[] = 4 1 6 1 3 answer is "yes"
how to solve div2-C
Try after this logic : For 3 nos a,b,c:
GCD (LCM(a,b),LCM(a,c),LCM(a,d)) = LCM(a,(__gcd(b,c,d)))
can you plz prove that
How did you come up with this? Was this just an observation or something u knew beforehand?
https://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml check this boi
The problem is simplified if you solve it for each prime factor of the answer independently.
Why not?
Maybe there will be more questions than Div2.B if we did so.
What about putting the statement first, then explaining definitions for those who don't know them?
That's what I love about atCoder, clear and concise statements.
Good idea. I'm aplologizing for that.
I think they must make/update a list of standard Good Practices for problem setters and testers.
It's not necesaary that everyone is familiar with the terms GCD, LCM. Some people might have started participating recently. You should appreciate the effort of the authors that they have clearly explained every single term.
people who don't know about lcm and gcd shouldn't be participating on codeforces but learn some basic math
You could have simply replied with your real id.
It is a very common practice that definition of LCM,GCD, bitwise OR/AND/XOR are not provided in problem statements. Instead of providing definition, those word are used as hyperlink and a link is provided where those terms are explained. When some explanation are necessary for a very small no people then it is good idea to keep problem statements short and easy.
Entire question in 'Output' section
At div2-C / div1-A I thought that a prime is a part of the gcd, if all or all but one number can be divided by it. Say 2 2 1 and 2 2 2 words, if it was 4 4 1 or 4 4 4 i would divide by two and start again (2 2 1 or 2 2 2). However my program failed pretest 9 for some reason. Was I wrong in my reasoning?
same reasoning applied by me. failed at pretest 9 same as you
It's probably overflow for you too... Try using 64 bit num for gcd instead of int.
yes bro. i changed my default file 2 days back for some other ques. changed vi vector to vi vector in the macros section. let this be a lesson
First I also got W.A. in Pretest 9, But I think you were using the last number for this calculation:
Resubmit it by avoiding the last number as (i<j), so don't do any operation for i=n.
Why? I'm not sure I understand you, the answer for 2 2 1 is 2 and for 2 1 1 is 1. Clearly all positions are equivalent?
I got wrong on pretest 9 due to overflow should have used long long to store answer.
Oh, mine too... For some reason I was sure it can't go over 200000 lmao.
Your approach is right, maybe you made some implementation error?
Here's my code
It was overflow for result... Didn't think it can get that large.
I feel you lol, this is why i completely abandoned int and am using long long everywhere
In Div2 problem D or Div1 problem B, I checked for
$$$k 0 k$$$
$$$k 0 1$$$
$$$1 0 k$$$
$$$1 0 1$$$
$$$k k$$$
$$$1 k$$$
$$$1 1$$$
structure in the array, where elements less than k have been replaced by 0 and greater than k replaced by 1.
The proof is by construction. What's wrong with my solution (WA IN PRETEST 2)??
Does your code work correctly when $$$n = 1$$$?
I handled that test-case separately. Also, I updated my original comment: please help.
Try the input
Your latest submission outputs "YES" to this
OMG OMG OMG OMG THE ERROR I PUT THE IF(N==1) CASE BEFORE THAT CHECKING IF THERE EXISTS ATLEAST 1 ELEMENT EQUAL TO K I AM DEAD
Try the following test case :
The answer is yes
You had to check all subarrays and check if there exists a subarray with 2 or more elements >=k.
What does it help? I mean if we got
5 1 1 5as input, we cannot make all 5. Please explain, I do not get it.Let me elaborate
1. check for n<3 cases
2. for n>=3 check if k exists in the array.
3. If k exists in array then check if there is any subarray of length 3 which has atleast 2 elements greater than equal to k.
4. If such subarray exists then answer is yes else no
This works because after checking for the existence of k we have to check if there is a subarray for which median is >= k. To do this every subarray that will satisfy this would have a subarray of length 3 satisfying the constraint. So simply check for all subarrays of length 3.
If the found subarray has a median > k and k exists in array we can always convert all elements to k.
Ah... got it, thanks. I was under the impression I would have to find biggest median of all subarrays. But turns out biggest of all is the same as biggest of all of size 3.
Actually Div1 F1 is much solvable than Div1D, you can try that now. We as testers first solve F1 and than D. But the coordinator said F1 and F2 should be placed together. Previously we decide to put F1 before D.
I think that's reason to set Div1.F1 as Div2.F. But we can't ask a person to see div2 while competing :(
Yeah, it seems more solvable. It's fine to put the Fs together, but D and E should've had more points regardless and perhaps E and F should've been swapped to hint at the difficulties.
Good idea. We should have increase the score of DE. F2 is really hard. What we expected was that F2 is the final match between top contestants.
what
I mean...
I think that it is our (as participants) fault that nobody has managed to solve 5. Some people were close.
I can see that you could underestimate the difficulty and think that someone with enough luck could solve ABCDEF1.
But thinking that several people will be able to solve ABCDEF1 and have enough time to approach F2 (and maybe even succeed) is outright crazy.
The fact is, during testing phase we have several testers solved both D and F1 in virtual participation. And yeah, E is quite implementation-heavy and F2 is something crazy and almost totally unsolvable during contest.
What we expected is most GMs can get either D or F1, top contestants get both of them and maybe someone will make an final-hit by E or (maybe, with little probability)F2. However it's a pity that things become tough and even no one can solve both D and F1.
what is pretest 10 in div.2d/div1.b?
Try the following test case :
The answer is yes
thx
something like
thx
Weak pretests on B... Why not put all $$$3^n$$$ possible tests for $$$n \leq 8$$$ in pretests?
Can you check this https://codeforces.me/contest/1350/submission/79899269 please. This is pure brute force but got AC in the system test.
Div 1 / B
No DIV2 B
you gotta be kidding me :P
PS: what is that Pokemon in your pic?
From now on, if anyone asks me why I bothered to get a mathematics degree, I'll point them to this contest xD
What was Div2 B's pretest 2. My approach was to make a tree out of all the models and do a dfs to find max possible height. Can't find an edge case :(
Isn't it a DAG, not a tree? For example, the construction for $$$n = 4$$$ (assuming the sequence is strictly increasing, something like $$$1, 2, 3, 4$$$):
(Maybe reverse the edges, I haven't really looked too much at your code)
Your solution is close though. The fix for it would be, instead of stopping when you hit an already-visited node, you'd want to return the deepest "child" node you can reach from that node. This is easy — you already compute that in the dfs, so you can just store it and return the stored value if you've already visited a node.
How to solve Div2D? How to handle cases like:
6 3
3 1 1 4 2 5
where the segment considered for the operation is not a subarray?
My approach :
For $$$n = 1$$$, check if the only element is $$$k$$$ or not.
For bigger $$$n$$$ :
First check if we have at least one $$$i$$$ such that $$$a_i = k$$$(if no such $$$i$$$ exist then the answer is no), then if we had such $$$i$$$ that $$$a_i >= k\;and\;a_{i+1} >= k$$$ then the answer is yes(proof it yourself), otherwise if we had such $$$i$$$ that $$$a_i >= k\;and\;a_{i+1} < k\;and\;a_{i+2} >= k$$$ then the answer is yes, otherwise its no :)
Probably the easiest way to solve 2C 79828664
can you please explain the solution a little ?
Since $$$\gcd(\gcd(set_1),\gcd(set_2))=\gcd(set_1\cup set_2)$$$, we can calculate the answer separately and then combine them. My way is to fix $$$j$$$ each time and the answer turns out to be $$$lcm(\gcd(\lbrace a_i|i<j\rbrace) ,a_j)$$$, but I can't prove it mathematically.
Forgive my bad English.
but there are no inbuilt gcd and lcm function how did that work
c++17 has built-in gcd and lcm. check this out
i use VScode can you plz tell me how can i get c++17 ಥ_ಥ (PLJ)
Are you using code-runner plugin?
yes I use code runner. How to use c++17 in vscode?
you should modify the "executor map" in settings and add "-std=c++1z" to cpp's compile command. This can be a bit complicated if you have no experience of modifying the settings.json file
-std=c++17is better IMO.see this also.79898013
how did the function gcd,lcm work?? UPDT : got it
Why this solution is not giving TLE?? https://codeforces.me/contest/1350/submission/79823696
Because, n is at most one million, and the solution runs on linear time.
On the first iteration of k n is even, it goes to "else" and once find the smallest divider. On the other iterations it goes to n%2
Thank you for the C div2 task. It was very exciting to solve it
Can somebody help me on why my solution for div2-B fails https://codeforces.me/contest/1350/submission/79878448
test: 1 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
The answer should be 5. Your program outputs 6
Can you please tell the wrong in mine too?? https://codeforces.me/contest/1350/submission/79893472
Of course:) test: 1 6 1 2 3 2 1 3. The correct answer is: 3. Your program outputs 2
thank you so so much :)
Your loops count sequences like 1,3,6,12,18 but 12 is not a divisor of 18
System testing was lightening fast today
Not much work to do.
When will ratings update?
Just install browser plugin named "CF-Predictor". support Firefox and chrome.
pretests of C were weak caused me +50 ༼ ºل͟º ༼ ºل͟º ༼ ºل͟º ༽ ºل͟º ༽ ºل͟º ༽
At first,the contest is very great,but I think I have a long way to go.Come on!
I think C Div1 is the most beautiful grid problem i have ever solved
Chinese people again proved that they are the math gods for the $$$69th$$$ time.
[answered elsewhere]
Nice questions Div1-ABC. For the first time today I was able to solve Div1C/Div2E. Thanks for a Div1C with same difficulty as Div1B.
WA on test 19 can somebody please help? https://codeforces.me/contest/1350/submission/79890541
In cases like:
You can use the
[8, 9]and go fill 8 left, and then use[5, 8]to fill up the rest.I have WA on the same test and the one you gave works in my solution ( https://codeforces.me/contest/1350/submission/79875162 )
Try this (the answer is
yes):You're right on that there should be some alternating triplets. But they do not need to contain k. You just need any two numbers that are >= k. You can carry them toward any k nearby.
thanks! wonder why they didn't add that to the pretests...
I thought people be joking about mathforces, looked at DIV2 ABC problem tags and its all math lmao wtf, still liked the problems tho, even if couldnt solve them
i want to know the solution of div2E which got memory limit exceed as mine is just simple bfs
BFS should work. My solution: https://codeforces.me/contest/1349/submission/79869421
I got AC with my submission I just want to know the solution approch got memory limit exceed because i can't think one right now
From what I heard it’s to block bitset<1000>[2000][1000]
why there is no hacking round ? I got some tetcases of Div 2 problem C where my friend answer is wrong but he got AC.
Yeah... I also think hacking round is must
It depends on the format of the round. In rounds like the educational ones, there is a separate hacking phase after the coding phase. But in the regular Div2/Div1 rounds participants can lock their accepted solution for a problem and hack solutions of other participants in the same room for the same problem during the competition.
Let's be honest, although most of the problems were $$$mathematical$$$, those problems are really interesting.
Literally wasted all of my time on div2/prob b,still cant find any bug,can anybody tell me what is wrong,it dont pass pretest 2 ,i used dp approch code -> https://codeforces.me/contest/1350/submission/79864654
In some cases your dp[index] will remain zero, if this
if (index*count<(len)&&arr[index * count] > arr[index])statement is never true in the while loop. So you should set your dp[index] to 1 in your else before entering the while loop. Because you can always at least take the value itself.Thanks man!!!You saved me hours of debugging.
Great contest! People might say that it was math heavy, but keep going cuz the haters will hate and each author should have their own distinct style! Definitely tuning in again if you guys offer a new contest in the future! Also shout out to Mike, because the queue time was virtually non existent!
Why is a lot of time taken after system testing to display the rating changes?
First people have to calm down, else they will complain about the results.
I thought it was a very computationally expensive task. So it takes a lot of time to calculate.
WA on pretest 2 div2/prob B. whats the problem https://codeforces.me/contest/1350/submission/79864654
Amazing contest It was comparatively tough!!
An awesome round after a very long break. I personally enjoyed all the four problems I solved (D2 ABCD), I have a passion for maths and D2 C was a beautiful number theory problem. Thanks to the contest designers. Also it was great to feel that adrenal rush after such a long time. Great to see CodeForces back again. Cheers!!
For D2 C, does anyone have suggestions on how this problem could be systematically approached? My thoughts were very haphazard when I attempted to solve it, though it finally got accepted. I could imbibe the ideas for future problems.
Please refer to my explanation in this blog post, not sure if this is the best way as I could see some easier solutions after contest, but worth looking at: https://sahilbansal17.github.io/Competitive_Coding/2020/05/12/cf-641.html
CouNting Round, CountForces
gcdforces
Sounds really, really silly, I know, but I was unable to solve div 2A and I can't figure it out. Can someone point me in the right direction here? 79892383
Take a look at values of f(any odd number) and f(any even number).
Ah, I see. From what I can understand, if the input is even, then it's just adding 2 each time. If it's odd, then the smallest divisor is odd for the first iteration and then even (2) for the rest of the iteration.
Am I the only one who has a glitch in the rating changes of div.2? The ranking(eg. specialist and expert) is not changing.
Um_nik and tourist got swapped now!
I got TLE in Div2C (with pypy). My approach was to: 1) To find prime factors of all elements in the array. 2) Find last second minimum exponent for each prime factor in all array numbers, as taking LCM is like taking maximum for each pair of exponent. Multiplying all prime^(last second minimum) will give the answer.
Solution link: 79870496. Any better approach or any comment on TLE will be great.
Your approach is fine I did same and got AC, but your implementation has a time complexity of O(n*sqrt(2*n)*log(2*n)) which gives TLE. Instead, calculate the prime factorization till 2*10^5 beforehand using a sieve in n*log(n).
Thanks that worked.
Are u kidding me! The ratings updated, Wow!
I think i will make better performance if i stop checking div 1 standings during the contest i always solve a and b in div2 and then i go to see what is tourist doing
This is just a waste of time and focus. Good idea not to do it :)
OMG. Even I does the same.
Super clear (short )statement and good pretest. Thank you !
Can someone explain or point me to the direction where this is proven as I am having trouble understanding Div2C:
gcd(lcm(a,b), lcm(a,c), lcm(a,d)) = a*gcd(b,c,d)/gcd(a,b,c,d) = lcm(a, gcd(b,c,d))While thinking of gcd and lcm, think about the powers of prime factors, as each prime factor contributes to the result independently of the others.
In that sense, we can consider the numbers to be powers of the same prime factor, and all that matters is that power, so we replace the number by its log.
So, the operation $$$gcd(a,b)$$$ becomes $$$min(a, b)$$$, and $$$lcm(a, b)$$$ becomes $$$max(a, b)$$$, and $$$*$$$ becomes $$$+$$$, and so.
If you reformulate things like this, it can be generally helpful while working with gcd and/or lcm. However, it may be overkill sometimes.
It's not hard to use that way to prove your statement.
With your reformulation, I understand how the statement above is equivalent. This might be a typo but what do you mean by "so we replace the number by its log."
Also, do you have any suggestions on how one would come up with this during the contest (not knowing the lemma beforehand)? Or some resource/book where I can learn more about number theory as I would consider math one of my weaknesses.
I meant that if $$$n == x^k$$$, replace $$$n$$$ by $$$k$$$, which is its log to the base $$$x$$$.
There are multiple ways to approach the problem. As I said, you can think about what happens for each prime factor through these operations. This is a straightforward approach to reach the fact that the power of the prime factor in the final answer is the second minimum of its powers in the given array.
Generally, getting exposed to more ideas helps you sharpen your skills to approach problems and you get used to some thinking patterns. You should also not only know the solution of some problem you couldn't solve, but also think about how possibly you could have reached it.
I don't have in mind a specific resource, but you can search for some stuff and will find many nice things. I also think to improve in a certain topic you can simply solve problems on it with incremental difficulties and try to understand the solution and how to reach it as much as you can. Also it's most probably helpful to have someone to discuss with, even if he's not significantly better than you.
https://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml i found this... may be helpful ʕ•ᴥ•ʔ
I think the pretest is too weak since I FST on two problems. :(
I also fst on C,but I don't think pretest should be strong enough.Fst makes the contest more exciting.If pretests are as strong as system tests,what do we need them for?
well I think this is the biggest Uno reverse card in my entire life.
(I'm sorry guys I need to change this comment, I posted the old comment when the main comment was -6)
noice <3
Any other Blake's 7 fans here? I liked the name of the character in Div2 A to E. https://blakes7.fandom.com/wiki/Orac
I wanted to point out that this was legendary bad round for Poland. Our TOP7 (at the time, cause I am no longer there xD) competed in it, consisting of me, mnbvmar Radewoosh Errichto Marcin_smu Anadi and tribute_to_Ukraine_2022 and we lost respectively 163, 59, 115, 71, 103, 100 and 86 rating points. That totals to 697 which is almost 100 per person xD. Moreover last two rated rounds were my two the worst contests in last 5 years (at least I can counter that with 6th place in an unrated round between them and that I did pretty good in last OpenCup).
A : https://www.geeksforgeeks.org/find-the-gcd-of-lcm-of-all-unique-pairs-in-an-array/?ref=rp
The article was published after the contest, per webpage data: