### BledDest's blog

By BledDest, history, 3 years ago, A. Word Correction
C. Constructing Tests
E. Max History
F. Erasing Substrings
G. Shortest Path Queries  Comments (54)
 » 3 years ago, # | ← Rev. 3 →   @BledDest Sir , in problem C , why are we taking only non-intersecting submatrices of size k x k? Here's what my thought process was for the problem C : let's suppose we have a matrix of size n x n and let us consider a submatrix of size k x k. Now to ensure there are minimum number of zeros(i.e max no of 1s), we'll place 0 at rightmost bottom most cell of the k x k matrix and now we'll consider the total number of submatrices of size k x k sharing this 0, and that would be according to me k x k number of submatices. Now if we consider total number of submatrices(intersecting and non intersecting) of size k x k in the matrix of size n x n , then that would (n-k+1) x (n-k+1) , so according to my deductions , the formula should be (n^2 — ((n-k+1)^2)/(k^2)) which is wrong as per the editorial? Could you help me with what am I thinking wrong? Sorry to bother you , if my question is stupid..
•  » » The main problem is that you can't always put zeroes in such a way that k × k submatrices are covered by this zero.For example, let n = 4, k = 2:According to your algorithm we put the first zero in cell (2, 2) and cover 4 submatrices: 1111 1011 1111 1111 And now it's impossible to put a second zero to cover 4 submatrices we didn't cover previously.
•  » » » Thank you sir , I understood what you explained.
•  » » » 3 years ago, # ^ | ← Rev. 4 →   i was doing a silly thing!!, ignore.
•  » » » » This obviously doesn't give us maximum possible number of ones, since for n = 5 and m = 3 we can use the following: 11111 11111 11011 11111 11111 And for n = 5 and m = 2 — the following: 11111 10101 11111 10101 11111 
•  » » » » » oh yes! thank you for resolving my doubt
•  » » » 3 years ago, # ^ | ← Rev. 2 →   @BledDestif we do:1111101011111010we have covered all submatrices. now say t=15 , we get perfect square x(>=15) x=16 ,so given 1s =15 hence 0s are 1(16-1) now answer could be 4 31111111111011111if t=12 then zeroes can be:16-12=4 so answer is 4 2 1111101011111010and for all t from 16 to 21 answer:-1 isn't that approach right?
•  » » » » Yes, from every answer is  - 1 since if we set n = 4, then we can't obtain anything greater than x = 15; and if we set n ≥ 5, then x ≥ 21 (if we don't consider m = 1).
•  » » » » » but I did it that way,and get WA
 » Love the model solutions- helps clear up the implementations immensely.
 » I don't know why my D passed. I just ran DFS multiple times (10 times DFS passed) and in each time I took the minimum of that node and all it's neighbors. Is this logic correct or just my luck that it passed. Thanks.
•  » » Why do you only use 25 for used?
•  » » » It passed with 10 only. I still don't know how it works. I thought 2 DFS might be sufficient but it wasn't the case. If I increase the number of times I do DFS it will time out.
•  » » » » But m equals 200000 in one of the test cases. Wow.
 » 3 years ago, # | ← Rev. 2 →   I wrote n^2 solution for E, but it got WA#16 instead of expected TLECan somebody help me?
•  » » cnt2[i]+=(fact[i-1]*fact[n-j-1])%MD/fact[i-1-j];You can't do this. If , it doesn't mean that . In fact, you should use the modulo inverse instead of division. (i.e. use a × b - 1 instead of .) You can use Fermat's little theorm (i.e. when p is a prime and (a, p) = 1) and quick pow to work out when p is a prime. Otherwise, you can use extended euclidean algorithm instead. Hope this will help.
•  » » » 3 years ago, # ^ | ← Rev. 4 →   Hi, thank you so much for your answer. I did what you said but now i have WA#5. Any suggestions?Edit: Fixed Thank you again :)Final solution
 » I was trying to solve D using a DFS and updating a DP array for each node. Can someone point out what is wrong with my logic?http://codeforces.com/contest/938/submission/35438377
