BlueSmoke's blog

Codeforces Round #641
By BlueSmoke, 5 years ago, In English

Hello, Codeforces!

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

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

We would like to express our sincere gratitude to:

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

UPD: Tester list updated.

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

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

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

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

UPD: Congratulations to the winners!

Div.1:

Div.2:

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

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

Comments Comments (463)
| Write comment?
»
5 years ago, # |
  Vote: I like it +344 Vote: I do not like it

Since the round is rated

Don't jinx it.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it -336 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +80 Vote: I do not like it

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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    Again seems like it was more of Mathforces competition!

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      absolutely agree

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

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

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

        Downvote if:

        1. Its irrelevant

        2. Its bullying someone

        3. If something is unrequired and just for sake of upvotes.

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

        → Reply
»
5 years ago, # |
  Vote: I like it +89 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +254 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +253 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +292 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +70 Vote: I do not like it

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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +250 Vote: I do not like it

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +39 Vote: I do not like it

      There are no ugly geometry

      Number Theory: Allow me to introduce myself ..

      Joking aside, the problems were interesting.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +59 Vote: I do not like it

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

        Number theory has neither of these problems.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +193 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +166 Vote: I do not like it

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

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    1v9tta.jpg

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Problems were very good anyways. Thanks for the contest!

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -31 Vote: I do not like it

Thanks

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
              ← Rev. 4   Vote: I like it -7 Vote: I do not like it

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

              → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -122 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -17 Vote: I do not like it

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

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it -7 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +12 Vote: I do not like it

              Not everyone is Kid my friend.

              → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +82 Vote: I do not like it

Hope no unrated again.

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow djq_cpp! /se

→ Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    But you got FST on B last round

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it -22 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +90 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

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

          → Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    This is racism based on colour. @Mike

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      You can use the term ratist.

      → Reply
»
5 years ago, # |
  Vote: I like it +284 Vote: I do not like it

![ ]()

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any special reason for this unusual time schedule ? :(

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Mike needs to .pop()the queue more frequently ...

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    You can always switch to priority queues ;)

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope no unrated again

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +313 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +55 Vote: I do not like it

    Have any contest in codeforces been delayed because of someone requesting in the comment section. If not then why are people still complaining?

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 5   Vote: I like it +111 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +19 Vote: I do not like it

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

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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Notice the unusual start time.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
»
5 years ago, # |
  Vote: I like it +120 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +163 Vote: I do not like it

    Here they are: Link.

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

    And particularly this is the Dijkstra one.

    → Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it +118 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I like the new timing tho !!

→ Reply
»
5 years ago, # |
  Vote: I like it -43 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it -88 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

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

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +30 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +119 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

And my dinner goes wooooosh

→ Reply
»
5 years ago, # |
  Vote: I like it -54 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it -58 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Div2D/Div1B is missing!

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Why is it always delayed at the last minute?

→ Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Sorry for disturbing, but 18:35 utc+7 is 1 hour earlier than the original time.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +118 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +64 Vote: I do not like it

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

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

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

→ Reply
»
5 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

      int ans=0;
for(int s1=1;s1<=60;s1++){
   for(int s3=3;s3<=60;s3++){
        if(dp[s1][s1][s3][s3])
            ans=max(ans,s1*s3);
   }
}
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thnxx

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -12 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You both are discussing about which contest ?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why there are less registrations this time

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

We got long queue again :(

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks for the starting time :).

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -63 Vote: I do not like it

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

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    No, it is not possible to extend it.

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -36 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

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

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

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

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

People showing arrogance are getting up-votes and positive contributions

People showing respect are getting down-votes and negative contributions

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it -46 Vote: I do not like it
Spoiler
→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -71 Vote: I do not like it

Please reschedule the time. At least +30 minute.

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

    It has been already asked and answered.

    → Reply
»
5 years ago, # |
  Vote: I like it +119 Vote: I do not like it

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it -31 Vote: I do not like it

1533 codeforces virgins registered for the contest.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it

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

    +1 to you, good sir.

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

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

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -31 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

MathForces returns !!!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +61 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

This is the best round I've ever tested

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +159 Vote: I do not like it

More complicated mathematics than multiplication and exponentiation: *appears*

