### Kilani's blog

By Kilani, 2 years ago,

• +48

 » 2 years ago, # |   +28 LOL, my solution for E in $O(n^3+qn)$ passed. Although, I know how to make it $n^3+q$.
•  » » 2 years ago, # ^ |   0 I think authors didn't want to cut off solutions with such complexity.
•  » » » 2 years ago, # ^ |   0 Authors solution seems to be a lot faster. Mine works in nearly 1.9 sec, which is very tight.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 I wrote this approach (which works in O(n*(nm + q))) and it works about 1076 ms on the worst test-case.
•  » » » 2 years ago, # ^ |   0 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.
•  » » » » 2 years ago, # ^ |   0 It makes sense but they could make q equal to 2e6.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Do you know solution with such comlexity O(min(n,m)*nm + q)?
•  » » » » » 2 years ago, # ^ |   0 Yes, I wrote it in my first comment.
•  » » » » » » 2 years ago, # ^ |   0 Can you explain it please?
•  » » » » » » » 2 years ago, # ^ |   0 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.
•  » » » » » » » » 2 years ago, # ^ |   0 I'm sorry, but I still couldn't understand your algorithm. Would you mind elaborating it or posting your submit?
•  » » » » » » » » » 2 years ago, # ^ |   +5 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.
•  » » » » » » » » » 2 years ago, # ^ |   0 I'm sorry, I mean the algorithm with the time complexity of O(n^3+q), which you have mentioned previously.
•  » » » » » » » » » 2 years ago, # ^ |   0 I suppose you can go here RMQ solution and follow Farach-Colton and Bender algorithm link.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 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)$...
•  » » » 2 years ago, # ^ |   0 The problem is $log^{3}n$ is actually a lot more than $n$. Does anybody know what's wrong with math parsing?
•  » » » » 2 years ago, # ^ |   0 Yeah,you are right,so I have to rewrite my code now...
•  » » 2 years ago, # ^ |   0 Why I got TLE in O(n^3 + qn)??
•  » » » 2 years ago, # ^ |   0 The TL is very tight, you must write optimal code to pass.
•  » » 21 month(s) ago, # ^ |   0 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
•  » » » 21 month(s) ago, # ^ |   0 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$.
 » 2 years ago, # | ← Rev. 2 →   +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)$
•  » » 2 years ago, # ^ |   +1 You're right, sorry I will fix it.
•  » » » 2 years ago, # ^ |   +1 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.
•  » » » » 2 years ago, # ^ |   0 Can You please explain, why are we assigning (k+1) zeroes to first z mod g group?
•  » » » » » 2 years ago, # ^ |   +1 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.
•  » » » » » » 2 years ago, # ^ |   0 Yeah now understood completely Thanks alot!!
•  » » » » » » 16 months ago, # ^ |   0 thanks a lot.
•  » » » » 2 years ago, # ^ |   0 thanks i was also unclear about (k+1)*(zmodg)
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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).Kilani, 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.
 » 2 years ago, # | ← Rev. 2 →   +13 Kilani Thank u for this Editorial But i thnik you mean "at most" instead of "at least" in the last problem tutorial !
•  » » 2 years ago, # ^ |   +1 Can you point where in the problem statement that "at most" is? I missed it.
•  » » » 2 years ago, # ^ |   0 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"
•  » » » » 2 years ago, # ^ |   +1 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?
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   +1 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
•  » » » » » » 2 years ago, # ^ |   +1 Ahh, ok, makes sense. Use every color at most once.
•  » » » » » » » 2 years ago, # ^ |   0 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!!
•  » » » » » » » » 2 years ago, # ^ |   0 The path never used the same color twice, because it would be shorter using the color only once.
 » 2 years ago, # |   +21 Problem F, how do we find a path where we have to use "tunnels" of more than one color, one after the other?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +4 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
•  » » » 2 years ago, # ^ |   +1 I see. Since you have to do this for every pair of colors only once you use cvis[]. Thanks!
 » 2 years ago, # | ← Rev. 4 →   -29 Nevermind, I messed up with author's solution
 » 2 years ago, # | ← Rev. 2 →   -6 .
