Thank you for the fast editorial.

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.

Can someone point out the flaw in my code? 87334189

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

Those who are still getting WA in A, this is the case you probably missed:

1
13
abacab?bacaba

Output: No

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

1
13
abacab?bacaba

Output: No

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

UPD they 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! :-)

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.

Plz,tell my mistake for A Code: 87298100

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.

1
2 3
100 1
100 1
1 101

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?

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?

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

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.

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

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

ok i got my mistake in question A. Acacius and String and sorry for previous comment... click this to check solution

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

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

I made a greedy strategy for Problem C but 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.me/contest/1379/submission/87394947

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

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