Alexdat2000's blog

By Alexdat2000, 2 years ago, translation, In English

Сoronavirus work, coronavirus school, coronavirus rest, coronavirus time spending, coronavirus contest.

Hello, Codeforces!

Codeforces Round #645 (Div. 2) will start at May/26/2020 17:35 (Moscow time). This round will be rated for the participants with rating lower than 2100. You will have 2 hours to solve 6 problems.

Problems of this round were prepared by Alexey Alexdat2000 Datskovskiy, Ilian crazyilian Andrianov, Vsevolod sevlll777 Lepeshov. We have made an effort to create interesting problems, beautiful statements and strong tests. We wish you like problems and your rating increase.

We would like to express our gratitude to:

UPD 1: Scoring distribution: 500 — 750 — 1500 — 1500 — 2000 — 2500

UPD 2: editorial

UPD 3: Congratulations to winners!

Top 5 official participants:

Place Participant Problem solved =
1 Ariadne.w. 6 6910
2 HackerMonk 6 6752
3 Potassium 5 5543
4 qwertz73355a 5 5478
5 SorahISA 5 5446

Top 5 all participants:

Place Participant Problem solved =
1 Egor 6 7821
2 kort0n 6 7495
3 Golovanov399 6 7365
4 nuip 6 7346
5 Geothermal 6 7332

Participants who sent the first correct solution to the problems:

Problem Participant Penalty
A Geothermal 0:00
B IgorI 0:02
C KostasKostil 0:04
D neal 0:11
E Geothermal 0:27
F chemthan 0:40

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

»
2 years ago, # |
  Vote: I like it +252 Vote: I do not like it

"coronavirus contest"
I won't risk taking part in it.

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

    Everything is thoroughly sanitized!

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

    Just sanitize your hand after attempting each task.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -294 Vote: I do not like it

    I was trying to create a funny comment on your message. But I couldn't think of one. Can you like my comment it for trying?

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

    use mask ….

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

    Don't worry! CF will maintain long distant Queues.

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

    Actually it is a special kind of coronavirus vaccine. The higher score you achieve — the stronger immunity you get.

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

    Don't worry — your rating makes you immune to rating change as well as coronavirus.

»
2 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I hope this would be a very good contest for everyone.

enjoy coders...

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

This is what we all love to have — "beautiful statements and strong tests".

»
2 years ago, # |
  Vote: I like it +207 Vote: I do not like it

I'll keep social distance between me and good results.

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

    You don't need to bother — good results will be keeping social distance from you.

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

It's a Сoronavirus contest! Amazing! hope problem-set will be related to it!

»
2 years ago, # |
  Vote: I like it -41 Vote: I do not like it

Sadly this comes from Russia, not China. (If you know what I mean)

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +293 Vote: I do not like it

As a tester, I can confirm that this contest requires programming and/or problem-solving skills. The problem statements may or may not be short, just as the pretests are possibly strong.

»
2 years ago, # |
Rev. 2   Vote: I like it +71 Vote: I do not like it

P R O B L E M — — — S T A T E M E N T S — — — W I L L — — — F O L L O W — — — S O C I A L — D I S T A N C I N G — — — N O R M S.

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

    Lmao expecting a problem which asks to find the longest distance between two nodes in a graph.

»
2 years ago, # |
  Vote: I like it +59 Vote: I do not like it

The time shown in calendar differs.

»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

The funny thing is that when you go to Codeforces, whose logo says Make Codeforces, not Coronaforces, the first thing you see is that announcement

I hope that there will not be any new disputes on this topic

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Сoronavirus work, coronavirus school, coronavirus rest, coronavirus time spending, coronavirus contest.

LOVE THOSE LINES

»
2 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Сoronavirus work, coronavirus school, coronavirus rest, coronavirus time spending, coronavirus contest.