Green coders: mAtHForCeS

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

RIP rating bois!

→ Reply
»
5 years ago, # |
  Vote: I like it +48 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +99 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

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

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

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

            → Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it was preety easy

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      how to solve it?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Aah! How easy that was! I couldn't solve during contest time.
          Now upsolved it. Couldn't solve C too. But C was an interesting problem. Just have Upsolved it now.
          Today was not my day. Problems were nice.

          → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

Reason behind half memory limit in C -
People avoid long long and read p as int and get WA.

Well played BlueSmoke

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +66 Vote: I do not like it

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

        → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +120 Vote: I do not like it

Codeforces Div.1 is not just for grandmasters.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +137 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

This round is ridiculously hard!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

      → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

→ Reply
»
5 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Errichto words guided me to solve B

→ Reply
»
5 years ago, # |
  Vote: I like it +193 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good Number Theory Round

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +112 Vote: I do not like it

Guess my opinion.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Does your code works for this test :

    4

    3 2

    2 1 3

    3 2

    3 1 2

    3 2

    3 1 3

    3 2

    2 1 2

    all the answers are "yes" except third one.

    It was some typo in the test cases.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    1

    6 3

    4 1 4 1 1 3

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    1
3 3
3 1 3

    The expected output is yes.

    → Reply
»
5 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Too much Math

