Hello, Codeforces!

I am very glad to invite you to the Codeforces Round #672 (Div. 2), which will take place in Sep/24/2020 17:35 (Moscow time). **This round will be rated for the participants with rating lower than 2100**.

All tasks were made by me, but gepardo helped me a lot with the last two tasks, probably these tasks wouldn't have appeared if he didn't help me.

My thanks to:

antontrygubO_o for coordinating this round. With this great coordination only good tasks remained in the contest.

gepardo made a lot, there wouldn't have been this contest if he didn't help me. He not only helped me with making last two tasks, but also helped me to understand how to make tasks for Codeforces rounds. Thanks!

EIK this is the person who teached me competitive programming — my Informatics teacher. Thanks!

programmer228, Hacktafly, K1ppy inspired me to make this round, listened for the every task idea, provided feedback and testing. Thanks!

Osama_Alkhodairy, vamaddur, thenymphsofdelphi, Devil, Ari, SleepyShashwat, TechNite, 1-gon, Tech.Maniac, Kavit_Kheni for testing the round and the tasks. Thanks!

MikeMirzayanov for Codeforces and Polygon platforms. Thanks!

You for participating in this round. Thanks!

**You will have 2 hours for solving 5 tasks, one of which will be divided into easy and hard verions.** I hope you will enjoy the round, I tried to make ~~short statements and strong pretests~~ interesting tasks.

Score distribution: ** 500 — 1000 — (1000 + 1250) — 2000 — 3000 **

**UPD**: The editorial is available. ~~English version will be ready after the system testing is over.~~

**UPD2**: The english version of the editorial is ready.

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.

![ ]()

.

1-gon 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 1-gon 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 1-gon 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. :(

SpoilerSpoilerSpoilerr/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. 1-gon , 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.

1-gon Love the way you ask for upvotes. One upvote for you from my side. LOL

How is 1-gon ?

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

1-gon,Seems like you will achieve those in this comment section itself, congrats.

Who is errichto???

look in the top contributors table , you will know

Are you from the future?

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.

You can do DIV-2/3 if you're comfortable.. It will not put pressure on you as it would be unrated for you.

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

You missed- "Make good memes and post in the comment section"

## include<bits/stdc++.h>

using namespace std; typedef long long ll;

int main(){ int t; cin>>t; while(t--){ ll n, count = 0, limit; cin>>n; ll a[n]; bool flag = true;

} Its the 1st sum: why did this kept exceeding pretest 2

This is quadratic, the constraints can go upto 10^5.

Yes. I just figured it out. What's the solution to it?

An array can take atmost n*(n-1)/2 swaps to sort and that worst case is when the array is strictly decreasing.

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

No Adhoc/Constructive unfortunately :'(

Legend says 1-gon 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

2020after 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 roundare 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!!!

1-gon 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)

I will get rating in this round.

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 1-gon Comment Here Or Has Mono Gone??!!

Are the problem statements clear? They can be long provided they are clear.

i

wish,it Will be Clear:)I'll do you one better: Why is 1-gon?

Is Mono gone?

Who is monogon?

A codeforce user, and sometimes a problems setter, and sometimes a problems tester.

Greetings 1-gon

Hello Sir.

Hello, sir!!11!

What a rare sight, Monogon being downvoted

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

asisdeo

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

hello,MikeMirzayanov..plz..help me..i forgot to register in this contest..please..enable me to join the contest!.or anyone help me..(its bigger than ocean..)..plz..give me a chance..

or..Wind_Eagle..

I still don't know who, or what

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

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

https://medium.com/@harryjobz/pok%C3%A9mon-army-3f4348d57143

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

maximasandminimasin 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

me too lol. spent so much time

And here I am! Applied bubble sort logic and was counting the number of swaps. I'm so dumb!!!! Received TLE.

well the number of inversions required will be maximum when the array is sorted in decreasing order and all elements are distinct and it will be equal to : n*(n-1)/2. Since we are given 1 operation less then this count so answer will be no only when all elements are distinct and sorted in decreasing order.

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

It was bubble sort, and in worst case number of swaps are (n*(n-1))/2. So we just need to check if it was the worst case of bubble sort i.e strictly decreasing array.

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

The merge sort part in your code is something which looks close to actual code, the rest looks like some cryptic code written to burn someone's eyes. No offense.

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

Really Nice problems.

tnx:)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)`

for`n <= 10^9`

for problem D, I did it with`C(n, r)`

for`n <= 10^6`

.I did the exact same. Can you please tell why it's giving TLE on test 11? Thanks

Your

`ncr_mod`

function 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

Really, Enjoyed the contest! Thanks to all the testers and problem setters who made such a fantastic contest. You guys are legends. Love you all.. :)

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

prabhAmbrose then go and read novels if you like stories

Usually, you guys say that you don't like stories now you are liking his comment just because he is yellow

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.

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

Problem C1 solution explanation

https://youtu.be/skRw0pSNwS4

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!

Nice problems.

can someone explain me whats wrong with my code? 93695276 Its giving WA in pretest 6

In the best case scenario you always choose an odd number of Pokemon so sometimes your code will needlessly subtract the last element I think.

are you sure your code is ignoring even index (in reference to the subsequence) value if that is situated at last index?

yes,I think so..my friend wrote similar code.only difference was I wrote a[n]=a[n-1]-1; and he wrote a[n]=0;

I think I solved B 30 seconds after the contest so unlucky...

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 have`x & y >= x ^ y`

(because in the`xor`

operation, this most significant bit is destroyed, while in the`and`

operation it is preserved).deleted

It is because of the log function, you will get wrong answers when you will do log of bigger values.

Issue was integer overflow not that log function.

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

But we still have to use the brute force approach with a nested loop right ? Please help me since I've got 2 TLEs in a row.

store the highest bit in a map or something. Then for each unique value k of highest bit add (k choose 2) to the total.

Definitely no need for sorting as it will disturb the order of calculation of answer in the first place..just calculate the position of highest set bit in all numbers and notice the following :

AND of 2 number will be greater or equal then XOR iff the position of highest set bit in a[i] and a[j] are the same, else XOR will always be greater.

Store these positions of highest bits of all numbers in an array and iterate to find all such indices which are equal. Can use a map for it.

I think you can solve it with brute force I am not sure because I optimized it 20 seconds before the contest ended but what you need to use is this to optimize it. https://www.geeksforgeeks.org/sum-product-pairs-array-elements/ I am not 100% sure my approach is correct as I can't submit now but I got TLE and not WA before the optimization.

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

newbietohappy newbiexDxDxDC 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

Anyone explain in problem A why there are 0 exchanges for values 2,1?

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

Problem C1 solution explanation

https://youtu.be/skRw0pSNwS4

Can anyone explain why in problem A there are 0 exchanges for values 2,1?

using formula in A max exchnages allowed = (n * (n − 1)) / 2 − 1 for n = 2 , max exchanges allowed = 0

Thanks I misunderstood question

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

is it DIV 2 or DIV 1 ? please reply !!

div 1

contest was good ... although keep it up Wind_Eagle

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.

Update: solved..

Sorry, I commented Twice

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

Problem similar to C1 was already on internet.Check this Wind_Eagle .

https://tkramesh.wordpress.com/2009/10/08/maximum-alternating-sum-subsequence/

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.