I really hope this does not mean the problems will be themed on the coronavirus.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Ah. What an absolute shame. I really thought Codeforces would have the decency to not use a virus responsible for killing hundreds of thousands of people to simply make the statements more amusing. Also, some people retreat to websites like CF to not think about the ongoing situation and reduce anxiety; sadly, this act completely defeats that purpose.

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

        Yeah, they should maintain absolute distance from it. But who knows may be the problem statements will be anti-corona.

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

          The statements might be related to people wearing masks and maintain social distancing, but it might be about the coronavirus spreading as well... Who knows. Let's just wait for the contest to come! :D

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

        I hope problems will be related to fighting coronavirus.

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

          Given a map of Italy. Surprisingly, Italy can be represented as a tree! If at the moment, there's an outbreak in city i, the next moment, there will be outbreaks in all cities adjacent to i. Dr. Evil created the virus and wanted you to help find the city to plant the virus in, so that it will take over Italy the quickest.

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

        Your concern for the fresh wounds of the world is commendable, but all the same, different people having different coping methods. For some, breaking the taboo by incorporating it in humor and mundane activities in daily life is a way of normalizing the scope of the tragedy! Given the huge volume of jokes and memes spreading on corona, I think not that the humanity's response has been to shy away from involving corona in different aspects of life. For those who, rightfully, are sensitive to the topic, they have been notified and can skip the contest or solve some virtual in the meantime. As for fighting corona, if we take it seriously in our real life measures, I don't see the harm in using it as a theme in the virtual world. All my respect to those who have lost loved ones.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -24 Vote: I do not like it

          good words

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -47 Vote: I do not like it

          While your argument isn't completely untrue, I highly suspect that this is a result of the lack of creativity of the authors rather than a motive of "breaking the taboo". To compare this with memes about the subject is borderline absurd. My argument is why must problems be themed on issues which have the potential to hurt the sentiments of a significant amount of people? Why must they skip taking this contest due to the lack of originality and thoughtfulness of the authors? While we are at it, why don't we "normalize" other tragedies such as the forest fire in Australia or even the 9/11? What's stopping us from creating problems about terminal illnesses such as cancer? In the end, problem statements are supposed to enhance the contest through light humor not become a reason for people to decide not to participate in a round beforehand.

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

            Which tragedies are normalized and which ones aren't is a complex question beyond the reach of this discussion. I've heard though plenty of jokes about terror groups, and lots of WW2 games glorifying the traumatic event are frequently released.

            That being said, society will often make a clear distinction between acceptable and unacceptable. If (I doubt) there is an uproar over the covid problems (we still don't know what they will be like) we will inevitably see it in due time..

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

              But the stories were really sh**ty.

»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

I'll wear my mask during the round. Gotta play it safe

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

    mhm good job. Also remember to wash your hands and sanitize the environment lol

»
2 years ago, # |
Rev. 4   Vote: I like it -274 Vote: I do not like it
Disclaimer: Contains Offensive Content

I request you guys to take it as JOKE

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    we aren't

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

    Who cares if a joke is offensive. What cannot be forgiven is a joke not being funny.

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

    Look, this is really insulting. Imagine yourself being one of the Chinese people, would you consider this as a "funny" joke anymore?

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

      Foremost rule of a joke is that its never meant for insulting somewhat like a healthy roast.

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

        Whatever. But I don't quite like that though. Sorry.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 2   Vote: I like it -9 Vote: I do not like it

          Has someone asked that you like this or no? Who cares?

          UPD: This was made for people like you only. So Mission Successful!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please clarify the exact timing ? It differs from that of the announcement and the contest page !!! @Alexdat2000

»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

300iq always makes so interesting contests :D

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't want beautiful statements, I want short statements.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

your your rating increase in English version, Alexdat2000

»
2 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

I'm tester of this round. I like problems very much and i strongly recommend everybody to take part in this contest

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

    Lol..Every tester copy pastes the same line.

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

    pls check for problem B I have checked my code's sample output on 3 different compilers but when I submit it is giving wrong on pretest 1 itself. If anybody can tell why this is happening I will be very grateful. Pls check what is wrong

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I can get a big positive $$$\Delta$$$, good luck to everyone!

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Alternatives to names Alexdat2000

Coronavirus and Programming, Coronavirus and Sanitization , Coronavirus and Social Distancing , Coronavirus and Quarantine , Coronavirus and Prediction, Coronavirus and Symptoms.

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

After the contest everyone should be quarantined for 14 days. :p

»
2 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Deleted

»
2 years ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

First I thought it will kill my rating, but now I decided to take part in the contest.

Happy Coding.
»
2 years ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

i don't want to end up in lockdown

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

Stay home and Code because Codeforces will never let you go away from coding. These days are really helpful for many developers like me who now has interest in coding. Thank you MikeMirzayanov.

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

Deleted

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

i hope to find nice problems and nice ideas

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That illustration looks like it's from a Rick & Morty episode. "Covid Riiiick!"

»
2 years ago, # |
  Vote: I like it +164 Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Y'all got any more of that bat juice? Cause I'm running short of supply.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice score distribution:)

