### fakeac's blog

By fakeac, history, 12 months ago, ,

This problem appeared in one of my university assignments, but I only know of one algorithm which is to find Shortest Distance from each node node to every other node using Dijkstra's Algorithm and take the maximum of all distances found in each iteration. This is going to take time = O(V(E+V)log(V)) which is too large for the given data set.

I don't understand what does the approach — "Instead, randomly select pairs of vertices and evaluate minimum weight path (also referred to as shortest path) between them", mentioned in the 4th question mean. Please help.!Here is the problem statement. I need help for the 4th problem.

•
• +1
•

By fakeac, history, 14 months ago, ,
Let's say we have 2 recurrence relations -
summation(a[i]*f[i] for i=1 to n1)+summation(b[i]*g[i] for i =1 to n2) = 0 --------> Equation 1
summation(c[i]*f[i] for i=1 to n3)+summation(d[i]*g[i] for i =1 to n4) = 0 --------> Equation 2
.
.
.
.
.
-----------------------------------------------------------------------------------> Equation m
WHERE a[i], b[i], c[i] AND d[i] are constants.

##################################################################################################
In what cases is this above system of recurrence relations separable?
I want to express: f[i] in terms of only f terms and g[i] in terms of only g terms.
Is there a method to do it? If not, what are some of the specific cases under which this is doable?

I know of 1 such method when:
f[i]=a*f[i-1]+b*g[i-2] --------------------------------------------------Equation A
g[i]=c*f[i-5]+d*g[i-4] --------------------------------------------------Equation B
-> g[i-2]=(f[i]-a*f[i-1])/b -------------------------------------------- by rearranging A
-> f[i-5]=(g[i]-d*g[i-4])/c -------------------------------------------- by rearranging B
But now once you have say g[i-2]=(f[i]-a*f[i-1])/b, then by replacing i with i+2, we get,
-> g[i+2-2]=(f[i+2]-a*f[i+2-1])/b
-> g[i]=(f[i+2]-a*f[i+1])/b
Similarly g[i-4]=(f[i-2]-a*f[i-3])/b (from previous result)
now substitute these in Equation B.
Solve similarly for f.
Thus, separated.
##################################################################################################
Any general method?


•
• -24
•

By fakeac, history, 15 months ago, ,

I have written the code to solve this problem, but it gives TLE. I think the complexity of my soln. is O(n). My approach is as follows:

Let dp[from][to] = 1 if all nodes in the subtree of "to" (including "to") are of the same color when we perform dfs from node "from" and "to" is the child of node "from". dp[from][to] = 0, otherwise.

To calculate dp[from][to] we use dfs. Let node "to" have k children, then let's compute dp[to][child] for all children of "to". Then dp[from][to] = 1 if and only if dp[to][child]==1 for all children of "to" and the color[child]==color[to] for all children of "to". Otherwise, dp[from][to]=0;

Now, to compute the final answer, Let's iterate over all "from" nodes, and for each "to" such that "to" is adjacent to "from", if dp[from][to]==1, then final answer="YES", and node="from".

If no such "from" is found then answer="NO";

But this looks like O(n^2) solution. But, if we observe carefully, we see that each "from","to" pair of nodes corresponds to a directed edge going from node "from" to node "to". Since there are exactly n-1 edges, the no. of "from","to" pairs = 2*(n-1).

Here is my submission ----> http://codeforces.com/contest/764/submission/24382711.

NOTE: In this solution instead of passing -> "from","to" to dfs function, I have passed "from","index of 'to' in adj[from]". I have made multiple dfs calls but each call is computed exactly once, since I have made a vis[] array which keeps track of it.


NOTE: If we put a break statement in dfs for loop, we get AC. Lol :P Here is the AC submission. I don't know why it does not get TLE, as the time complexity remains the same, but it is slightly optimized.

Please tell where I am wrong in calculating the time complexity? Thanks in advance.

•
• +9
•

By fakeac, history, 16 months ago, ,

Here is my code for this problem — http://codeforces.com/contest/749/problem/D from Div-2 D round #388 Here is my submission --> http://codeforces.com/contest/749/submission/23178341 My code is well commented and as per the editorial given. It is taking too much time. The complexity is O(nlog(n)). How do I optimize my code? What operation/operations are taking too long ? Please Help! Thanks in advance.

By fakeac, history, 17 months ago, ,

I am trying to solve — http://codeforces.com/problemset/problem/721/C. Here is my submission — http://codeforces.com/contest/721/submission/22405854

By fakeac, history, 17 months ago, ,
You have been given a n*n matrix consisting of 0's and 1's.You need to find the number of squares in the matrix such that it contains no 1's (All entries should be 0).


Constraints:
1=<n<=5000


Input:
First line consists of a single integer n.
Each of the next n lines consist of a binary string of length n.
Output:
Output just one integer, the answer as described above.


Sample:

Input:
3
000
000
000
Output:
14

Explanation: There are 9=> 1 * 1 squares, 4=> 2 * 2 squares and 1=> 3 * 3 square.


Input:
2
10
10
Output:
2

Explanation: There are 2=> 1 * 1 squares. All other squares contain a 1.


Input:
2
11
11
Output:
0


Input:
1
0
Output:
1
`