By awoo, history, 4 weeks ago, translation, In English

Hello Codeforces!

On Mar/18/2021 17:50 (Moscow time) Educational Codeforces Round 106 (Rated for Div. 2) will start.

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:

Codeforces and Harbour.Space

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

You can find more information about the scholarship here.

MORE INFO→

Harbour.Space

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
E KaladinStormblessed 0:17
F 718_MiL 0:10
G rainboy 1:27

UPD: Editorial is out

 
 
 
 
  • Vote: I like it
  • +132
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -107 Vote: I do not like it

Please don't make round unrated during contest time. Which is cause Big heart break (Like last div 2).

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    why so many downvotes?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for not getting unrated in this round...

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Hoping a good round

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone!

»
4 weeks ago, # |
  Vote: I like it +228 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -55 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +82 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +63 Vote: I do not like it

        well said sir you have my respect

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +45 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it -16 Vote: I do not like it

          Ok, then what about those who are not female and have lack of motivation and all.

          Why steps are not being taken for them?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +20 Vote: I do not like it

            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.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      It is worrying that your comment has a negative contribution

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it -43 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        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"?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          @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)

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it +14 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  @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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it +7 Vote: I do not like it

                  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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        nice one bro

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -15 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +137 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -53 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it -27 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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!

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it -28 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +55 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it -40 Vote: I do not like it

              You are not understanding what he is saying.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
              Rev. 2   Vote: I like it +4 Vote: I do not like it

              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

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Better words were never spoken.. Thanks you made me re-realise few things..

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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" ?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          I'm confused.I did not say that we need gender quotas because of differences between genders.my comment was against gender quotas.smh

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Spoiler
      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Please enlighten me on what fundamental difference makes it more difficult for women to have jobs in tech(as this post is concerned with).

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +22 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Attack on Feminists!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it -42 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +91 Vote: I do not like it

    IMG-20210318-174818

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    its such a good point, try this on reddit you'll rock:)

»
4 weeks ago, # |
  Vote: I like it -116 Vote: I do not like it

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!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    You can be noticeable with negative comment too! :D

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we please bring this announcement on top of today's round(708)?

»
4 weeks ago, # |
  Vote: I like it +291 Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Expecting a good round without any failure and a high rating increase to all ^_^.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

Its clashing with another big contest between India and england :P

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Aren't we gonna have a testing round after what happened yesterday?

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Codeforces should not be a place for messages like this. Can you name the month when world celebrates men?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It's in "NEVER" month

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -39 Vote: I do not like it

    You do realise your hypocritical behavior nah ?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +39 Vote: I do not like it

      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.

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

hope good performances.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Good Luck Everyone !! I wish this round to be wihtout any technical issues and have interesting problems

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

oh,there are two different contests in two next days...

I don't know which one to choose...

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

good luck everyone, I hope this round will be rated

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope this round will be rated!!

»
4 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Educational round 106 will be my 106-th rated contest

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

18k+ Registrations.... UPD: At this rate 20k+..

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

BringItOn

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

!(viva la codeforces)

»
4 weeks ago, # |
  Vote: I like it +149 Vote: I do not like it

Sorry, +15 minutes. Hope the problems will be OK. Good luck on the round!

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

