FunkyCat's blog

Codeforces Round #212 (Div. 2). Tutorial. Part 1.
By FunkyCat, 11 years ago, translation, In English

362A - Two Semiknights Meet

Autors have proposed different solutions. One can notice that if semiknights did not have a meeting after first step (it is not necessary they have a meeting in "good" square), they will not meet at all. This fact appears from board size and possible semiknight's moves. As the initial semiknight's squares are considered good for the meeting the semiknights have arrived to the one square and then they move together to one of the initial squares and meeting will count.

362B - Petya and Staircases

One has to note that the number of dirty stairs  ≤ 3000. Petya can reach stair number n if the first and the last stairs are not dirty and there are not three or more dirty stairs in a row. So let sort the array of dirty stairs and go through it, checking for three or more consecutive dirty stairs. Also one need to check if the first or the last stair is in this array.

362C - Insertion Sort

The number of times swap is called equals the number of inversions in the input permutation. It’s easy to see that it is reasonable to swap only such elements ai, aj that i < j and ai > aj (otherwise the number of inversions will increase). Let di, j be the number of permutation of elements with indices from 0 to i inclusive which are strictly less than j. Then, after swapping elements with indices i and j, the number of inversions will be old - 2 * (di, ai + dj, aj - di, aj - dj, ai) - 1, where old is the number of inversions in the initial permutation. It is sufficient to search all pairs of elements and pick those which help to minimize the number of inversions. The reader may prove the correctness of the formula as a supplementary task.

362D - Fools and Foolproof Roads

If the given graph contains less than q connectivity components, then there’s no solution. Otherwise it’s optimal at first add edges that connect different components and afterwards all remaining edges (they will be connect edges from one component). For the first phase you can use greedy algorithm: each time you select two components, current weight of which is minimal, and connect them with an edge. For example, you can store weights of all components in the current graph in some data structure (like set in С++). For the second phase it’s enough to find any component that contains two or more vertices (because loops are forbidden) and add all remaining edges between some two vertices of this component. If some action cannot be successfully executed (for example, you added all the edges and number of connectivity components if greater than q), then there’s no solution.

Asymptotics — O(n + m + plogn).

362E - Petya and Pipes

Construct the following flow network. Water tank 1 is the source, water tank n is the sink. Every pipe from water tank u to water tank v is presented as two arcs — the first one with capacity cuv and cost 0 and the second one with infinite capacity and cost 1. Thus, the answer is the maximum flow with cost not greater than k. It can be found by standard augmenting paths algorithm.

UPD1. Tutorial for problems A and B added. UPD2. Tutorial for problem C added.

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

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

can you give an explanation/proof for the fact used to solve problem A? (if semiknights cannot meet in the first step they cannot meet later)

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

    Bruteforce?

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

    I recommend you to draw the usable (or reachable) cells of the chess board from (1,1), you will realize that there are just a few valid cells to meet, and even less taking into account the invalid (#) cells.

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

    I think the fact you find just hold when n is small. I recommand you to find a way to solve the problem no matter how large n is(of course not too lager). During the hack, I find a solution that calculate the position of two knights difference Mod 4. And I think that is the point to the problem. If (a[0] — a[1]) % 4 != 0 || (b[0] — b[1]) % 4 != 0, ans is no. else yes. Sorry for my poor English.

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

      yes, I thought this way too. It's quite obvious. If two knights can meet each other, afterwards we can think about them as an unit entity and move this entity to the initial position of any of two knights by reverse sequence of moves of this knight. Because this position is available for meeting, we are just about to check if one knight can reach the initial position of the second knight — your conditions just check it right.

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

      I don't understand problem A. You say that "If (a[0] — a[1]) % 4 != 0 || (b[0] — b[1]) % 4 != 0, ans is no. else yes."

      But these knights can move: "2 squares forward and 2 squares to the right, 2 squares forward and 2 squares to the left, 2 squares backward and 2 to the right and 2 squares backward and 2 to the left."

      So ..., a knight at (4,1) can jump to (6,3). In the following example, the two knights meet and ((x1-x2)%4==2 && (y1-y2)%4==2)==true 

      1
........
........
......#.
K..##..#
.......#
..K##..#
......#.
........
      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Every step knight leaves the position where he is.

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

          OK, thanks. I get it: they move at the same time

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

Can someone please explain the solution to C again? Some of the accepted solutions appear to be using BIT tree to solve the question. What's the logic behind it? Thanks.

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

    Here is the logic i used for problem C

    let's name the array A

    for any value at index i ... The number of swap function calls related to this number is equal to the number of values greater than A[i] in the segment A[:i] ...

    So for every index i ... I store the number of values greater, and smaller than A[i] in every segment A[:j] (0 <= j < N)

    Now when I change the position of some value to an index greater than its intial index ... The total number of swaps decreases (or increases) by the factor Bigger[i][j]-Bigger[i][i] + Smaller[i][i] — Smaller[i][j], where i is the initial index and j is the new index , We will need to reverse that expression in case of moving from j to i

    Now i try every possible swap between 2 elements (i,j where j>i) calculating the change due to change of position of A[i] and change of position of A[j], and take the swap with the best benefit.

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

      and also if you are computing number of swap before swapping on of those pairs you have to increase your ans by one because you are counting the number of change in swap of that pair twice in this formula.

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

Regarding Question E: Does mincost maxflow also allow us to find the maximum flow within a particular cost ? [ I am concerned as to how would I find this statement: "answer is the maximum flow with cost not greater than k" ]

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

    +1

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

    In this problem, we are trying to solve the "minimum cost flow" problem, rather than the "minimum-cost max-flow". This more general solution is useful here because we can fix a flow amount and check whether the cost goes over K. So some people used binary search with the "min-cost-flow" algorithm, rather than just using the min-cost-max-flow algorithm (which is a special case). The binary search thing works here because the cost increases with flow (this might not always be the case).

    Alternatively, if I recall correctly, if you use an "augmenting path" based approach for solving the min-cost max-flow problem, each time you augment the flow by an augmenting path, you actually have the minimum cost for that specific flow amount. I don't remember a direct proof of this, sorry. But it may be useful to think about how one might solve the minimum-cost flow problem using a minimum-cost max-flow algorithm.

    So, in my solution, I first augmented as much as possible without any cost. And then I augmented by 1 flow unit at a time, keeping track of the cost used so far. Once it became greater than K, I stopped and returned the previous answer. This also worked because the cost increases with flow (i.e.: there is never a time where you increase the flow but the cost goes down). That's definitely not true in general though.

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

      Instead of augmenting by 1 you can augment by min((k-costsofar)/cost_for_reaching_sink,maxflow).

      → Reply