By awoo, history, 6 months ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Dear Codeforces!

We are coming with another scholarship opportunity to share with you. This time, our scholarship is targeted towards the brightest women in the community.

As you might know, March is the month where the whole world celebrates women. At Harbour.Space we want to use this opportunity to encourage more women to join the tech world and challenge the gender-bias in this field.

We believe that gender equality in the workplace starts with gender equality in the classroom. For that reason, we are offering our Women in Tech Scholarship. The scholarship consists of:

• 50% off the yearly tuition fee: covers around €29,000 for bachelors and €11,450 for masters.
• 32% off the application fee: €85 instead of €125

Make sure to apply before March 31st to benefit from the scholarship and discount.

Don’t hesitate to share this opportunity with any bright women in your personal circle as well. A simple share can help us transform someone's life.

We are always happy to see Codeforce members join the Harbour.Space family.

Keep in touch and follow us on LinkedIn for more scholarship opportunities. And follow us on Instagram to stay in touch with our student life, events, and success stories from our students.

Good luck on your round, and see you next time!

Harbour.Space University

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 dlalswp25 6 128
2 Maksim1744 6 138
2 DreamingLeaf 6 138
4 nuip 6 149
4 kotatsugame 6 149

149 successful hacks and 1485 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A pavement 0:01
B PCTprobability 0:04
C PCTprobability 0:08
D Parliament 0:09
F 718_MiL 0:10
G rainboy 1:27

UPD: Editorial is out

• +132

 » 6 months ago, # |   -107 Please don't make round unrated during contest time. Which is cause Big heart break (Like last div 2).
•  » » 6 months ago, # ^ |   -29 why so many downvotes?
•  » » » 6 months ago, # ^ |   +11 Bruh when the hell did they want to make a round unrated before it begins ... That just happens against their will for some unexpected reason
 » 6 months ago, # |   0 Hoping for not getting unrated in this round...
•  » » 6 months ago, # ^ |   +9 Wish all run as usual...
•  » » 6 months ago, # ^ |   0 Round Delay 15 Minutes
 » 6 months ago, # |   -9 Hoping a good round
 » 6 months ago, # |   0 Good luck everyone!
 » 6 months ago, # |   +228 Here also women are being supported. Why to support based on gender? Skills should be the only criteria, irrespective of any stupid thing in the world. Rather scholarship should be given to the deserved ones who may not afford the fees.Everyone is allowed through the common channel then why to create a separate channel for women.This creates 2 channels for women and 1 channel for others.Is this equality? This is inequality for others.So, now what you will do to attain equality again?