15 min delay

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Extended , Hope at the time of contest everything run properly and the contest will be rated !!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Educational rounds seem to be attracting a greater number of participants than usual...

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lets hope no more delay and rated round. wish u positive delta : )

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Another 15 minutes :(

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

15 min delayed? why

»
4 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

what to do with my life for the next 15 minutes!!

»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

15mins again :(

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Delayed by 15 minutes!!

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Delay is new tradition on codeforces

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

what happened?? 15 mins late?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please... Don't discuss the delay to make the comments meaningless...

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

why most of the Educational round delay for 15 min :(

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hope Contest run properly this time

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting to get my first positive rating :)

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Does codeforces do this for 20k registrants?

»
4 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

Delay by 15 minutes.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

we hope this round to be rated though if i get -120 today lmao

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

whenever there is a delay in contest, le me: It's contribution time xD

»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

2021-03-18-2

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

HardForces part INT_MAX.

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is wrong with my approach? I print "No" only if the string contains 1100 as a substring else "YES"?

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      what about 1110100011.. u can remove mid 1 then u wl be left with..?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      try 110100, answer is no but your solution gives yes

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What about 110100? It doesn't contain 1100 and still, the answer is "NO"

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        coz it can be converted to 1100 after removing that mid 1

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      your solution will output YES for string 1101001, but answer is NO.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    exactly

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I use O(sqrt * log) and passed in 1.2s(

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also did the same thing, but after looking at your code, it seems like using vectors was the reason for TLE.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I just removed two vectors and it passed, I wonder how non-C++ solutions will pass such a tight limit :(

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          yep i had to do all kinds of optimisation in java but its all good learning experience

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              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 :)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I maybe answering above my league but maybe using sieve can help since it's time complexity is O(nlognlogn).. Link

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In my case, I used this technique. Preprocessing and then for each query, simply $$$O(sqrt(x))$$$.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    pray I guess :D

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 ?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +27 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What if some prime divisor appears multiple times in the factorization?

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
              Rev. 10   Vote: I like it 0 Vote: I do not like it

              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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Code
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Great problems.Can someone tell me hints for problem D? (Please put them in spoilers) Thanks.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it
    Spoiler
    Spoiler
    Spoiler
  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

Why very tight limit in D? :(

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the key idea to solve D ?? :(

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Hint: gcd(a,b) must me a divisor ofx;

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
»
4 weeks ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D:- Can someone please explain how we are getting 8 pairs in the 4th test case?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    You need to sieve till 2 * 1e7.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      AHHHHHHhhhhhhhhhhhhhhhhhHHHHHHhhhhh dammit that's tricky. Thanks, that fixed it... now I just have a TLE on test set 15 like everyone else :p

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Was E dp?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes I think so, didn't manage to finish the code in time though.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    Sorry...wrong problem.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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/1

    This 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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C. Should i use dynamic programming here. Anyone plz help..!! Thanks in advance.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    greedy will work. Maintain minimum for odd and even index separately.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Isn't this an edge case? 1 1 1 2

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Cheapest path here is obviously n+n for using c[0] and c[1]. Whats the edge in there?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I know but doesn't your solution do this? (1 * 3) + (1 * 3) + (1 * 1) + (2 * 1)

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think Greedily. You can also refer to this video. Problem C Minimum Grid Path

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to avoid TLE on TC 15 in question D?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I kept getting TLE on test 15 in D. What's the ideal complexity?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Alog log(A)+ t sqrt(A) where A is 10^7

    actually 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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      A is 2*10^7, using 1e7 caused me RE on test 4 XD

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        yes but in a O() you can ignore constant

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Getting runtime error on test-4 in problem D, would really appreciate if someone could help.

110384394

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain the logic behind C, can't wait till the arrival of editorial, Any help would be really appreciated !!!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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 prefix
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think Greedily, try to minimize the length of segment choosen. You can also refer to this video:- Problem C :- Minimum Grid Path

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me the meaning of the term segment used in problem C? What is a segment?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Sad "RE on Test 4 on problem D" noises :(

»
4 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

Time limit for D was too strict IMO :( Should have been 3000ms

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why ternary search didn't work in Problem C?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The graph can have more than 1 local minima. I was also thinking to use ternary search first, but luckily I observed it.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you give me one example where more than 1 local minima are present?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        100 100 100 100 100 5 100 100 100 100 100 1 100 100

        something like this?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        1000 10 10 10 10 1 1000, this should be the correct testcase which you are looking for.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm so happy that I'm not gonna ask "how to solve A?" :) any way... How to solve B? :)))

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    look for if there is '00' after '11' if there is '11' in the string. else 'yes'

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why I am getting runtime error on my submission for problem D? I already made MAXN to 2e7 + 20

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone thought that sieve for 2e7 numbers would give TLE and haven't coded it for some time like me?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The sieve that I use runs in $$$O(Nlog(logN))$$$ which is approx $$$O(N)$$$, so I guess, it should go through.

»
4 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Since a decade they run on gigahertz and more.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 6   Vote: I like it 0 Vote: I do not like it

        I am fairly sure they simply count the processor ticks used while running the thread/process, or something similar.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually you must get ride of log(1e7) by doing a sieve beforehand

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can some one pls tell soln for B, idk I am not getting ideas to solve B

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      thanks , I thought 1100 and cupped the contest!! , btw any DP solution for this problem??

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    JUST check for consecutive 0's if the string already have consecutive 1 before it

    if this happens then print NO else YES

    Reason : 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 --> NO

    hope you understood

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

»
4 weeks ago, # |
Rev. 4   Vote: I like it +14 Vote: I do not like it

Problem D approach :
1616099494874

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    In second line of proof why did you divide LHS by $$$ gcd( c , d )$$$ but in RHS by $$$ gcd(a,b)$$$ ?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      By mistake I wrote gcd(a,b). Thanks for pointing it out!! Corrected now!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is the final condition sufficient? Is there something obvious?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What topics are prerequisites for understanding this solution?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it +61 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -61 Vote: I do not like it

    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 .

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -23 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Males are downvoting because they are distributing unnecessary scholarships to females.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      The Misogyn army strikes back.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I doubt that more than 5 people read the part that Harbor.Space writes in the announcement, so that can't be the reason.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.