*С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 ilian04 Andrianov, Vsevolod Sevlll 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:

MikeMirzayanov for wonderful platforms Codeforces and Polygon!

300iq for excellent coordination and helpful advices!

Thanks to Siberian, mohammedehab2002, Degalat57, Kuroni, pajenegod, hugopm, Dart-Xeyter, alexxela12345, FlameDragon, Monogon, YanikusGG, Mangooste, mbolgov, Ziware, xiryss for delightful testing!

Special thanks to testers imachug, dorijanlendvaj, antontrygubO_o,_overrated_ and Allvik06 for help in finding errors in problems!

**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 | OI_Blacksmith | 6 | 6910 |

2 | HackerDemon | 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 |

`"coronavirus contest"`

I won't risk taking part in it.

Everything is thoroughly sanitized!

hopefully my addresses will be sanitized

Hacks should be sanitized.

Just sanitize your hand after attempting each task..

Before is better

I WANT MAXIMUM NEGATIVE CONTRIBUTION PLZ HELP ME.

You are not doing well man. :(

he used reverse psychology to get so many upvotes.well done @Mr_Frustrated

And then how would you analyse the way i get upvotes?

alas! my friend it will not work for u. IN YOUR FACE

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?

use mask ….

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

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

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

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

enjoy coders...

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

I thought it was "short* statements ... " :p

It's beautiful when it's short xD

Check April Fool's contest and change your mind :D

-That's what she said :P

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

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

Damn, u was right!

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

it will

Every contest maker say that.

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

Yes, I know what u meant lol:)

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.

Schrödinger's Contest

In other news, water is wet.

WATER IS SINK

I see I was mentioned?

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.

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

The time shown in calendar differs.

You're the only man on earth who checks the calendar in Codeforces.

I was born in last century.

fixed, thanks

The funny thing is that when you go to Codeforces, whose logo says

`Make Codeforces, not Coronaforces`

, the first thing you see is that announcementI hope that there will not be any new disputes on this topic

LOVE THOSE LINES

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

See

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.

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

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

I hope problems will be related to fighting coronavirus.

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.

You spelled CHINA wrong.

DO YOU MEAN IT？

Hey I got nothing to do with that.

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.

good words

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.

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

But the stories were really sh**ty.

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

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

Disclaimer: Contains Offensive Content`I request you guys to take it as JOKE`

we aren't

Then its SafeWho cares if a joke is offensive. What cannot be forgiven is a joke not being funny.

You R wrong my son, history is the witness that offensive content gets downvoted not the low level jokes. RIP my post

You are right as always, daddy.

No my son,then they are called Daddy of Americans God will help u, son. Have faith in GOD

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

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

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

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

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

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

It is 14:35 UTC. There is Moscow time in announcement

300iq always makes so interesting contests :D

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

They are not mutually exclusive.

Short statements, like April Fools Day Contest.

`your your rating increase`

in English version, Alexdat2000thanks, fixed

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

Lol..Every tester copy pastes the same line.

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

did you try it on codechef ide? sometimes testing contest code on codechef ide helps!

yes

cur=0

THNX BRO. I TOTALLY MISSED IT.

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

Alternatives to names Alexdat2000

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

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

Deleted

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

i don't want to end up in lockdown

Stay homeandCodebecauseCodeforceswill 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.Deleted

i hope to find nice problems and nice ideas

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

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

Nice score distribution:)

Got to learn a lot !What about social distancing???.

No

Corona Virus Contest! Expecting Bats in problem statements!!

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

Deleted

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

I bet there gonna be a bit masking problem!

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

Well you've got 4 hours to study it though. :)

Thanks for helping me to figure this out!! LOL!

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

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

thanks :)

Do setters contact MikeMirzayanov or anyone from Codeforces contact high rated people?

when you are eligible to proposing contests/problems the option to do so will appear on your account (read this)

Deleted

I think you should fix yourself(your bug) first .Your memes are being boring .

Please downvote me.

I'm in!

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

The "original coronavirus" isn't magenta

