### ch_egor's blog

By ch_egor, 4 weeks ago, translation, , 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 of Codeforces Round #657 (Div. 2)  Comments (134)
 » Thank you for the fast editorial.
•  » » Video Editorial of Problem C: Choosing Flowers
•  » » » made me understood clearly, thanks for the tutorial. namanbansal013
•  » » I have tried to make editorial for questions A-D . please have a look. Language :- Hindihttps://www.youtube.com/watch?v=Omy25cs6JY8&list=PLrT256hfFv5UiRIzkAk6iSHwpwJrJKGMz
 » 3 weeks ago, # | ← Rev. 3 →   pretest 2 was a nightmare. but anyway thanks for the fast editorial
•  » » Can Any Please One tell me what is the problem with the test case 42? 87356615
 » 3 weeks ago, # | ← Rev. 3 →   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!
•  » » » 3 weeks ago, # ^ | ← Rev. 4 →   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
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   Try input: 11 aba?a?acaba
 » 3 weeks ago, # | ← Rev. 2 →   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. 1 13 abacab?bacaba 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
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   You probably getting wrong answer for these two test cases.2 13 abacab?bacaba11 abac?bacabaNO NO
•  » » » » » » It still gives the the correct output..
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   1 19 abac???cabaz??????? Look at this test, your code gives NO, but answer is YES abaczzzcabazabacaba 
•  » » » » » » Thanks man. Yeah, I just figured it out.Tanks a lot!!
•  » » » » » » Even for the below case: 1 13 ab??a?ab??a?aCode gives N0, But the answer can be YES if abacababddada ??
•  » » ya this was my edge case thanks a lot now,i understood where i was wrong
•  » » figured it out minute after contest was over :(
 » 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.
 » 3 weeks ago, # | ← Rev. 2 →   Please make others submission visible.UPD they are visible now.
 » Were these problems supposed to be solved by 5-8 grade students?
•  » » Maybe they were practicing for very similar problems. but still, I agree with you, it seems odd.
 » "Wrong answer on pretest 2" The contest summarized in 5 words
 » Why does it say that the blog was made 3 days ago?
•  » » cause it was private!
 » Was it Div 1???
•  » » haha...mujhe bhi same feel aaya bro XD
 » 3 weeks ago, # | ← Rev. 2 →   Fastest editorial, system testing and least submissions.. records been broken here.Thanks to iynaur87 for the key update! :-)
•  » » Least submissions.
 » 3 weeks ago, # | ← Rev. 2 →   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.
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   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.
 » 3 weeks ago, # | ← Rev. 2 →   Plz,tell my mistake for A Code: 87298100
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   Consider this case115abac?bacabac?baYour output has two occurrences of "abacaba"
 » 3 weeks ago, # | ← Rev. 2 →   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 qwqUpdate: found hack test case. 1 2 3 100 1 100 1 1 101 
•  » » 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
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   I did the same and got WA on pretest 4 . Do not know why ! How did you debugged it ? Here is the code : https://codeforces.com/contest/1379/submission/87346998
•  » » » » » I also did the same but I am getting TLE on 4th pretest https://codeforces.com/contest/1379/submission/87445386
•  » » Thanks
 » 3 weeks ago, # | ← Rev. 2 →   Extra fast tutorialExtra 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?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   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.
•  » » »
•  » » » » Thanks
 » 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.
 » 3 weeks ago, # | ← Rev. 2 →   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: $md1 = m \mod a$ $md2 = a-md1$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 ?
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   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
•  » » Yeah thank you Ahmad45123 , it's clear now
 » HELP Someone please tell me what's wrong in my code of C . Failed on Test 4 . https://codeforces.com/contest/1379/submission/87346998
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   Update : Found my mistake. for input: 1 3 3 16 18 2 20 19 2 My code gives output = 52 , but the right answer will be 53.
•  » » » @naharis.daario hi I am getting the correct answer on above test case, however, my code is giving TLE on the 4th test case and I am able to figure it out.
 » 3 weeks ago, # | ← Rev. 2 →   Hi Guys, could somebody please help me to understand why this simple brute force solution for problem A gets WA on the 4th pretest? Thank you very much in advance!
•  » » Found my mistake, just in case someone is interested, here is my accepted solution.
 » It would have been better if the contest was of 2:30 hrs.
•  » » yes, however I would get "Wrong answer on pretest 2" for 30 more minutes :)
 » 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).
 » 3 weeks ago, # | ← Rev. 2 →   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$CodeFor 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 wont change until we hit some train. So, this solution is also $O(n \log n)$ Code
 » 3 weeks ago, # | ← Rev. 4 →   Can Any Please One tell me what is the problem with the test case 42 in Problem A? 87356615
 » Check out the detailed explanation of Problem A
 » Can somebody please explain B ?? Not able to understand what to do after fixing some arbitrary value of a.
•  » »
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   here is my solution of problem B with implementation click....
 » can someone help me whats wrong in my code CPP- problem B 87357784
 » I am unable to understand the solution for Problem c. Can anyone explain it?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   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-b at 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's from 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 is x and the total sum they provide is valNow, if ai (the type-a for our current bi) is not in that x, we'd have no choice but to take it if we want to use current bi.Hence we have two cases: If 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. If 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 >= n it'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 : 87331654Thanks!
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   Wow Sir, Very elegant approach.
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   @Dsxv @vjudge6 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 :1 2 3 9 1 9 1 1 10 
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   Test Case:16 298 8650 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/87395143Your help and time would be much appreciated.
•  » » » » Hi! Sorry for the delayed replyIt's happening when, m-n-1 has value < 0.Here's your AC submission: 87406888Thanks!
•  » » » » » 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
•  » » » » Not really! I will check my answer for every bi. 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;

