Сoronavirus work, coronavirus school, coronavirus rest, coronavirus time spending, coronavirus contest.
Привет, Codeforces!
Во 26.05.2020 17:35 (Московское время) пройдёт Codeforces Round 645 (Div. 2). Он будет рейтинговым для всех участников, чей рейтинг ниже 2100. Вам будет предложено 6 задач и 2 часа на их решение.
Задачи были придуманы и подготовлены Алексеем Alexdat2000 Дацковским, Илианом crazyilian Андриановым, Всеволодом sevlll777 Лепешовым. Мы постарались сделать интересные задачи, красивые условия и сильные тесты. Надеемся, что вам понравятся задачи и ваш рейтинг станет выше!
Мы выражаем благодарность:
MikeMirzayanov за великолепные платформы Codeforces и Polygon!
300iq за прекрасную координацию и полезные советы!
Спасибо Siberian, mohammedehab2002, Degalat57, Kuroni, pajenegod, hugopm, Dart-Xeyter, alexxela12345, FlameDragon, Monogon, YanikusGG, Mangooste, mbolgov, Ziware, talant за восхитительное тестирование раунда!
Отдельное спасибо тестерам purplesyringa, dorijanlendvaj, antontrygubO_o,_overrated_ и daubi за помощь в поиске ошибок в задачах!
UPD 1: Разбалловка: 500 — 750 — 1500 — 1500 — 2000 — 2500
UPD 2: разбор
UPD 3: Поздравляем победителей раунда!
Топ 5 официальных участников:
| Место | Участник | Задач решено | = |
|---|---|---|---|
| 1 | Ariadne.w. | 6 | 6910 |
| 2 | HackerMonk | 6 | 6752 |
| 3 | Potassium | 5 | 5543 |
| 4 | qwertz73355a | 5 | 5478 |
| 5 | SorahISA | 5 | 5446 |
Топ 5 всех участников:
| Место | Участник | Задач решено | = |
|---|---|---|---|
| 1 | Egor | 6 | 7821 |
| 2 | kort0n | 6 | 7495 |
| 3 | Golovanov399 | 6 | 7365 |
| 4 | nuip | 6 | 7346 |
| 5 | Geothermal | 6 | 7332 |
Участники, пославшие первое правильное решение по задачам:
| Задача | Участник | Штраф |
|---|---|---|
| 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
use mask ….
Don't worry! CF will maintain long distant Queues.
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.
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
как тестер, я могу заявить, что авторам <= 16 лет.
как автор, я могу заявить, что авторам >= 15 лет
Тут даже и постиронии не надо.
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
I'll sanitize my laptop before attempting this contest.
and after too
I request you guys to take it as JOKEwe aren't
Who 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.
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.
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 increasein 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
i don't want to end up in lockdown
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.
i hope to find nice problems and nice ideas
Давайте сделаем специальный контест под названием "Coronavirus Contest", будет рейтинговым либо для всех, либо для зараженных коронавирусом (надеюсь таких на Codeforces нет)
Мы хотели так назвать этот контест, но нам не разрешили
That illustration looks like it's from a Rick & Morty episode. "Covid Riiiick!"
Nice score distribution:)
What about social distancing???
.
No
Corona Virus Contest! Expecting Bats in problem statements!!
Hope "Accepted" wouldn't make social-distancing from "Pretests Passed" :)
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
Коронавирус, кет кет кет Коронавирус, нет нет нет
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!
Изменится ли рейтинг, если я зарегистрировался на контест, но не смогу принять в нем участие?
нет, он изменится только если сделаете хотя бы 1 посылку
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
.
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 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
what is the solution of C... isn't it (x2-x1)*(y2-y1)+1?
it is
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.
THANK YOU
U did n't send ur code, how can anyone check it?
Nice problemset. Thanks!
1358B - Марья Ивановна нарушает самоизоляцию 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
$$$(x2-x1)(y2-y1)+1$$$
(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.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.
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......
Интересно что за 12й тест был в задаче D.
Ладно, это было обидно) Я x считывал как int, а не как long
adhocforces
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); }}
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!
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 still wrong
afwul 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
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 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".
Key observation: the holiday must end at the end of some month.
Iterate 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.
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 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
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.
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！
man I made terrible decisions this contest I could have solved C if I didn't try to hack unhackable A,B problems :'(
Anyone please explain this solution of C https://codeforces.net/contest/1358/submission/81496705
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
waiting for editorials !!!
No DS ALGO required. Quite adhoc(bad) problems.
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.
.
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.
it is not formal statement, it has some "legend", some story about characters of problem
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.
Changing the city name to Naha was suggested by MikeMirzayanov. You know whom to blame now :)
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.
@imachug is right, the first name of the city was reversed "Wuhan". But is isn't good name for Russian participants...
It sounds even more offensive for people from Wuhan. I think it is not good even you didn't mean it.
тильт
bad statements,for problem D.
bad like translation is bad or like you want formal statements without any story?
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 ^ ^
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.
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.
I didn't mean that COVID-19 should not appear in statements, but dating a virus makes me uncomfortable.
Why I can't submit now?
Wait till system testing is over.
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.
at least you found the easy solution for C! after https://codeforces.net/contest/1358/submission/81535983 I didn't even have time to understand how D can be solved xD
I just try and guess. I cant prove my solution for C, and it got AC with some luck.
How did you arrive at the formula of colsum?
I just divided the rectangular into a square and a rectangular. Then the square has some rules such like 2*2->2 3*3->5 4*4->10 just (n-1)*(n-1)+1 and the left rectangular can guess a formular too which is very easy.
Going down then right is exactly one more than going right then down.
Excellent question. I think it went somewhat like this: - pattern recognition to formalize changes between adjacent cells - using Wolfram Alpha to get an O(1) formula to describe the value in a cell as a function of row and column - using Wolfram Alpha on a sum over this formula, like this https://www.wolframalpha.com/input/?i=sum_%7Bi+%3D+1%7D%5Ex+%28+i*%28i%2B1%29%2F2+%2B+%28%28i-1+%2B+y-1%29*%28i-1+%2B+y-1+%2B+1%29%2F2+-+i*%28i-1%29%2F2%29+%29
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.
I also did the same approach and fortunately It got submitted in last moment.
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.
"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
I really enjoyed F statement
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).
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?
let X be path.
Then
and
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.
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.
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.
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.
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
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.
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.
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
I just uphacked the solution, so that test will be added for all future submissions.
Thanks a lot Alexdat2000 for setting this round... Finally became CM :)
good job!
Very happy to reach expert for first time :-D
[Deleted]
Resubmission costs you 50 points
became expert in this round.solved D problem for the very first time.
thanks for tbe wonderful round.
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!
You created a new account to just write a comment and now you telling that you don't afraid of down votes?
That is exactly why I am not afraid
Is Div2B is same as the problem here with a different granny story? #Justasking.
no, I don't think so
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'.
F was so hard to me....
The problems are interesting as well as the pictures in Tutorial except problem D:(
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!! ;>
Did you just assume that everyone has a girlfriend? Maybe he wants to see his crush?
I can hear the pain from that comment
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
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.
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
Can you explain what skipped verdict means?
https://codeforces.net/blog/entry/13611?#comment-185398
Thanks
Could someone please tell why this fails for D?
https://codeforces.net/contest/1358/submission/81573541
Can div 2 c be solved using dynamic programming
No, DP is too slow for this problem cuz $$$(1≤x1≤x2≤10^9)$$$ $$$(1≤y1≤y2≤10^9)$$$
Try to find formule. It can be solved with easy formule
I did see your love to Сoronavirus. Seems you are really happy to play with 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.
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? 出题人就是个傻逼。出题人给爷爬。你自己不感染很狂？
Is this the REAL NaCly_Fish???
I don't think it's him(
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.
So none of us knows his exact CF account？
I do, at least I once do... It was unrated, with a image of Honkai Impact 3...
No,it's i not l
Yeah, probably not.
actually certainly not.
出题人 May I inquire after your family
Респект, парни!
deleted
Can anyone check why my code for problem D doesn't work? I used the idea from the editorial and for every small given test it works but when it comes to those where n=200 000 it fails. My code: https://ideone.com/rLE5jx.
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.
May I ask what racism you saw in the pictures?
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?
Overgeneralization itself is a crime.
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.
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.
"coronavirus"
AHAHAHAHHAHAHAHAHA
what a joke
agree?
Plz repeat your question to doctors and nurses who are still on their position of fighting this goddamned virus. What a joke to them.
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.
I don't think racism should be the exact word... Though it was unproper.
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.
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).
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.
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?