»
2 years ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

»
2 years ago, # |
  Vote: I like it -61 Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +110 Vote: I do not like it

»
2 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Got to learn a lot !

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about social distancing???

»
2 years ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Corona Virus Contest! Expecting Bats in problem statements!!

»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Hope "Accepted" wouldn't make social-distancing from "Pretests Passed" :)

»
2 years ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

Deleted

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Would be wearing a mask inside my home for the first time, thanks to Codeforces :)

»
2 years ago, # |
  Vote: I like it +68 Vote: I do not like it

I bet there gonna be a bit masking problem!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Implementing Bit masking is a kind of tough job. ₍ఠ ͜ఠ₎

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

    Sorry was thinking the problems are about saving ourselves and social distancing not a romantic story with Coronavirus-chan!

»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

The problem setters of this round are hosting their first round on Codeforces.Best of luck to them!

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

Deleted

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I'm in!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

By the way Image of corona Virus in post can be like original corona virus with pricking peaks and magenta colour. for real feel.

»
2 years ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

Nice flop. I pretty much knew the meme was gonna flop but still went with it.

»
2 years ago, # |
  Vote: I like it +66 Vote: I do not like it

Is it r̶a̶t̶e̶d̶ sanitized?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Сoronavirus work!!coronavirus school!! coronavirus rest!! coronavirus time spending!! coronavirus contest.!!

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Make sure everyone sanitize their code before compiling.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Prevent corona-unrate virus through queue-distancing.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Scoring of C and D are same. Let's See #ofsubmission(c)?#ofsubmission(D) (? = </>).

»
2 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Coronavirus contest should include bit-mask problems

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

bulmanupje? kut!!

»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

As you got used to it, upsolving is on us 5 mins after the round ends:

https://youtu.be/KfiUrDLad4Q

On Algopedia. Bring your masks!

»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Previously I need water,pen and pencil. For this contest I need extra 2 things: Mask, Hand sanitizer.

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

Nice

»
2 years ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

