Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | Um_nik | 3538 |

2 | tourist | 3509 |

3 | Benq | 3473 |

4 | ecnerwala | 3446 |

5 | ksun48 | 3432 |

6 | maroonrk | 3404 |

7 | Radewoosh | 3383 |

8 | yosupo | 3324 |

9 | boboniu | 3300 |

10 | apiadu | 3238 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 199 |

3 | SecondThread | 191 |

4 | antontrygubO_o | 185 |

4 | pikmike | 185 |

6 | Um_nik | 184 |

7 | vovuh | 183 |

8 | Ashishgup | 182 |

9 | pashka | 168 |

9 | Radewoosh | 168 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Global Round 6

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2020 21:05:49 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Wow, fastest editorial out there!

Gap between E and F is HUUUUUGGGGGEEEEE :C

Fast Editorial and system testing :)

epic F...

wow fastest guide ever i have seen

Thanks for the Fastest Editorial and it was a very nice contest :D

For D, you have given solution for min dept, how to find number of depts?

I did a greedy solution 67115957, can anyone please tell me why i am getting TLE.

IN Russia, please!!!:)))

Yeeee. This is the fastest guide I've ever seen

For E , what ideally we should have done -" It is obvious that we cannot do better and this number is necessary. Let's prove that it is also sufficient. "

What most people did — " It is obvious that we cannot do better and this number is necessary. Let's submit."

How to solve D with rule 1 changed to d(a, b) and d(b, c) instead of d(a,b) and d(c, d)? If I understand that correctly, it means we cannot greedily match balances and we need to preserve (more or less) the original graph structure.

Yes, I also thought that it was important in the contest, but if you carefully read and understand all the limitations in the first operation, it will become clear that you can get any situation that is described in the solution.

Yeah, I know, I managed to reread the problem statement after 1 hour and solved it, but I am wondering about a harder problem now :P

Sorry, confused in the letters :D

https://codeforces.com/contest/1266/submission/6708325 Please someone can find mistake in my first question solution..

Your link is incorrect. This one I think you mentioned. Try this test:

`100`

. Your output I think red, instead of cyan.thanks for your reply.. i found my mistake

Thanks for the quick editorial.Thanks for the quick editorial!!!

fast!!! awesome!!

H is very cool, one of my favorite problems now. Thanks!

Then I have a bonus for you:

It looks like this bonus is a previous code jam problem from a while ago: https://code.google.com/codejam/contest/2075486/dashboard#s=p4&a=2

Damn! It's really difficult to come up with something original.

Hello majk !

I want to ask something about problem C. Since it is a constructive algorithm task ; could you please describe the thought process involved while arriving at the construction.

PS : I also solved the problem in the contest ; however it took me a lot more time to derive the construction.

Thanks in advance !

Here is how I thought of it it, Since we have to produce minimum magnitude and all Gcds should be distinct, I thought the gcds should be of the form 1,2,3,4,5. I didn't know of this will work, but just a trail. I tried to produce gcd = 1. This can easily be done by writing 2,3. I also noticed that 1 cannot be written anywhere as it make gcds of column and row same. So in the first row I wrote 2,3,4,5,6,....,m + 1.after this I observed that I can make gcds of each column the topmost element if each column is a multiple of the topmost element. After this, I thought that if I multiply the first row by some number and write it in the second row, the gcds of the second row will be the number it was multiplied with as I can take the number common and the gcds of remaining elements is one. It's easy to see how this works after this.

Thanks! I was just thinking like you, but missed to notice a silly mistake I was making in my logic, now I understand my mistake.

Thanks. It's helpful.

I think my solution for C plainly describes the thought process involved. here

I created two arrays(one for row and one for column) that contains the targeted minimum disjoint gcd values that can be achieved ie { 1,2...r...(r+c) }then I filled the matrix by multiplying each row array element with column array element. By analyzing output you can infer {1...r} values can be achieved by taking gcd of each row and remaining {r+1...c} can be achieved by taking gcd of each column.

It would be really helpful if someone could provide the thought process required for C,as it is a constructive algo?

Since we want to minimise GCD we may want to start with putting 1 but we can't do so because it will make the GCD of that particular row and column 1 which will not satisfy condition that GCD values must be distinct. Firstly, try a simpler case like when r = 1 and c > 1, we can have values like 2,3,4,...c-1. Similarly, for case when c = 1 and r > 1. Now, Let us consider case when r = 3 and c = 3. Then in first row we can have 4,5,6 which have GCD = 1. Now observe that for second row we can multiply the first row by 2, which gives for second row 8,10,12 which will have GCD as 2. Similarly, third row will be 12,15,18 having GCD as 3. And for the first column GCD will be 4, second column GCD will be 5 and for third column GCD will be 6. So set of distinct values of GCD = {1,2,3,4,5,6} and also we can say that r+c will always be the optimal value.

good contest !

Thanks majk !

Why is it clear in problem D that we can't do better than sum of balances divided by 2?

I have a linear-time solution (67124772) to F.

