Alexdat2000's blog

Codeforces Round #645 (Div. 2)
By Alexdat2000, 4 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

Comments Comments (371)
| Write comment?
»
4 years ago, # |
  Vote: I like it +252 Vote: I do not like it

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

→ Reply
»
4 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...

→ Reply
»
4 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".

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

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

→ Reply
  • »
    »
    4 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.

    → Reply
»
4 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!

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

→ Reply
»
4 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.

→ Reply
»
4 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.

→ Reply
  • »
    »
    4 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.

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

The time shown in calendar differs.

→ Reply
»
4 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

→ Reply
»
4 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.

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

    See

    → Reply
    • »
      »
      »
      4 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.

      → Reply
      • »
        »
        »
        »
        4 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.

        → Reply
        • »
          »
          »
          »
          »
          4 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

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

        I hope problems will be related to fighting coronavirus.

        → Reply
        • »
          »
          »
          »
          »
          4 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.

          → Reply
      • »
        »
        »
        »
        4 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.

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

          good words

          → Reply
        • »
          »
          »
          »
          »
          4 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 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..

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

              But the stories were really sh**ty.

              → Reply
»
4 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

→ Reply
  • »
    »
    4 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

    → Reply
»
4 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

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

    we aren't

    → Reply
  • »
    »
    4 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.

    → Reply
  • »
    »
    4 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?

    → Reply
    • »
      »
      »
      4 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.

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

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

        → Reply
»
4 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

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

300iq always makes so interesting contests :D

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

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

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

your your rating increase in English version, Alexdat2000

→ Reply
»
4 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

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

    Lol..Every tester copy pastes the same line.

    → Reply
  • »
    »
    4 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

    → Reply
»
4 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!

→ Reply
»
4 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.

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

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

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

Deleted

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

i don't want to end up in lockdown

→ Reply
»
4 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.

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

i hope to find nice problems and nice ideas

→ Reply
»
4 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!"

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

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

Nice score distribution:)

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

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

What about social distancing???

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

.

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

Corona Virus Contest! Expecting Bats in problem statements!!

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

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

→ Reply
»
4 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 :)

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

I bet there gonna be a bit masking problem!

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

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

    → Reply
  • »
    »
    4 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!

    → Reply
»
4 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!

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

Deleted

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

I'm in!

→ Reply
»
4 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.

→ Reply
»
4 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.

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

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

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

Make sure everyone sanitize their code before compiling.

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

Prevent corona-unrate virus through queue-distancing.

→ Reply
»
4 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) (? = </>).

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

Coronavirus contest should include bit-mask problems

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

bulmanupje? kut!!

→ Reply
»
4 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!

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

It is strictly recommended to hate 300iq

→ Reply
  • »
    »
    4 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 :(

    → Reply
    • »
      »
      »
      4 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.

      → Reply
»
4 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

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

is the new rating system starting from this contest?

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

I like it

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

How do you prepare yourself 30 minutes before the contest?

→ Reply
»
4 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.

→ Reply
»
4 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)

→ Reply
»
4 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.

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

    How would you modify the statements to make then nicer?

    → Reply
    • »
      »
      »
      4 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???

      → Reply
    • »
      »
      »
      4 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.

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

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

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

    Strongly agree

    → Reply
  • »
    »
    4 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

    → Reply
  • »
    »
    4 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.

    → Reply
»
4 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 :(

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

C was certainly not worth 1500.

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

    You mean its worth more or less? lol

    → Reply
    • »
      »
      »
      4 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.

      → Reply
      • »
        »
        »
        »
        4 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

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

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

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

            WTF

            → Reply
          • »
            »
            »
            »
            »
            »
            4 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?

            → Reply
          • »
            »
            »
            »
            »
            »
            4 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..

            → Reply
      • »
        »
        »
        »
        4 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

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

        it is short in code but idea is not really easy

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

          True AF :3

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

          Write a generator and observe, is it that hard?

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

            not hard, but not too easy for div2C

            → Reply
          • »
            »
            »
            »
            »
            »
            4 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

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

            Are you familiar with the concept of proof?

            → Reply
  • »
    »
    4 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 :))

    → Reply
»
4 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".

→ Reply
»
4 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

→ Reply
  • »
    »
    4 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?

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

Nice problemset. Thanks!

→ Reply
»
4 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

→ Reply
»
4 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

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

Me after solving C

