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).
But the tutorial is great, thanks :) I can go fix my E now :D
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!
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
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
random.johnnyh Can you please elucidate?
I have written this O(m*m*n) solution for problem B https://codeforces.me/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.
praveenojha33 Can you please give a short explanation of your code. Thanks in advance!
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.