It is strictly recommended to hate 300iq

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

    Yeah, he removed a lot of good stuff. For example, small memes under each problem :(

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

      As tester I can say that this memes were typical shitty Facebook boomer jokes for me. They were completely unrelated to statements.

      So removing it from statements was necessary.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm hoping vaccine for corona virus is found by scientists in problem statements

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

is the new rating system starting from this contest?

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I like it

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

How do you prepare yourself 30 minutes before the contest?

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Expecting a question to maximize social distance between all people on a grid.

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Nice problems, thanks for your effort, but in my opinion the gap between problems were just too much(they were growing harder so fast), you could have added two problems to make it a nice div1 contest.(i know its not as easy as it seems to be)

»
2 years ago, # |
  Vote: I like it +51 Vote: I do not like it

I came here after solving D (in between contest).

The problems are nice, the statements are ugly.

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

    How would you modify the statements to make then nicer?

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

      Mainly D, I don't like such themes

      (and then maybe you can win the heart of Coronavirus-chan).

      Also coronavirus-chan???

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

      I'll still thank you guys for the contest because the problems in themselves were very nice.

»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

C and D do not deserve same points. Change my mind :|

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

    Strongly agree

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    We are really sorry for this, all our testers who solved C also solved D :(

    Hope, you enjoyed problemset anyway

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

    Agreed. The coordinators asked us to change D from 1750 to 1500.

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

1st half hour solved A,B and rest of time just thinking about solution C and D.but fail to find any way to reduce time complexity.This called life of pupil :( sad life :(

»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

C was certainly not worth 1500.

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

    You mean its worth more or less? lol

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -38 Vote: I do not like it

      Less xD, if you get the pattern, it is just 2 lines of code per test case, else you'll just be scratching your head for the rest of the contest.

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

        Yeah, I was scratching all right. Now tell me the pattern already

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -13 Vote: I do not like it

          1+(x2-x1)*(y2-y1)

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

            WTF

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

            Can you please explain, how you arrived at the formula? I'll be much obliged sire, Thank you!

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

            can you tell why and what exactly was the question asking us to calculate?

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

            i tried with (x2-x1)+(y2-y1) in the last minute without any logic though..my unfortunate..

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

        I haven't found the pattern, so I coded brutforce and facepalmed a lot after it

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

        it is short in code but idea is not really easy

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

          True AF :3

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -25 Vote: I do not like it

          Write a generator and observe, is it that hard?

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

            not hard, but not too easy for div2C

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

            I don't think one can say "hard" or "easy". It is hitting the right spot, or knowing the pattern beforehand. The idea is not hard, but you need to guess there might be a pattern, come up with bruteforce to check, and finally write (w-1)(h-1)+1 XD

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

            Are you familiar with the concept of proof?

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

    It really took me almost an hour to realise that you can solve C with only 1 formula :))

»
2 years ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

Looks like more of a Maths Contest than a Coding Contest, special credits to "C".

»
2 years ago, # |
Rev. 6   Vote: I like it -20 Vote: I do not like it

pls check for problem B I have checked my code's sample output on 3 different compilers but when I submit it is giving wrong on pretest 1. If anybody can tell why this is happening I will be very grateful.

void solve()
{
    ll n;   cin>>n;
    ll a[n];    loop(i,0,n)     cin>>a[i];
    set<ll> S;
    unordered_map<ll,ll> M;
    loop(i,0,n)
    {
        S.insert(a[i]);
        M[a[i]]++;
    }
    ll cnt=0,cur,nany=0;
    for(ll x : S)
    {
        nany+=M[x];
        if(cur+M[x]>=x)
        {
            cnt+=nany;
            nany=0;
        }
        cur+=M[x];
    }
    cout<<cnt+1<<nl;
}

int main() {
	fast_io;
	
	test{
	    solve();
	}
	return 0;
}

THANK YOU

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

    U did n't send ur code, how can anyone check it?

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Nice problemset. Thanks!

»
2 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

1358B - Марья Ивановна нарушает самоизоляцию Now I see what the point of grannies near to my house is

»
2 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Loves the problemsets, but apparently statements are too long. Would have been nice if statements were a bit shorter

»
2 years ago, # |
Rev. 2   Vote: I like it +118 Vote: I do not like it

Me after solving C

Me after solving C

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

    What's the pattern?
    Edit: I'mma cry myself to sleep.

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

      $$$(x2-x1)(y2-y1)+1$$$

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

      (x2-x1) * (y2 — y1) + 1

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

        Can you please explain how you got there ?? though I observed a zig-zag matrix of different sizes same sum

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

          Maximum possible sum — minimum possible sum + 1. I shifted to origin and calculated both sums using double AP. Minimum was when you go RRRRDDDD and maximum was when you go DDDDDRRRR.

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

            AdsT I got the same observation. But couldn't make it to formula.How did you get it?Would you please elaborate?

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

              There is a better solution available now, in editorial. I feel stupid now for solving so much maths. But anyway if you wanna look into the formula here you go https://www.quora.com/How-do-I-find-the-sum-of-a-sequence-whose-common-difference-is-in-a-p

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

                I too did the same thing but without shifting the points and hence got the wrong answer, can you kindly explain your logic of how you shifted the points.

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

                  I assumed my starting point was 1, 1. So I calculated the ending point as r = x2-x1+1 and c = y2-y1+1. Now I need the sum from 1 to cth term (for RRRRR). Then sum of r terms starting from previous term (for DDDD).

                  Similarily doing the same for DDDDRRR, now notice this time starting term of difference AP was 2. Don't forget to subtract the corner term which could be counted twice.

                  You can look at this solution of mine https://codeforces.com/contest/1358/submission/81527124 It has my logic, although it failed test case 5 because of long long oferflow while calculating the sums. It gives correct output for all the values less than 1e8. So I had to do the calculation on paper and arrived at r*c+1.

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

    Imagine you have some path and you changed a "corner" from (x,y) to (x-1, y+1), path value changes by 1.

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

    Well we have the upper and lower bound. Just take the diff

»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Humorous and awful......

»
2 years ago, # |
  Vote: I like it -50 Vote: I do not like it

Problem D was failing in Pretest 12. could you tell me why. here is my code

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;

public class TheBestVacation { public static int getMaxSum(int arr[], int x) { int s = 0; int maxSum = 0; for (int i = 0; i < x; i++) { s += arr[i]; } maxSum = Math.max(s, maxSum); for (int i = x; i < arr.length + x; i++) { s += arr[i % arr.length] — arr[(i — x) % arr.length]; maxSum = Math.max(s, maxSum); } return maxSum; }

public static void main(String[] args) throws IOException {
    BufferedReader sc =
            new BufferedReader(new InputStreamReader(System.in));
    String[] s = sc.readLine().split(" ");
    int m = Integer.parseInt(s[0]);
    int x = Integer.parseInt(s[1]);
    String[] days = sc.readLine().split(" ");

    int totaldays = 0;
    int arr[] = new int[m];
    int i = 0;
    for (String _s : days) {
        arr[i] = Integer.parseInt(_s);
        totaldays += Integer.parseInt(_s);
        i++;

    }

    int input[] = new int[totaldays];
    int idx = 0;
    for (int j : arr) {
        int k = 1;
        int a = 0;

        while (j > a) {
            input[idx] = k;
            k++;
            a++;
            idx++;
        }
    }

    int sum1 = getMaxSum(input, x);


    System.out.println(sum1);


}

}

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

    x should be a long

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

      Lol, I spend 1 hour and can't find this problem in my solution. Now I send same code (except reading x) and get AC.

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

    maybe you forgot to double the size of the size of array. I too was getting Runtime Error because of this.

»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Hello Specialist Rank

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain how to solve problem C ??

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very informative problem statements for a hard time like this pandemic.

»
2 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Why did $$$n = 2$$$ have to be allowed for F?

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

    To make solution much more shitty!

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

    to make it not div2D-E

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

      So (Div2D-E) + (some awful implementation) = Div2F?

      Wow!

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

        Lol it literally took me 130 lines to deal with it, and it's still wrong

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -22 Vote: I do not like it

        afwul implementation? okk, but you can solve any problem and make it "some awful implementation"

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

          When you solve good problem (on cf) implementation may be a bit heavy, but not awful.

          Since case with n = 2 is obvious when you have solved n > 2 it is pure implementation with many cases.

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it -22 Vote: I do not like it

            n=2 is obvious after n>2? many testers disagree with you

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

              I don't think that argument that uses "many testers" is good since many testers is your friends.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it -19 Vote: I do not like it

                What's obvious for a Div1 might not be obvious for a Div2.

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

                  Is div2F intended to be solved by Div2 participant during round?

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

        The implementation wasn't awful in my solution and I enjoyed writing it. Some problems were non-classic, e.g. the problem was with small $$$n$$$, not large $$$n$$$, and that was enough for me to think of it as an interesting problem.

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

      But then it just becomes a more annoying version of this problem (same basic idea with more casework), and as it's the only hard part ("go backwards" observation is necessary for $$$n = 2$$$ as well, so it's strictly easier to solve with larger $$$n$$$), you might as well have not allowed $$$n > 2$$$ then.

      Maybe my idea is wrong, I'll check myself after testcases become visible, but at least one part seems unnecessary and just to add on extra annoying implementation.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i have written a recursive function for C but it gives tle on pretest 4..could someone help me convert it into a dp solution using memoization or something like that?

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

    We can't use dp, limits are of x and y are 10^9.

    The answer is just 1+(x2-x1)*(y2-y1)

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

      Can you please explain how you are coming up with this formula?

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

        For C, We know that sum will be least if we go from (x1,y1)->(x2,y1)->(x2,y2) and sum will be maximum if we go from (x1,y1)->(x1,y2)->(x2,y2). So the answer is basically each sum between max_sum and min_sum. You can also notice that the max_sum is min_sum + no. of rectangles below it. Hence the answer is 1+(width-1)(height-1)

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

      Please elaborate.

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

        The constraints are too big. DP Solution will be $$$O(N^2)$$$ which means about $$$O(10^{18})$$$ operations which'll take months to pass ig.

        EDIT: Okay, maybe you were asking about how he arrived at the formula....

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

          I wanted about formula

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

            Yep, I edited right before your reply, sorry :)

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

            So let's have MxN rectangle:

            the least sum that you can get is when you first go right as much as possible and and then down.

            Each time you decide to go down before you reach right corner you add number of numbers left to right corner.

            So, max sum is the least sum + rectangle below, of size (m-1)(n-1). So the ans is (m-1)(n-1)+1

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

        Maximum possible sum — minimum possible sum + 1. I shifted to origin and calculated both sums using double AP. Minimum was when you go RRRRDDDD and maximum was when you go DDDDDRRRR.

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

        What my idea is: The sum will be minimum will we will just travel right and then down. And for maximum, travel down and then right.So, the answer will the total distinct sums between minimum and maximum.

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

    Even DP will be too slow for this problem since the points are in the range of $$$[1, 10^9]$$$. A test case could be $$$x_1 = 1, y_1 = 1, x_2 = 10^9, y_2 = 10^9$$$, and then the DP solution would require both $$$O(10^9*10^9) = O(10^{18})$$$ time and memory complexity (way too slow and too much memory).

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

      but let's just say the if the limits would have allowed for a dp solution to pass...then could u tweak my code from purely recursive to recursive +dp? Thx in advance.

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

        This article has implementation details of the purely recursive solution, DP algorithm, and a combinatorics solution. Hope that helps!