Ohk!

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

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

Сoronavirus work!!coronavirus school!!coronavirus rest!!coronavirus time spending!!coronavirus contest.!!Make sure everyone sanitize their code before compiling.

Prevent corona-unrate virus through queue-distancing.

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

Coronavirus contest should include bit-mask problems

bulmanupje? kut!!

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!

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

Nice

It is strictly recommended to hate 300iq

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

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.

There were other testers besides you who liked the pictures.

You can share this memes so everybody can judge on their own.

As tester, I totally agree with you.

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

is the new rating system starting from this contest?

I like it

How do you prepare yourself 30 minutes before the contest?

making tests for the problems

We try to keep ourselves calm before the contest, if i talk about myself then i go for a short evening walk before contest, which relax my mind, also i prepare all my templates, charge my laptop, take a water bottle, go to washroom and start contesting... you don't need to be preparing hard by solving problems just before the contest...its not my a university exam...

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

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)

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

The problems are nice, the statements are

ugly.How would you modify the statements to make then nicer?

Mainly D, I don't like such themes

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

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

thanks

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

Strongly agree

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

Hope, you enjoyed problemset anyway

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

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

C is just observation based. :)

again tried bro..but failed (bad luck or my little knowledge)..

C was certainly not worth 1500.

You mean its worth more or less? lol

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.

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

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

WTF

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

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

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

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

it is short in code but idea is not really easy

True AF :3

Write a generator and observe, is it that hard?

not hard, but not too easy for div2C

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

Are you familiar with the concept of proof?

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

Same here buddy. XD

It really took me almost an hour to realise how foolish I am. :(

lmao, I felt the same

Can you share your approach please !!

what is the solution of C... isn't it (x2-x1)*(y2-y1)+1?

it is

https://codeforces.com/contest/1358/submission/81529915

I forgot to convert in long long ... my bad

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

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

}

THANK YOU

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

Nice problemset. Thanks!

1358B - Maria Breaks the Self-isolation Now I see what the point of grannies near to my house is

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

Me after solving C

What's the pattern?

Edit: I'mma cry myself to sleep.

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

I also came up with the same solution .. but can't figure out when the paths will have same sum...help me with C

For $$$(1,1)$$$ to $$$(3,3)$$$: $$$1-2-5-9-13$$$ and $$$1-3-5-8-13$$$. You can work the pattern out similarly for other values.

https://codeforces.com/contest/1358/submission/81529915

I forgot to convert in long long.. my bad

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

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

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.

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

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

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.

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.

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

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

Humorous and awful......

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; }

}

x should be a long

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.

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

Hello Specialist Rank

come to me! u get a partner!

Can somebody explain how to solve problem C ??

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

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

To make solution much more shitty!

to make it not div2D-E

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

Wow!

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

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

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.

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

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

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

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

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.

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.

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?

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

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

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

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)

Please elaborate.

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

I wanted about formula

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

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

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.

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.

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

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.

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

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

How to solve E?

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.

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

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 .

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

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?

Look at the third example case.

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.

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

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

How come so many people solved D?

What is the trick in D?

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.

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

Couldn't submit in time. But you can instead find

minsum 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".Key observation: the holiday must end at the end of some month.

SolutionIterate over each month and do binary search to find in which month the holiday starts.

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.

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

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

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

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.

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

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

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.

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.

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.

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

agree

I can't disagree with that.

secrof tnemetats

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

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

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

arrayspresum 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

ternary search over start date of each month

Yes

I tried writing it in my own way using exponential search (or binary search) submission can you check out and tell if theres a way to simplify

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

Video tutorial for today's C

Discord server

you talk too much!!! just tell the logic and move on!!

check out the poll here, I did a poll to see what the subscribers want

Question B exposed my reading skills.

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

can C be solved using recursion+dp?

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

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

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

can you please explain it's approach..i still did't get it thanks in advance.

The difference between max and min sum + 1.

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

9

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

I think this can be one of the counterexample.

Thanks, this was very helpful to correct my solution.

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

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

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.