### Medeowex's blog

By Medeowex, 8 months ago,  Tutorial of Codeforces Round #619 (Div. 2)  Comments (95)
 » LOL, my solution for E in $O(n^3+qn)$ passed. Although, I know how to make it $n^3+q$.
•  » » I think authors didn't want to cut off solutions with such complexity.
•  » » » Authors solution seems to be a lot faster. Mine works in nearly 1.9 sec, which is very tight.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   I wrote this approach (which works in O(n*(nm + q))) and it works about 1076 ms on the worst test-case.
•  » » » Looks like it is impossible to distinguish between log n log m, which is approximately 100, and n / 2, which is 250.BTW the math markup appears to be broken, as a line break is added everywhere after using it.
•  » » » » It makes sense but they could make q equal to 2e6.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   Do you know solution with such comlexity O(min(n,m)*nm + q)?
•  » » » » » Yes, I wrote it in my first comment.
•  » » » » » » Can you explain it please?
•  » » » » » » » Well basically I reduce the problem into $O(n^2)$ arrays of length $n$ and then use some imple of RMQ. Stupid one is $O(n)$ per query, but (we all know) it can be solved in $O(n)$ precount and $O(1)$ per query using the method of four Russians.
•  » » » » » » » » I'm sorry, but I still couldn't understand your algorithm. Would you mind elaborating it or posting your submit?
•  » » » » » » » » » At first I precount a cubic dp[i][j][len] — best ans for a square len * len at position (i,j). Now when a query comes we need to check $O(n)$ squares to find the optimal answer. That's where I use RMQ (so it can be implemented in many ways). You can read more about best RMQ algorithms on wiki.Submission is here 70999212.
•  » » » » » » » » » I'm sorry, I mean the algorithm with the time complexity of O(n^3+q), which you have mentioned previously.
•  » » » » » » » » » I suppose you can go here RMQ solution and follow Farach-Colton and Bender algorithm link.
•  » » 8 months ago, # ^ | ← Rev. 2 →   Because I haven't learnt 2D sparse table,I tried to solve the problem in $O(n^3+nmlog^2n+qlog^3n)$.But it seemed to be failed... In this problem, $O(log^3n)$is much slower than $O(n)$...
•  » » » The problem is $log^{3}n$ is actually a lot more than $n$. Does anybody know what's wrong with math parsing?
•  » » » » Yeah,you are right,so I have to rewrite my code now...
•  » » Why I got TLE in O(n^3 + qn)??
•  » » » The TL is very tight, you must write optimal code to pass.
•  » » can you tell me proof that the required element for problem number 2 is always the average of the lowest number and the highest number in the array? Thanks in Advance
•  » » » Formal proof: for any two numbers $a$ and $b$ we need to minimize $max(|a-x|,|b-x|)$. This happens when those functions intersect which occurs in $(a+b)/2$.
 » 8 months ago, # | ← Rev. 2 →   Typo in C, should be $\dfrac{n\cdot(n+1)}{2} - \dfrac{k\cdot(k+1)}{2}\cdot g - (k+1)\cdot(z\mod g)$