»
2 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Recent contests are just about finding patterns and adhoc solutions rather than any algorithms.

»
2 years ago, # |
  Vote: I like it +35 Vote: I do not like it

How to solve E?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it -25 Vote: I do not like it

    I think this should pass

    • if x > 0 : only possible k is n

    • else : optimal k is ceil(n/2)+-1 or ceil(n/2)

    I did not submit though.

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

      It doesn't pass. Wait for the editorial, we're going to release it soon.

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

    I applied if second val is > 0 , then total sum > 0 for ans to exist. if (x < 0) , then k >= (n+1)/2, so start traversing from back and find min length > 0 as increasing len further will make more negative for initial ones. but my failed somehow .

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

    Suppose, there exists a $$$k < \bigl \lceil \frac{n}{2} \bigr \rceil$$$ which satisfies the given condition, then for any $$$p > 1$$$, $$$pk$$$ also satisfies given condition. So it is just enough to search for $$$k \geq \bigl \lceil \frac{n}{2} \bigr \rceil$$$. Let $$$m = \bigl \lceil \frac{n}{2} \bigr \rceil$$$. Also, let $$$s_i = a_1 + a_2 + ... + a_i$$$. So for $$$k \geq m$$$, the consecutive sums are equal to $$$p_1 + (k - m)x, p_2 + (k - m + 1)x .... $$$

    All of these terms should be positive. Now consider first $$$i$$$ terms and you get an upper bound or a lower bound (depends on whether x is positive or negative) and check if $$$n - i + 1$$$ satisfies that bound. For case when $$$x = 0$$$, just check if $$$p_i > 0$$$ for all $$$i$$$.

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

    Isn't it allways optimal to use k=n? If sum of all is positive this works, if negative ans=-1 anyway. What did I miss?

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

      Look at the third example case.

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

        The example outputs 4, but 6 would be a valid answer, too. n is allways an valid answer if sum of all n months is positiv.

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

          Consider the 3rd case again: -2 -2 6 -3, total sum = -1, but k=3 is valid :D

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

            Ok, thanks. I think I misunderstood the problem statement.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How come so many people solved D?

