HolkinPV's blog

Codeforces Round #163 (Div. 2) Tutorial
By HolkinPV, 12 years ago, translation, In English

266A - Stones on the Table

In this problem you should count number of consecutive pairs of equal letters. It can be done using one cycle and O(N) time.

266B - Queue at the School

In this you should realize the given process. You should t times swap elements i and i + 1 if on the place i was a girl and on the place i + 1 was a boy. You should not push some girl to the left multiple times at once. The solution can be written using O(N·T) time.

266C - Below the Diagonal

This problem can be solved using constructive algorithm. We will use inductive approach. At first, we have matrix of size n and n - 1 ones in it. Therefore, there is a column with no ones in it. So, we put this column to n-th place. In this case, the lower right element will be 0. Then find any row with at least one integer one and put it to the n-th place.

After these operations the element in cell (n, n) equals to 0 and the last row has at least one integer one. Therefore, we can reduce the dimension of our problem, that is n:  = n - 1. In our new problem we have no more than n - 2 ones. So, we can solve this problem using the same algorithm. When n equals to 1 you should finish algorithm, because there is no ones left. This algorithm uses O(N) swap operations, no more than two for every n.

266D - BerDonalds

I'll tell a few ideas how to solve this problem. Firstly, describe the solution with time O(N4). Consider every edge (u, v) of length len where could be the answer point. Let this point lie at a distance x from vertex u. So, the distance from this point to vertex i would be min(x + d[u][i], len–x + d[v][i]), where d[x][y] — distance between vertices x and y. Equate these values and get the critical value x for vertex i, x = (len + d[v][i]–d[u][i]) / 2. It follows that the answer to the problem is half-integer. So, for every edge and every other vertex we get set of critical points. We should check them all include the vertices of the graph (ends of the segments). This solution may probably pass with some optimizations.

Another solution with complexity O(N3·log2). Multiply all weights by 2. Consider every edge where should be the answer and make binary search for the answer (in integers). To check some current value you should consider every vertex i and assume that the answer is achieved in this vertex. In this case, the answer point must lie on this edge <= some value l[i] or >= some value r[i]. This subproblem is solved using offline algorithm using sorting events and maintaining the balance.

Also, you can use ternary search on every edge of the graph. But you should divide every edge on several segments and find the answer on every segment, because the ternary search is incorrect in this problem.

The last two solutions can provide accepted, if you realize them carefully. Also note, that there is the solution with complexity O(N3) by the author RAD.

266E - More Queries to Array...

This problem can be solved using data structure. We would use segment tree, we will support k segment trees for every power. At every vertex we will calculate weighted sum of the appropriate power, also we will save some number that indicates the color of the whole segment, if any.

User Egor in comments to the post and user mexmans in comments to the tutorial tell their formula to get the answer. I try to describe how to get them by yourself. Firstly, you should write what value your segment tree gives. The tree can calculate the sum . You need to calculate the sum , you can write it also as . Then you should write the last sum for some first powers (at least three) (at piece of paper) and subtract the second sum (what you need) from the first sum (what your tree can calculate). You get an expression that describes what should be subtracted to get the answer from the value what you tree can calculate. This is just the Newton binomial without the highest power.

So, the answer for power j is expressed as the subtraction of the value of query to your segment tree and the Newton binomial, with all powers that are less than j (these values can also calculated using your segment tree). Partial sum of the powers and binomial coefficients can be precalced. The solution has the complexity O(N·K·log(N)).

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (41)
| Write comment?
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

tutorials for d & e?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

For D i tried the following approach but somehow couldn't finish debugging it. 

For all those vertices v whose eccentricity == radius of graph:
        For all the adjoining edges of v i.e. edge(v,x):
                Binary Search for the location l on the edge (v,x) which minimizes graph    
                radius considering l as a vertex
                Keep track of minimum of all such graph radii