•  » » 6 months ago, # ^ |   -55 Even though we can find highly skilled women, but the tech field is more or less dominated by male experts. So it's just an effort to popularize tech more among women by giving the scholarships only to them, because otherwise most probably men will take major portion of the scholarships once again. And yeah, "equality" is probably not what's going on here and achieving "equality" is probably not the actual target, but you cannot be brutally critical and honest in your advertising, can you? :D ..
•  » » » 6 months ago, # ^ |   +82 The same thing is with the less skilled male students as well. They are trying hard but not able to get to the top. Then a new channel should be created for them as well. Eventually, everyone will be on top then.In a real time situation, only the skilled person will be able to do the work in the best way no matter what the gender of that person is. And the people who have reached there through other channels will increase the load on the skilled people by not being able to do the things properly.
•  » » » » 6 months ago, # ^ |   +63 well said sir you have my respect
•  » » » » 6 months ago, # ^ |   0 Everyone should get equal opportunity and chances to grab any position in any institution but only capable one should hold that irrespective of their gender, background and culture. We must focus on creating equal opportunities.
•  » » » » 6 months ago, # ^ |   +45 If I was born in Brazil and I was interested in football, probably I will make it a profession. But if I am born where I am born, I will dare not try to make football my profession. It's not about less skilled people of the community, it's about those who have potential but rather not look into this field, due to lack of motivation, lack of personalities to look up to.
•  » » » » » 6 months ago, # ^ |   -16 Ok, then what about those who are not female and have lack of motivation and all.Why steps are not being taken for them?
•  » » » » » » 6 months ago, # ^ |   +20 Because women empowerment is like the trending page of youtube in today's society. What more can be said. But from what I have seen, harbour space has offered a lot of scholarships in the past, so one time giving them to the female, I don't think is exaggerating the issue and is bearable to me.
•  » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   -24 You are bad, that's what i think as a boy I_love_Kim_Dahyun
•  » » » » » » 6 months ago, # ^ |   +1 Because demotivated people have the opportunity that everyone else has, lack of motivation is a personal issue whereas women face hurdles because of their identity, i.e. being a woman. It has nothing to do with the individual bt instead with the society we live in which is why it is imp for the society to fix the inequality that occurs in it. This is why the 2 cases arent comparable.
•  » » » 6 months ago, # ^ |   -26 It is worrying that your comment has a negative contribution
•  » » » 6 months ago, # ^ | ← Rev. 3 →   -43 ****For those who want to Down Vote, look at this 3 minute video then its your choice to down Vote**** ****Your text to link here...**** ****https://www.youtube.com/watch?v=4kFC7669quE****I support the scholarship for women and this picture says a lot about why I do, it is called Equity it much better than Equality. Support ++, it's not about the gender it's about people and society if you are in a country where females need more support we should need to do it if you are in a country where males need more support we should need to do it. And I believe this scholarship is provided to females because the place where it provides need more support for female.https://www.salvationarmy.org.nz/sites/default/files/uploads/screen-shot-2020-03-18-at-10.43.47-am.png
•  » » » » 6 months ago, # ^ |   +24 Oh, You mean to say that women are weaker and need extra support in order to become equal to men?So, as shown in the picture, please explain in what way are they "handicapped"?
•  » » » » » 6 months ago, # ^ |   0 @errorfound No one is saying neither women are weaker nor men's as well, it's been said that in some places women need to be given more chances for their development and in some places men's need to be given more chances for their development. it depends on the society in which they are in and they need to be supported. I don't know why are you using the work "Weaker", no one is weaker it's just some people need to be given chances. I am not saying women are handicapped, the context of the image is entirely different.giving equal opportunity to all is good but in some places, some people are need to be given more opportunity(it does not mean to be men or women)
•  » » » » » » 6 months ago, # ^ |   +3 From where I belong to, I have always seen both genders treated equally. Then why we have to give women more chance?Ok, tell me one place where men are given more chances
•  » » » » » » » 6 months ago, # ^ |   +14 @errorfound, I am happy that you are in a place where both genders are treated equally. but it does not mean all part of the world is same as where you are from. there are still places where women need some support and these scholarships are meant for the same. I can understand women are given more opportunities much better than past but still in some places they need support and we should do it.
•  » » » » » » » » 6 months ago, # ^ |   +1 uplifting them through such means is also a form of sexism. What about a more talented male who is left out just because of his gender. Is it his fault that majority of people in his field are male?
•  » » » » » » » » » 6 months ago, # ^ |   0 @Sundaram_Sharma, just because a fraction of the total population of women were given the small opportunity does not mean all the opportunities for men were taken by them. can you say a company has 100 vaccines and the entire 100 vaccines are filled with females? , even now companies were trying to make male-female ratio 70:30 in all companies, before few yers the ratio of male to female is 95:5 where are you during that time why did you raise your voice against it? "what is flat in being women Since the majority of people in the field are men why arent they are given equal postings?", try to understand no one is trying to take means opportunity, they are creating more opportunity for women
•  » » » » » » » » » 6 months ago, # ^ |   +7 ok "just a fraction of total women population" is not the right way to put it. I have seen this first hand in my college. Secondly, even if it is a fraction it is unfair and that is what matters. How am I supposed to respect my female colleagues when I have seen so much bias. As for the time when ratio was 95:5, I was at the age that I didn't understand the word feminism then. And even if the ratio was 95:5 without any bias in selection, it is totally fair. Women are given 33%,even 50%, reservation in political and competitive seats in many places and fields. why aren't they given 50% reservation in the job where they have to clean sewers. Even there, male have a much higher ratio, even more than 95:5. It will take 20 30 more years for a large group of people to see how much damage feminism has caused. till then we gotta suffer.
•  » » » » 6 months ago, # ^ |   +2 nice one bro
•  » » 6 months ago, # ^ | ← Rev. 2 →   -15 A hypothetical reason maybe that sex ratio plays a vital role when meritorious males are unable to decide their college out of their own best choices... harbour does wants to fill in every hole..
•  » » » 6 months ago, # ^ |   0 Please refer to my comment that is just above your comment
•  » » 6 months ago, # ^ |   +137 It's not a coincidence that there are much fewer women in programming, engineering, science, etc.Pretty much every culture in the world normalizes stereotypes about women. Being overly superficial, tying their self-esteem to whether they look attractive, feeling pressured to marry and have children so they don't "fail" as females, among many others. Imagine your family, friends, and community all having these types of expectations about you, ever since you are born. I don't think you'd be very motivated to face the enormous challenges needed to thrive in the tech world or other areas dominated by men. You'd be distracted trying to fit in to this toxic social expectation.These extra opportunities for women attempt to compensate this cultural disadvantage, and try to fight the huge stigmas that constantly pull women back from professional success in man-dominated areas. It doesn't even come close to fixing social female oppression as a whole, but it's a start.
•  » » » 6 months ago, # ^ |   -53 This was the case earlier. Now women are CEO of companies, are doing everything which earlier only men did and there is no barrier for them in any field.The thing is: by supporting females everywhere and to such an extent, is this justice for others?Rather, now others are struggling in the same way women were struggling earlier.So we are in the same situation again, but this time men and others are the victims.
•  » » » » 6 months ago, # ^ |   +29 Stereotypes still exist, although in some cultures very little. I don't think men are the victims at the moment and they won't be in the near future
•  » » » » » 6 months ago, # ^ |   -27 I don't know about other fields but in IT Jobs men are the victim. In order to maintain gender ratio, females are being hired in large numbers over others. This leads to other candidates not getting the job they deserve.Hence Proved!!!One such example is this: https://codeforces.com/blog/entry/82937
•  » » » » » » 6 months ago, # ^ |   0 Consider all people who have the mind to become engineers. Of all these people, the females are at a disadvantage in that they are less likely to become engineers than the males.Efforts to promote women aim to compensate for this disadvantage.
•  » » » » » » » 6 months ago, # ^ |   0 Ok, then promote in all the fields.Make gender ratio equal in the Army as well.Do you think this will be fruitful for the country?Rather this will ruin everything. Now consider the same logic in other fields!
•  » » » » » » » » 6 months ago, # ^ |   -28 I think Harbour Space does not care about the gender ratio in the army. And probably they do not care for "if it is good for the country", whichever country that could be.But they care for if women have equal chances at Harbour.Space, and because of this they are doing something there.
•  » » » » » » » » » 6 months ago, # ^ |   0 Thant was an example.You are saying that they are giving equal chances this time, that means they were not giving equal chances before.Can you show me any single post from harbour University where they said that they will not entertain women?Every time every where equal opportunities are being given to everyone.Hence, no need of 2 opportunities only on the basis of gender
•  » » » » » » » » » 6 months ago, # ^ |   0 We are going in circles, see https://codeforces.com/blog/entry/88744?#comment-771912
•  » » » » » » » » » 6 months ago, # ^ |   0 You might be under illusion if you truly believe that skill is the only thing that matters. It is a university that has no accreditation yet. Maintaining the gender balance could be one of the main criteria for such assessment.It's great for their reputation if students are all skilful and have greater chance to thrive in academia and the industry, but it hurts if they don't have enough female. As simple as that.
•  » » » » » » 6 months ago, # ^ |   +55 I find it worrying that one extra scholarship from one university seems to trigger you more than the wage gap, work environment harassment, pregnancy discrimination, and many other historic world-wide proven injustices women face in professional fields.You either lack empathy to understand women's ongoing struggle against gender inequality, or you need to inform yourself better about the subject.
•  » » » » » » » 6 months ago, # ^ |   -40 You are not understanding what he is saying.
•  » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   +4 Hey Eiden, I also think too much support is given for females. What you are saying did exist but not do exist. Even if it exists it is very little. Now a days only women are taking advantage over men by providing false accusations, gaining sympathy even it is her fault or etc.. Also women also have many advantages over us. So i dont think giving extra support to them is needed. Pls look at this video. https://www.youtube.com/watch?v=e57iXe-QJio
•  » » » » » » » 6 months ago, # ^ |   0 I understand what you're trying to say, but giving opportunities to women just because of the problems they face? That's a bit weird. Of course, opportunities should be provided equally to people of all genders, but I would rather have competent people leading the world rather than just men or just women.
•  » » » 6 months ago, # ^ |   +6 Better words were never spoken.. Thanks you made me re-realise few things..
•  » » » 6 months ago, # ^ |   0 Gender norms,Cultural Stereotypes are not the only reason. We have to admit that there are fundamental differences between genders. Those differences also play a role in this.'Gender specific opportunities' is an over simplified solution for a very complicated Sociocultural problem.
•  » » » » 6 months ago, # ^ |   +3 LOL!!! It is obvious that there are differences between genders. So, what about those fields in which there are a lot of women, so are male being given "Gender specific opportunities" in that field.If you find such a thing then please tell me about it.And talking in general, if you are stuck in a problem then who will be able to solve it, a skilled person or a person who is not skilled but is the one who was given "Gender specific opportunities" ?
•  » » » » » 6 months ago, # ^ |   +1 I'm confused.I did not say that we need gender quotas because of differences between genders.my comment was against gender quotas.smh
•  » » » » 6 months ago, # ^ |   +1 Spoiler...
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +8 Please enlighten me on what fundamental difference makes it more difficult for women to have jobs in tech(as this post is concerned with).
•  » » » » » 6 months ago, # ^ |   0 It doesn't makes it more difficult for women.(Maybe in some cases it generally affects any carrier. Like having to take care of a baby) I think those differences affects their preference. There are many reasons. Men tends to work more hours than women. Women were evolved as the caretaker of the family so they prefer carriers in healthcare etc. Please note that I'm generally speaking and not telling what women should and shouldn't do. To achieve equal representation in STEM fields we have to consider about those reasons too. That's why i said gender quotas are an over simplified solution.
•  » » » » » » 6 months ago, # ^ |   0 No one advocated gender quotas. No one believes having gender quotas will solve the larger cultural issue. He specifically mentioned having extra opportunity. Interesting how on a post about fewer women in STEM, you immediately imply an inherent gender difference, then immediately backpedal.
•  » » » » » » » 6 months ago, # ^ |   0 "These extra opportunities for women attempt to compensate this cultural disadvantage,"These extra opportunities are for the cultural disadvantage.I did not "immediately imply an inherent gender difference". These extra opportunities only focus on a single aspect of the problem. My effort was to just imply that there are more aspects of the problem. One of them being inherent gender difference.We can't completely fix a large problem right away so that strategy is fine as long as it does not affect negatively on other groups. And i don't think i backpedaled. I stand by every statement i made.
•  » » » » » » 6 months ago, # ^ |   0 Women are just as qualified as men to do STEM jobs. If they are a minority in those fields, it's because society has historically pressured them to stay away from them, by maintaining incorrect, vicious stereotypes and stigmas such as the ones you're claiming right now.
•  » » » 6 months ago, # ^ |   0 I think this video is informative and/or entertaining, in terms of the state of neo-feminism (at least in the West). It's worth a watch!
•  » » » 6 months ago, # ^ |   +1 But does it actually help? How can women in IT be equally respected (as they should be) if we might assume they got there easier?
•  » » » » 6 months ago, # ^ |   +7 It's harder for women to thrive in the tech world because they face extra challenges of gender inequality and stereotypes. Giving them a small nudge like a scholarship helps relieve them from that extra effort.Therefore, it's wrong to say they "got there easier". Otherwise, a woman in IT could say you got there easier than her because you never struggled against gender inequality on your way there.
•  » » » 6 months ago, # ^ |   +9 Maybe I am less informed on this matter, but I feel like you are exaggerating. I am a male and my mom has already started pressuring me to marry and have children even though I don't want to. On top of that, it's expected of me (as a male) to look after them financially. No matter how stressed or hurt I am, I am told to man up and hide my emotions. I am not that distracted trying to fit in to this toxic social expectation and I hope I won't be in the future. I have sister and some female cousins. I have never seen any of them be pressured for looking attractive, we all were instructed to look tidy.Creating a separate competition based on gender doesn't solve the roots of the problem (some people's weird thoughts and some other people's vulnerability to those thoughts). Doesn't it mostly benefit women who were privileged (born into good family, hence doing better because of having less distraction / pressure from immediate surroundings)? I can understand doing so in some sectors like medical / psychiatry (as female patients may feel more comfortable having female doctors), but why IT?
•  » » » » 6 months ago, # ^ |   +31 There are toxic stereotypes about men as well, and I'm also firmly against them. But it's less likely for them to pull us back professionally. Women are prone to be catalogued as more delicate than men, which translates as weakness or unpreparedness for professional challenges or leadership positions. Also, women are still mostly expected to quit their job when they have children, to take care of them. Moreover, being a stay-at-home dad is still viewed as a lack of masculinity. Ask your mom what she would think if your wife worked to sustain you while you have no job and stay home taking care of your kids.Eventually, women who have talent and potential for IT jobs are discouraged by these realities, leaving only men in charge of them, even if they're less prepared. Then, the next generation of girls finds out there's no women in IT, catalogue it as a man's job, and feel unmotivated to choose it as a career. Measures like this scholarship aim to break this vicious cycle, and make sure women don't waste their talent due to cultural oppression.Gender inequality happens with women of all social statuses. So even if a privileged woman gets the scholarship, it still helps combat social stereotypes, because it normalizes the idea of women doing "men's jobs". They might even inspire girls not born in privilege to fight their way into a tech job themselves.You mention women inclusion important in medicine and psychiatry, but not in tech. You are misunderstanding what all this is about. The ultimate goal of work equality is that everyone should have a chance to choose their profession, without being judged, stereotyped, or harassed in any way for their decision.
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   +1 Thanks for explaining. I kinda get your point, but I can't agree with your last statement, I don't think women are currently being judged, stereotyped or harassed for joining IT. At least rational people don't have such stereotypes. But if some women get their job easier, that will definitely put that idea into others' mind and even rational people may start having stereotypes that women got their job despite being less qualified and it may hurt real qualified women.Apart from that, I agree with you.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +22 When you say that it mostly benefits women who are privileged, this is true because of the wider economic oppression within society. To combat this, we don't ignore the gender based oppression, instead, it is necessary to take up an intersectional viewpoint which considers both economic and gender oppression, this includes supporting women in IT(which has been a predominantly male-dominated field, and women historically being pushed out), and supporting poor, lower class people and women in IT.
•  » » » » » 6 months ago, # ^ |   0 I agree, but when were women pushed out from IT? Maybe they were left behind, but not pushed out. Maybe they are less interested in it? School students don't usually have much burden due to gender, but how many high school girls (compared to boys) participate in math or informatics olympiads or try CP?
•  » » 6 months ago, # ^ |   +21 Attack on Feminists!
•  » » » 6 months ago, # ^ |   +2 Ironically that is pro-feminism, since feminism is based on the advocacy of women rights on the basis of equality, and I think it is a solid argument that exclusive scholarships abuse the notion of equality.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +10 When there's concern for women, it's concern for the women community as a whole, but when a there's a talk of the man it's only about that particular man. Nobody stands with him but himself. Is this what feminists wanted? congo succeeding for sure.
•  » » 6 months ago, # ^ | ← Rev. 3 →   -42 I also agree with you. Let's make a movement #maleequality. Let all men not participate in today's round as symbol of protest. To show your protest, I request all men on this platform to downvote the blog and not participate in today's contest.Those who are downvoting my comment are SIMPS. If you are man enough, upvote my comment.
•  » » » 6 months ago, # ^ |   +19 lol no
•  » » 6 months ago, # ^ | ← Rev. 3 →   +91
•  » » 6 months ago, # ^ |   0 Why to support based on gender? Skills should be the only criteria,Can you develop good programming skill, if no-one around you do programming, no-one support you or appreciate you for your programming skills, or people say it's not for someone likes you.I do programming because, its in many way rewarding for me and there is lot of things that motivates me.P.S Exception may exist, but we are talking about ordinary humans.
•  » » 6 months ago, # ^ |   0 its such a good point, try this on reddit you'll rock:)
 » 6 months ago, # |   -116 MikeMirzayanov geranazavr555 cannor147 brother please note that whenever participants goes around 20k, the website crashes. Please do the needful ASAP! Observing this thing from a long time!Please Upvote guys to make this noticeable to team CF!