What is the trick in D?

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

    There isn't really a trick, you just see that it is always optimal to end the last day of a month, and then you iterate over ends of month adjusting the beginning of the window so it is $$$x$$$ days large and "dynamically" calculate the hugs in the window with arithmetic progression sum formula.

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

      Literally thought the same but failed to implement during the contest. Thanks to C.

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

    Couldn't submit in time. But you can instead find min sum subarray with elements equal to total days — x in the cyclic array of days (Note a cyclic array is just a concatenation of 2 arrays). Now its always optimal that min sum subarray will start from day 1 or (last day) of any month. So just iterate over the months, and get sum using prefix arrays. And return "total sum — min".

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

    Key observation: the holiday must end at the end of some month.

    Solution
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I am not able to come up with a counter-example to this observation, but it's not really very clear either that it must hold.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        The official editorial explains this, we'll release it soon.

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

Did anyone else wrongly overthink B as 2 pointers and screw up the timer?

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

I know that C was easy 1 line formula and so and so...... I don't get that, I m very stupid!! Now plz explain the logic!!

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

    You need to think about the max possible sum and min possible sum. For example, take (1,1) and (3,3) as the coordinates. The grid is like this:-

    1 2 4

    3 5 8

    6 9 13

    As you can see, max possible sum will come when we go column first and then row i.e. 1->3->6->9->13. min possible sum will come when we go row first and then column at the end i.e. 1->2->4->8->13. Now you have to realize the difference in the terms . Draw 2-3 examples you will get it.