•  » » You're right, sorry I will fix it.
•  » » » In the editorial of problem C, it's mentioned that (k+1) zeroes are given to (z mod g) groups and the remaining groups are given k zeroes.That means the number of substrings which need to be subtracted from the total $= \dfrac{k\cdot(k+1)}{2}\cdot(g-(z \mod g))+\dfrac{(k+1)\cdot(k+2)}{2}\cdot(z \mod g)$ $= \dfrac{(k+1)}{2}[(k\cdot g-k\cdot(z \mod g))+(k+2)\cdot(z \mod g)]$ $= \dfrac{(k+1)}{2}[(k\cdot g-k\cdot(z \mod g))+k\cdot(z \mod g)+2\cdot(z \mod g)]$ $= \dfrac{(k+1)}{2}[(k\cdot g+2\cdot(z \mod g)]$ $= \dfrac{k\cdot(k+1)}{2}\cdot g+(k+1)\cdot(z \mod g)$Despite being written in the explanation about the count of substrings having 'L' zeroes, the final equation was directly written.But nevertheless the editorial is very well written.
•  » » » » Can You please explain, why are we assigning (k+1) zeroes to first z mod g group?
•  » » » » » See we that there are total z zeroes in the string and we want to equally divide it into the string in sets of continuous substrings of zeroes so that the substrings removed from the total possible substrings of the complete binary number get reduced.So, z zeroes need to be divided into g groups. $\left\lfloor{\dfrac{z}{g}}\right\rfloor=k$Let $r=z \mod g$So, $z=kg+r$Now if (g-(z mod g)) groups are assigned k zeroes and (z mod g) groups are assigned (k+1) zeroes, then total should come as z (as it's the total number of zeroes present). $k\cdot (g-(z \mod g))+(k+1)\cdot (z \mod g)$ $= kg-k\cdot(z \mod g)+k\cdot(z \mod g)+(z \mod g)$ $= kg+(z \mod g)$ $= kg+r$ $= z$Thus, (g-(z mod g)) groups are assigned k zeroes and (z mod g) groups are assigned (k+1) zeroes. Now we simply apply the formula of possible substrings when we have a string of length L as mentioned in the tutorial.It is not necessary that you assign the (k+1) zeroes to the first (z mod g) groups only. You can assign (k+1) zeroes to any of the (z mod g) groups out of the g groups available.
•  » » » » » » Yeah now understood completely Thanks alot!!
•  » » » » thanks i was also unclear about (k+1)*(zmodg)
•  » » » 8 months ago, # ^ | ← Rev. 2 →   In the D problem, the contraints for the number of steps is too weak (1<=a<=3000) when all the paths can be traversed in just 1500 steps only (even mentioned in the editorial as 3n steps).Medeowex, I really have to admit the round as a whole was very well written along with the tutorials to the problems. Despite being a little tough round and getting a dip on my ratings, I have to say, I loved upsolving the questions of this round. Learned new concepts, especially from the E problem.
 » 8 months ago, # | ← Rev. 2 →   Medeowex Thank u for this Editorial But i thnik you mean "at most" instead of "at least" in the last problem tutorial !
•  » » Can you point where in the problem statement that "at most" is? I missed it.
•  » » » I mean here in the tutorial of F " you may use an edge that goes from a cell to another one with the same color at least once"
•  » » » » Yes, I understand. But I cannot find that in the problem statement. So, I do not understand why this sentence is there.I think the problem statement says we can use edges between cells of same color as many times as usefull, no limit at all. Not at least, not at most.Can you explain?
•  » » » » » 8 months ago, # ^ | ← Rev. 3 →   As i understood , you don't have to use two edges or more and stay in the same color .. because if you at the cell x and go to y with the same color then go from y to z with the same color.. that is not optimal because u can go from x to z directly .. so that i say you may use "at most" one edge
•  » » » » » » Ahh, ok, makes sense. Use every color at most once.
•  » » » » » » » But what about going from color c1 to c1 then to c2 and then c2 again. Here we have used the "same-color type" edge twice!!
•  » » » » » » » » The path never used the same color twice, because it would be shorter using the color only once.
 » Problem F, how do we find a path where we have to use "tunnels" of more than one color, one after the other?
•  » » 8 months ago, # ^ | ← Rev. 3 →   We can do this during the BFS.We need to BFS for $k$ times and every time we calculate one color. Now we only consider one BFS which calculates color $a$.Let $d$$i$$s$$[$$i$$] the minimum cost from color a to cell i.During the BFS, when we reach cell u, whose color is b, we update all the cells in color b by d$$i$$s$$[$$u$$]$$+$$1$, because we can go to them from $u$ in one second.In this way, when finding pathes we can use "tunnels" of more than one color. Here's my code. 71045624
•  » » » I see. Since you have to do this for every pair of colors only once you use cvis[]. Thanks!
 » 8 months ago, # | ← Rev. 4 →   Nevermind, I messed up with author's solution
 » 8 months ago, # | ← Rev. 2 →   .
•  » » Imagine that you have a set of 1D points and need to find a point such that maximum distance between this point and any point in the set is minimised.This is exactly the same problem here. The point that will minimise that distance is the mid point.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   Edit:- Got it.
 » I don't understand why the solution works for problem B
•  » » Place all the determined numbers on an axis, and your mission now is to find a point where the maximum of the distance from that point to any other points is minimized. There are three conditions: on the left of the min, on the right of the max, and in between the min and the max. It's obvious that the first two conditions are not better than the third one, and in the third one You'll find out by intuition(apparently) that the mid point of the min and the max is the optimal choice. On top of that, you have to consider the determined numbers adjacent already, which have to be calculated, and is hinted in the sample.
•  » » » Nicely Explained!
•  » » » Thank you!!! I understood at once B as soon as read "Place all the determined numbers on an axis".
 » "The current mid is correct if the maximum element in that 2D range is greater than or equal to (4⋅mid⋅mid)". How does the existence of such an element guarantee that the answer >=4*mid*mid for the given submatrix ?
 » Can someone explain the binary search version of B?
•  » » I think in that way too but can't find its correctness. here my partial solution :- why have range of k from 0 to 10^9. for every mid we check if it is lower from both its adjacent elements if it is then thats may be answer(i think it might be local minima where there is a trick). if not then it may be either non increasing or non decreasing which is again a trick.I dont know whether binary search may work If someone have solved it or wanna add up in it please explain.
•  » » I would say it's rather a standard ternary search problem. It is easy to observe that k varies on a convex function,i.e there is a local minima which is our required answer. In each iteration, we check the function value at mid and mid+1 and accordingly reset our low and high till the while loop ends.
•  » » 8 months ago, # ^ | ← Rev. 2 →   The problem asks to find the smallest number of an absolute value function. If you plot an absolute value function (for eg. f(x) = |x|) on a graph, it's V shaped — both negative and positive values of x converge at a minima (in case of f(x) = |x|, that minima is 0). The goal is to find this minima.In the given problem, f(x) generates a similar graph — if mid is too large, then f(x) (which returns the max between mid and every element in the array) can be very large. Same thing when mid is too small (the absolute difference between max value and mid can be very large). You want to find the right middle ground.So, by comparing f(x) with f(x+1), you can get a sense of which direction to go: - If f(mid) <= f(mid+1), you want to go the direction of mid. Drop the second half of the array (mid+1 through high), and focus on low through mid - If f(mid) > f(mid+1), you want to go the direction of mid+1. Drop low through mid, and focus on mid+1 through high.So in a gist, keep comparing mid with mid+1, and go in the direction of the smaller value. Stop as soon as l>=h. (Reference: https://codeforces.com/contest/1301/submission/71083423)There's another approach (https://codeforces.com/contest/1301/submission/70970135) which seems to follow a similar concept though I'm not clear on the implementation details.
•  » » Actually, a ternary search may be more appropriate than a binary search here: https://cp-algorithms.com/num_methods/ternary_search.html
 » Thanks for the quick editorial <3
 » 8 months ago, # | ← Rev. 3 →   Let me show a solution for problem D with quite short code. 71031620Move like this: Pictrue Constuct the "ans" string to go through all the grids with 'R' 'U' 'L' 'D'. Cut out the first k characters of the string. Merge the consecutive characters as one step. The largest number of steps is 2996.
 » in problem B, why can't I just take all the non missing elements instead of taking only adjacent to missing elements?
•  » » because that will make the answer worse, consider the following testcase 1 4 100 -1 1000 1000 the answer is 450 550 if you take those adjacent elements. but if you take all non missing element then you answer will be 600 700.
•  » » » I got such test cases. Can you please expalin why adjacent numbers like 1 4 100 or 1000 1000 always make the answer worse ?
•  » » » » because the extra 1000 has nothing to do with the answer consider 1 -1 100 1000 -1 1000 10000 , in this case the only best thing you can do is to find a integer such that it will give minimum absolute difference with 1 & 1000. ' Why only 1 & 1000??? Because they are adjacent to -1 but now the question is , 100 is also adjacent to -1 why we are not considering it?? Because it is not contributing to the answer. As we have to minimise the absolute difference, only two integer(1 & 1000) are affecting the answer like if we choose k=500 as then (1000-500)=500 && (500-100)=400 && (500-1)=499; so you can see in absolute difference ,100 is not contributing to the answer, it will always come from MAX and MIN adjacent element.Similarly all the element which are not adjacent to the -1 are not affecting the answer coming from replacing the -1 with k. They have their constant absolute difference(which might be greater, but k has nothing to do with it).As in our case the answer will 9000 (10000-1000).
•  » » » » » got it..thanks
•  » » » » » Thanks a lot. Now I understood mistakes in my reasoning.
 » can anyone help me why this solution fails? https://codeforces.com/contest/1301/submission/71037252
 » 8 months ago, # | ← Rev. 4 →   @Medeowex by this line in problem C:-"we should give every group k zeroes, except for the first (zmodg) groups, we should give them k+1 zeroes." you mean there are infinite no of strings are made having maximum substrings since you placed (xmodg groups with k+1 zeros at starting remaining spaces? btw thanks for really good problems and contest!!
 » E can be solved in O(n^3 + q log n) without the use of data structures. Call a red point such that they are part of the center of a Nanosoft logo a "critical" point, and it's "range" half the maximum subsquare that can be a Nanosoft logo. Then we can run binary search on answer. In order to check if subrectangle (r1, c1) — (r2, c2) can contain a subsquare of size m such that it is a Nanosoft logo, the subrectangle (r1 + m — 1, c1 + m — 1) — (r2 — m + 1, c2 — m + 1) must contain a critical point with range m (and it's green, blue, yellow counterparts as well). In order to check this in O(1), we can use prefix sums, and since you need to calculate it for all values, it works in O(n^3). Here is my code: https://codeforces.com/contest/1301/submission/71003726.