•  » » You should read about the Dijkstra algorithm. I'll try explain the difference with your solution briefly. Doing right way we should take a node with the smallest distance to it and then update the information for its neighbours. After that we should delete this node from our list ( Dijkstra proved it ) and then repeat the first step until we considered all the nodes of the graph. This update in your solution can be wrong very often: dp[u] = min(dp[u], 2*wt + dp[v]); Value in dp[v] is not correct. Example: 4 3 1 2 3 2 3 3 2 4 3 10000 100000000 100000 2 Your solution is good without "visited", but then it will be O(n^3).
•  » » » I guess I'm late to the party, but when I implement this Dijkstra without keeping a count of visited cities I get Time-out, but the solution gets Accepted as soon as I ignore the cities which I have already visited. Also, for some questions like this: 20C Dijkstra, I don't need any visited array to pass the tests.Could you please explain why does this happen. Obviously, analyzing the Time-complexity is the key, but I find it hard to visualize what's happening. Thanks in advance.
•  » » » » Well, it was a long time ago, so I can't tell a lot. First of all, the main idea of Dijkstra is to keep array of visited cities. Otherwise, you would iterate over cities you've already visited again and again, that's why you get timeout. It's just an infinite loop. What about visualization you can look at wiki page. There is a good gif out there that explains a lot — https://en.wikipedia.org/wiki/Dijkstra%27s_algorithmGood luck with competitive programming :)
•  » » » » » The visualization on Wikipedia was really cool. Thanks bud.
 » 3 years ago, # | ← Rev. 2 →   could any one tell me what's the upper bound of n and why it is in problem C? well i mean while iteration.
•  » » 3 years ago, # ^ | ← Rev. 2 →   I've solve it. The range of n should be when x ≠ 0 .
•  » » » huangwenlong, can you explain how did you get the upper bound?
•  » » » » Sorry for the late reply. We can get , from . If x ≠ 0, m should not be less than 2. So when m = 2, . When m = n, . And we can conclude that is a decreasing function. So the range is .
 » 3 years ago, # | ← Rev. 2 →   In E problem, for every 2 ≤ i ≤ n if aM < ai then we set fa = fa + aM and then set M = i.Does this statement mean, M = 1; fa=0; for(int i = 2 ; i <= n ; i++){ if(a[M] < a[i]){ fa += a[M],M=i; } else break; } or M = 1; fa=0; for(int i = 2 ; i <= n ; i++){ if(a[M] < a[i]){ fa += a[M]; } M = i; } Please, somebody help.
•  » » First code without "else break" is correct.
•  » » » thank you. :)
 » Hi everybody.Here is my code which uses FFT (Fast Fourier Transform) to solve Task E. It doesn't fit in time and memory limits (works well for ) but it's good for educational purposes. Actually it has time complexity but FFT has a large constant so it takes around 10secs for .
 » 3 years ago, # | ← Rev. 2 →   I don't understand how can we use Dijkstra to actually find closest j for every i. Why does solution in editorial works? Can someone explain?
•  » » same question here
•  » » consider a new node(v) in addition to all given vertices.This node represents watching a concert. properties: has n edges with weight equal to costs of watching a concert for each vertex. now the problem reduces to single source shortest path between v and all remaining vertices(people from all cities have to (watch a concert so reach node v )in minimum cost) which is solved by dijkstra's.
•  » » » Thanks bro!!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   thanks
•  » » Consider a vertex having Min(a) (All of them in case of having multiple minimums) and name it "u". The answer for this (those) city is ai. Lest consider the next minimum (Min2(a)) and name it "v". There are two cases. it can go to the city having Min1(a) or just stay there(why?). This property holds for every vertex having Mini(a). It can go to one of those vertexes having Minj(a) with j ≤ i.Now we assume that it's better for vertex "v" to go to vertex "u". on the shortest path from "v" to "u" there is a vertex (call it "x". Of course it can be "v" itself) which is adjacent to "u". It can be easily proved that best answer for vertex "x" would be to go to "u".So what it means? every time we find the answer for some vertex we can relax all of its neighbors and then we are done with remaining vertex having minimum found answer.
 » For problem C: I searched for two divisors of x with same parity and found n & n/k .then re-checked.Can someone explain what is wrong with the code? http://codeforces.com/contest/938/submission/35461430
 » In C problemhow we concluded that if: floor(n/k)=sqrt(n^2 -x)then k=n/sqrt(n^2-x) ???
 » I don't understand problem B well could any one explain it for me ?
 » Can somebody please explain why im getting TLE in problem D http://codeforces.com/contest/938/submission/35611719
 » @BledDest Sir, one small doubt, I can't get my head around this problem C,so suppose x = 14, then can't my answer be n = 4 and m = 4 because if my m = 4 then my whole matrix has zeroes > 0.Like this:- 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0Here i am considering m = 4 that is whole matrix ? I know many people asked doubts related to problem C but I am still not able to understand this flow ? I know my question is stupid but please help me this last time.
