Thanks for the participation!

1379A - Acacius and String was authored by ch_egor, meshanya and prepared by ch_egor, vintage_Vlad_Makeev

1379B - Dubious Cyrpto was authored by jury and prepared by DebNatkh

1379C - Choosing flowers was authored and prepared by grphil

1379D - New Passenger Trams was authored by Helen Andreeva and prepared by KiKoS

1379E - Inverse Genealogy was authored and prepared by voidmax and I_love_myself

1379F2 - Chess Strikes Back (hard version) was authored by 300iq and prepared by isaf27

Tutorial is loading...

**vintage_Vlad_Makeev code**

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Thank you for the fast editorial.

Video Editorial of Problem C: Choosing Flowers

made me understood clearly, thanks for the tutorial. namanbansal013

Very helpful, highly appreciated!!

I have tried to make editorial for questions A-D . please have a look. Language :- Hindi

https://www.youtube.com/watch?v=Omy25cs6JY8&list=PLrT256hfFv5UiRIzkAk6iSHwpwJrJKGMz

pretest 2 was a nightmare. but anyway thanks for the fast editorial

I used binary search for B.

Here's my submission: 87322797

I basically fixed my lower bound and upper bound to M+(R-L) and M+(L-R). Let them be up and lo respectively. Now, we need some values of A.N such that the inequality lo <= A.N <= up is satisfied. As we know that a lies in the range L-R and that some value of N for some value of A always exists, for every value of A I used binary search to find for every A if some value of N exists.

Explain pls!

Here's my submission: 87322797

I basically fixed my lower bound and upper bound to M+(R-L) and M+(L-R). Let them be up and lo respectively.

Now, we need some values of A.N such that the inequality lo <= A.N <= up is satisfied. As we know that a lies in the range L-R and that some value of N for some value of A always exists, for every value of A I used binary search to find for every A if some value of N exists.

Can someone point out the flaw in my code? 87334189

Try input: 11 aba?a?acaba

My video Solution For Problem A And Problem B. Hope you like it

Difficulties are not seems like it is div2. Thanks for the fast editorial

If you are still getting WA in A, this is an edge case you probably missed.

Output: No

I still got WA even after managing this test case :/

Can u send ur code? I gonna take a look

Yes, Please if you can any give any test case . https://ideone.com/juBi2V

You probably getting wrong answer for these two test cases.

2 13 abacab?bacaba

11 abac?bacaba

NO NO

Look at this test, your code gives

`NO`

, but answer isThis contest was a Nightmare for me.

My approach in C was almost the same as the editorial's approach.

If anyone wants to check the implementation, check out my submission 87337116. :)

Questions are quite interesting after many contest.

Please make others submission visible.

UPDthey are visible now.Were these problems supposed to be solved by 5-8 grade students?

"Wrong answer on pretest 2" The contest summarized in 5 words

Was it Div 1???

Fastest editorial, system testing and least submissions.. records been broken here.Thanks to iynaur87 for the key update! :-)

Least submissions.

Very similar problem to F has appeared on the 2019 Canadian Mathematical Olympiad before, you can check it out here.

Edit: you can check the solution to that problem here.

Funny coincidence! I haven't seen this problem. I was inspired by the problem "Grid Guardian" from the GP of America, where you had to count the generalized version of grids from my problem.

Plz,tell my mistake for A Code: 87298100

Consider this case

1

15

abac?bacabac?ba

Your output has two occurrences of "abacaba"

my approach to C:

find the maximum element among a[] and b[], if one of the maximum is a[i] then decrease n by 1, add a[i] to the answer, and change a[i] to b[i].

if not, then iterate over all sort and find out the maximum a[i]+(n-1)*b[i].

however this approach is getting WA on pretest 4, can anyone tell me why?

thanks in advance qwq

Update: found hack test case.We need to check each b[], and for each b[i], choose all better a[j], and only the remaining number of that b[i].

So it is more brute force than greedy.

Yeah I understand the correct solution.

yet I racked my brain and can't figure out why mine is incorrect, so I want to get some sort of countercase or how to construct one

Extra fast tutorial

Extra level question(Difficulty similar to div1)

Extra ranks(3K rank after doing just 1 question)

Hope extra rating :)