»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Im so sad...Problem C was really EZ but I spent most time of the contest and I couldn't solve it ;-;

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

    Same thing... I don't know how, but just multiplying difference between x and y + 1 works

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

      You need to think about the max possible sum and min possible sum. For example, take (1,1) and (3,3) as the coordinates. The grid is like this:-

      1 2 4

      3 5 8

      6 9 13

      As you can see, max possible sum will come when we go column first and then row i.e. 1->3->6->9->13. min possible sum will come when we go row first and then column at the end i.e. 1->2->4->8->13. Now you have to realize the difference in the terms . Draw 2-3 examples you will get it.

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

        It's not best way. I count it like summ of number in row 0 1 2 3 4 5 ... 5 4 3 2 1 0 and it wasn't correct for some of cases where n != m. The main problem is to count all these numbers.

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

          Try to look at my submission. I know it is not the best way but the question was not obvious to me when I tried it in the contest.

          Try to look at my formula in the submission. If you don't get it, I will explain how i arrived at it.

»
2 years ago, # |
  Vote: I like it +123 Vote: I do not like it

These were one of the worst problemsets ever, if we want to read newspaper we would go to other site not here

»
2 years ago, # |
Rev. 3   Vote: I like it -27 Vote: I do not like it

secrof tnemetats

»
2 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

I tried to use something of sort of exponential search for D, but couldn't write it. Is the algorithm below correct for Div2D?

  1. If $$$max(d_i) \ge x$$$ then we can just choose that month in reverse order, that is $$$max+(max-1)+..(max-x+1)$$$

  2. If not then we set end point at a month and try to reach as far before as possible. For this we can concatenate $$$d$$$ with itself so it becomes size $$$2n$$$ and precalculate arrays presum and presumsq each of size $$$2n$$$ (presum array is for presum of $$$d$$$ and presumsq is holding presum of $$$\binom{d_i+1}{2}$$$

Is this correct approach, what is the correct approach

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

I spent most of the contest trying to calculate sums of difference series in question C until I figured out the simpler solution... oof

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Question B exposed my reading skills.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How To solve E if $$$x <= 0$$$ $$$?$$$

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can C be solved using recursion+dp?

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

    No. DP is too slow because x, y can get very large.

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I feel like I'm getting worse each contest. Took an awful amount of time for A,B and I'll barely stay expert thanks to C

»
2 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Problem C is cool.(Only after you get it)

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

I can't figure out why my solution for E gives WA. I did the following:

  • If the sum of $$$a$$$ is positive, answer is $$$n$$$.
  • Otherwise, if $$$x$$$ is not negative, there's no answer.
  • Otherwise, let $$$w$$$ be the smallest integer such that the sum of $$$a_{n-w+1}, a_{n-w+2}, ..., a_n$$$ is positive. If all subarrays of size $$$w$$$ are positive, $$$w$$$ is the answer.
  • Otherwise, there's no answer.
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    9

    -1 -1 2 -2 5 -1 -1 -1 -1

    I think this can be one of the counterexample.

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

      Thanks, this was very helpful to correct my solution.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    6
    4 -4 4
    -1
    
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Misinterpreting and misreading questions since 4-5 rounds. Fucking up every contest like a boss.

»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It took me to see comments to get the pattern in C and still don't understand. please explain why it works

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

    You need to think about the max possible sum and min possible sum. For example, take (1,1) and (3,3) as the coordinates. The grid is like this:-

    1 2 4

    3 5 8

    6 9 13

    As you can see, max possible sum will come when we go column first and then row i.e. 1->3->6->9->13. min possible sum will come when we go row first and then column at the end i.e. 1->2->4->8->13. Now you have to realize the difference in the terms . Draw 2-3 examples you will get it.

»
2 years ago, # |
  Vote: I like it -24 Vote: I do not like it

This competition is very innovative , and I believe that as long as we work together, we will be able to defeat the virus one day. Let's work together to eliminate the virus!

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

man I made terrible decisions this contest I could have solved C if I didn't try to hack unhackable A,B problems :'(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone please explain this solution of C https://codeforces.com/contest/1358/submission/81496705

  • »
    »