•  » » 6 months ago, # ^ |   +38 You can be noticeable with negative comment too! :D
 » 6 months ago, # |   0 Can we please bring this announcement on top of today's round(708)?
•  » » 6 months ago, # ^ |   0 Finally now it's on top!!!
 » 6 months ago, # |   +291
•  » » 6 months ago, # ^ |   +54 Welcome to ratism
•  » » » 6 months ago, # ^ |   -51 Bro ratism isn't a real thing, lmao. There are just too many trolls.
•  » » 6 months ago, # ^ |   +41 :(
 » 6 months ago, # |   +2 Expecting a good round without any failure and a high rating increase to all ^_^.
 » 6 months ago, # |   0 We are for gender equality that's why we make supportive only for women. Guys, really? It looks like you want to take the best from women and the best from men, but it is not gender equality. You should choose the best from both genders at the same time.
•  » » 6 months ago, # ^ |   +8 We need to support women too... Do you want to have a girlfriend who can help you debug the code? Increasing the number of women in programming increases your chance to find one.
•  » » » 6 months ago, # ^ |   +17 I have such girlfriend)))
 » 6 months ago, # |   +39 Its clashing with another big contest between India and england :P
•  » » 6 months ago, # ^ |   -26 Nobody cares!
•  » » 6 months ago, # ^ |   0 Can't hope for India to bat first also
•  » » 6 months ago, # ^ | ← Rev. 2 →   +8
•  » » 6 months ago, # ^ | ← Rev. 3 →   -17 .
 » 6 months ago, # |   +13 Aren't we gonna have a testing round after what happened yesterday?
 » 6 months ago, # |   +12 Codeforces should not be a place for messages like this. Can you name the month when world celebrates men?