Will it work ?

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem C the important part is how can you find the 0 row fast (I mean the row with all numbers 0 in it), because you do it O(N) times and naive way (O(N^2)) is not sufficient. I used some dynamic arrays and updated them after each swap. For me the difficulty was in implementation and not in the algorithm, I got it in about 5 minutes.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    n = 1000 whats the problem with n^2 algo?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      you do N^2 thing O(N) times, in total it becomes O(N^3). I mean in O(N) times you will have to find 0 row in remaining square. That's not a straightforward thing to do, for me it was harder than the part that is written in the tutorial.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it 
        you have O(n) phases (O(n) swaps to make):
    each phase you search for the appropriate column //O(n)
    you perform the swap in O(n)

        the two steps are independent, so this gives O(n^2), which is feasible. you just need an array of size n counting the number of ones in each column to search for the appropriate column in O(n)

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          that's what I did actually

          → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

D and E ? at least some hint ?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like it

    E: 1) Let's understand how to solve this problem if k for all queries to calculate the sum is equal to 0. It's quite easy to do it: we can just use a segment tree.

    2) Let's learn to answer queries where k is greater than zero. Let's assume that we know a correct answer for a node's left child and right child. We need to merge node's children answers. To do it, we can figure out the following formula: answer for current node and power k ans[k] = ans_left[k] + ans_right[k] + sum for all 1 <= j <= k ans_right[k — j] * L ^ j * c[k][j], where ans_left and ans_right are the answers for node's children, c[k][j] is a binomial coefficient and L is the length of a segment represented by the left child of the node.

    3) However, we still don't know how to process assign queries. But this is rather simple: if we precalculate prefix sums for all powers, we'll be able to find a value for a certain node in a tree in constant time even if its value has been updated.

    Such solutuion works in O(N + M log N) time.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It seems that I had underestimated the C problem — very interesting idea to solve it.
Thanks for tutorial!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could I solve D Problem, using Hakimi algo, for searching an absolute center of Graph?

Article in Russian is here:

http://www.uchimatchast.ru/teory/abs_center.php

(algo in the bottom of the page)

→ Reply
»
12 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

For problem C there is an O(n) solution. 2997252 (this is not my original idea, i learnt it from 2993213 and edit the swap part to make it O(n)) The main idea is that after j steps, for all 1<k<=j, kth marked cell will lies in column 1 to k, row c+1(c=its column number) to j+1.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

a

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Tutorial for chinese version chick here

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My idea for problem D is using ford-bellman, then with every edge[i], I find the furthest way from edge[i].x, from edge[i].y without pass through the edge[i] and determine the point, but I get WA. Anyone can explain, or have a wrong test case for that ? Thank you for helping, and sorry for my poor english :).

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    open your submission, you'll find the test cases below your code, and you'll find the one that gives your WA.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know about that, but that one is too big.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        How do you determinate the point on edge? You can't use ternary search, because function on it isn't convex

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          point = ( furthest(edge[i].x) — furthest(edge[i].y) + edge[i].w )/2; Is it right ?

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            No, it isn't. I thought so too, but Egor said me, that function on the edge is piece-wise linear. So you must disintegrate it on the segments. I'm still thinking, how to do it

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              there is a Monotonicity when the answer(ans) is increasing , you will find more such points that satisfy the condition Max_shortest_distance <= ans,so i think you can try binary search of this problem .

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Have you passed the solution? If yes, please write the idea :)

              → Reply
»
12 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Still waiting for D and E solutions...

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think you also should provide the link to good code for each problem in contest with each problems explanation in tutorial. [ Best : Good and nice implementation and better complexity]

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

tutorials for D & E pls!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You can find editorial for D from problem C at here.

    Hope someone can do some explanation on E!

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      thanks, nice explanation of problem D

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry but I don't think so: In the discussion of D we read: " It follows that the answer to the problem is half-integer. So, for every edge and every other vertex we get set of critical points. We should check them all include the vertices of the graph (ends of the segments). This solution may probably pass with some optimizations." I don't think that it is true for the 3-rd example. Even if not so, the proof is quite ambiguous.

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      whats that?

      there are only solutions. where to read problems ?

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      a

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Great source for learning the Min. Diameter Spanning Tree but the link seems to be broken. Here's the web archive link for the pdf: Link

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my approach that gets WA.. but i don't know why..

First i compute the shortest distance between pairs using floyd warshal, then iterate all pairs getting the furthest node to each one of them.. then using binary search i get the optimal place on the road of those pair.. getting the min for every pair and printing it.

Can anybody tell me whats the problem of my solution?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The tags for Div2B include Max flow. Can anyone elaborate on how to model this problem as a graph?

→ Reply