Привет, Codeforces!
Я очень рад пригласить вас на Codeforces Round #672 (Div. 2), который пройдет в 24.09.2020 17:35 (Московское время). Этот раунд будет рейтинговым для участников, чей рейтинг ниже 2100.
Все задачи придумал я, но с двумя последними задачами очень помог gepardo, без него этих задач могло бы и не быть.
Мои благодарности:
antontrygubO_o за координацию раунда. Именно благодаря такой отличной координации в соревновании остались только хорошие задачи. Спасибо!
gepardo сделал много чего, без него этого соревнования просто не было бы! Он не только помог с двумя последними задачами, но и помогал мне разбираться, как правильно делать задачи на Codeforces. Спасибо!
EIK это тот человек, без которого я бы вообще не попал в спортивное программирование — мой учитель информатики. Спасибо!
programmer228, Hacktafly, K1ppy вдохновили меня на создание раунда, выслушивали идеи на каждую задачу и высказывали свое мнение, а также тестировали раунд. Спасибо!
Тестировали задачи и предоставляли свой бесценный фидбек Osama_Alkhodairy, vamaddur, thenymphsofdelphi, Devil, Ari, SleepyShashwat, TechNite, Monogon, Tech.Maniac, Kavit_Kheni. Спасибо!
MikeMirzayanov за платформы Codeforces и Polygon. Спасибо!
Вы, за то, что участвуете в этом раунде. Спасибо!
У вас будет 2 часа на решение 5 задач, одна из которых разделена на простую и сложную версии. Надеюсь вам понравится раунд, я очень старался сделать короткие условия и сильные претесты интересные задачи.
Разбалловка по задачам: 500 — 1000 — (1000 + 1250) — 2000 — 3000
UPD: Готов разбор.
UPD2: Разбор теперь можно читать и на английском.
As a tester, ask me anything.
What's the solution to the last problem?
I would tell you if I knew how to solve it :sob:
Now this seems entirely believable, it wasn't easy at all
Hi Monogon, How come you are getting downvotes?
I don't know, I thought my formula for getting upvotes was foolproof. To become top contributor, maybe I'll just make another contest instead.
Are you sure you can become the real top contributor by just making another contest?
Hmm, it might take 2 contests.
Errichto laughing in the corner.
)
.
Monogon Please consider me as one of the tester in your next round. Hopefully would be able to see your next round soon.
How so orz?
I just memorized some stuff that's enough to solve puzzles.
I think this one comes from Um_nik's blog.
Must be a notorious coincidence.
is this like the ecnerwala blog but in contest blog?
Not at all. In ecnerwala's blog, you get to ask someone who's actually good.
so do you mean you are not good? if so why should we ask you when we can ask ecnerwala?
I cannot say for sure whether you should ask me or ecnerwala, as it depends not only on the question you ask, but also on what you seek to gain from asking. If you ask ecnerwala, he may give a thoughtful reply. But such a reply might also come very late or never seeing that his AMA was posted some time ago. On the other hand, my replies are likely to be stupid, repeated jokes, but you will get them immediately.
Whenever I see Monogon in the list of testers, I immediately visit the comments section for his quick wit. The comments section, in general, is great fun. Or maybe it's the lockdown that's rendered me so aimless.
Its more fun when either Monogon or vovuh are among round contributors.
How to become tester???!!!!
Click
I guess it was a joke.
Oh wow. Didn't knew it was a joke. I wanted to help him become a tester once. :(
r/woooosh
It's very simple. Just pick a random user from the "top rated" or "top contributors" box to the right, and send them a direct message asking to be a tester. They are all making contests right now, so they'll immediately let you see the upcoming problems and pay you to test them. Hope this helps!
they pay you to test or you pay them to test?
It depends on how well you do. Testing is no different than a game of blackjack.
You guys are getting paid?
why you are asking me? ive never been tester
I'm pretty sure Errichto isn't making any rated contest for cf right now.
don't they judge me ??? I want to know what qualification need to be a tester?
How was the testing?
Testing was good. I found that one problem had appeared before and so it was replaced. But then because it was replaced, I dropped in the standings, and other testers assumed I was even dumber than I really was.
As a tester. You cannot participate in this round. Is this guaranteed by technical means or is it consciously? Do you know all the problems? Or only the parts?
Yes, I know all the problems, and I'm not allowed to participate in the contest. I don't think there's anything in the system preventing testers from actually registering for the contest and submitting solutions, but obviously it would get caught by Mike Mirzayanov's omnipresence.
MR. Monogon , Why 5 problem in most of the recent contests ?
This is a better question to ask coordinators. It could be a false pattern in random data.
How is Monogon ?
I'm doing ok. What about you?
Just started now need to explore the things !
What is the probability of solution getting accepted after passing of pretests in total.
Hope it is not like previous contest. I know your pain brother.. :(
I've tried my best to make pretests strong enough. Hope it will be so.
Thanks champ
Given the large number of users, there have to be very few pretests on early problems to prevent a long queue. This is pretty limiting, even if each test has many test cases. So, it's very hard to write good pretests. Despite this, I think on average we're in a much better place than a few years ago.
As a tester, how much contribution do you want ?
Errichto + 1
Monogon,Seems like you will achieve those in this comment section itself, congrats.
Who is errichto???
Done.
how to get +195 contribution?
Just set 2 contests solo, 1 contest on a team, write a tutorial, and hijack the comment section of all rounds you test as your personal upvote farm.
Your genius, it generates gravity. Really loved(and upvoted) every comment. errichto should have participated too.
Why does Errichto has two youtube channels?
So he can say he has double the subscribers.
Why don't you have a youtube channel?
I've considered it. But I'm afraid doing screencasts will put pressure on me, and will negatively impact my performance. Especially if I provide commentary. Other content such as video tutorials is actually very time-consuming, and I don't think I could explain things better than existing resources for most topics. I admire those who do make videos and try to grow the competitive programming community because I understand it's a lot of work. Personally, I find problemsetting a better way for me to give to the community.
Why does problem C have more point in total than problem D?
To anger and confuse you.
When are you becoming red ?
Soon
This aged well
well played.. you should have told you true intentions lol XD
Where is/are Mifafavov, is there some bigger conspiracy we are not aware of?
If it's a conspiracy then I'm not a part of it. Although I suppose I'd say that even if I was in the conspiracy...
how to get contribution??
It's a known fact.
Thanks luctivud
off-topic, how to be a tester for some round?
This was a genuine question but whatever...
Genuine question asked on almost every other contest announcement blog. Again and again.
Well, I suppose I should've searched before posting here.
Usually you can connect with the coordinators or the author and they can allow you to test and discuss , mostly its yellows and reds because of their greater experience and knowledge they can find issues / judge difficulty better. Hope that helps :)
I love rounds coordinated by antontrygubO_o.
Ad-hoc and Constructive algorithm missiles incoming!!
First of all, I'm not talking about the nature of the problems. Sometimes I like ad-hoc and constructive problems, and sometimes I don't.
What I like and he delivers — short statement, strong pretests, normal readable English, coherent sentences (unlike the last round), understandable and unambiguous statements.
I enjoy reading the clear statements in his rounds, and I never feel ripped off after the contest. I think that's a good enough reason to like his rounds...
Legend says Monogon will reply to every comment on this blog
Well it would be kind of rude not to answer questions in my own AMA, wouldn't it?
If you don't mind, what is the full form of "AMA"? Thanks!
"Ask Monogon Anything"
Thanks for enlightening me!
Is the apocalypse near? Why is Monogon getting downvotes?
Duh! It's 2020 after all.
Hope there will be short statements and strong pretests .
After a series of thanks by WIND_EAGLE,thanks from the contestants who will witness a positive rating change
Interesting that most of testers for the Div2 round are orange or higher.
Long statements is Boring :(
Наконец-то меня упоминули
Whenever I see the short statements and strong presets statement, I instantaneously imagine that I will be losing rating in this contest but then again most of the contest I take part in become unrated ://.
We hope there will be interesting tasks with strong pretests.
bro, what happend? why all coders dislike your comment!!!
Monogon has earned a total of 652 upvotes in this blog alone where the blog post is sitting at 414. (Also, you might think how free am I to do count such dumb shit. Guess what, you are right)
Interesting to see the total score of problem C greater than that of problem D ! I wonder how many times has this happened before ?
Best of luck everyone and hope u positive rating change
Will Monogon Comment Here Or Has Mono Gone??!!
Is Mono gone?
Who is monogon?
A codeforce user, and sometimes a problems setter, and sometimes a problems tester.
Greetings Monogon
Hello Sir.
Hello, sir!!11!
it's really amazing how he tried to appreciate every one..!!
After seeing the long lists of upcoming contests...
I think that this round will be amazing
But I won't take part in it :(
It's toooooooooo late for me :(
Ohh, it's really sad.I hope that virtual solve help you
Adhoc shit incoming
I hope that queue of testing solutions is not long on this round
That's what we need to hope for, not short statements
I am not sure why this happened last time but the pretests were way too short as compared to other recent cf rounds. Quite a few failed system tests. Hope it is not the case this time around. :(
i really started to love the comment section lol
Best Of Luck to everybody for the round
I still don't know who, or what Nibel is.
Nibel is a forest where Ori lives.
Is the plot based on Ori and the Will of the Wisps? I had played Ori 1 and didn't recognize things in the statement
nice problems btw
No, the statement is based on Ori and the Blind Forest.
Sorry I'm just dumb. I never played the game in English and never remembered the names of those things.
Well, I understand you, I've never played this game in English too :)
hey,can you please give me a chance to register..i forgot..and solved problem A 1 hour ago(maybe much)..
The contest is over now.
.
The last submission which passed pretests is considered, the others are ignored.
.
As a participant, I declare that this round was great.
Thank you!
when you spend an hour debugging code because u forgot to set mod inverse factorial of 0 to 1 :(
The contest is still ongoing.
when you spend an hour first trying to fit python solution into the constraints and getting +4 rejected and then giving up and rewriting it in c++
Dude, what is wrong with you ? why are you posting such things during contest ? MikeMirzayanov
Nice Round! What's the solution for D?
Just sorting ends of the intervals and then a bit of combinatorics
Come on, answer the question or ignore it. But do not act like a dick.
Come on. I did answer it. Without giving details, but nevertheless.
That "answer" did not help at all. You just did tell that is was easy for you.
I'm pretty sure that knowing that you need to put ends of the intervals in the array and then use combinatorics is quite a huge hint
nice round .. thank you how to solve C2 ?
reconsider (check for peak or bottom) only adjacent elements of swapped ones. (and the swapped elements too of course)
Answer is sum of max(a[i] — a[i + 1], 0) (a[0] = 0). Change in answer can be calculated in O(1).
Can you pls explain the reasoning behind this? Thanks!
If we take two numbers, first number should be larger than second. So if there is some decreasing sequence $$$a_1, a_2, a_3, ..., a_k$$$, value of $$$a_1$$$ — $$$a_k$$$ is same as $$$(a_1 - a_2) + (a_3 - a_4) + (a_i - a_{i+1})$$$. So we will always add two numbers(add zero to end of array a answer doesn't change).
Seems like I massively overkilled but my solution would work for any changes, not just swaps:
Keep a segment tree where each node store the maximum value of a sequence with the following properties: (starting with pos, ending with neg), (starting with pos, ending with pos), (starting with neg, ending with pos), (starting with neg, ending with neg)
The merge is trivial to do in O(1).
Using the observation that as long as numbers are distinct, the contribution of $$$i$$$th term to the final answer depends only on $$$a_{i - 1}, a_i, a_{i + 1}$$$, you can arbitrarily update any index trivially in $$$O(1)$$$.
Since only minima's and maxima's contribute to the final solution. The contribution of $$$i$$$'th term is $$$a_i$$$ if it's maxima (i.e, $$$a_i > a_{i- 1}, a_{i + 1}$$$), and $$$-a_i$$$ if it's minima ($$$a_i < a_{i - 1}, a_{i + 1}$$$).
Now to update some index $$$i$$$, delete from answer the contribution of $$$i - 1, i, i + 1$$$'th term, update $$$i$$$th term, and add the contributions of $$$i - 1, i, i + 1$$$.
As a participant, I declare that this round was nice
As non-monogon, you might get downvoted!
Hint for C2?
If a[i] is greater than a[i-1] and a[i+1], add a[i] to the answer. If a[i] is less than a[i-1] and a[i+1], subtract a[i] from the answer. And let a[0]=a[n+1]=0. Change the contribution of up to 6 positions per exchange. Complexity: O(n).
Solution of D: https://www.geeksforgeeks.org/number-of-ways-to-choose-k-intersecting-line-segments-on-x-axis/
I tried to do the same approach but got WA. here is my submission https://codeforces.com/contest/1420/submission/93713635 . Can you tell me what went wrong?
Edit: Got AC.
THe gfg soln is wrong, you have to add value to the total.
Time limit on C2 was too tight. I wrote up a Segment Tree and got TLE on pretest 6...
No, I also wrote a segment tree, got AC in 1.2s, it's 16*N only.
Actually it's 8*N since you can reduce the size of the tree to 2*N with a well known trick. Still, my seg tree implementation must be bad, because I still got TLE. Very sad :(
The same, wrote a solution with sets O(QlogN) and got TLE.
How did you use a segment tree to solve that?
Can someone give a hint for C2?
Wait for editorial, it will appear very soon.
Keep track of maximas and minimas in an array, and see how answer can easily be computed only from the sums and indices of maximas and minimas.
Problem D: https://www.geeksforgeeks.org/number-of-ways-to-choose-k-intersecting-line-segments-on-x-axis/
Most common mistake made in those 3500 failed submissions of problem D in this round %9982444353.
I solved A using mergesort lol how did u count inversions so easily ? isn't it counting inversions ?
Total number of swap needed for sorting a strictly decreasing array are $$$n * (n - 1) / 2$$$. That means if the array is not strictly decreasing answer is YES, else NO.
OMG I'm so stupid
When listening to your college teacher actually pays off lol..
{ a1 > a2 > a3 > a4 > ... > an } is the only case that you need to make exactly n*(n-1)/2 operations
You don't need inversions, you have to check if atleast one pair i < j with a[i] <= a[j], you can just store minimum
You write so unreadable code man :(
if you mean mergesort code I didn't write it just copied it from some site I don't even how it's working
By the way you can also solve it (count inversions) using a segment tree
My favorite room is the one with 3 * 10^5 lamps
Can anyone please tell how to calculate binomial coefficient C(n,r)%Prime when n<=10^9 ? (or n<=10^18 maybe)!
(Please don't give Links of blogs. I went through many of them during the contest. Please provide a link to the Code)
Also, can anyone please tell why my solution for Problem D gave TLE on Test-11 (Gave me PTSD)? Thanks.
I don't think you need
C(n, r)forn <= 10^9for problem D, I did it withC(n, r)forn <= 10^6.I did the exact same. Can you please tell why it's giving TLE on test 11? Thanks
Your
ncr_modfunction looks too slow (seems to be O(n+r))`my go-to fast nCr is https://github.com/cheran-senthil/PyRival/blob/f1cdbdd6257dfae86d64dc80a027c015583d79cf/pyrival/combinatorics/nCr_mod.py
Specify the modulo or range of 'r'. If r <= 10^6, we can do it or if modulo is <= 10^6 we can still do it, else I don't think it is possible.
Precompute all factorials and their inverses under N then O(1) multiply for each query
not sure about 1e9
I solved C2 with a segment tree to maintain the product of matrices.
It feels so dumb to write such a monster to solve a d2C.
Can you please explain the basic idea? I can't think of a way to merge nodes, support updates, and queries.
Sorry for the late reply.
First we redefine the multiplication of matricies. Here $$$C_{i,j} = \max { A_{i,k} + B_{k,j} }$$$.
Consider the dp solution of C1: $$$f_{i,0} = \max ( f_{i-1,0}, f_{i-1,1} + a_i) , f_{i,1} = \max ( f_{i-1,1}, f_{i-1,0} - a_i)$$$. It can be represented as a matrix multiplication. We have
\times
\quad \begin{bmatrix} 0 & a_i \\ -a_i & 0 \end{bmatrix} \quad
=
\quad \begin{bmatrix} f_{i,0} & f_{i,1} \end{bmatrix} \quad
$$$
You can use a segment tree to maintain the product of the matricies. Check my submission for better understanding
for problem D, Time Complexity of my Python 3 solution is O(NlogN) but still getting TLE.
can anybody help. link of My solution
You don't seem to use any recursion in your code, it should work with pypy (without all the setrecursionlimit, threading etc code)
I don't think there is any need for recursion. here is my solution in pypy which was also getting TLE.
How to solve E?
If we fix number of zeros between adjacent ones (let's denote it as $$$g_i$$$), then answer is sum of $$$g_i$$$ * (sum $$$g_j$$$ where $$$j$$$ < $$$i$$$). So now this can be easily calculated with dp[i][last][moves], each transition is O(N), overall complexity is O(N^5), but there is a lot of unreachable states so it should pass.
Yes, my solution was something about n^5/27.
what the hell is that quotations in starting of each question??
Can someone tell me what wrong in my code? 93694586
The problems were great but for heavens sake you didn't have to set such tight constraints for D
Really annoying when solution with the correct asymptotic does not fit into constraints just because it is written in the wrong language and/or lacks some microoptimisations
I understand that there are plenty c++ lovers here, but still, don't do it. It is div2 after all
I implemented counting the overlapping intervals. That needs to sort an array of size N*2 which should be possible in all languages. The other loop is then O(n).
That's the same thing I did
Except that just sorting 3*10^5 tuples in pypy can take nearly a second. Much faster in cpython though.
Note that even your c++ solution with all io-tricks takes half a second.
10^5 would be enough to cut off ineffective c++ solutions
problems were nice but is it too hard for problem setters to understand that we don't want any lame story along with the problems.
Why? The stories were short and nice :)
Atleast I agree with Wind_Eagle, they were actually nice and short :)
adding the stories is something that gives happiness to the problem setters. If one doesn't know the game the story doesn't feel awesome(maybe lame) but just bear with it for the setters.
Please,for the problemD. How to get (Cmn mod M) when m is big
Precalc factorials up to $$$n$$$, precalc inverse factorials by modulo $$$m$$$ up to $$$n$$$ too. Because $$$\frac{a}{b} \mod m = a * b^{-1} \mod m$$$, as $$$m$$$ is prime you can use Fermat theorem and so $$$a^{-1} = a^{m - 2} \mod m$$$. Then you can easily calculate $$$nCr = fact[n] * invfact[n - r] * invfact[r] \mod m$$$
Hi, I tried to use segment tree to maintain maximum and minimum for alternating sequence with odd and even length for C1 and C2, it passes the sample test but failed on pretest 2? Could someone have a look and help me figure out what is wrong? Tks a lot!
My Submission
I used a similar recursive implementation and got TLE on pretest 5. I'll try this blog when I get time. BTW I used your CP templates to make mine, thanks for putting it on Github!
about long long. Is it okay to use long long everytime, because I forget sometimes when to use it, and today, I wasted my time thinking my logic to B is wrong.
Problem D How to get (Cmn mod M) when m is big
this
Thanks!
can someone explain me whats wrong with my code? 93695276 Its giving WA in pretest 6
are you sure your code is ignoring even index (in reference to the subsequence) value if that is situated at last index?
Since when do segment trees belong in task A of a div2 contest? lmao
why do you need to sort the array in problem B?
not needed
You don't need to sort the array. To see if
x & y >= x ^ y, just look at the most significant bit of each number. Only if these two numbers have the same most significant bit, then we havex & y >= x ^ y(because in thexoroperation, this most significant bit is destroyed, while in theandoperation it is preserved).Realy like it. Waiting for your next contest.
What are your guys' approaches to solve B ? I'm really curious since the only one I can think of is using brute force.
Hint:-
$$$a[i]$$$ $$$and$$$ $$$a[j]$$$ $$$>=$$$ $$$a[i]$$$ $$$xor$$$ $$$a[j]$$$ if highest bit set in a[i] and a[j] are same
Consider two numbers a and b. If both of them have highest bit on the same position, then a&b > a^b. Otherwise a&b < a^b. The rest should be easy (if not, i can explain).
I took a time to think this (especially to use long long instead of int). see the numbers as its binary form. now AND of 2 numbers will be one always less than or equal to the minimum of the two. XOR of 2 numbers can be more or less than any of the two. sol- count all the numbers whose highest precedence bit is set and those bit are in the respective positions of the array. do this for all the positions from 0 to 33, and add the number of ways you can choose 2 numbers at ith(higest precedence) postion as set. (pos[i]C2) my sol
Note that the answer depends only on higest precedence bit
Can someone please tell me what was the solution to A. I'm new and this was my 2nd contest. I applied bubble sort logic and counted the number of swaps but got TLE on pretest 2.
I used merge sort just coz I had a prepared file for finding inversions ... it works but there must be so much easier ways as well
The total number of swaps needed for sorting a strictly decreasing array is n∗(n−1)/2. That means if the array is not strictly decreasing answer is YES, else NO.
-- by some guy whose name was in blue..
Actually the intuition of inversion count actually makes sense, but the worst case of such is when the array is in strictly decreasing manner. This case takes the no of swaps = (n * (n — 1)) / 2 and hence if the array is in any other manner it will take less than this much swaps which is the intended limit given to us. So if the array is strictly decreasing we need more than the given limit of swaps and answer is no else yes. Hope this helps and wwelcome to cf community :)
Thanks for explaining so nicely.
.
5 6
the expected answer to this is 0 but ur solution gives 1. it s one of many special cases where "If the number of bits of 2 integers are same, it's a valid pair" isn't correct.
I solved my first official dp problem ever but struggled with A and B... so basically my rating just raised from newbie to happy newbie xDxDxD
C was nice observation based : ans = sum(max(0,a[i] — a[i+1])), where a[N+1] = 0
D was standard problem if you know the range overlap relation, ie,
max(L1,L2,L3.....LK) <= min(R1,R2,R3,R4....Rk) So fix Li, as max of all L's for a set of choices of K intervals, then if M intervals overlap with such an Li, then add to the answer:
ncr(M,k) — ncr(M-D,k) , where D is the number of intervals with left boundry = Li
I am just wondering if the C2 is more difficult than D.
I completed D very fast but still has less idea for C2.
When I came to the task C, I thought that it will be good task D. But I had current task D which could not be a task C. So I decided to make C1 and C2.
Alright,I am thinking about a solution based on dp and never think that:
This conclusion is not difficult to prove but I'm always think abount dp dp dp dp dp.
I am still have a lot to improve
QAQ
Can you prove why the above solution works? I too spent a lot of time coming up with dp solution but failed and submitted the wrong greedy.
If your dp[i][0/1] means that the previous number to the i-th number is subtracted(0) or added(1),You will have a simple equation:
Notice that dp will be add only if $a[i] > a[i-1]$. Also dp will add a[i] — a[i — 1]
so this is why that solution works.
Should've put C1 -> D -> C2 if possible LOL
maybe
Did anyone solve E using flows?
Please, let me know your solution with flows, I am very interested!
Actually I misinterpreted the question and allowed all 1 positions to move by a single step in one chance. So for each chance I made a layer of nodes corresponding to the gaps between 1s, and connected the final layer with the sink, with edges with cost (i-1) for each flow so that they add upto (gap*(gap-1)/2). Applying MinCostMaxFlow will give the answer. Without the restriction of a single move in a chance we can easily add edges between the layers but I am unable to figure out how to impose this restriction.
I like this kind of game with strong pretests. For problem D, enumerate the ending points of all values, and then count the number of new values $$$a$$$ each time, and the number of values that are still ending before $$$b$$$. The added contribution of the answer is: COMB(a + b, k) — COMB(b, k).
I like this kind of contest with strong pretests. For problem D, enumerate the ending points of all values, and then count the number of new values $$$a$$$ each time, and the number of values that are still ending before $$$b$$$. The added contribution of the answer is: COMB(a + b, k) — COMB(b, k).
Can anyone prove why this solution for C1 is correct?
He took local maximas for addition in the sum and local minimas for the subtrating values. This would always greedily prove best for u
You too have solved like this. I'm not getting why this will give an optimal answer.
Check the editorial, the solution for C2 uses exactly this idea.
Sorry problem setter, but you ruined the nostalgia by keeping pokemon trainer's name Andrew and not Ash.
One of my testers is Andrew :)
It went well. Very cool contest
Can anyone tell me where I did wrong with the solution for D? https://codeforces.com/contest/1420/submission/93711225
can anybody tell me why it is important to use long long in problem B ? (as I wasted 3 submissions before getting it correct D: ).
If all numbers are same and n = 1e5 then the answer (n * (n — 1)) / 2 will overflow int.
I want to say that problem C1 is not new. Check this
In this problem you need to choose a segment, not a subsequence.
Sorry, my bad
can you explain the difference?
Segment is something like [2,3,4,5,6], all elements are neighboring, subsequence is something like [2,3,5,7,10].
Good to see the editorial has the hint part.
Can we solve C2 with some dp and breaking array into $$$sqrt(n)$$$ part ??
and then find this values for each part with dp:
maximum sum if we start with a negative and end with a positive
maximum sum if we start with a positive and end with a positive
maximum sum if we start with a negative and end with a negative
maximum sum if we start with a positive and end with a negative
and then we need another dp to calculate the final answer witch can be done in $$$O(sqrt(n))$$$
each time we just need to recalculate dp values for 2 part(the ones witch the L and R are inside them)
i tried the above solution and i know that the time complexity is really bad( $$$O((n + q) sqrt(n))$$$ and got TLE on test 5 with long long and WA on test 5 with int because of overflow)
i just want to know if my solution gives the correct answer or not(i don't care about the time, just want to know if the algorithm is correct or not) ??
EDIT: i submitted my code witch got TLE on pretest 5 with GNU C++17 (64) and got AC :( the time complexity isn't so bad :)
Well my solution is kinda similar, just with segment tree 93668816.
thanks
The best thing about this contest was the stories were short!! Hope this stays for a longer run
Thanks a lot for preparing for this contests.Although problems are a little easy.
Couldnt even solve A!!
I can understand it, task A was a little bit difficult for task A.
Greedy solution for problem C1:
Iterate from left to right.
Find decreasing segments. (a[i] > a[i+1] > a[i+2] > ... > a[j])
Take first and last number of the segments. (a[i] — a[j])
Sum up every segments.
i know that A can be done in less than 5 line of code easily but the harder solution can be done in n log n with just a search in google
the same thing with c1, just a google search
other problems were nice, but its not good to see problems witch their solution is "just google things" in a CF contest :)
If there were 36 pretests in problem D and my solution 93708784 passed all the pretests, how can I get TLE on test 17 during system testing?
If your solution tightly fits into the time limit, it might happen that it worked a little longer on system tests and got TLE.
Such strict time limit that O(nlogn) solution did not fit.
The intended solution is also $$$O(n\log n)$$$ and fits into time limits twice on Java. But those sets and maps significantly show down your solution, while you may use only sorting.
Just added another map for storing calculated inverse mod values and it worked 93729552.
why did u add quotes in problem statements???? dumbest contest ever......
I like these quotes :)
so u just put them in a contest???? where is the logic broooo...
Well, the logic is that quotes can be just skipped if you don't want to read them.
how do we know they are useless without reading them??? you have to realize these are not your personal notes, we had a clock on our head, and do u really think this is some sort of smart or funny move? because I clearly can't see the point of putting them in the contest!!
editorial by tourist.
When you overkill problem A with Merge Sort and Counting Inversions!
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Wind_Eagle MikeMirzayanov I got TLE on test 9 in system testing and after that I submitted same code and I got accepted verdict.
I request you to look into this situation and do the needful.
Please review my code
TLE Solution- https://codeforces.com/contest/1420/submission/93705280
Accepted Solution — https://codeforces.com/contest/1420/submission/93728093
I guess it is the reason for the higher load of the evaluation machine during system testing? Because your program running time is already close to the time limit. I don't know if it can be rejudged, the author must have this permission. It depends on whether he is willing to help you.
Timer on Codeforces is not so precise, it has some inaccuracy.
Well, it happens sometimes. I don't know is this enough reason to rejudge solutions in contests. I cannot take a decision in this situation.
So, Who can take this decision? Because this is not my fault. Problem Setter can make question with Time 3s instead of 2s for avoiding such situations. Or another option is to reduce N which can be 10^5 or 2*10^5
Well, if i'd made the TL 3 seconds, somebody who had TL might pass the task with 2998 ms after the system tests. He would say that I should make 4 seconds e.t.c.
Who can take this decision? Only MikeMirzayanov I think :)
If I were the only one then I won't say anything. but many people got accepted verdict with this close margin. you can see that here with accepted filter on C2 question https://codeforces.com/contest/1420/status/page/55?order=BY_CONSUMED_TIME_ASC
and more and more people are getting TLE on this problem.
e.g. https://codeforces.com/contest/1420/submission/93659360 Can you explain me how TLE for this solution?
Yes, I can explain. Participant made an obvious mistake: he forgot to write ios_base::sync_with_stdio(false); cin.tie(0);
You cannot read and write in one time without this commands; otherwise you will have TL.
He could read all the data and write the answers only after this, maybe it wouldn't get TL then.
If someone implemented the code efficiently enough to fit in the time limit, he/she should not be able to get WA on both pretests/system tests. However, for inefficient codes, the author cannot complain whether the judging system judged AC or TLE. Sure, it is unfair that if both of people with same codes got constrasting results(in this case: AC and TLE), but it is not the thing that author can complain, because the time can vary with status of server, which is uncontrollable. Moreover, you had chance to know that your code's processing time on your submission logs, which would be very close to the time limit. You first should have looked over the code what makes the processing time so long.
I don't understand what people expect posting such examples every contest
I'm especially surprised to see it from a candidate master.
Obviously execution time of the program slightly changes on different runs. That's completely normal
Program that has a borderline performance obviously may pass and may not pass by a mere chance
It would be one thing if one of your solutions passed with 1s and the other TLEd with 2s
But 1996ms. Are you fckg serious?
check out this solution of c2 93676743
can anyone explain why my code got wrong answer at test case 44. although i done same thing as mentioned in editorial.
here is code :-93742154 Thanks for help!!
Problem D : can anyone explain why my code got wrong answer for test case 44, although i have done the same thing mentioned in editorial.
submission : 93742154 Thanks for Help
fmap[cnt]=cnt; //WHY? WITHOUT this it will get AC
Thanks for help i get it what you want to say
Good Round! I like it.
All the questions are interesting!
In general what is the reason for the rating changes to be rolled back? Also when do they get fixed?
Click here
When is the rating returned? Why did it take so long to remove the cheaters? In the past, it did not take more than one hour!
I just received a message from System: Your solution 93688303 for the problem 1420C2 - Армия покемонов (сложная версия) significantly coincides with solutions 93698667. I have no idea how this match happened. I have coded this myself and haven't shared it with anyone / anywhere online. Our solutions indeed match a lot, but it's mostly because variables we used (a, l, r) was defined in problem statement itself. The best evidence I can put for my defence is consistency in my coding style compared with other problems. For example I use lf instead of endl. Pinging admin MikeMirzayanov, coordinator antontrygubO_o and setter Wind_Eagle to please look into this matter.
There is one explanation for this case, which is that this person has another account and this other account is in your same room and closed the problem C2, then take your code and send it from this account!
But do not worry, only he will be disqualified from the contest.
Oh, I didn't think about that possibility. Thanks. But again, to close C2, he had to solve C2. If he solved C2, why would he send my code from another account? Also if he indeed copied from my code, I don't think he would code so similarly.
I am worried not for possible disqualification of me (I can gain / lose rating later), but because I am sensitive about accusation of cheating.
No one will accuse you of cheating because he is the one who sent your code after you, I think MikeMirzayanov should see this, Let's see how that person got your code!?
this was a smooth round. problems were good yet rating changes are taking like forever. any idea why?
The rating has been reset!
what is DDOS attack ?