•  » » 6 months ago, # ^ |   +8 It's in "NEVER" month
•  » » » 6 months ago, # ^ |   +24 equality goes brrr
•  » » » 6 months ago, # ^ |   +1 international men's day is November 19th
•  » » 6 months ago, # ^ |   -39 You do realise your hypocritical behavior nah ?
•  » » » 6 months ago, # ^ |   +39 Separating of women makes more inequity. It shouts "You are woman, you can't compete with men, so we create special event for you". That's sounds sad.
 » 6 months ago, # |   +12 hope good performances.
 » 6 months ago, # |   +1 Good Luck Everyone !! I wish this round to be wihtout any technical issues and have interesting problems
 » 6 months ago, # |   -9 for me, neither of the three websites m1/m2/m3 are loading for the past few months. They are down for me right now too.
•  » » 6 months ago, # ^ |   +6 They are working fine for me.
•  » » » 6 months ago, # ^ |   0 +1
 » 6 months ago, # |   +5 oh,there are two different contests in two next days...I don't know which one to choose...
•  » » 6 months ago, # ^ |   +9 Which contests are you talking about?
 » 6 months ago, # |   +3 good luck everyone, I hope this round will be rated
 » 6 months ago, # |   0 Hope this round will be rated!!
 » 6 months ago, # |   +22 Educational round 106 will be my 106-th rated contest
 » 6 months ago, # | ← Rev. 2 →   0 18k+ Registrations.... UPD: At this rate 20k+..
 » 6 months ago, # |   0 BringItOn
 » 6 months ago, # | ← Rev. 2 →   0 !(viva la codeforces)
 » 6 months ago, # |   +149 Sorry, +15 minutes. Hope the problems will be OK. Good luck on the round!
•  » » 6 months ago, # ^ |   0 Good luck to you too Sir for the servers..
•  » » 6 months ago, # ^ |   -29 Please ensure that contest is rated.
 » 6 months ago, # |   +1 15 min delay
 » 6 months ago, # |   0 Extended , Hope at the time of contest everything run properly and the contest will be rated !!
•  » » 6 months ago, # ^ |   0 Educational rounds seem to be attracting a greater number of participants than usual...
•  » » 6 months ago, # ^ |   0 lets hope no more delay and rated round. wish u positive delta : )
 » 6 months ago, # |   -10 Another 15 minutes :(
 » 6 months ago, # |   -11 15 min delayed? why
 » 6 months ago, # |   +37 what to do with my life for the next 15 minutes!!
•  » » 6 months ago, # ^ |   +4 Its just a delay dude, not the end of the world.
•  » » 6 months ago, # ^ |   0 do regret
 » 6 months ago, # |   -7 15mins again :(
 » 6 months ago, # |   0 Delayed by 15 minutes!!
 » 6 months ago, # |   -11 Delay is new tradition on codeforces
 » 6 months ago, # |   -11 what happened?? 15 mins late?
 » 6 months ago, # |   0 Please... Don't discuss the delay to make the comments meaningless...
 » 6 months ago, # |   -11 why most of the Educational round delay for 15 min :(
 » 6 months ago, # |   0 hope Contest run properly this time
 » 6 months ago, # |   0 Waiting to get my first positive rating :)
 » 6 months ago, # |   +3 I am curious, is it finalized that the contest will have 6 problems or 7 problems, or are we supposed to know only after we enter the contest?
 » 6 months ago, # |   +6 Does codeforces do this for 20k registrants?
 » 6 months ago, # |   -28 Delay by 15 minutes.
 » 6 months ago, # |   +9 2 min before the contest — electricity cut, no wifi.4 min after the contest — (joining with mobile data and hotspot) contest delayed for 15 min.
•  » » 6 months ago, # ^ |   0 lucky lucky
•  » » 6 months ago, # ^ |   +3 After the contest — +200 delta.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Next contest (-100) delta
 » 6 months ago, # |   -9 we hope this round to be rated though if i get -120 today lmao
 » 6 months ago, # |   -10 whenever there is a delay in contest, le me: It's contribution time xD
 » 6 months ago, # |   -26
•  » » 6 months ago, # ^ |   +1 Me for C :(
 » 6 months ago, # |   0 HardForces part INT_MAX.
 » 6 months ago, # |   +11 Got 4 wrong submissions before making the correct one for B and now I can't stop seeing that green text Accepted. I just love it when I solve a problem after struggling hard and thinking hard Thank you codeforces for making me have such good feeling in every contest
•  » » 6 months ago, # ^ |   0 what is wrong with my approach? I print "No" only if the string contains 1100 as a substring else "YES"?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 what about 1110100011.. u can remove mid 1 then u wl be left with..?
•  » » » » 6 months ago, # ^ |   0 i can remove both 0s
•  » » » 6 months ago, # ^ |   0 try 110100, answer is no but your solution gives yes
•  » » » 6 months ago, # ^ |   0 What about 110100? It doesn't contain 1100 and still, the answer is "NO"
•  » » » » 6 months ago, # ^ |   0 coz it can be converted to 1100 after removing that mid 1
•  » » » 6 months ago, # ^ |   0 your solution will output YES for string 1101001, but answer is NO.
•  » » » » 6 months ago, # ^ |   0 Simply put, if there is consecutive 11 followed by a consecutive 00 in the string somewhere, it will be NO. try it out. I had to make around 20 cases to think about this
•  » » » 6 months ago, # ^ |   0 I used the approach that once we have 11 , then after that 11 all should be 1 ,to maintain in ascending order. So after 11 if there is any occurence of 00 , we print NO. 1100 being together is not necessary. Lets say If I run your code on 110100, There is no instance of 1100 but still the answer is NO I hope you understood!
 » 6 months ago, # |   +15 Question about D problem. And not, not about the solution, it is relatively obvious. The question is: how to factorize all this in 2 seconds?
