Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### BledDest's blog

By BledDest, history, 2 years ago, ,
A. Word Correction
C. Constructing Tests
E. Max History
F. Erasing Substrings
G. Shortest Path Queries

• +84

 » 2 years ago, # | ← Rev. 3 →   +1 @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..
•  » » 2 years ago, # ^ |   +1 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.
•  » » » 2 years ago, # ^ |   0 Thank you sir , I understood what you explained.
•  » » » 2 years ago, # ^ | ← Rev. 4 →   +2 i was doing a silly thing!!, ignore.
•  » » » » 2 years ago, # ^ |   +2 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 
•  » » » » » 2 years ago, # ^ |   +1 oh yes! thank you for resolving my doubt
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 @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?
•  » » » » 2 years ago, # ^ |   0 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).
•  » » » » » 2 years ago, # ^ |   0 but I did it that way,and get WA
 » 2 years ago, # |   0 Love the model solutions- helps clear up the implementations immensely.
 » 2 years ago, # |   +6 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.
•  » » 2 years ago, # ^ |   0 Why do you only use 25 for used?
•  » » » 2 years ago, # ^ |   0 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.
•  » » » » 2 years ago, # ^ |   0 But m equals 200000 in one of the test cases. Wow.
 » 2 years ago, # | ← Rev. 2 →   0 I wrote n^2 solution for E, but it got WA#16 instead of expected TLECan somebody help me?
•  » » 2 years ago, # ^ |   +1 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.
•  » » » 2 years ago, # ^ | ← Rev. 4 →   0 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
 » 2 years ago, # |   0 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
•  » » 2 years ago, # ^ |   0 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).
 » 2 years ago, # | ← Rev. 2 →   0 could any one tell me what's the upper bound of n and why it is in problem C? well i mean while iteration.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I've solve it. The range of n should be when x ≠ 0 .
•  » » » 2 years ago, # ^ |   0 huangwenlong, can you explain how did you get the upper bound?
•  » » » » 2 years ago, # ^ |   +1 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 .
 » 2 years ago, # | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   0 First code without "else break" is correct.
•  » » » 2 years ago, # ^ |   0 thank you. :)
 » 2 years ago, # |   0 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 .
 » 2 years ago, # | ← Rev. 2 →   +3 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?
•  » » 2 years ago, # ^ |   0 same question here
•  » » 2 years ago, # ^ |   0 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.
•  » » » 23 months ago, # ^ |   0 Thanks bro!!
•  » » » 23 months ago, # ^ | ← Rev. 2 →   0 thanks
•  » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   0 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
 » 2 years ago, # |   +5 In C problemhow we concluded that if: floor(n/k)=sqrt(n^2 -x)then k=n/sqrt(n^2-x) ???
 » 2 years ago, # |   0 I don't understand problem B well could any one explain it for me ?
 » 2 years ago, # |   0 Can somebody please explain why im getting TLE in problem D http://codeforces.com/contest/938/submission/35611719
 » 2 years ago, # |   0 @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.
•  » » 2 years ago, # ^ |   0 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 
•  » » » 2 years ago, # ^ |   0 Thanks a lot @BledDest sir, understood now clearly, was making such a small error. Thank you so much now it's clear
 » 2 years ago, # | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   +1 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 .
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
 » 2 years ago, # | ← Rev. 3 →   0 Could someone explain more about the simple O(n3logn) dp solution of problem F mentioned in the tutorial?
•  » » 23 months ago, # ^ |   0 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.
 » 2 years ago, # |   0 can anyone explain me problem c how did the editorialist derived the formula ?
 » 23 months ago, # |   0 Far better than PikMike's editorial. Kudos!
 » 23 months ago, # |   0 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).
 » 19 months ago, # |   0 40571008 can somebody help me in debugging the solution.