195A - Let's Watch Football

The whole video will be downloaded in all = (c·a + b - 1) / b seconds. In this problem you can choose every 1 <  = t <  = all as an answer. To fulfill coditions of the problem it is enough to check the condition t0·b >  = (t0 - t)·a at the moment of time t0 = all.

195B - After Training

In this problem you should carefully implement the given process. Firstly note that ball number i > m will be in the same basket as ball number i - m. Therefore it is enough to distribute first m balls. It can be done using two pointers lf, rg from the middle. Alternately put one ball to the left and to the right and shift pointers. In only case you should shift left pointer twice in the first moment of time if m is odd.

195C - Try and Catch

In this problem you was to implement what was writen in the statement. In my solution I did the following. Erase all spaces from the text except spaces in messages in try-catch blocks. Then when we get word "try" we put number of the new try-catch block in stack. When we get word "throw" we remember it's type and current state of stack (that is what try-catch blocks are opened). For example, put these number in set. When we get word "catch" if it's type equals to type of operator "throw" and the number of current try-catch block is in your set then write the answer now else erase this try-catch block from stack. If there was no suitable try-catch block write "Unhandled Exception".

195D - Analyzing Polyline

Tutorial by author Igor_Kudryashov

In fact in this problem we were given lines y_i = k_i * x + b_i but negative values were replaced by zero. Your task was to find the number of angles that do not equal 180 degrees in the graph s(x), that is the sum of the given functions.

Firstly note that sum of two lines is also line. Indeed y = y₁ + y₂ is y = k₁ * x + b₁ + k₂ * x + b₂ = (k₁ + k₂) * x + (b₁ + b₂).

Consider points where y_i = 0, that is x_i =  - b_i / k_i. While we assume that k_i doesn't equal to 0. Then line number i is divided in two lines one of which identically equals to 0. Consider all different points x_i and sort them. Then, obviously, the sum of the given functions between two consecutive points is line. Find the equation of the line. Assume that we consider point i from the left. Then equation of the line between points i and i + 1 will not be equal to equation of the line between points i and i - 1. That is in point i is formed an angle that doesn't equal 180 degrees.

So we should find equations of lines between every pair of points i and i + 1. It can be easily done using two arrays with queries of increasing value on the interval offline.

195E - Building Forest

Tutorial by author Fefer_Ivan

The longest operation in this problem is to find the root of some vertex and the sum of the path to this root. To find these values fast we will use compression ways heuristics which is used in data structure "disjoint-set-union".

For every vertex v we keep two values : c[v] and sum[v]. c[v] = v, if v — root, else c[v] — next vertex on path from v to root. sum[v] = sum of lengths of edges on path from v to c[v].

To add new edge from u to v of length w it is enough to do c[u] = v and sum[u] = w.

Note that we only add new edges (we don't erase edges).

That is, if we find root(v) and depth(v) for some vertex v we can assign c[v] = root(v),

Unable to parse markup [type=CF_TEX]

int root(int v){  
   if(c[v] == v){  
       return v;  
   }else{  
       int u = root(c[v]);  
       sum[v] = (sum[c[v]] + sum[v]) % M;  
       c[v] = u;  
       return u;  
   }  
}  

It can proved that such implementation works using O(log(n)) time for every query. The complexity of the solution is O(n * log(n)).