•  » » Thanks for the hint. It's much easier.
 » Question of problem F "But visiting all other cells that has the same color every time is too slow, so we can only visit these cells when we reach the first cell from every color." what does that mean? How do you complete bfs while skipping grids with same color? I did not understand this part…
•  » » Read the code, then you can understand it.
 » Can anyone mathematically prove for problem B that the best k is equal to (minimum value + maximum value)/2 ? Thanks.
•  » » 8 months ago, # ^ | ← Rev. 3 →   Let us denote minimum value by min, maximum value by max. Let us assume that k is best at some point other than the average say t, this gives the cost to be maximum(abs(max — t), abs(min — t)). Case 1: t > average, cost = t — min > average — min >= average — min + 1 (since average can be 1 more from the right than left). Therefore the calculated cost is greater or equal to the cost when we choose k to be the average of minimum and maximum value. Similarly, we can show for the case when t < average. I hope that helps.
 » 8 months ago, # | ← Rev. 2 →   Cam someone please tell me why my binary search solution is getting timed outhttps://codeforces.com/contest/1301/submission/71014146
•  » » Got it. Never mind
 » Can someone explain to me how to solve 'B' by using Binary search??
•  » » Do a binary search with:low = smallest elementhigh = largest elementif both low and high remains -1 then answer will be 0 and any number can be treated as K.otherwise:find mid and calculate the maximum absolute value of the adjacent element with K as mid and do same for mid-1 and mid+1See the Solution to know about how low and high will change.
 » 8 months ago, # | ← Rev. 3 →   I am having problem in question C for k size string their will be k*(k+1)/2 substring but for k+1 size why the total substrings are k+1 ? UPD: i got it now
 » Hello,In Problem 1301B, why doesn't calculating the mean(average) of all the non-negative numbers adjacent to -1s, instead of (minimum value + maximum value) / 2, give the correct answer. Really stuck at this :) Thank you for the help.