Me after solving C

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

    ‎

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

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

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

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

      → Reply
      • »
        »
        »
        »
        4 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

        → Reply
        • »
          »
          »
          »
          »
          4 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 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.net/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.

                  → Reply
  • »
    »
    4 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.

    → Reply
  • »
    »
    4 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

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

Humorous and awful......

→ Reply
»
4 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);


}

}

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

    x should be a long

    → Reply
    • »
      »
      »
      4 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.

      → Reply
  • »
    »
    4 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.

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

Hello Specialist Rank

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

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

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

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

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

    To make solution much more shitty!

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

    to make it not div2D-E

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

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

      Wow!

      → Reply
      • »
        »
        »
        »
        4 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

        → Reply
      • »
        »
        »
        »
        4 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"

        → Reply
        • »
          »
          »
          »
          »
          4 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 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.

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

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

                  → Reply
      • »
        »
        »
        »
        4 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.

        → Reply
    • »
      »
      »
      4 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.

      → Reply
»
4 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?

→ Reply
  • »
    »
    4 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)

    → Reply
    • »
      »
      »
      4 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?

      → Reply
      • »
        »
        »
        »
        4 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)

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

      Please elaborate.

      → Reply
      • »
        »
        »
        »
        4 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....

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

          I wanted about formula

          → Reply
          • »
            »
            »
            »
            »
            »
            4 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

            → Reply
      • »
        »
        »
        »
        4 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.

        → Reply
      • »
        »
        »
        »
        4 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.

        → Reply
  • »
    »
    4 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).

    → Reply
    • »
      »
      »
      4 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.

      → Reply
      • »
        »
        »
        »
        4 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!

        → Reply
»
4 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.

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

How to solve E?

→ Reply
  • »
    »
    4 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.

    → Reply
    • »
      »
      »
      4 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.

      → Reply
  • »
    »
    4 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 .

    → Reply
  • »
    »
    4 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$$$.

    → Reply
  • »
    »
    4 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?

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

      Look at the third example case.

      → Reply
      • »
        »
        »
        »
        4 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.

        → Reply
        • »
          »
          »
          »
          »
          4 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

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

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

            → Reply
»
4 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?

→ Reply
  • »
    »
    4 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.

    → Reply
    • »
      »
      »
      4 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.

      → Reply
  • »
    »
    4 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".

    → Reply
  • »
    »
    4 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
    → Reply
    • »
      »
      »
      4 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.

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

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

        → Reply
»
4 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!!

→ Reply
  • »
    »
    4 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.

    → Reply
»
4 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 ;-;

→ Reply
  • »
    »
    4 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

    → Reply
    • »
      »
      »
      4 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.

      → Reply
      • »
        »
        »
        »
        4 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.

        → Reply
        • »
          »
          »
          »
          »
          4 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.

          → Reply
»
4 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

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

secrof tnemetats

→ Reply
»
4 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

→ Reply
»
4 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

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

Video tutorial for today's C

Discord server

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

Question B exposed my reading skills.

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

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

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

can C be solved using recursion+dp?

→ Reply
  • »
    »
    4 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.

    → Reply
»
4 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

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

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

→ Reply
»
4 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.
→ Reply
  • »
    »
    4 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.

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

      Thanks, this was very helpful to correct my solution.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    6
4 -4 4
-1
    → Reply
»
4 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.

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

→ Reply
»
4 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

→ Reply
  • »
    »
    4 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.

    → Reply
»
4 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！

→ Reply
»
4 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 :'(

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

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

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

    when k=(x2-x1)=(y2-y1) ans=k*(k+1) — k=k*k which is same as (x2-x1)*(y2-y1)

    otherwise if (x2-x1 < y2-y2) than totDiag = (x2-x1+y2-y1 — 1 — 2*(x2-x1)) = y1-y1 -(x2-x1) -1 (here k=(x2-x1))
    ans=(x2-x1)*(x2-x1+1)+ totDiag*k (where k=(x2-x1))
    ans=(x2-x1)*(x2-x1+1+totDiag)=(x2-x1)*(y2 -y1)

    anyway the answer is (x2-x1)*(y2-y1)+1

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

waiting for editorials !!!

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

No DS ALGO required. Quite adhoc(bad) problems.

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

    Most problems here weren't ad-hoc. They made you think, sometimes use some well-known ideas, sometimes make up some parts yourself. If you're looking for plain tasks which can be solved using data structures without any ideas, check gym.

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