For D, it is also very helpful, that an optimal starting time can always be selected, so that either the trains departure or arrival, coincides with some existing freight train.

Therefore, we can just check all those 2n possibilities, and obtain quite an easy solution, as then we just have to get the number of freight trains in 2 ranges.

Many of them solved C using Convex Hull Trick. Is it a standard problem?

Yes, it is a nice trick to solve such problems!

Link to a gooood blog on "Convex Hull Trick": CF Blog

This is optimization for dp. In my opinion the solution in this case is much easier.

Could you please provide any solution link using convex hull. I was unable to recognize it.

Here

It could be more balanced, if removed D, shift ABC to BCD and paste easy A.

By the way, problems are insanely amazing!!

This contest is too damn hard for Div.2. Aren't you Shaco?

Can F1 be solved with maximum bipartite matching and binary search?

I thought of it too, but couldn't reach up to a solution.

Here's my approach for B:

We know that we need an $$$a$$$ such that $$$(m+x)/a=n$$$ where $$$n$$$ is any positive number and $$$x$$$ is just any number in between $$$r-l$$$ and $$$-(r-l)$$$. Now fix $$$a$$$ by looping from $$$l$$$ to $$$r$$$. Then $$$x$$$ will have 2 possibilities computed by using the modulo operator as follow:

Where $md1$ is the number that must be subtracted from $$$m$$$ for the module to be zero and $$$md2$$$ is the number that must be added to $$$m$$$ for the modulo to be zero.

Now $$$b = l+md1$$$ and $$$c = l$$$ if and only if $$$md1 \leq r-l$$$ and $$$m-md1 \neq 0$$$

Or, $$$b = l$$$ and $$$c = l+md2$$$ if and only if $$$md2 \leq r-l$$$

Else, continue iterating on $$$a$$$

can you explain, why two possibilities of x ? md1 and md2 ? can u elaborate this part ?

As I said in the post, $$$m \mod a$$$ is essentially just the number you need to subtract from $$$m$$$ in order for $$$m$$$ to be divisible by $$$a$$$ so if that value is less then $$$r-l$$$ you can always choose $$$b$$$ and $$$c$$$ such that $$$b-c$$$ is your $$$md1$$$.

But sometimes you need to add to $$$m$$$ rather then subtract from $$$m$$$ and thus the number to try here would be $$$a-md1$$$ and do the same as above.

I hope it's more clear :)

E: Submission with idea: https://codeforces.com/contest/1379/submission/87346264

It would have been better if the contest was of 2:30 hrs.

Problems were very nice! B was easier than A and A was definitely very tricky unlike usual A. Took me more than 30 minutes! I wonder if the partication was less due to unusual timing or difficult problems. C finally looked like as a usual C from the past (hard).

I had a bit different solutions for B and D.

For B, I tried all possible values of a, and then let $$$d = b - c$$$ , $$$z = m \ mod \ a$$$

Then $$$na + d = m \Leftrightarrow \ n = \frac{m - d}{a} \Leftrightarrow d = ka + z$$$

I checked only $$$k = 0$$$ and $$$k = -1$$$ to make shure that $$$n > 0$$$

Code

For D, lets solve problem for $$$ m \leq 10^5$$$. For fixed $$$t$$$ all segments where no freight trains are allowed to depart and should be canceled are in segments $$$[t - k + 1 + i\frac{m}{2}; t - 1 + i\frac{m}{2} ]$$$ for some $$$i$$$. Lets create array $$$a$$$ and add 1 to time when some freight train departs. Then answer is $$$t$$$ whith minimum sum of segment $$$[t - k + 1 ; t - 1]$$$. Let $$$d_i$$$ — time when i-s train departs. Now, lets check not all t from $$$0$$$ to $$$\frac{m}{2}$$$, but only $$$d_i + 1, d_i-1, d_i+k, d_i-k$$$ for all $$$i$$$. Instead of counting sum we can count number of trains in segment with upper_bound.

