Educational Codeforces Round 38 — Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

A. Word Correction

B. Run For Your Prize

C. Constructing Tests

D. Buy a Ticket

E. Max History

F. Erasing Substrings

G. Shortest Path Queries

This is a more complex version of problem G from Educational Round 27. You can find its editorial here.

To solve the problem we consider now, you have to use a technique known as dynamic connectivity. Let's build a segment tree over queries: each vertex of the segment tree will contain a list of all edges existing in the graph on the corresponding segment of queries. If some edge exists from query l to query r, then it's like an addition operation on segment [l, r] in segment tree (but instead of addition, we insert this edge into the list of edges on a segment, and we make no pushes). Then if we write some data structure that will allow to add an edge and rollback operations we applied to the structure, then we will be able to solve the problem by DFS on segment tree: when we enter a vertex, we add all edges in the list of this vertex; when we are in a leaf, we calculate the required answer for the corresponding moment of time; and when we leave a vertex, we rollback all changes we made there.

What data structure do we need? Firstly, we will have to use DSU maintaining the distance to the leader (to maintain the length of some path between two vertices). Don't use path compression, this won't work well since we have to do rollbacks.

Secondly, we have to maintain the base of all cycles in the graph (since the graph is always connected, it doesn't matter that some cycles may be unreachable: by the time we get to leaves of the segment tree, these cycles will become reachable, so there's no need to store a separate base for each component). A convenient way to store the base is to make an array of 30 elements, initially filled with zeroes (we denote this array as a). i-th element of the array will denote some number in a base such that i-th bit is largest in the number. Adding some number x to this base is really easy: we iterate on bits from 29-th to 0-th, and if some bit j is equal to 1 in x, and a[j] ≠ 0, then we just set $\text{[math]}$ (let's call this process reduction, we will need it later). If we get 0 after doing these operations, then the number we tried to add won't affect the base, and we don't need to do anything; otherwise, let k be the highmost bit equal to 1 in x, and then we set a[k]: = x.

This method of handling the base of cycles also allows us to answer queries of type 3 easily: firstly, we pick the length of some path from DSU (let it be p), and secondly, we just apply reduction to p, and this will be our answer.

Model solution

Comments (44)

Show archived | Write comment?

I_D0nt_Kn0w

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

→ Reply

BledDest

7 years ago, # ^ |

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:

And now it's impossible to put a second zero to cover 4 submatrices we didn't cover previously.

WarBoy

← 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:

And for n = 5 and m = 2 — the following:

oh yes! thank you for resolving my doubt

tatya_bichu

← Rev. 2 →

@BledDest

if we do:
1111
1010
1111
1010
we 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 3

1111
1111
1101
1111
if t=12 then zeroes can be:16-12=4 so answer is 4 2

1111
1010
1111
1010
and for all t from 16 to 21 answer:-1 isn't that approach right?

Yes, from every $\text{[math]}$ 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

hell_hacker

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.

michaelw12

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.

aijey

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

Can somebody help me?

deep_learning

cnt2[i]+=(fact[i-1]*fact[n-j-1])%MD/fact[i-1-j];

You can't do this. If $\text{[math]}$ , it doesn't mean that $\text{[math]}$ . In fact, you should use the modulo inverse instead of division. (i.e. use a × b^- 1 instead of $\text{[math]}$ .) You can use Fermat's little theorm (i.e. $\text{[math]}$ when p is a prime and (a, p) = 1) and quick pow to work out $\text{[math]}$ when p is a prime. Otherwise, you can use extended euclidean algorithm instead. Hope this will help.

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

atrophy98

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

Shudi

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

blue_m00n_eoy

4 years ago, # ^ |

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_algorithm

Good luck with competitive programming :)

huangwenlong

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

I've solve it. The range of n should be $\text{[math]}$ when x ≠ 0 .

susg

huangwenlong, can you explain how did you get the upper bound?

Sorry for the late reply. We can get $\text{[math]}$ , from $\text{[math]}$ . If x ≠ 0, m should not be less than 2. So when m = 2, $\text{[math]}$ . When m = n, $\text{[math]}$ . And we can conclude that $\text{[math]}$ is a decreasing function. So the range is $\text{[math]}$ .

drexdelta

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

M = 1; fa=0;
for(int i = 2 ; i <= n ; i++){
    if(a[M] < a[i]){
        fa += a[M];
    }
    M = i;
}

Please, somebody help.

vbobrov

First code without "else break" is correct.

thank you. :)

Taxman

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 $\text{[math]}$ ) but it's good for educational purposes. Actually it has $\text{[math]}$ time complexity but FFT has a large constant so it takes around 10secs for $\text{[math]}$ .

Vasiljko

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?

Swiftending

same question here

blowin_in_the_wind

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.

yashgulani

Thanks bro!!

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 a_i. Lest consider the next minimum (Min₂(a)) and name it "v". There are two cases. it can go to the city having Min₁(a) or just stay there(why?). This property holds for every vertex having Min_i(a). It can go to one of those vertexes having Min_j(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://mirror.codeforces.com/contest/938/submission/35461430

agamanan96

In C problem

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

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

zenwraight

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

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:

Too_lazy_to_solve

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 $\text{[math]}$ ), and if it is unsuccessful, then we perform only one operation with Gaussian elimination. So the complexity is $\text{[math]}$ .

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.

just_soso

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

Lych4o_

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.

plehem

Far better than awoo's editorial. Kudos!

dalt

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

Fly_37

5 years ago, # |

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.

Dhruv_Gheewala

4 years ago, # |

My Approch and solution for problem C.

Approch

Solution

BledDest's blog