The idea is to make extensive use of the trivial data structure that maintains a set of integers and supports the following operations:

To do this, just store for every value how many times the value appears in the set, and maintain the maximum.

We'll loop from $$$k = 1$$$ upwards, and maintain $$$dp[i] = $$$ number of subtrees of $$$i$$$ with depth at least $$$k$$$ (including parent). Then at step $$$k$$$ we have $$$ans[2k] = \max(\max_{i} dp[i], \max_{a, b \text{ adjacent}} dp[a] + dp[b] - 2)$$$ and $$$ans[2k-1] = \max_{i} dp[i] + \text{at least one of the subtrees of i has depth exactly } k-1$$$.

To maintain $$$dp[i]$$$, note that when we increase $$$k$$$ and calculate the new value $$$dp'[i]$$$, we have $$$dp'[i] = \sum_{t \in conns[i]} \max(1, dp[t]) - 1$$$. Hence we can store a queue of nodes whose some neighbour had their $$$dp[i]$$$ decreased to one in the previous step. The nodes in the queue are exactly the nodes whose $$$dp[i]$$$ will decrease in this step (multiple times if they appear multiple times). Since initially $$$dp[i] = deg(i)$$$, and they can only decrease, and we do updates to them in $$$\mathcal{O}(1)$$$ time, this part takes linear time.

We'll use one copy of the data structure to maintain values of $$$dp[i]$$$. To maintain the values we need to calculate $$$ans[2k-1]$$$, we'll maintain the values $$$dp[i] + \mathbb{I}[dp[i] \text{ got decremented in the previous step}]$$$ in another copy of the data structure.

Lastly, to maintain the values to calculate $$$ans[2k]$$$, we'll maintain for every node a copy of the data structure storing the current values of $$$dp[i]$$$ for its children. Note that every $$$dp[i]$$$ appears in exactly one such data structure, so to initialise and maintain them we again do only linear work. We'll also have a data structure storing the "active" values $$$dp[i] + \max_{c \in childs[i]} dp[c] - 2$$$. Whenever $$$dp[i]$$$ decreases, we decrement its active value, its parents children data structure, and its parents active value if $$$dp[i]$$$ was the unique maximum in the data structure. All the operations we'll ever do again take in total time equal to the sum of degrees, which is linear.

I have a similar solution to you, and the complexity is also linear: 67162965.

We notice that the number of subtrees of $$$i$$$ with depth at least $$$k$$$ is always smaller than that of $$$k - 1$$$. So, instead of looping $$$k$$$ from $$$1$$$ upwards, we loop $$$k$$$ from $$$n$$$ downwards, which will make every variable in the computation non-decreasing, so we don't have to use any data structures; straight up updating every variable using the $$$max$$$ function is enough.

Edit: Courtesy to LunarStellarshot for helping me with this discovery :D

In D editorial can someone explain "We have just reduced the total debt by z, which is a contradiction."

We assume that the debt is already minimal, and there is a vertex triple such that ... We managed to reduce the debt, so it wasn't minimal. This means that for a minimal debt, there cannot be such triple.

[DELETED]

In question D

for input:

6 4

1 2 6

2 3 4

4 5 3

5 6 5

is this a correct solution?:

4

1 6 5

4 3 3

5 2 2

1 3 1

Edit: It is .. nevermind

In problem H:

How to prove that these conditions are sufficient?

https://codeforces.com/contest/1266/submission/67100495

Can someone tell why my solution is failing in D. Is there something to do with it out of bounds?

You should swap these two lines.

Shit. How could I make such mistake. Thanks for help.

Thanks for the contest!

In problem D

"It follows that any solution in which every vertex has either outgoing or incoming edges is constructible using finite number of applications of rules."

I couldn't understand why... How to prove it? Can someone explain?

"It follows that any solution in which every vertex has either outgoing or incoming edges is constructible using finite number of applications of rules." Because if there is combination of vertices like a->b->c then this combination surely results in a decreased total debt i.e. why using any number of operations we can achieve the state of graph where every vertex has either incoming or outgoing edge.

Thank you,but why "any solution is constructible"...?

I understood there exists the graph which we can construct where every vertex has either outgoing or incoming edges,but I don't think it is clear that we can construct "any" graphs that satisfies the condition.