Why is it correct? I thought, if we can find better answer for another t, we can move this segment to the left or to the right and answer won`t change until we hit some train. So, this solution is also $$$O(n \log n)$$$

Code

Can somebody please explain B ?? Not able to understand what to do after fixing some arbitrary value of a.

Check this https://codeforces.com/blog/entry/80216?#comment-665003

I am unable to understand the solution for Problem c. Can anyone explain it?

Hi!

Let's consider both arrays sorted in non-increasing order(greatest element first).

The main idea is that we can take only one-type of an element of

type-bat max ( why? because if you can take the current element of b why go for an element-b that has a lower value). (think).Now, let's

iterate over all b'sfrom start and see what is the max value we can take with them!How to do that? Let's say the current

`b[i]`

is`bi`

, (note that array b and is sorted)It's understandable that we should take all the a's that are greater than this

`bi`

( think). So we first calculate all the a's that are greater than`bi`

. let's say the count isxand the total sum they provide isvalNow, if

`ai`

(the type-a for our current`bi`

) is not in thatx, we'd have no choice but to take it if we want to use current`bi`

.Hence we have two cases:

ai >= bi(means ai is in those x) :`ans = (n - x)*bi + val`

, because it's better to take x elements that have value greater than bi.ai < bi(means ai is not in x) :`ans = (n-x-1)*bi + val + ai`

, because we'd have to take our ai if we want to use bi.Also, note that if we have

x >= nit's just dumb to take any bi (think).So, all we need to do is iterate over all b and take max amount we can take.

Here's my submission : 87331654

Thanks!

Wow Sir, Very elegant approach.

@Dsxv @Sol1 Can you help me with a test case which can point out what is wrong in my approach?

My approach: Take the max b[i] (lets call it maxB), add all a[j] >= maxB to the val. Then go through all a[i] and if a[i] is already included, then update ans = max(ans, val+(n-x)*b[i]) else ans = max(ans, (n-x-1)b[i]+a[i]+val).

Difference is that I think maxB will always give optimal result (which is wrong). Can anyone please give a hack test for this?

test case :Test Case:

1

6 2

98 86

50 92

Better explanation than the official tutorial. Thanks!

@Dsxv, bro I tried to code what you explained in your post but I am getting a WA at TC5. I have been trying to debug it since last night but was unsuccessful to get my code AC. Please, go through my code and let me know where am I going wrong.

link to my solution: https://codeforces.com/contest/1379/submission/87395143

Your help and time would be much appreciated.

Hi! Sorry for the delayed reply

It's happening when,

`m-n-1`

hasvalue < 0.Here's your AC submission: 87406888

Thanks!

Thank You for the help, bro. I was not expecting any reply since as a sports programmer everyone of us has lot of problems of ourselves that needs to be debugged, but you talking out time to actually debug someone else's code was very generous.

Keep on doing this great job, wish you high rating!!

P.S: We all know how irritating it is to not get an AC even after brainstorming the logic.

Hi.I am having a confusion if ai<bi(the largest b). Eg:- 7 4 1 5 If n=4, first element is seven.Now considering remaining three elements. According to you we will select 1 5 5 (sum is 11).But, if we take 4 4 4 (sum is 12).So, in this case we should not take the largest b. Am I doing something wrong? Please explain. Thanks!

Not really! I will check my answer for

everybi. Hence when I'll reach`bi = 4`

I'd have already visited my`ai = 7`

and that is the only value greater than me! so my answer would be bi*(n-1) + pref, where pref = 7. If I misinterpreted your doubt, feel free to ask again! Thanks!I did this for just largest value of b and calculated the max sort sum for remaining values.This is failing on Test Case 2. I got your approach which is the correct one but how this one is failing?

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

using namespace std; vector<pair<long long ,long long> > v; vector v1; bool comp1(long long a,long long b) { if(a>b) return true; return false; }

bool comp(pair<long long,long long> p1,pair<long long,long long> p2) { if(p1.first>p2.first and p1.first>p2.second) return true;

} int main() { int t; long long a,b,n,m;

} Thanks!

I'm sorry but I am not here to debug codes! If there's anything wrong with logic feel free to ask.

Also, use some links while sharing code :p

hey, i dont think ur logic will hold...... in case 2 where ai<bi,what if n=x+1,would u still go for ai,or would u choose any b[i],from already chosen a[i]'s

I'd leave this case upon your imagination! (note that you can choose to take no bi)

Approach to problem D: squeeze all m_i to a circle of length m/2. For all points with coordinate p in the circle, (p, p + k) represent locus of points where t cannot be 'inside' it. Then, the problem is equivalent to removing minimum number of points on that circle such that there'll exist two consecutive points of distance at least k. To find it, we can keep track of # (say ins[] )points inside (p,p+k) for all p using pointers (87364059). Then, we can take the point p with minimum ins and delete all point inside (p,p+k). However, I couldn't pass it. Can you find mistakes in this approach?

Can someone help me understand where my code is giving wrong answer.Thanks in advance https://codeforces.com/contest/1379/submission/87357034

Problem A and B has same difficulty rating but problem B has far more points than A. Even(for me) B seems easier than A...Is it fair? Would get more (+) if started with B... :(

Can someone share in what topic/concept question C belong? I want to practice more such problems, but I am unable to get where exactly does this belong.

P.S: Contest time should have been 2:30 mins.

Can anyone tell me what's wrong with this submission? Implements the same idea as the editorial but gets WA on test 5;(

Did anyone else waste time trying to solve problem A in O(n)? :|

In case the count of 'abacaba' was 0 (>=2 or 1 are easy cases) I did the following:

Created a list of starting indexes of occurrences of

possible'abacaba'.Then I iterated over the list, realizing the that a problem can occur only in the following: If the next possible starting index is +4 or +6, and after the current occurrence there is 'caba' or 'bacaba' respectively.

For example, 'abac???caba' is a problem, and 'abacab?bacaba' is a problem. These are the only types of problems, if this doesn't happen, you've found your starting index.

In the meantime the solution was to just plug the substring and count the number of occurrences :<

There are a lot of grammatical errors in the tutorial.

Can anyone check this code for me , I get WA on test case 179 in pre test 2 :< ( Problem A )

If you get num == 1 after the first iteration answer will be "YES". It should not depend on "codinh"

Why was the time limit for problem F so tight? My $$$\log^2$$$ solution wasn't able to fit in the 2s time limit (but should pass given 3s).

Our bad, none of us wrote a solution with 2d tree. All our AC solutions use 1d tree which work $$$\leq$$$ 0.4 s

We can also solve D by dynamic segtrees .. its very much intutive (just like brute force) that way.

dynamic segtrees can always be used in problems where sweepline works.

I made a greedy strategy for

Problem Cbut it's giving the wrong answer but I can't figure out where it's going wrong.I find the pair with max Bi (if there are multiple Bi's with max value) than I select the one with highest Ai. Now we have 1 Ai and n — 1 Bi. Next for every Ai greater than my chosen Bi, I replace that one Bi with Ai. This should be optimal, apparently, it's not. Can anyone help me out here? I know this explanation is messed up and hence I am sharing the link to my unsuccessful submission, hope you'll get an idea.

https://codeforces.com/contest/1379/submission/87394947

Max Bi isn't always optimal:

One of the most difficult division 2 contest I ever participated. even the first problem was of 1500 rating.

A seriously awesome contest after a long time. This one Makes you learn the importance of time where a single question require high implementation and multiple concepts.

I am getting wrong answer in test case 5 in problem C. Can Someone please tell me where i am wrong? Submission

You do not handle the case where n is smaller than m. With such input the binary search can return an index bigger than n, and then your formulars are not correct because they calculate with some negative flower count.

Thanks :)

I had a different solution 87485483 in 1379A - Acacius and String. Since the length of n and the length of "abacaba" is small. I bruteforced all possible variations of "abacaba" with '?'. Then I try all possible places those variations can occur and check if it create another "abacaba".

It is better to write "In the form of $$$2^n-1$$$" than "almost a power of two".

I have tried to make editorial for questions A-D . please have a look. Language :- Hindi

programming Language :- C++ https://www.youtube.com/watch?v=Omy25cs6JY8&list=PLrT256hfFv5UiRIzkAk6iSHwpwJrJKGMz

For problem A, I first check if there is only one or more abacaba , if one make the string and return , else return no.

after That I try for every position to test if I can make abacaba, if I do , I check the propagation . so let's say we are in pos i, and we made abacaba, what I can see is that the propagation might start from a or aba, or aba at the end, or a in the last character. so I check forward and backward , if the propagation does not make another abacaba, I make the new string and output it,

here is my submission : https://codeforces.com/contest/1379/submission/189264603 , can anyone help me find why my approach is not correct? :)