if(p1.second>p2.first and p1.second>p2.second)
return true;
return false;


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

cin>>t;

while(t--)
{
cin>>n>>m;
v.clear();
for(int i=1;i<=m;i++)
{
cin>>a>>b;
v.push_back(make_pair(a,b));
}
sort(v.begin(),v.end(),comp);

long long c=0;
for(int i=0;i<v.size();i++)
c=max(c,v[i].second);

long long sum=0;
int pos=0;

for(int i=0;i<v.size();i++)
{
if(v[i].first>=c)
{
sum+=v[i].first;
pos=i;
}
}
n=n-(pos+1);

v1.clear();
for(int i=0;i<v.size();i++)
{
if(i<=pos)
v1.push_back(n*v[i].second);
else v1.push_back(v[i].first+(n-1)*v[i].second);
}
sort(v1.begin(),v1.end(),comp1);

sum+=v1;
cout<<sum<<endl;
}

return 0;


} 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
•  » » » » I'd leave this case upon your imagination! (note that you can choose to take no bi)
 » 3 weeks ago, # | ← Rev. 2 →   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
 » I think Div2 B has weak test cases, my solution got AC https://codeforces.com/contest/1379/submission/87373765, but it should be TLE at this simple test case: 1 1 4 10000000000 
 » 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.
 » 3 weeks ago, # | ← Rev. 2 →   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"
•  » » » thanks
•  » » Sir, you can check for this test case: 1 19 abac???cabaz??????? It prints out No, but the answer is possible: abaczzzcabazabacaba
•  » » » Thank you very much
 » 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).
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   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.
 » 3 weeks ago, # | ← Rev. 2 →   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.com/contest/1379/submission/87394947
•  » » Max Bi isn't always optimal: 1 2 2 1 10 7 8 
•  » » » thanks man.. I'll try again.
 » can someone explain editorial of problem, I am not getting it?
 » 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.
 » Why codeforces site is getting shrink every time i am opening it in google chrome? What's wrong with the site is happening I can't figure it out?
 » I usually use java to solve problems. So I was using Java to solve Problem B today and got TLE. This has never happened to me in codeforces before. Can anyone help me figure out what might causing the problem? Java : Solution(TLE) C++ : Solution(AC)
»
3 weeks ago, # |
Rev. 2

Explanation for problem B

m = n*a + (b-c) Let us say x = (b-c) Then it becomes m = n*a + x which is of the form, Dividened = Quotient * Divisor + remainder Then range of a, b, c is [l, r] So then range of x becomes [l-r, r-l] We need to observe that (m-x) % a should be equal to 0. Then only we can get a quotient n. So we iterate a from [l, r] We calculate mod = m % a.

## Case 1:

when we get mod i.e; (x as <=r-l) which is in the required range also the (m-x) != 0 because when it is zero, then n is 0 which is not we want. Then b = r and c = r — rem because x is b-c = rem <= r-l We can also have b as l + rem and c as l.

## Case 2:

Sometimes we get (m-x) as <= a or (m-x) == 0. in that case, we add a to make (m-x+a)>=a. Here (x-a) is obviously negative then only (m-(x-a)) >= a. We take (m-x+a) and we check whether our rem = (x — a) <= r-l If it is true, then our c>b, rem = (b-c) = (x-a) if b = l then c = l — x + a or if c = r then b is r + x — a

(c — b) = (a — x) < = (r-l)

 » 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".
 » can someone explain question no 1 ACACIUS AND STRING? string "a?b?c" can be transformed into strings "aabbc" and "azbzc", but can't be transformed into strings "aabc", "a?bbc" and "babbc". THIS LINE MAKE NO SENSE TO ME .it's fine for the first part but after that i can't make sense.. how those strings are not possible.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   "aabc" — not possible because one of the '?' was not converted to any alphabets. "a?bbc" — not possible because the in the output string all the '?' must be changed to an alphabet. "babbc" — not possible because we cannot change a character in the input string which not a '?'.
•  » » » thank you .
 » I'm both bad at English and Russian.Everytime I see the problem I need comoputer to help me. That's fun!
 » It is better to write "In the form of $2^n-1$" than "almost a power of two".
 » Can anyone point out my mistake in div2-C-"Choose Flowers" question. I have commented my code for better understanding.My code
 » 2 weeks ago, # | ← Rev. 3 →   https://codeforces.com/contest/1379/submission/87865452Can anyone tell me mistake in this code?(Problem A)
•  » » Hi, you can check for this test case: 1 19 abac???cabaz??????? It prints out: abacabacabazzzzzzzz, it has two occurrences of abacaba.But the answer could have been something like: abaczzzcabazabacaba`
 » 88386178 Can someone help me to find my mistake?
•  » » all good got it
 » I have tried to make editorial for questions A-D . please have a look. Language :- Hindiprogramming Language :- C++ https://www.youtube.com/watch?v=Omy25cs6JY8&list=PLrT256hfFv5UiRIzkAk6iSHwpwJrJKGMz