iakolzin's blog

Codeforces Beta Round #22 Tutorial
By iakolzin, 14 years ago, translation, In English

Contest discussion

Problem А. Second Order Statistics

Sorting

In this problem one should find a minimal element from all elements, that are strictly greater, then the minimal one or report that it doesn't exist. Of course, there can be a lot of different solutions, but one of the simplest - to sort the given sequence and print the first element, that's not equal to the previous. If all elements are equal, then the required element doesn't exist.

Problem B. Bargaining Table

Simulation, dynamic programming

In this problem one should find the maximal perimeter of a rectangle that contains no '1'. Define these rectangles "correct". To solve a problem you are to check each possible rectangle for correctness and calculate its perimeter. The easiest way to check all rectangles is using 6 nested cycles. Using 4 of them you fix the coordinates while other 2 will look for '1'. So the complexity is O((n*m)3). It seems slow, but those, who wrote such a solution, says that it hasn't any problems with TL.

One may interest in much faster solution. Using simple DP solution one can get a solution with an O((n*m)2) complexity. It's clear, that rectangle with coordinates (x1, y1, x2, y2) is correct if and only if rectangles (x1, y1, x2-1, y2) and (x1, y1, x2, y2-1) are correct, and board[x2][y2] = '0'. So each of rectangles can be checked in O(1) and totally there will be O((n*m)2) operations.

Problem C. System Administrator

Simulation

In this problem you are to construct a connected graph, which contains n vertexes and m edges, and if we delete vertex with number v, our graph stops being connected or to report that such a graph doesn't exist. Moreover, each pair of vertexes can have no more than one edge connecting them. Obviously, a connected graph doesn't exist if the number of edges is less than n-1. It's easy to notice, that the maximal possible number of edges reaches when there is a vertex connected to v and doesn't connected to any other vertex, those can form up to complete graph. So the maximal number of edges is (n-1)*(n-2)/2+1. If m is in that range then required graph always exists. Then you should place one vertex on the one side of v (let it be 1), and other vertexes - on the other side. First, you should connect all this vertexes to v and then connect them between each other (except 1).

Problem D. Segments

Scanning line

In this problem one should place minimal number of points on the line such that any given segment touches at least one of these points. Let's call the coordinate of ending of any segment as event. There will be events of two types: beginning of a segment and its ending. Let's sort this events by coordinates. In the case of equality of some events consider that the event of the beginning will be less than the event of ending. Look at our events from left to right: if there is a beginning event, then push the number of this segment to the special queue. Once we take an ending of some segment, place the point here and clear the special queue (because each of segment in this queue will touch this point).

Problem E. Scheme

Graph theory

Given an oriented graph, find the minimal number of edges one should add to this graph to make it strongly connected. Looking at statement we can get the fact that each vertex has exactly one outcoming edge. It means that starting at some point we'll get stuck in some cycle. So each connected (not strongly) component is a set of simple paths, ending in some cycle or just a simple cycle. First consider vertexes, which has no incoming edges. When passing through some vertex we'll paint it until the current vertex will be already painted. Then we call the starting vertex as "beginning" and the finishing one as "ending" of a component.

After that consider other vertexes - they belong to cycles. Beginning and ending of a cycle - is any vertexes (possible coinciding) belonging to it. So we got a number of components which we have to connect. Let's connect them cyclically: the edge will pass from the ending of i-th component to the beginning of ((i+1)%k)-th, where k is the number of such components. The answer will be k. There is an exception: if we have only one component which is a simple cycle, the answer will be equal to 0.

So we'll consider each edge exactly once and the total complexity will be O(n).

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

Comments Comments (15)
| Write comment?
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Some of your types seem incorrect... Problems B and C are not simulation. Simulation involves running some sort of given process (usually efficiently), and neither of these problems involve that. B is brute force / DP, and C is graph theory.

But the tutorial is great, thanks :) I can go fix my E now :D
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I am not solving E with tutorial's method, and I got Wrong Answer on test 15 for a long time. Did U get any trouble on test 15? Thanks.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      http://piratepad.net/ZosxPMMqyK

      There's my code for it. It passes 15, but gets RE on Test 22. I'm really not sure why. Tell me if you can find it, and hopefully it helps you with yours!
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it
        You have stack overflow in dfs. Stack for default thread in java is not very big, you can avoid it by creating your own thread and executing code in it, like
        class Sample implements Runnable {
        public static void main(String[] args) {
        new Thread(new Sample()).start();
        }

        public void run() {
        //Solution here
        }
        }

        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Thanks (to Ivan too)!

          I really shouldn't have missed that... though I didn't know that a new Thread could get extra stack space. Most interesting.

          I've got AC now and I've updated my code :D
          → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        new Thread(null, new Sample(), "1", 1<<23).start(); - 8 megabytes stack.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
problem C may also be solved using a stack + dp, which gives an extremely fast O(mn) solution
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    *problem B

    ps: there really should be an edit function for comments
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Could you give more details for the O(mn) solution?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        its a fairly standard solution
        its the same as the "largest rectangle in a histogram" problem except now you're looking for maximal perimeter, and you need to do a dp preprocessing
        the "largest rectangle in a histogram" solution is here: http://homeofcox-cs.blogspot.com/2010/04/max-rectangle-in-histogram-problem.html
        → Reply
    • 6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have written this O(m*m*n) solution for problem B https://codeforces.net/contest/22/submission/54368605 I am unable to think of any better approach. Can you please provide working code for O(m*n) solution. Thanks in Advance.

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

        praveenojha33 Can you please give a short explanation of your code. Thanks in advance!

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

          Do you know about maximum submatrix sum in a 2D matrix using Kadane Algorithm. If not you can watch it here https://www.youtube.com/watch?v=yCQN096CwWM

          The problem is same as finding submatrix sum in 2D matrix this can be done using either O(n^4) approach using 2D prefix sum or using Kadane Algorithm in O(n^3). As you know Kadane Algorithm is O(n) and in 2D Kadane Algorithm we divide 2D matrix in n^2 submatrices that is from column (1-1),(1-2),(1-3),(1-4),(2-2),(2-3),(2-4),(3-3),(3-4),(4-4) and then apply kadane Algorithm to find max sum in that rectagular strip.

          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
the complexity of my solution of problem B is O(m^2 * n).
→ Reply