•  » » 6 months ago, # ^ |   0 exactly
•  » » 6 months ago, # ^ |   0 I use O(sqrt * log) and passed in 1.2s（
•  » » » 6 months ago, # ^ |   0 I also did the same thing, but after looking at your code, it seems like using vectors was the reason for TLE.
•  » » » » 6 months ago, # ^ |   0 I just removed two vectors and it passed, I wonder how non-C++ solutions will pass such a tight limit :(
•  » » » » » 6 months ago, # ^ |   +3 yep i had to do all kinds of optimisation in java but its all good learning experience
•  » » » » » » 6 months ago, # ^ |   +1 Not all. Took your submission 110397725, replaced all long's with int's, replaced x / i != i with i * i != x in one place, and it passed in $1.9$ s — dangerous, but it's expected from non-optimal solution.
•  » » » » » » » 6 months ago, # ^ |   +3 you are right! I dont know why i took everything long. Anyways when i failed system testing, to avoid recalculating i saved pre visited prime factorisations in an array and my "all long" code passed in 1.9 but after fixing that its passing in about 1.6s which is less dangerous i guess :)
•  » » 6 months ago, # ^ |   +3 I maybe answering above my league but maybe using sieve can help since it's time complexity is O(nlognlogn).. Link
•  » » 6 months ago, # ^ |   0 In my case, I used this technique. Preprocessing and then for each query, simply $O(sqrt(x))$.
•  » » 6 months ago, # ^ |   0 pray I guess :D
•  » » 6 months ago, # ^ |   +26 We just used linear sieve (that maintains the smallest divisor for each number). After calculating smallest divisors, we can find the number of different divisors for each number in linear time as follows: the number of divisors of $x$ is the number of divisors for $\frac{x}{d[x]}$, plus $1$ if $d[x] \ne d[\frac{x}{d[x]}]$.I agree that time limits may be a bit tight though.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 I think you mean number of different prime divisors, instead of number of divisors. A follow up question, is there any method to calculate number of different divisors (not necessarily prime) for 1 to N in linear (or nlog(logn)) time ?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +27 Yes, I meant prime divisors, thank you.To calculate the number of distinct divisors, we can use a similar recurrent relation.Since the number of distinct divisors of a number equal to $p_1^{k_1} p_2^{k_2} \dots$ is $(k_1 + 1)(k_2+1)\dots$, let's calculate an auxiliary recurrence: let $k[x]$ be the number of times $d[x]$ (the smallest divisor of $x$) appears in its factorization. $k[x]$ is either $1$ if $d[\frac{x}{d[x]}] \ne d[x]$, or $k[\frac{x}{d[x]}] + 1$ otherwise. Then, the number of distinct divisors of $x$ (let's call it $f[x]$) is $\dfrac{f[\frac{x}{d[x]}] \cdot (k[x] + 1)}{k[x]}$ (since we are replacing $k[x]$ with $k[x] + 1$ in the number of divisors).
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 when counting f (x) — what about for each number up to 2e7 count the number of prime divisors = cnt and add 2^cnt to the answer(C(0, cnt) + C(1, cnt) + ... C(cnt, cnt) = 2^cnt
•  » » » » » » 6 months ago, # ^ |   0 What if some prime divisor appears multiple times in the factorization?
•  » » » » » » » 6 months ago, # ^ | ← Rev. 10 →   0 Erotasphen rep(i, 2, N){ if(used[i]) continue; for(int j = i; j <= N; j += i){ divisor[j]++; used[j] = 1; } }with the help of this type of Erostaphen sieve, in an easy way, I count the number of prime dividers
•  » » 6 months ago, # ^ |   0 Aw, I had investigated something interesting. This codes calculates two arrays: $pr[i]$ — minimum divisor of $i$ or $-1$ if $i$ is prime, $cnt[i]$ — number of prime factors of $i$. If I understood correctly, it works faster than $O(n \log \log n)$, and gets $800 ms$ on $D$. Codeconst int N=20000005; int pr[N]; int cnt[N]; void prepare(){ for(int i=0;i<=N;i++) pr[i]=-1; for(int i=2;i<=N;i++){ if(pr[i]!=-1) continue; for(long long j=1ll*2*i;j<=N;j+=i){ if(pr[j]==-1) pr[j]=i; } } for(int i=2;i<=N;i++){ if(pr[i]==-1) cnt[i]=1; else{ if(pr[i]==pr[i/pr[i]] || pr[i]*pr[i]==i) cnt[i]=cnt[i/pr[i]]; else cnt[i]=1+cnt[i/pr[i]]; } } } 
 » 6 months ago, # |   +3 Great problems.Can someone tell me hints for problem D? (Please put them in spoilers) Thanks.
•  » » 6 months ago, # ^ |   +16 Spoilergcd divide lcm Spoilergcd divide x you can iterate the gcd over divisor of x and infere the lcm Spoilerfor given gcd and lcm the number of solution is a power of 2 depending on their quotient
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 Hint 1$a * b$ = $gcd(a, b) * lcm(a, b)$ Hint 2For each possible $g$ let's count how many pairs $(a, b)$ with $gcd(a, b) = g$ satisfies our condition. Hint 3How can you bruteforce only $O(\sqrt x)$ possible options of $g$?
•  » » 6 months ago, # ^ |   +2
 » 6 months ago, # |   +30 Why very tight limit in D? :(
 » 6 months ago, # |   0 What's the key idea to solve D ?? :(
•  » » 6 months ago, # ^ |   0
•  » » 6 months ago, # ^ |   +6 let G=gcd(a,b) L=lcm(a,b) Now cL-dG=x G (c(L/G) — d ) = x L/G must be an integer Thus G will be a factor of x By this we can check for all possible values of G and L Now for given G and L , The number of possible values of (a,b) corresponding to it is 2^(number of prime factors of L/G).
•  » » 6 months ago, # ^ |   +1
 » 6 months ago, # |   0 How to solve D?
•  » » 6 months ago, # ^ |   +12 Hint: gcd(a,b) must me a divisor ofx;
•  » » 6 months ago, # ^ |   +1 HINT 2 if we are given gcd(a,b) and lcm(a,b) how many possible pairs (a,b) such that a,b>0 exist ?? Example gcd(a,b)= 2^2 * 3^4 * 5 * 7^2 lcm(a,b)= 2^4 * 3^4 * 5^2 * 7 The Number of pairs is 8
•  » » 6 months ago, # ^ | ← Rev. 2 →   +4 You might have got this relation. Here $g = gcd(a,b)$$a\times b = g\times \frac{(d\times g + x)}{c}$.You can reduce it into...$\frac{a\times b}{g^2}=\frac{(d+\frac{x}{g})}{c}$From here you can see that $g$ has to be a factor of $x$. And a disjoint distribution of the factors of R.H.S leads to unique values of $a$ and $b$.A disjoint distribution basically means partitioning the prime factors into two groups such that each prime factor belongs to exactly one group.
•  » » 6 months ago, # ^ |   +1
 » 6 months ago, # | ← Rev. 2 →   -11 .
 » 6 months ago, # |   0 Problem D:- Can someone please explain how we are getting 8 pairs in the 4th test case?
•  » » 6 months ago, # ^ |   +11 [(1, 16), (5, 30), (10, 15), (15, 10), (16, 1), (25, 100), (30, 5), (100, 25)]
•  » » » 6 months ago, # ^ |   0 Thanks
 » 6 months ago, # | ← Rev. 2 →   +1 argh -- anyone else keep getting runtime error on testcase 4 for D? I hope I was actually doing something wrong and it wasn't just a weird quirk of pypy.
•  » » 6 months ago, # ^ |   +15 You need to sieve till 2 * 1e7.
•  » » » 6 months ago, # ^ |   +10 AHHHHHHhhhhhhhhhhhhhhhhhHHHHHHhhhhh dammit that's tricky. Thanks, that fixed it... now I just have a TLE on test set 15 like everyone else :p
•  » » » » 6 months ago, # ^ |   0
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 Hey, How you concluded that upper limit of lcm would be 2*1e7 ??I am unable to figure it out. Thanks in advance.UPD : Got it... we actually require upper limit of lcm/gcd which is 2e7...
 » 6 months ago, # |   +1 Was E dp?
•  » » 6 months ago, # ^ |   +3 Yes I think so, didn't manage to finish the code in time though.
•  » » 6 months ago, # ^ | ← Rev. 2 →   -10 Sorry...wrong problem.
•  » » 6 months ago, # ^ |   0 E seems to be a dp.We can build a dp[i][j][b]=num seqs with i symbols from x and j symbols from y and last one taken is from x/y -> b=0/1This gives us the number of all subseqs starting at indexes 0 in both, x and y.Then we can sum up from that table (...somehow...) to get the numbers for all substrings. See that solution for example (neal) : https://codeforces.com/contest/1499/submission/110349694
 » 6 months ago, # |   +1 How to solve C. Should i use dynamic programming here. Anyone plz help..!! Thanks in advance.
•  » » 6 months ago, # ^ |   +8 greedy will work. Maintain minimum for odd and even index separately.
•  » » 6 months ago, # ^ |   0 it is greedy, neal used greedy and greedy makes perfect sense here...however, i spend an hour implementing it and always failing at 4th test set...just don't know what i did wront
•  » » » 6 months ago, # ^ |   0 It must probably be due to overflow. Same happened with me.
•  » » » » 6 months ago, # ^ |   0 yap with ll it doenst work but with ull it works....thats soo evil
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 It works with ll too.
•  » » » » » » 6 months ago, # ^ |   0 Yeah u right, I initilized INF badly
•  » » 6 months ago, # ^ |   +2 Nope. The answer is: Try using from 2~n segments. Observe that you can solve horizontal and vertical parts separately. Also, WLOG you can assume the first step is horizontal. Let's consider only the horizontal part. Suppose you are using k segments, then the horizontal steps are segment 0, 2, 4, 6..... it is easy to figure out how many horizontal steps you took, suppose it is E. Then for those E segments, it is obvious that you should use the one with the minimum cost to move n-E+1 length(and for other segments, move length 1). So prefix minimum and prefix sum(on even indexes) will do the work. Then for every k, you add horizontal and vertical, take minimum. That's it.
•  » » 6 months ago, # ^ |   +2 The idea in C is to split both directions.We can go a number of steps in one direction with even costs, so c[0]*someLen+c[2]*someLen+...Same for other direction, but with odd indexes.Then, for each direction and number of steps there is a minimal cost of: each c[i] one time and the minimum of the c[i] n-i times.And finally, the whole path consists of i steps in even direction, and i or i-1 in odd direction. Find the min of those.
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 Isn't this an edge case? 1 1 1 2
•  » » » » 6 months ago, # ^ |   0 Cheapest path here is obviously n+n for using c[0] and c[1]. Whats the edge in there?
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 I know but doesn't your solution do this? (1 * 3) + (1 * 3) + (1 * 1) + (2 * 1)
•  » » » » » » 6 months ago, # ^ |   0 Nah... The solution finds the min price for using c[0], or c[0]+c[2]. And c[1], or c[1]+c[3].Then from those it chooses the min of possible number of cost used in each direction (1,1), (1,2), (2,2)
•  » » » » » » » 6 months ago, # ^ |   0 Oh, got it thanks
•  » » 6 months ago, # ^ |   0 Sort of Dp, you have to assume that some path used will be the last one so you make an iteration from 3 to n (as the initial state is when the answer is n*c[1] + n*c[2] where c[i] = cost for path i). Now at every step, you use a greedy solution, based that if you use first i paths, on the odd i you will have paths for x axis and on the even i you will have paths for y-axis. So in order to use all x paths and y paths, the optimal way is as follow: Supose you have "a" paths of type x-axis and "b" paths of type y-axis. Then the most optimal solution is the min(all x-axis paths) * (n-a+1) + sum(all a paths — min(all x-axis paths)) + min(all y-axis paths) * (n-b+1) + sum(all b paths — min(all y-axis paths)). You have to calculate this at any step and at the end find the minimum answer, Hope you understand!
•  » » » 6 months ago, # ^ |   0 You can check my solution for more clarifications! https://codeforces.com/contest/1499/submission/110363833
•  » » 6 months ago, # ^ |   0 Think Greedily. You can also refer to this video. Problem C Minimum Grid Path
 » 6 months ago, # |   0 How to avoid TLE on TC 15 in question D?
•  » » 6 months ago, # ^ |   0 Maybe removing #define int long long will work (in C++)
•  » » 6 months ago, # ^ |   0 Precalculate number of prime factors in O(2*1e7*log(2*1e7)) using sieve.
•  » » 6 months ago, # ^ |   0
 » 6 months ago, # |   0 I kept getting TLE on test 15 in D. What's the ideal complexity?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +6 Alog log(A)+ t sqrt(A) where A is 10^7actually you can do much faster if you precompute also the factorisation and not just the number of prime factor so Alog log(A)+ t d(A) where d is the maximal number of divisor for an integer up to A
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 A is 2*10^7, using 1e7 caused me RE on test 4 XD
•  » » » » 6 months ago, # ^ |   +1 yes but in a O() you can ignore constant
•  » » » » » 6 months ago, # ^ |   +1 This response doesn’t make sense. 10^7 is just as much a constant as 2 so could just as easily be ignored with this logic.He’s saying that the relevant upper bound is 2*10^7 not 10^7 which is correct.
 » 6 months ago, # |   +3 Getting runtime error on test-4 in problem D, would really appreciate if someone could help.110384394
•  » » 6 months ago, # ^ | ← Rev. 2 →   +18 I think your MAXN need to be 2e7 because if c = 1, d = 1e7, x = 1e7 the req could be 2e7
•  » » 6 months ago, # ^ |   0
 » 6 months ago, # |   +1 Can someone explain the logic behind C, can't wait till the arrival of editorial, Any help would be really appreciated !!!
•  » » 6 months ago, # ^ |   +2 You must iterate on the number of segment it would require to reach $(n,n)$. It is obvious that number of segments is at least 2, so $n\cdot (c_1+c_2)$ is the base cost. Now, iterate on the number of segments used from $3$ to $n$. For example if the number of segments required is $L$, then we will consider just a prefix of the input array of length $L$. And take minimum for answer over $3\leq L\leq n$. Solving for a prefixTo solve for any prefix of length $L$, we can observe that the cost of it is equal to $c_1\cdot l_1 + c_2\cdot l_2 + c_3\cdot l_3 +\cdots +c_L\cdot l_L$. Where $l_i$ is the length of the $i^{th}$ segment. And sum of $l_i$ for odd $i$ is equal to sum for even $i$, which is equal to $n$. FinallyGreedily assign the values of $l_i$ for even and odd indices independently, so that the minimum cost gets the highest length segment.
•  » » » 6 months ago, # ^ |   0 Thanks Buddy :)
•  » » 6 months ago, # ^ |   0 Think Greedily, try to minimize the length of segment choosen. You can also refer to this video:- Problem C :- Minimum Grid Path
 » 6 months ago, # |   +3 Why time limit of problem D is 2 seconds ? should have been 4 seconds since it's tagged as brute force. I changed long long to int after contest and it passed in 1996 ms . I think it will fails system test . What was intended time complexity ? submission
•  » » 6 months ago, # ^ |   0
 » 6 months ago, # |   0 Can someone explain me the meaning of the term segment used in problem C? What is a segment?
•  » » 6 months ago, # ^ |   +8 It simply means a line segment
•  » » » 6 months ago, # ^ |   0 Thanks!
•  » » 6 months ago, # ^ |   +8 line segment
•  » » » 6 months ago, # ^ |   0 Thanks
 » 6 months ago, # |   0 Sad "RE on Test 4 on problem D" noises :(
•  » » 6 months ago, # ^ | ← Rev. 2 →   +8 array size limit has to to be 2e7+1
•  » » » 6 months ago, # ^ |   0 Yeah, I figured after 4 penalties.
•  » » » » 6 months ago, # ^ |   0 I figured out at end of contest :/
 » 6 months ago, # |   +52 Time limit for D was too strict IMO :( Should have been 3000ms
•  » » 6 months ago, # ^ |   0 yes it was too strict !! can this time constraint be increased now and can the solutions be rejudged? Is it possible or happened in the past?
 » 6 months ago, # |   0 Why ternary search didn't work in Problem C?
•  » » 6 months ago, # ^ |   0 The graph can have more than 1 local minima. I was also thinking to use ternary search first, but luckily I observed it.
•  » » » 6 months ago, # ^ |   0 Can you give me one example where more than 1 local minima are present?
•  » » » » 6 months ago, # ^ |   +4 100 100 100 100 100 5 100 100 100 100 100 1 100 100something like this?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 1000 10 10 10 10 1 1000, this should be the correct testcase which you are looking for.
 » 6 months ago, # |   0 I'm so happy that I'm not gonna ask "how to solve A?" :) any way... How to solve B? :)))
•  » » 6 months ago, # ^ |   +9 look for if there is '00' after '11' if there is '11' in the string. else 'yes'
 » 6 months ago, # |   0 Can someone tell me why I am getting runtime error on my submission for problem D? I already made MAXN to 2e7 + 20
•  » » 6 months ago, # ^ |   +3
•  » » » 6 months ago, # ^ |   +1 Thanks!
 » 6 months ago, # |   0 Does anyone thought that sieve for 2e7 numbers would give TLE and haven't coded it for some time like me?
•  » » 6 months ago, # ^ |   +1 The sieve that I use runs in $O(Nlog(logN))$ which is approx $O(N)$, so I guess, it should go through.
 » 6 months ago, # |   -13 I didn't submit D for following reasons idea was trivial. Assuming that the idea will not fit in Time limit.how can 10000 * sqrt(1e7) log(1e7) = this ~ 10000*3300*20 ~ 66 * 1e7 ~ 6 1e8 operations fit in 2s. I don't know how magical there processors are.
•  » » 6 months ago, # ^ |   0 Since a decade they run on gigahertz and more.
•  » » » 6 months ago, # ^ |   0 Ya there is some hidden secret which only MikeMirzayanov can share as an IT enthusiast the way threading is done on the judge the way they are handling these many operations which may TLE on most of the other Ojs. I think that he can write some info about the tech used at backend
•  » » » » 6 months ago, # ^ | ← Rev. 6 →   0 I am fairly sure they simply count the processor ticks used while running the thread/process, or something similar.
•  » » » » » 6 months ago, # ^ |   0 Actually I worked in this field. I found many systems failing in such critical pressure. Most of the such websites now depend on Z0s API to judge a code. but it is not that fast Here the way of handling queue and maintaining the submissions and at the same time giving a performance of 1e9 operations in a span of 2 seconds. is just a great thing. Either the originial system is tricked a lot or they are having a strong processor which is capable of handling all the tasks. May be it is the second. and if it is then it is expensive and we all know that the site is non commercial. There are certain confusions in my mind I don't know if Mike can help me understand the infrastructure of codeforces judge.
•  » » 6 months ago, # ^ |   0 actually you must get ride of log(1e7) by doing a sieve beforehand
•  » » 6 months ago, # ^ |   -8 All the test cases are not that big. Only a few of them will be as big as the constraints.So, you can ignore the $T = 10^4$ part most of the time. Otherwise, the complexity is around $O(\sqrt{N}logN)$ is good enough.
•  » » » 6 months ago, # ^ |   0 The complexity would actually be better than $O(\sqrt{N}log(N))$ since the number of divisors of a number is bounded by $O(N^\frac{1}{3})$. So this part where we are computing the distinct prime divisors for each divisor of N will be bounded by $O(N^\frac{1}{3}log(N))$. Even if all test cases were huge, I don't think this will time-out.
•  » » » » 6 months ago, # ^ |   0 How is no. of divisors N bounded by N^(1/3)?, Like 24 has 8 divisors, which is much more than 24^(1/3) https://math.stackexchange.com/questions/1699330/upper-bound-on-number-of-factors#:~:text=Let%20d(n)%20denote%20the,nloglogn)).
•  » » » » » 6 months ago, # ^ |   0 When I say $f(n) = O(g(n))$, it means that $f(n) <= c * g(n)$ for some constant c and for all values of $n$ >= some constant $n_{0}$You should not consider $N^\frac{1}{3}$ as a hard bound. It just gives an idea of the relative magnitude.The number of divisors of $N$ would be of the same order as $N^\frac{1}{3}$
•  » » » » » » 6 months ago, # ^ |   0 For better understanding, if I say that $cnt(N)$ is the number of divisors of N. Then the rate at which $cnt(N)$ and $N^\frac{1}{3}$ grow are comparable
•  » » » » » » » 6 months ago, # ^ |   0 got it, but the constant (c) can be too large, i think
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 I don't think time complexity will be (T * sqrt(X) * log(X)) Instead it would be (T * sqrt(X)) + (T * no_of_divisors(X) * log(X)). for divisors of X only we will be getting log(X) factor.Also the max possible value for no_of_divisors(x) where x <= 1e7 will be atmost 500.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Fawkes don't worry your calculations are correct all those peeps got TLE in main tests in problem D.. everything is normal nothing magic too in processors! lol spookywooky
 » 6 months ago, # |   0 can some one pls tell soln for B, idk I am not getting ideas to solve B
•  » » 6 months ago, # ^ |   +3 The only "NO" case is the one where if you iterate the string from left to right u find at least two adjacent ones and later in ur iteration u find at least two adjacent zeroes.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 thanks , I thought 1100 and cupped the contest!! , btw any DP solution for this problem??
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Yeah, I solved using $dp$. The idea is to store whether string $s[1...i]$ is good, with the last element being $0$ or $1$ and the last index is removed or not.Basically $dp[i][j][k]$ -> Upto $i^{th}$ position, the last character taken is $j$ and the $k$ is $1$ or $0$ based on whether $i-1^{th}$ is taken or not.Solution
•  » » 6 months ago, # ^ |   +3 JUST check for consecutive 0's if the string already have consecutive 1 before it if this happens then print NO else YESReason : as we can't remove adjacent bits, we can't have two zero's after two one's but in vice versa we don't need to remove consecutive 1's as they will already be sorted TESTCASE : 1001110111 --> YES TESTCASE : 1100 --> NOhope you understood
•  » » » 6 months ago, # ^ |   0 thanks got it!!
 » 6 months ago, # |   0 Where is my logic failing in C ? I distributed total sum of n for among both set of numbers in c i.e c[0]+ c[2] + c[4] + .... =n ans c[1] + c[3] + c[5] = n . now to solve this I tried to assign least values to those having large weight . In other words , until I reach the least element in C I tried to assign 1 to odd and even placed number ( except if the value is minimum in it's corresponding group ( odd or even group ) ) . for the two minimum values in two group ( i.e min(c[0] , c[2] , c[4] , ....) and min(c[1] , c[3] , c[5] , ....) ) are assigned whatever sum is remained for that corresponding group ( odd group or even group ) after assigning 1 to every other in that group . Link (for better explanation ) : 110382867
 » 6 months ago, # |   0 Somehow my solution is giving Wrong answer on testcase 2. Expected value is 10, but my solution gives 9. Well, I am not sure why my code is giving less value than the optimal answer. I used the following approach of finding the minimum for odd and even indices respectively which minimizes the total answer.I cannot understand why is it failing? Please help! My submission
•  » » 6 months ago, # ^ |   0 Yeah, the same problem
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 I think the approach is wrong, because you can't just calculate min up cost and min right cost separately and add them up. For example if your min up cost only uses one segment, the min right cost cannot use more than one segment.
•  » » 6 months ago, # ^ |   +1 Think Greedily, how to choose segments to minimise the value of the expression. Link to detailed solution and explanation of Problem C
 » 6 months ago, # | ← Rev. 2 →   +19 umm..I found some guys cheating in the contest. Idk Where to report. 110342157 and 110336335 Just look at the code/logic and you will understand they are cheating or not. And not just this, Check there other submissions too, like mostly div2B and div2C are the same for many contests. shivam_aiml Even got his submissions skipped last contest but nothing else happened and they are still "pair-programming". MikeMirzayanov Pls look into this.
•  » » 6 months ago, # ^ |   +19 I agree that these two pieces of code are questionable. Strong pieces of evidence are:1) In 110342157, there is ll curr=i,next=i;;, while in 110336335 there is int prev=i,prevv=i;;. Same typos at the exact same places.2) 110342157 commented int ch-0; and int no=0;, which are the exact same codes and variable names in 110336335.3) 110342157 defines functions like gcdll, gcd, mpow, which have nothing to do with either the problem or his solution. They seem to serve the purpose of disguising.I also encourage people to look into this and express their opinions. Cheating harms the foundation of online coding competitions, and possible cases should be examined seriously.
 » 6 months ago, # | ← Rev. 4 →   +14 Problem D approach : Now, we can iterate over the factors of x' in sqrt(x) time complexity. Fixing the gcd we can easily find the lcm using the equation given. Now we know lcm and gcd, our problem is reduced to finding the pairs whose lcm is k and gcd is l (which are known). This is easy to solve and a common problem. https://www.geeksforgeeks.org/given-gcd-g-lcm-l-find-number-possible-pairs-b/ Don't use the method mentioned in the article to count the number of primes. This can be pre computed using sieve.
•  » » 6 months ago, # ^ |   +1 In second line of proof why did you divide LHS by $gcd( c , d )$ but in RHS by $gcd(a,b)$ ?
•  » » » 6 months ago, # ^ |   +1 By mistake I wrote gcd(a,b). Thanks for pointing it out!! Corrected now!
•  » » 6 months ago, # ^ |   0 How is the final condition sufficient? Is there something obvious?
•  » » 6 months ago, # ^ |   0 What topics are prerequisites for understanding this solution?
•  » » » 6 months ago, # ^ |   +1 Euclidean algorithm and general maths.
•  » » » » 6 months ago, # ^ |   0 Thanx!!
 » 6 months ago, # |   0 I saw this in someone's code. The format was like: /** * author : name * created : 2021-03-18 11:11:11 **/Can anyone tell me how to do this so that my submission time is printed automatically in my code.
•  » » 6 months ago, # ^ |   +3 if you use vscode and vscode snippets as a template, then you can add the creation date when the snippet is created (see here)
 » 6 months ago, # |   +61 Why do you think the post is almost in minuses? Is it due to the specifics of the announcement, or was there something wrong with the problems or the website during the round? I think the system worked fine.
•  » » 6 months ago, # ^ | ← Rev. 2 →   -61 Time limit in problem D . I can't imagine number of people getting fst tomorrow .tbh post deserves downvote . You just get -100 because they didn't set proper time limit .
•  » » 6 months ago, # ^ | ← Rev. 2 →   -23 Yes in problem D, time constraint was strict. Inspite of having the correct time complexity, the code needed some optimisations to reduce runtime and hence to get AC.
•  » » 6 months ago, # ^ |   +19 Males are downvoting because they are distributing unnecessary scholarships to females.
•  » » » 6 months ago, # ^ |   +10 The Misogyn army strikes back.
•  » » » 6 months ago, # ^ |   +15 I doubt that more than 5 people read the part that Harbor.Space writes in the announcement, so that can't be the reason.
•  » » 6 months ago, # ^ |   +20 I think downvotes for contest announcements should be disabled.As far as I know, downvotes are supposed to function as a filter to blogs/posts which doesn't fit in Codeforces. But official contest announcement blogs never fit in this category. No author ever intends to ruin the experience of participants (not that I know of).People usually downvotes contest announcements for the stupidest reasons, such as containing a topic he doesn't like, TLs being strict, performing bad in that contest, etc (You can actually see those guys right below your comment).So there are no benefit of having downvote option open for contest announcements that I can think of.