Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### ch_egor's blog

By ch_egor, 3 years 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 (94)
| Write comment?
 » 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 :- Hindihttps://www.youtube.com/watch?v=Omy25cs6JY8&list=PLrT256hfFv5UiRIzkAk6iSHwpwJrJKGMz
 » 3 years ago, # | ← Rev. 3 →   pretest 2 was a nightmare. but anyway thanks for the fast editorial
 » 3 years 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 years 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 years ago, # ^ | ← Rev. 3 →   Try input: 11 aba?a?acaba
 » 3 years 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 years ago, # ^ | ← Rev. 2 →   You probably getting wrong answer for these two test cases.2 13 abacab?bacaba11 abac?bacabaNO NO
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   1 19 abac???cabaz??????? Look at this test, your code gives NO, but answer is YES abaczzzcabazabacaba 
 » 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 years 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?
 » "Wrong answer on pretest 2" The contest summarized in 5 words
 » Was it Div 1???
 » 3 years ago, # | ← Rev. 2 →   Fastest editorial, system testing and least submissions.. records been broken here.Thanks to iynaur87 for the key update! :-)
•  » » Least submissions.
 » 3 years 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 years 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 years ago, # | ← Rev. 2 →   Plz,tell my mistake for A Code: 87298100
•  » » 3 years ago, # ^ | ← Rev. 2 →   Consider this case115abac?bacabac?baYour output has two occurrences of "abacaba"
 » 3 years 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 years 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 years 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.
•  » » »
 » 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 years 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 years 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
 » 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).
 » 3 years 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
 » 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?
•  » » 3 years 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 years ago, # ^ | ← Rev. 2 →   Wow Sir, Very elegant approach.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   @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 :1 2 3 9 1 9 1 1 10 
•  » » » » 3 years 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 years 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
 » 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 years 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"
 » 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 years 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.
•  » » dynamic segtrees can always be used in problems where sweepline works.
 » 3 years 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 `
 » 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 :- Hindiprogramming 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? :)