I was so surprised when I used the translator for the D problem. Is it… funny? UPD : The editorial pic is ridiculous.I am so disappointed.

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

    it is not formal statement, it has some "legend", some story about characters of problem

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

      Thank you for replying and a good contest! (Unfortunately, My rating is gone... I need more practice :(

      I understand the problem statement is not intended to hurt someone. but I hope you think about people who are suffered from COVID-19. I guess dating viruses is not appropriate.. even if that is " legend". Also, considering Naha is one of the cities in Japan, some people may misunderstand your intension. sorry for my bad English.

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

        Changing the city name to Naha was suggested by MikeMirzayanov. You know whom to blame now :)

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

          The point is not who decided the city name, but the background of the statements.

          I’m not interested in who’s at fault. because no one knows all cities name in the world, and we might have a mistake even we do best. if you notice the city name is not appropriate and some people may have negative feelings about the statements, it’s ok.

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

        @imachug is right, the first name of the city was reversed "Wuhan". But is isn't good name for Russian participants...

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

          It sounds even more offensive for people from Wuhan. I think it is not good even you didn't mean it.

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

bad statements,for problem D.

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

    bad like translation is bad or like you want formal statements without any story?

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

      I think a virus-free statement is better.
      Many people lose their lives because of it, more serious pls.
      Maybe some of our friends in CF ^ ^

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

        The quarantine doesn't affect people well. Many people are depressed because of news about COVID-19, and I thought bringing some fun into this situation would help.

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

      I think dating with virus isn't a good idea, as virus is such a disaster to humans. What's more, some users' friends or parents in CF may have just killed by Coronavirus. Therefore, a virus-free or anti-virus background is better I think. Anyway, I have to say that the problems are very great. With a better description, the contest would be more perfect.

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

      I didn't mean that COVID-19 should not appear in statements, but dating a virus makes me uncomfortable.

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

Why I can't submit now?

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

ratings down again. Special A B and C problems took me more time than before to solve them. And I didn't have much time to implement D, what a pity.

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

My idea to Solve C is completely different just find maximum value of all paths from source to destination and also minimum value of path from source to destination and out put max — min+1 as answer.

Though when I went submitting it contest was Over and ratings RIP.

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

    I also did the same approach and fortunately It got submitted in last moment.

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +8 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 since sums need to be unique.

Now you can also notice that max_sum = min_sum + no. of rectangles below it. Hence the answer is 1+(width-1)(height-1). Try to draw a grid and check this to understand better.

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

"Solve this problem and get the cookie, or the coronavirus will extend the quarantine for five years and make the whole economy collapse!"

One of the best quotes from statement I've ever seen xDDDDD

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

I really enjoyed F statement

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

Problem C took forever, as I was trying to prove the solution. The problem writers had presented another problem (D) with the same score, so in retrospect, perhaps focus should've gone there instead..

The gist of the solution is that if you take any rectangle block, then all possible sums range from a begin value to an end value, covering every value in between. The smallest value is if you run along row 1 and then down the last column. The largest value is if you run down column 1 and then along the last row. So for one of the examples (x1=1, y1=2, x2=2, x4=4), the sums range from 25 to 27, resulting in a total of 3 (i.e. 27 — 25 + 1) values.

The proof roughly lies in the fact that at each position, you can move to the right or down. Moving down = 1 + moving right (by virtue of the layout of the numbers). The more right that you move from any position, the smaller your score gets relative to the score had you gone down instead.

I ended up with a needlessly complex solution (by calculating the number of diagonals and their lengths) rather than simply realizing that there are always (y2-y1)*(x2-x1) + 1 total possible sums in a grid of (x1,y1) to (x2,y2).

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

Anyone else who found D to be much more easier than C ?

I'm still not able to figure out how is (x2-x1)*(y2-y1)+1 working !

Tho intuitively i was guessing the answer to be (x2-x1+y2-y1)!/(x2-x1)!*(y2-y1)!, the simple mathematical approach to go from A to B in a matrix when only going down and right are allowed . Why is this approach not working here, can someone give an example when sum of values of 2 paths will be same in this approach? And from where on earth did (x2-x1)*(y2-y1)+1 came from?

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

    let X be path.

    Then

    XXO
OXO
OXX

    and

    XOO
XXX
OOX

    will have the same sum on any 3x3 subgrid. With some experimentation, we find that the sum is directly correlated to the number of "O"s on the top right section of the path.

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

    Like Failure said, RDDR weights the same as DRRD, always.

    The minimum possible path is going full right, and then down, whereas the max possible path is going down then right. You can manipulate the paths by one block to obtain a still valid one that weights 1 less or 1 more. Therefore $$$max$$$, $$$min$$$, and all values between are possible.

    The number of paths is precisely $$$max - min + 1$$$. To calculate $$$max - min$$$ what you can do is pairing the elements in both paths if they are in the same diagonal, take the differences and add them up. There are two ways to notice this is equal to $$$(x_2 - x_1) \times (y_2 - y_1)$$$. The first way is to imagine the differences as distances in the grid. Then it's pretty clear that the sum is the area of the rectangle.

    The second one, which was the one I used, was expressing the sum in terms of the minimum and the maximum between $$$h = x_2 - x_1$$$ and $$$w = y_2 - y_1$$$. The sum can be easily separated into two triangles and a diagonal section:

    $$$max - min = min(h, w) \times (min(h, w) + 1) + (max(h, w) - min(h, w) - 1)\times min(h, w)$$$.

    Working out the formula gives $$$max - min = h \times w$$$, but I didn't really notice that during the contest, I just sent the formula above.

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

      Maybe I can give a more easy justification for (x2-x1)*(y2-y1) + 1. It is obvious that the maximum path is D...DR...R and the minimum path is R...RD...D . Now to see these many distinct paths one can observe that including one cell in the minimum path increases the path sum by one. This is because each diagonal contains an increasing sequence. At most you can include (n-1)*(m-1) cells giving you the correct answer.

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

    We find the sum in the maximum sum path (DDD...RRR), and the sum in minimum sum path (RRR...DDD). All the values between these values are possible. (Change one DR pair to RD pair to decrease the sum by one). Now, the difference between the sums can be found easily, every D-R pair will be swapped once. Therefore, the answer is (count(D)*count(R))+1.

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

Does anybody else thought that C is just finding number of different paths from start to end ?? And finally ended up finding number of ways to loose your contest rating ...XDD

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

Imho, problem C should cost similar to A or B. Adding more samples would make this problem a problem A. Though, the formulae was pretty hard for me to derive. But very easy for some participants just to guess it.

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

    For me I didn't guess it but counted the difference between minimum and maximum sum paths and noted that all intermediate sum paths can be achieved. But in the end I realised the same thing as you said, that taking some cases one can guess the formula.

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

Alexdat2000 , In problem D, I've found an accepted solution which is giving wrong output for this case:

3 3
1 1 1

The actual answer of this case is = 3. But the solution is giving 1 as output. Kindly add this type of case in the dataset of problem D.

Submission Link: https://codeforces.net/contest/1358/submission/81555078

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

    I just uphacked the solution, so that test will be added for all future submissions.

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

Thanks a lot Alexdat2000 for setting this round... Finally became CM :)

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