•  » » Because you can consider ,Test_case: 1 -1 100 -1 101 So as per your logic k=67 so m=66 but if you do k=(max+min)/2 k=51 so m=50 I hope this helps!!!
 » I cannot seem to pass Test Case #2 for C...However, I don't know how to improve my code. Any help would be appreciated!!PyPy3: T = int(input()) for case in range(T): n, m = [int(x) for x in input().split()] g = m + 1 z = n - m k = int(z/g) A = n*(n + 1)/2 - (k*(k + 1)/2)*g - (k + 1)*(z % g) print (int(A)) 
•  » » It turns out that doing: n, m = [int(x) for x in input().split()] is too slow. Instead, this is better: from sys import stdin n, m = [int(x) for x in stdin.readline().split()] 
 » Why did no one ask about whether you can rotate the square in problem E to make it a valid logo...? I think this should be made a clarification for future virtual pariticipants.
 » can someone help why this code for problem B gets wa ??:( tnx in advance.this
 » The hard part of the proof in C is proving that it should be "as equal as possible". The author conveniently skips that.
•  » » Can you please explain me the proof for it
•  » » Yes can anyone give the proof for this?
•  » » » Well the hint to the proof is: you can see that for$f(x)=\frac{x\cdot(x+1)}{2}$and you have $x_1=t-d$ and $x_2=t+d$, $x_3=t$ and $x_4=t$,we have, $x_1+x_2=x_3+x_4$ and, $f(x_1)+f(x_2)>f(x_3)+f(x_4)$so, reducing the "distance" between variables always minimises the value of the function.
•  » » » » Thanks. Really appreciate your efforts
 » Why does this straightforward $O(n * m * k + q * k)$ solution fail for problem F https://codeforces.com/contest/1301/submission/72293018
 » B's second test's 369th testcase sucks
 » I have an alternate solution to E with time $O((nm+q)\sqrt{nm})$.A logo with radius $k$ has area $4k^2$, and logos can't overlap. So, there are at most $\frac{nm}{4k^2}$ logos with radius at least $k$.Because large rectangles are rare, we can check each of them with every query. And for smaller rectangles, we can build a DP table of size $n\times m\times k$ to quickly check for small logos in a subrectangle.Preprocessing takes $O(nmk)$ time and each query takes $O(k+\frac{nm}{k^2})$ time, which is optimal when $k=\sqrt{nm}$.
 » Hi, medeowex, somethings puzzled me in problem F: what's the "+1" for in "Otherwise you should find the best color that you will use that edge in it, the cost will be (the minimum cost between any cell of that color with first cell + the minimum cost between any cell of that color with the second cell + 1)."? don't we need to consider the possibility of jumping using multiple colors? As I see from your code, it seems it just use one color for jumping in the min solution.
 » In problem C can someone please explain me the proof for why the greedy strategy of dividing m+1 groups "as close as possible" works
»
5 months ago, # |
Rev. 2

Here my Binary Search approach for B, I check all the difference using binary search and choose the smallest one.

<spoiler summary="#include<bits/stdc++.h> using namespace std;

# define speed ios_base::sync_with_stdio(false); cin.tie(NULL)

int main() { speed; int t; cin>>t; while(t--) { ll n,l=0,h=INT_MAX,ans=0,diff; cin>>n; ll a[n]; ll m=-2; bool minus=true; for(ll i=0;i<n;i++){ cin>>a[i]; m=max(m,a[i]);

    if(a[i]!=-1)
minus=false;
}
h=m;
if(minus==true)
{
cout<<0<<" "<<0<<'\n';
continue;
}
while(l<=h)
{
ll m=l+(h-l)/2,rl=0,rr=INT_MAX,p,q;
bool possible=true;
for(int i=0;i<n;i++)
{
//cout<<a[i]<<" leftrange="<<rl<<" rightrange="<<rr<<'\n';
if(i<n-1&&a[i]==-1&&a[i+1]!=-1)
{
p=rl;
q=rr;
rl=max(a[i+1]-m,rl);
rr=min(a[i+1]+m,rr);
if(!(rl>=p&&rr<=q))
{
possible=false;
l=m+1;
break;
}
}
if(i>0&&a[i]==-1&&a[i-1]!=-1)
{
p=rl;
q=rr;
rl=max(a[i-1]-m,rl);
rr=min(a[i-1]+m,rr);
if(!(rl>=p&&rr<=q))
{
possible=false;
l=m+1;
break;
}
}

if(i<n-1&&a[i]!=-1&&a[i+1]!=-1)
{
if(m<abs(a[i]-a[i+1]))
{
possible=false;
l=m+1;
break;
}
}
}
if(possible)
{
ans=(rl+rr)/2;
h=m-1;
}
}
for(int i=0;i<n;i++)
{
if(a[i]==-1)
{
a[i]=ans;
}
}
diff=-1;
for(int i=0;i<n-1;i++)
{
//cout<<a[i]<<'\n';
diff=max(diff,abs(a[i]-a[i+1]));
}

if(ans>=0&&ans<=m)
cout<<diff<<" "<<ans<<'\n';
}
return 0;
`

}"> ...

 » My Pattern for D: From [1,1] go Right to [1,n] Go down to [2,n] Go left to [2,1] Go down to [3,1] Again Go right to [3,n]... i.e. keep repeating steps 1,2,3,4 till possible i.e. until you reach [n,n] Made bool right to handle odd/even length of n. Now we are either at [n,n] if n is odd, or at [n,1] if n is even If we are [i,1] we go UDR until we reach [i,n] then we go Up then goto step 9. If we are [i,n] we go UDL until we reach [i,1] then we go Up and goto step 8. Keep Repeating steps 8 and 9 until you reach [1,n] and make the final call to go only L to [1,1]. I agree the Editorial's approach is a bit simplier.Also, I was unable to fix an upper bound to as how many number of steps were required, so I simply checked the Max. Case 500 500 998000 and submitted. I'm not sure though. I think constraints for 'a' could be tightened.Anyways, Great Problemset !
 » why are we dividing z into m+1 groups?
 » Nice and Useful Contest