Codeforces beta round #27 just finished. It was a great contest. I really enjoyed it.

Here is the problems:

let's take a look at them and see if they can be solved.

We start at problem A:

We're given a set of numbers and we want to find the smallest number which is not in the list. This is easy. Take a boolean array of size 3000 and name it a. we assume a[i]=true iff i is present in the set. It's easy to update our array,And for giving input we just start at a[1] and go through until we find a false,then we would print its index.

Our algorithm for this question is O(n+3000)

Now let's move through Problem B:

I solved it like this:

I got two arrays of size n (number of participants). the first one was named play and the second was named won. play[i] indicates how many input lines contained i. and won[i] denotes number of times i has won. Of course for each participant we have play[i]=n-1 except for those two in the missing line , for them play[j]=n-2.

so we take a look through our play array and find out those with value n-2. let's call them u and v. Then we check won[u] & won[v]. If one of these is greater then of course that person has a better ability to sleep and wins.If they have same play then we can't find out which one was the winner and any ordering of their numbers is all right.

here's my code for this one:

This solution is O(n) so it works perfectly well in the given time limit.

Now we reached Problem C:

We have the input array. assume that second item>= first item. We start going through the array.The numbers rise to some point and then decrease.At the point where the rise ends and we start to decrease we have a number which is greater than one of the items before it and is certainly greater than the next item.These 3 provide our answer.

I think I didn't explain it well, Here's my CPP code:

It's obvious that this algorithm is O(n).

Here's my solution for Problem D:

If we have two edges on the same side (inside or outside).They will intersect iff their segments intersect. Think of two edges on the same side one from i to j and the other from u to v.Then these edges intersect iff (i,j) & (u,v) intersect.We make a graph for the problem in this way:

for each of the m new edges we put a vertex in our graph.Two vertices are adjacent iff when we put their corresponding edges on the same side,they intersect.for example the vertex (6,10) is adjacent to (9,12) but is not adjacent to (1,5).

note: If (i,j) is completely inside (u,v) we assume they don't intersect.

note: we use (6,10) not [6,10] as mentioned in the problem statement.

Now we can't place edges corresponding to adjacent vertices on the same side. so It's possible to do what problem wants if and only if our graph is bipartite.It's easy to check for this one and of course it's easy to make 'i's and 'o's afterwards.

Well this algorithm takes O(n^3) time in worst case with the most simplistic coding. As M<=100 , it works well. (We know that a normal computer can do 10^8 calculations per second)