Very happy to reach expert for first time :-D

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

[Deleted]

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

became expert in this round.solved D problem for the very first time.

thanks for tbe wonderful round.

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

The contest was terrible! Really boring problems! C and D were SOOOOOOO boring!

If you want to give me down votes because of this, give me! I'm not afraid of it!

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

    You created a new account to just write a comment and now you telling that you don't afraid of down votes?

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

Is Div2B is same as the problem here with a different granny story? #Justasking.

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

I thought this was an excellent contest with some very interesting problems. Hats off to the problem writers for doing a fantastic job!

However, I have one criticism of problem F:

Please stop guaranteeing things. It isn't clear when you guarantee something whether this is a constraint on what input is legal, or a hint to make the problem easier. This ambiguity is completely avoidable if you just say 'we can show ...' instead of 'it is guaranteed'.

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

F was so hard to me....

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

The problems are interesting as well as the pictures in Tutorial except problem D:(

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

After reading problem D, I really felt the author's pain and how lonely he's been feeling in this quarantine. I pray for you that you get to see your girlfriend soon!! ;>

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

    Did you just assume that everyone has a girlfriend? Maybe he wants to see his crush?

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

As i am new to this platform i am not able to understand its rating system which got changed recently i solved 1 problem in stipulated time but got -66 can any one explain me ? and how rating change works for a new account i was not able not understand the post

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

    Basically you are compared to all other participants of the contest, and if you have done good your rating raises.

    If you solve one problem and most of other people solve two your rating might not raise.

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

Since whatever he did is not clear so its not ethical to say anything about him right now, If he cheated,please stop it,If not,I am very sorry to him.I am keeping the attached blog as it was very helpful for many. Original Blog

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

Can div 2 c be solved using dynamic programming

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

    No, DP is too slow for this problem cuz $$$(1≤x1≤x2≤10^9)$$$ $$$(1≤y1≤y2≤10^9)$$$

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

    Try to find formule. It can be solved with easy formule

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

I did see your love to Сoronavirus. Seems you are really happy to play with it.

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

Idk why people have been joking around with Coronovirus while not seeing people devoting their lives to control it. Sorry for not being humorous.

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

Is the problem in love with the coronavirus?Did they kiss?Why are you making jokes about the coronavirus?Just because you didn't die of coronavirus?This is no fun at all.Here's a bowl of bats for the problem maker:-)Wish you enjoy it:-) Does Naha mean the reversation of Wuhan? 出题人就是个傻逼。出题人给爷爬。你自己不感染很狂？

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

    Is this the REAL NaCly_Fish???

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

      I don't think it's him(

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

        I asked him on QQ though he didn't reply. Yet it's still impossible to find him at school(his school's quite close to mine) due to the coronovirus.

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

          So none of us knows his exact CF account？

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

            I do, at least I once do... It was unrated, with a image of Honkai Impact 3...

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

      No,it's i not l

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

deleted

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

The photos in solution post are clearly racist. We need you to delete it immediately and apologize. This isn't funny at all. Freedom of speech does not mean you can say anything unthoughtfully at your will. I couldn't imagine this happened at codeforces.com. If it happen in my university, you will be subjected to charges from Student Council of Accountability!! The result could be complete expulsion from school. Pledase delete the photo, apologize to whom it may concern and stop playing with politics,boi.

You are too young as a boi who hasn't finished his homework to play with politics.

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

    May I ask what racism you saw in the pictures?

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

      Yes of course. The photo posted by Sevill used cartoon character dressing in traditional Chinese skirt to resemble an Asian, presumbly Chinese girl. The character holds a bowl with bat soup in it. Is this compelling enough?

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

      Overgeneralization itself is a crime.

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

      Furthermore, the fortune cookies are commonly found in oversea Chinese restaurants. I think there is no need to point out what the author of the photo was trying to express.

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

    Lol, I don't like to foist my viewpoints upon the others. However, this must be built upon the basis of mutual respect. No matter where, Russia , Europe , US, China, Asia , Africa, healthcare workings are working so hard to protect other people from this damned virus. Many of them are not fortunate enough to see the summer of 2020. At the same time, some people takes the death tolls carelessly as if it is a joke and use it to make fun at other people. I don't think this is correct.

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

      "coronavirus"

      AHAHAHAHHAHAHAHAHA

      what a joke

      agree?

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

        Plz repeat your question to doctors and nurses who are still on their position of fighting this goddamned virus. What a joke to them.

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

        Bro you don't get my point. This is a algorithm website. This isn't twtr where you could discuss some global issue and debate with each other. I think users should be more considerate when posting something about politics, espcially the topics that could potentially cause dispute. Let's focus on algorithm and competition.

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

    I don't think racism should be the exact word... Though it was unproper.

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

I started a few months ago. I didn't participate any contests but just do it as practice to improve my overall algorithm ability.

I am SO SHOCKED that Codeforces would allow this kind of racist content (problem D). I know that some people mentioned this is and got downvoted. I don't like downvotes (in fact I think this is my first comment), but I think I need to standup against this type of nonsense.

  1. I am okay with you mocking with COVID, but does it really need to be "Coronavirus-Chan"? Do you really need that "Chan" part? That's clearly insult to any Chinese/Eastern people (This is a surname used in China, Hong Kong, Taiwan, Singapore and many more places).

  2. Do you really need a picture of an Asian lady holding a cooked bat? That suggests the virus coming from people eating bats. But this is clearly not the case. Even in China, most people don't eat weird things like this.

  3. Every country got hit by COVID and many people die from it. My family member died because of it. When I looked that problem D, it is very unpleasant to work on it.

Can we keep this place a politically neutral place and only about algorithm and technologies?

→ Reply