→ Reply
»
5 years ago, # |
  Vote: I like it +182 Vote: I do not like it

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

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The round really needed me as a tester :(

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    6 3

    3 1 1 4 2 5

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    1
10 1
2 2 0 0 0 0 1 0 0 0

    you should convert it to

    2 2 2 2 2 2 1 0 0 0

    then it's possible to change it to 1s

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Try if this test is yes:

    1
7 5
5 1 1 1 6 6 1
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How come?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        5 1 1 1 6 6 1

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

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

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

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    try this

    n= 8 k= 3

    4 4 4 4 1 1 1 3

    answer should be yes

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How??

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +4 Vote: I do not like it

        4 4 4 4 1 1 1 3

        4 4 4 4 4 1 1 3

        4 4 4 4 4 4 4 3

        4 4 4 4 4 4 3 3

        and so on

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Eratostene's sieve for the win!

→ Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Maybe you miss some details.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -41 Vote: I do not like it

you should create problems on mathforces, not codeforces.

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I cant's support you more!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

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

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

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

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did you solve div2 C ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how did you solve div2 b?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve Div 2C?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    1 Prime factorize all given numbers with their prime powers!

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

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

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

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

    have power $$$j$$$ in above algo then multiply (ans with $$$i$$$^($$$j$$$))

    finally print the answer

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 12   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 5   Vote: I like it +2 Vote: I do not like it

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

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

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

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

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

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

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

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

    Here's my code

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Code
→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Its really nice to see it organised at that precision.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

    → Reply
»
5 years ago, # |
  Vote: I like it +109 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    same :(

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Good that you were good enough to solve everything.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

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

              → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -30 Vote: I do not like it

      Unrated?

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Same here :(

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Isn't it just (almost)850F - Rainbow Balls?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 4   Vote: I like it +55 Vote: I do not like it

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

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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div1.B/div2.D?

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Is it true that in E $$$i$$$-th ($$$0$$$-indexed) player with a black hat just adds $$$n - i$$$ to all values and decreases $$$i$$$-th value by $$$1$$$?

→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Hello guys we are excited to invite you to HandForces Round #228!!!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    (imho tasks are pretty good but there is a huge complexity gap between ABC and DEF)

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2D/div1B?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it -7 Vote: I do not like it

    comment was accidentally posted

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    if there's no element valued k in the array the answer is obviously "no", so we assume there is such element, and it's index is i. if n==1, all elements are already equal to k, so the answer is "yes".

    case 1: let's notice that if one of adjacent to i elements is not less than k, we can apply our operation to these two elements and they both will equal to k; after that, we can "expand" this segment so it will cover all the array.

    case 2: if adjacent to i elements' values are less than k, we can take such j < n that a[j]>=k and a[j]>=k, similarly to case 1 expand this segment so one of it's element would be adjacent to i. then we have case 1.

    case 3: if cases 1 and 2 are not performed, we can find such 1 < j < n that a[j-1], a[j+1] >= k, then apply operation to [j-1; j+1] (if j+1 or j-1 == j, the median will also be a[j]); then we have case 2.

    let's notice that if no one of these cases is performed, answer is "no" (because any operation will set some value that is less than 1).

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone 4th?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +596 Vote: I do not like it

Why not?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Maybe there will be more questions than Div2.B if we did so.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +205 Vote: I do not like it

      What about putting the statement first, then explaining definitions for those who don't know them?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        That's what I love about atCoder, clear and concise statements.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +48 Vote: I do not like it

        Good idea. I'm aplologizing for that.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think they must make/update a list of standard Good Practices for problem setters and testers.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    It's not necesaary that everyone is familiar with the terms GCD, LCM. Some people might have started participating recently. You should appreciate the effort of the authors that they have clearly explained every single term.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      people who don't know about lcm and gcd shouldn't be participating on codeforces but learn some basic math

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        You could have simply replied with your real id.

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      It is a very common practice that definition of LCM,GCD, bitwise OR/AND/XOR are not provided in problem statements. Instead of providing definition, those word are used as hyperlink and a link is provided where those terms are explained. When some explanation are necessary for a very small no people then it is good idea to keep problem statements short and easy.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Entire question in 'Output' section

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

At div2-C / div1-A I thought that a prime is a part of the gcd, if all or all but one number can be divided by it. Say 2 2 1 and 2 2 2 words, if it was 4 4 1 or 4 4 4 i would divide by two and start again (2 2 1 or 2 2 2). However my program failed pretest 9 for some reason. Was I wrong in my reasoning?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    same reasoning applied by me. failed at pretest 9 same as you

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's probably overflow for you too... Try using 64 bit num for gcd instead of int.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes bro. i changed my default file 2 days back for some other ques. changed vi vector to vi vector in the macros section. let this be a lesson

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First I also got W.A. in Pretest 9, But I think you were using the last number for this calculation:

    Resubmit it by avoiding the last number as (i<j), so don't do any operation for i=n.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why? I'm not sure I understand you, the answer for 2 2 1 is 2 and for 2 1 1 is 1. Clearly all positions are equivalent?

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got wrong on pretest 9 due to overflow should have used long long to store answer.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, mine too... For some reason I was sure it can't go over 200000 lmao.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your approach is right, maybe you made some implementation error?

    Here's my code

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It was overflow for result... Didn't think it can get that large.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I feel you lol, this is why i completely abandoned int and am using long long everywhere

        → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

In Div2 problem D or Div1 problem B, I checked for

$$$k 0 k$$$

$$$k 0 1$$$

$$$1 0 k$$$

$$$1 0 1$$$

$$$k k$$$

$$$1 k$$$

$$$1 1$$$

structure in the array, where elements less than k have been replaced by 0 and greater than k replaced by 1.

The proof is by construction. What's wrong with my solution (WA IN PRETEST 2)??

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Does your code work correctly when $$$n = 1$$$?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      I handled that test-case separately. Also, I updated my original comment: please help.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +13 Vote: I do not like it

        Try the input

        1
1 1
2

        Your latest submission outputs "YES" to this

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          OMG OMG OMG OMG THE ERROR I PUT THE IF(N==1) CASE BEFORE THAT CHECKING IF THERE EXISTS ATLEAST 1 ELEMENT EQUAL TO K I AM DEAD

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try the following test case :

    1
7 3
5 4 1 1 1 1 3

    The answer is yes

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You had to check all subarrays and check if there exists a subarray with 2 or more elements >=k.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What does it help? I mean if we got 5 1 1 5 as input, we cannot make all 5. Please explain, I do not get it.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Let me elaborate
        1. check for n<3 cases
        2. for n>=3 check if k exists in the array.
        3. If k exists in array then check if there is any subarray of length 3 which has atleast 2 elements greater than equal to k.
        4. If such subarray exists then answer is yes else no

        This works because after checking for the existence of k we have to check if there is a subarray for which median is >= k. To do this every subarray that will satisfy this would have a subarray of length 3 satisfying the constraint. So simply check for all subarrays of length 3.

        If the found subarray has a median > k and k exists in array we can always convert all elements to k.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah... got it, thanks. I was under the impression I would have to find biggest median of all subarrays. But turns out biggest of all is the same as biggest of all of size 3.

          → Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Actually Div1 F1 is much solvable than Div1D, you can try that now. We as testers first solve F1 and than D. But the coordinator said F1 and F2 should be placed together. Previously we decide to put F1 before D.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I think that's reason to set Div1.F1 as Div2.F. But we can't ask a person to see div2 while competing :(

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, it seems more solvable. It's fine to put the Fs together, but D and E should've had more points regardless and perhaps E and F should've been swapped to hint at the difficulties.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Good idea. We should have increase the score of DE. F2 is really hard. What we expected was that F2 is the final match between top contestants.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +56 Vote: I do not like it

        what

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +72 Vote: I do not like it

        I mean...

        I think that it is our (as participants) fault that nobody has managed to solve 5. Some people were close.

        I can see that you could underestimate the difficulty and think that someone with enough luck could solve ABCDEF1.

        But thinking that several people will be able to solve ABCDEF1 and have enough time to approach F2 (and maybe even succeed) is outright crazy.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          The fact is, during testing phase we have several testers solved both D and F1 in virtual participation. And yeah, E is quite implementation-heavy and F2 is something crazy and almost totally unsolvable during contest.

          What we expected is most GMs can get either D or F1, top contestants get both of them and maybe someone will make an final-hit by E or (maybe, with little probability)F2. However it's a pity that things become tough and even no one can solve both D and F1.

          → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

what is pretest 10 in div.2d/div1.b?

→ Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Weak pretests on B... Why not put all $$$3^n$$$ possible tests for $$$n \leq 8$$$ in pretests?

→ Reply
»
5 years ago, # |
  Vote: I like it +454 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

From now on, if anyone asks me why I bothered to get a mathematics degree, I'll point them to this contest xD

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was Div2 B's pretest 2. My approach was to make a tree out of all the models and do a dfs to find max possible height. Can't find an edge case :(

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Isn't it a DAG, not a tree? For example, the construction for $$$n = 4$$$ (assuming the sequence is strictly increasing, something like $$$1, 2, 3, 4$$$):

    Image

    (Maybe reverse the edges, I haven't really looked too much at your code)

    Your solution is close though. The fix for it would be, instead of stopping when you hit an already-visited node, you'd want to return the deepest "child" node you can reach from that node. This is easy — you already compute that in the dfs, so you can just store it and return the stored value if you've already visited a node.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2D? How to handle cases like:

6 3

3 1 1 4 2 5

where the segment considered for the operation is not a subarray?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 5   Vote: I like it +43 Vote: I do not like it

    My approach :

    For $$$n = 1$$$, check if the only element is $$$k$$$ or not.

    For bigger $$$n$$$ :

    First check if we have at least one $$$i$$$ such that $$$a_i = k$$$(if no such $$$i$$$ exist then the answer is no), then if we had such $$$i$$$ that $$$a_i >= k\;and\;a_{i+1} >= k$$$ then the answer is yes(proof it yourself), otherwise if we had such $$$i$$$ that $$$a_i >= k\;and\;a_{i+1} < k\;and\;a_{i+2} >= k$$$ then the answer is yes, otherwise its no :)

    → Reply
»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Probably the easiest way to solve 2C 79828664

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please explain the solution a little ?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Since $$$\gcd(\gcd(set_1),\gcd(set_2))=\gcd(set_1\cup set_2)$$$, we can calculate the answer separately and then combine them. My way is to fix $$$j$$$ each time and the answer turns out to be $$$lcm(\gcd(\lbrace a_i|i<j\rbrace) ,a_j)$$$, but I can't prove it mathematically.

      Forgive my bad English.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    but there are no inbuilt gcd and lcm function how did that work

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      c++17 has built-in gcd and lcm. check this out

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        i use VScode can you plz tell me how can i get c++17 ಥ_ಥ (PLJ)

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Are you using code-runner plugin?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yes I use code runner. How to use c++17 in vscode?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              you should modify the "executor map" in settings and add "-std=c++1z" to cpp's compile command. This can be a bit complicated if you have no experience of modifying the settings.json file

              → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    see this also.79898013

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    how did the function gcd,lcm work?? UPDT : got it

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why this solution is not giving TLE?? https://mirror.codeforces.com/contest/1350/submission/79823696

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because, n is at most one million, and the solution runs on linear time.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    On the first iteration of k n is even, it goes to "else" and once find the smallest divider. On the other iterations it goes to n%2

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the C div2 task. It was very exciting to solve it

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody help me on why my solution for div2-B fails https://mirror.codeforces.com/contest/1350/submission/79878448

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +19 Vote: I do not like it

Div1 be like

→ Reply
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

System testing was lightening fast today

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

pretests of C were weak caused me +50 ༼ ºل͟º ༼ ºل͟º ༼ ºل͟º ༽ ºل͟º ༽ ºل͟º ༽

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

At first,the contest is very great,but I think I have a long way to go.Come on!

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I think C Div1 is the most beautiful grid problem i have ever solved

→ Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Chinese people again proved that they are the math gods for the $$$69th$$$ time.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[answered elsewhere]

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Nice questions Div1-ABC. For the first time today I was able to solve Div1C/Div2E. Thanks for a Div1C with same difficulty as Div1B.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

WA on test 19 can somebody please help? https://mirror.codeforces.com/contest/1350/submission/79890541

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    In cases like:

    6 5
5 2 1 2 8 9

    You can use the [8, 9] and go fill 8 left, and then use [5, 8] to fill up the rest.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought people be joking about mathforces, looked at DIV2 ABC problem tags and its all math lmao wtf, still liked the problems tho, even if couldnt solve them

→ Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

i want to know the solution of div2E which got memory limit exceed as mine is just simple bfs

→ Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

why there is no hacking round ? I got some tetcases of Div 2 problem C where my friend answer is wrong but he got AC.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah... I also think hacking round is must

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It depends on the format of the round. In rounds like the educational ones, there is a separate hacking phase after the coding phase. But in the regular Div2/Div1 rounds participants can lock their accepted solution for a problem and hack solutions of other participants in the same room for the same problem during the competition.

    → Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Let's be honest, although most of the problems were $$$mathematical$$$, those problems are really interesting.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Literally wasted all of my time on div2/prob b,still cant find any bug,can anybody tell me what is wrong,it dont pass pretest 2 ,i used dp approch code -> https://mirror.codeforces.com/contest/1350/submission/79864654

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    In some cases your dp[index] will remain zero, if this if (index*count<(len)&&arr[index * count] > arr[index]) statement is never true in the while loop. So you should set your dp[index] to 1 in your else before entering the while loop. Because you can always at least take the value itself.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Great contest! People might say that it was math heavy, but keep going cuz the haters will hate and each author should have their own distinct style! Definitely tuning in again if you guys offer a new contest in the future! Also shout out to Mike, because the queue time was virtually non existent!

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why is a lot of time taken after system testing to display the rating changes?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    First people have to calm down, else they will complain about the results.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I thought it was a very computationally expensive task. So it takes a lot of time to calculate.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WA on pretest 2 div2/prob B. whats the problem https://mirror.codeforces.com/contest/1350/submission/79864654

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing contest It was comparatively tough!!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

An awesome round after a very long break. I personally enjoyed all the four problems I solved (D2 ABCD), I have a passion for maths and D2 C was a beautiful number theory problem. Thanks to the contest designers. Also it was great to feel that adrenal rush after such a long time. Great to see CodeForces back again. Cheers!!

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

CouNting Round, CountForces

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sounds really, really silly, I know, but I was unable to solve div 2A and I can't figure it out. Can someone point me in the right direction here? 79892383

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Take a look at values of f(any odd number) and f(any even number).

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Ah, I see. From what I can understand, if the input is even, then it's just adding 2 each time. If it's odd, then the smallest divisor is odd for the first iteration and then even (2) for the rest of the iteration.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only one who has a glitch in the rating changes of div.2? The ranking(eg. specialist and expert) is not changing.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Um_nik and tourist got swapped now!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got TLE in Div2C (with pypy). My approach was to: 1) To find prime factors of all elements in the array. 2) Find last second minimum exponent for each prime factor in all array numbers, as taking LCM is like taking maximum for each pair of exponent. Multiplying all prime^(last second minimum) will give the answer.

Solution link: 79870496. Any better approach or any comment on TLE will be great.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Your approach is fine I did same and got AC, but your implementation has a time complexity of O(n*sqrt(2*n)*log(2*n)) which gives TLE. Instead, calculate the prime factorization till 2*10^5 beforehand using a sieve in n*log(n).

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Are u kidding me! The ratings updated, Wow!

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think i will make better performance if i stop checking div 1 standings during the contest i always solve a and b in div2 and then i go to see what is tourist doing

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is just a waste of time and focus. Good idea not to do it :)

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OMG. Even I does the same.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Super clear (short )statement and good pretest. Thank you !

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Can someone explain or point me to the direction where this is proven as I am having trouble understanding Div2C:

gcd(lcm(a,b), lcm(a,c), lcm(a,d)) = a*gcd(b,c,d)/gcd(a,b,c,d) = lcm(a, gcd(b,c,d))

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +25 Vote: I do not like it

    While thinking of gcd and lcm, think about the powers of prime factors, as each prime factor contributes to the result independently of the others.

    In that sense, we can consider the numbers to be powers of the same prime factor, and all that matters is that power, so we replace the number by its log.

    So, the operation $$$gcd(a,b)$$$ becomes $$$min(a, b)$$$, and $$$lcm(a, b)$$$ becomes $$$max(a, b)$$$, and $$$*$$$ becomes $$$+$$$, and so.

    If you reformulate things like this, it can be generally helpful while working with gcd and/or lcm. However, it may be overkill sometimes.

    It's not hard to use that way to prove your statement.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With your reformulation, I understand how the statement above is equivalent. This might be a typo but what do you mean by "so we replace the number by its log."

      Also, do you have any suggestions on how one would come up with this during the contest (not knowing the lemma beforehand)? Or some resource/book where I can learn more about number theory as I would consider math one of my weaknesses.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I meant that if $$$n == x^k$$$, replace $$$n$$$ by $$$k$$$, which is its log to the base $$$x$$$.

        There are multiple ways to approach the problem. As I said, you can think about what happens for each prime factor through these operations. This is a straightforward approach to reach the fact that the power of the prime factor in the final answer is the second minimum of its powers in the given array.

        Generally, getting exposed to more ideas helps you sharpen your skills to approach problems and you get used to some thinking patterns. You should also not only know the solution of some problem you couldn't solve, but also think about how possibly you could have reached it.

        I don't have in mind a specific resource, but you can search for some stuff and will find many nice things. I also think to improve in a certain topic you can simply solve problems on it with incremental difficulties and try to understand the solution and how to reach it as much as you can. Also it's most probably helpful to have someone to discuss with, even if he's not significantly better than you.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    https://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml i found this... may be helpful ʕ•ᴥ•ʔ

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the pretest is too weak since I FST on two problems. :(

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I also fst on C,but I don't think pretest should be strong enough.Fst makes the contest more exciting.If pretests are as strong as system tests,what do we need them for?

    → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    well I think this is the biggest Uno reverse card in my entire life.

    (I'm sorry guys I need to change this comment, I posted the old comment when the main comment was -6)

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

noice <3

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any other Blake's 7 fans here? I liked the name of the character in Div2 A to E. https://blakes7.fandom.com/wiki/Orac

→ Reply
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I wanted to point out that this was legendary bad round for Poland. Our TOP7 (at the time, cause I am no longer there xD) competed in it, consisting of me, mnbvmar Radewoosh Errichto Marcin_smu Anadi and tribute_to_Ukraine_2022 and we lost respectively 163, 59, 115, 71, 103, 100 and 86 rating points. That totals to 697 which is almost 100 per person xD. Moreover last two rated rounds were my two the worst contests in last 5 years (at least I can counter that with 6th place in an unrated round between them and that I did pretty good in last OpenCup).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A : https://www.geeksforgeeks.org/find-the-gcd-of-lcm-of-all-unique-pairs-in-an-array/?ref=rp

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    IDK what point you were trying to make, but...
    → Reply