•  » » 2 years ago, # ^ |   +12 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Edit:- Got it.
 » 2 years ago, # |   0 I don't understand why the solution works for problem B
•  » » 2 years ago, # ^ |   +1 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.
•  » » » 2 years ago, # ^ |   +5 Nicely Explained!
•  » » » 2 years ago, # ^ |   0 Thank you!!! I understood at once B as soon as read "Place all the determined numbers on an axis".
•  » » » 8 months ago, # ^ |   0 can we take average off all numbers here? and it can be consider as k?
 » 2 years ago, # |   0 "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 ?
 » 2 years ago, # |   +2 Can someone explain the binary search version of B?
•  » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   0 Actually, a ternary search may be more appropriate than a binary search here: https://cp-algorithms.com/num_methods/ternary_search.html
 » 2 years ago, # |   0 Thanks for the quick editorial <3
 » 2 years ago, # | ← Rev. 3 →   +22 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.
•  » » 6 months ago, # ^ |   0 Can you please tell me how you come up with this solution?
 » 2 years ago, # |   0 in problem B, why can't I just take all the non missing elements instead of taking only adjacent to missing elements?
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   0 I got such test cases. Can you please expalin why adjacent numbers like 1 4 100 or 1000 1000 always make the answer worse ?
•  » » » » 2 years ago, # ^ |   0 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).
•  » » » » » 2 years ago, # ^ |   0 got it..thanks
•  » » » » » 2 years ago, # ^ |   0 Thanks a lot. Now I understood mistakes in my reasoning.
 » 2 years ago, # |   0 can anyone help me why this solution fails? https://codeforces.com/contest/1301/submission/71037252
 » 2 years ago, # | ← Rev. 4 →   0 @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!!
 » 2 years ago, # |   +21 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.
•  » » 2 years ago, # ^ |   0 Thanks for the hint. It's much easier.
 » 2 years ago, # |   0 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…
•  » » 2 years ago, # ^ |   0 Read the code, then you can understand it.
 » 2 years ago, # |   0 Can anyone mathematically prove for problem B that the best k is equal to (minimum value + maximum value)/2 ? Thanks.
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 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.
 » 2 years ago, # | ← Rev. 2 →   0 Cam someone please tell me why my binary search solution is getting timed outhttps://codeforces.com/contest/1301/submission/71014146
•  » » 2 years ago, # ^ |   0 Got it. Never mind
 » 2 years ago, # |   0 Can someone explain to me how to solve 'B' by using Binary search??
•  » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # | ← Rev. 3 →   0 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
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 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!!!
 » 2 years ago, # |   0 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)) 
•  » » 2 years ago, # ^ |   0 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()] 
 » 2 years ago, # |   0 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.
 » 2 years ago, # |   0 can someone help why this code for problem B gets wa ??:( tnx in advance.this
 » 2 years ago, # |   0 The hard part of the proof in C is proving that it should be "as equal as possible". The author conveniently skips that.
•  » » 2 years ago, # ^ |   0 Can you please explain me the proof for it
•  » » 23 months ago, # ^ |   0 Yes can anyone give the proof for this?
•  » » » 23 months ago, # ^ |   0 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.
•  » » » » 23 months ago, # ^ |   0 Thanks. Really appreciate your efforts
 » 2 years ago, # |   0 Why does this straightforward $O(n * m * k + q * k)$ solution fail for problem F https://codeforces.com/contest/1301/submission/72293018
 » 2 years ago, # |   0 B's second test's 369th testcase sucks
 » 2 years ago, # |   0 I have an alternate solution to E with time $O((nm+q)\sqrt[3]{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[3]{nm}$.
 » 2 years ago, # |   0 Hi, Kilani, 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.
 » 2 years ago, # |   +1 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
»
2 years ago, # |
Rev. 2   0

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;
`

}"> ...

•  » » 5 months ago, # ^ |   0 Can u pls explain this?
 » 22 months ago, # |   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 !
 » 21 month(s) ago, # |   0 why are we dividing z into m+1 groups?
 » 20 months ago, # |   0 Nice and Useful Contest