•  » » Your answer for x = 14 can't be n = 4 and m = 4, because if n = 4 and m = 4, the maximum number of ones is 15: 1111 1111 1111 1110 
•  » » » Thanks a lot @BledDest sir, understood now clearly, was making such a small error. Thank you so much now it's clear
 » 3 years ago, # | ← Rev. 2 →   BledDest Can you please explain a bit more on time complexity of dynamic connectivity?As per the approach of editorial , if we have to add an edge to an interval (L,R) then we will just insert it into segment tree nodes which lie completely under this range(but we will not push it further down).Doubt : Since there can be atmost log(n) nodes containing that range and if we are doing union by size/rank than it will take log(n).Time complexity should be : nlog(n)log(n)log(c) ...since each edge can occur in dfs atmost log(n) times and log(n) for their union operation and log(c) for gaussian elimination part first comment in this blog explains it .PS: please correct me if i am interpreting it in wrong way.
•  » » You don't have to multiply the logarithm that comes from Gauss and the logarithm that goes from DSU. The union operation is used only in DSU (so it's ), and if it is unsuccessful, then we perform only one operation with Gaussian elimination. So the complexity is .
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Sorry my analysis was wrong ,we will first do log(n) to check for their parents and if they are different then we will union them and if they are same we will do log(c)(new cycle) for gaussian elimination...so basically log(c)+log(n) for each edge during dfs.thank you so much it is clear now.
 » 3 years ago, # | ← Rev. 3 →   Could someone explain more about the simple O(n3logn) dp solution of problem F mentioned in the tutorial?
•  » » dp[m][mask] has an O(n^2) number of states, and in every state we traverse O(logn) position to decide which we use, and we use string compare to judge which we choose so there is another O(n)ps:"abcd--> abd --> a" is equal to "abcd --> acd --> a". So we can choose 2^i in turn.
 » can anyone explain me problem c how did the editorialist derived the formula ?
 » Far better than PikMike's editorial. Kudos!
 » A direct explanation for Problem.F. Let's denote dp[i][j] as the i-th character of the minimum substring after we remove (j-i) characters from S[1...j].Let i iterate from 1 to the length of result, and let j iterate from 1 to n.For dp[i][j], there are two possibilities:1.We will get the minimum substring without removing S[j], it is equivalent to such a fact that there is a number m which is 0 or a single bit of(j-i) satisfies dp[i-1][j-m-1]=min(dp[i-1][i-1],dp[i-1][i],dp[i-1][i+1],...,dp[i-1][n]).In this way dp[i][j]=S[j].2.If we have to remove S[j] to get the minimum substring, it produces following dp transition : dp[i][j]=min(dp[i][j-m1], dp[i][j-m2],...,dp[i][j-mt]), m1,m2,...,mt is the single bit of (j-i).
 » 40571008 can somebody help me in debugging the solution.
 » 7 months ago, # | ← Rev. 2 →   I believe that the first solution could be optimized to $O(n^2\log^2{n})$ since for each state in $dp[m][mask]$ we need to store only positions of $O(\log n)$ segments.
 » 6 weeks ago, # | ← Rev. 2 →   My Approch and solution for problem C. Approch I have made a Formula: F(n, m) = n * n — a * a + b * b * (m * m — 1). Here, a: (n — n % m) or (floor(n / m) * m) b: (a / m) or (floor(n / m)) This is a formula for the number of 1's in the n * m matrix. As you can see in Formula that, If we increase the value of n => number of 1's will also increase. Hence, I have done a binary search on n for a fixed value of m(1 <= m <= 1e5). n, m <= 1e5 according to formula._ But this solution is quite slow, so we have to go till only those values of m such then F(m, m) <= x. If F(m, m) > x, then it will be increased only and we will not get a value less than x. SolutionLink