Let's discuss solutions! How to solve D, G and J?

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

1 | Benq | 3747 |

2 | tourist | 3656 |

3 | Miracle03 | 3587 |

4 | ksun48 | 3530 |

5 | Radewoosh | 3511 |

6 | maroonrk | 3434 |

7 | jiangly | 3432 |

8 | Um_nik | 3422 |

9 | ecnerwala | 3400 |

10 | peehs_moorhsum | 3384 |

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

1 | 1-gon | 214 |

2 | Um_nik | 191 |

3 | sus | 183 |

4 | Errichto | 180 |

5 | awoo | 179 |

6 | tourist | 178 |

7 | -is-this-fft- | 172 |

8 | Radewoosh | 171 |

9 | maroonrk | 169 |

9 | Ashishgup | 169 |

Let's discuss solutions! How to solve D, G and J?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/17/2021 14:12:58 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

J. Sort the edges. Binary search for the answer. Sliding window over the edges gives us a sequence of queries to add and remove edges; need to check if the graph ever becomes connected when executing the queries. This can be done using divide and conquer that uses DSU with rollbacks.

Could you please elaborate on "divide and conquer that uses DSU with rollbacks". I have never heard of this technique before, so could you please point me to some source or provide a short explanation. Thanks a lot.

Something like this: dynamic connectivity problem offline

"DSU with rollbacks" — it's partially persistent DSU. You can save all changes in stack and "rollback" to previous state when you want.

Yep, it's a part of Burunduk1's thesis.

Suppose we have a sequence of queries that add and remove edges, or get the number of connectivity components; for simplicity, each edge is added exactly once, then removed exactly once. The recursive procedure will take a segment of queries [a,b) and a global DSU that already contains all edges that are present in the graph for the whole segment [a,b) (i.e. edges that were added with queries [0,a) and removed with queries [b,n)). The procedure will answer all these queries and roll back all the changes that it makes to the DSU. To do that:

When we get to a segment [a,a+1), and query a asks for the number of connectivity components, we can just answer this query by looking at current state of the DSU.

(Actually I believe this can be implemented a little shorter if we pass the list of edges to the recursive procedure by value, but in this problem I was too paranoid about the TL to do that)

Thanks a lot. That is a very nice idea.

Just one clarification, in point 5 shouldn't it be removed with queries [b,n) instead of [c,n).

Fixed, thanks.

What is DSU with "rollback"?

G: Final order of numbers will be equivalent to sorting an array of pair(

digit_sum(i),i). Now instead if you iterate through sum of digits, you can find number of numbers ≤ N and with given sum of digits using dp. For any given sum of digits at most one number can be in its correct place, which you can find by binary search.where can i see the problems??

http://opencup.ru/files/ocf/gp14/problems2-e.pdf

It will be here — Ural Championship 2015

Here is a solution of problem D.

If k = 2^x, the answer is always yes (Obviously). Else if k = 2x-1 or k = 2x, then f(k), the minimal n for which the answer is yes, equals to 2x+1.

f(2*x-1) >= 2x+1. |> Lets consider the last step, on which number k was obtained. (a, b) -> (a-b, 2b). 2b can't be equal to 2x-1. Then a-b = 2x-1; a >= 2x; b >= 1; n >= a+b >= 2x+1 <|

f(2*x) >= 2x+1, x is not a power of 2. |> Let p be an odd prime divisor of x. Initially all numbers equal to 1, thus are not divisible by p. The following invariant takes place: there is always a number which is not divisible by p. Indeed, if (a, b) -> (a-b, 2b) and a-b and 2b are divisible by p, then a and b are divisible by p. That means, we can not obtain a situation where one number is equal to 2x, and all other numbers equal to 0. Therefore n >= 2x+1 <|

Now if n = 2x+1, how to obtain 2x and 2x-1? The trick is to divide all the substance in two parts of volumes a and b, one of which is a power of 2. Then repeat the action on the two tubes until we are done. Why this works? Let's concider an action (a, b) -> (a-b, 2b). Since a+b = n, (a-b, 2b) = (2a%n, 2b%n). Therefore after t steps (a, b) will turn into (2^t*a%n, 2^t*b%n). Since n is odd and one of (a, b) is a power of 2, after some steps, this number will turn into 1, and on the next step it will turn into 2. Then the other number will be n-1 and n-2.

The only thing left is to divide in two parts. Let 2^x be the biggest power of 2 which does not exceed n. First unite 2^x tubes into one. Then after y steps you have (n-2^x)/(2^y) rounded up pieces of volume 2^y and one piece containing all the remaining volume. On y-th step you divide pieces of volume 2^(y-1) into pairs and unite them. If one piece was left without pair, you append it with the remaining piece. After x steps you have one piece of volume 2^y and one more piece containing all the remaining substance.