@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..

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.

I wrote n^2 solution for E, but it got WA#16 instead of expected TLE

Can somebody help me?

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://mirror.codeforces.com/contest/938/submission/35438377

could any one tell me what's the upper bound of n and why it is in problem C? well i mean while iteration.

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.

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 .

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?

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://mirror.codeforces.com/contest/938/submission/35461430

In C problem

how we concluded that if: floor(n/k)=sqrt(n^2 -x)

then k=n/sqrt(n^2-x) ???

@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 0

Here 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.

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.

Could someone explain more about the simple O(n³logn) dp solution of problem F mentioned in the tutorial?

Far better than awoo'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).

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.

My Approch and solution for problem C.