(I'm sorry if I misunderstood the editorial)

For example, imagine that there is a answer a->b 10, c->d 10. In order to get another answer, we add two edges a->c 10 and c->a 10, then we could use the first rule to get another answer a->d 10, c->b 10

Thanks,I got it

I'm really interested in yosupo's and abacabadabacaba's solutions to problem H.

It looks they are quite different from the intended solution.

For each vertex, we assign a level as the shortest distance for the vertex N.

Core part is making function succ(l, State={position, color, time}) -> new_State: this function simulate the state while a token reach one of the vertex whose level is l(we assume the first position of token is a vertex whose level is higher than l). We can memoize this function by (l, color of vertexes whose level is higher than l).

How many states this function memoized? ... actually I don't have any proof(so, my solution is unproved, sorry). My intuition say that it is exponential, but quite small (even in the worst case).

I can make a test which makes it memoize $$$O(n2^{n/2})$$$ states.

My solution uses simulation with memoization.

Suppose that we start in some state, and the token is in vertex $$$i$$$. If we know only the state of vertex $$$i_1=i$$$, we can simulate one step (or two, if the first step moves the token to the same vertex). Then, the token lands at vertex $$$i_2\ne i_1$$$. If we know the state of vertices $$$i_1$$$ and $$$i_2$$$, we can simulate more steps until the token lands at vertex $$$i_3\ne i_1,i_2$$$. This way, it is possible to construct the following lazy DP: the state is $$$(i,k,\textrm{state of }i_1\ldots i_k)$$$, and the value is $$$(i_{k+1},\textrm{new state of }i_1\ldots i_k,\textrm{number of steps})$$$.

The simulation function (

`run`

in my solution) takes the following arguments: initial vertex, current state and a set of vertices. It runs the simulation until the current vertex is not in the set. There is also an option to limit the number of steps. It starts with $$$k=1$$$ and $$$i_1=i$$$ to compute $$$i_2$$$, $$$i_3$$$ and so on. To compute DP for some $$$k$$$, it runs the same procedure recursively with starting vertex $$$i_k$$$ and the set $$${i_1,\ldots,i_k}$$$. For $$$k=1$$$, a straightforward simulation is used (this requires at most two steps).Can Somebody please explain problem D As I think that is incorrect, as d(1,2) = 10 and d(2,3) = 15 (as in example) doesn't work according to the writeup as here v = 2 is valid and also a tripe will occur as 1,2,3, with v as both incoming and outgoing debts, so how this can be a contradicton? Please correct if I am thinking wrong..

In the editorial, he is trying to prove by contradiction that if you try to eliminate all such cases where the triples exist, you can combine the rest of the remaining vertices to get your final answer. As they are the only way you can reduce the total sum given the conditions in the question. As a result, finally, you will be left with only vertices with either outgoing or incoming edges and not both for a single vertex

Could anyone help me why the following solution is incorrect for C? I hope my logic was correct.

https://codeforces.com/contest/1266/submission/67161724

Your logic is half correct,your solution does produce disjoint gcd arry or diverse matrix,but it is failing to produce the

`diverse matrix that minimises the magnitude`

For eg. dry run your program for 3 3,you will get it.Such a Terrible mistake! Thanks a lot

Two doubts for problem D editorial

how did you conclude this " This means that we can just find balances, and greedily match vertices with positive balance to vertices with negative balance.The total debt is then Σd=∑v|bal(v)|2 , and it is clear that we cannot do better than that"

how do we find the final debts i.e. the second half of the answers , the remaining edges.

Is it like to minimize the debt we have to pay all the loan back so that the overall debt decreases and that is why we are matching the positive ones with negative ones so as to make positive ones as small as possible. Do we have to think like this ??

i wonder how to prove the greedy algorithm can get the answer, i.e. second part of output

In E if we consider a = {1,1} and queries are — (1, 1, 2) and (2, 1, 1) then p will be {0,0} how is it possible to not create anything?

Hey, I was also stuck on this. However, the question states that

ti <ai.In problem H,why are these two conditions sufficient?

For a valid state, we take the subgraph of all active arcs.

It's easy to see that there exists exactly one vertex such that:

The active arc starting from it ends at v.

The path from 1 to the said vertex does not include v.

Then the only possible predecessor of v is the said vertex.

The rest is induction.

upd:I seem to have missed the case when v=1...Forget what I've said before.take the directed multigraph, where each arc appears exactly the number of times it is traversed.Given the constraints of the matrix, it's easy to see that there exists an Euler path(if it's connected, hence the condition we're checking).Consider constructing an Euler path the following way:Start from 1;If the vertex we're at has been traversed odd number of times, take the blue arc; else take the red arc.It could be checked that this Euler path is the legitimate path.P.S.

Since all other vertices must be traversed before v, it could be checked that they should all be able to go to v using only active arcs.

B solution

hi majk,i am quite new in coding,i still dont really understand problem D,i am lost after the part(we greedily match vertices with positive balance with vertices with negative balances).does it mean to perform the operation (u,v) (v,w) if v and w is the vertices chosen to be matched,could you please clear this up for me,thank you

how to construct r X c matrix in question C. there is only r and c is taken as input.please answer

bc

people at codechef give better explanation than codeforces editorial.Even the submissions are not intituitive at codeforces.here is disscussion for problem d https://discuss.codechef.com/t/cf-global-round-6-problem-d-decreasing-debts/46959/7

see royalfalcon156 ans on the given link

Here is a Detail explanation for Div2 D Here. Hope could be helpful to someone

This is the worst and the most unrigorous explanation I have ever seen.

Well Sorry for that.I will try to improve

In the editorial of problem G, "the answer is $$$|p|⋅(|p|+1)−∑LCP[i]$$$", shouldn't it be $$$|p|⋅(|p|+1)/2−∑LCP[i]$$$ ?

Good