Here you have the link to the Problem Statement.

My Solution:

vector <int> find(vector <int> h) {
	vector<pair<int, int> > a, v(h.size());
	vector<int> ans;
	int i, j;
	for(i = 0; i < h.size(); ++i) {
		v[i] = make_pair(h[i], i);
	}
	sort(v.begin(), v.end());
	for(i = 0; i < v.size(); ++i) {
		for(j = 0; j < a.size() && a[j].first == v[i].first; ++j);
		if(j != a.size() && a[j].second > v[i].second) {
			a.insert(a.begin() + j, v[i]);
		}
		else {
			a.push_back(v[i]);
		}
	}
	for(i = 0; i < a.size(); ++i) {
		ans.push_back(a[i].second);
	}
	return ans;
}

My solution description:

I sort the tower by heights and then add the towers to the solution vector, in order, by height. The i-th tower is added at the beginning or at the end part of the solution vector, such that the vector is lexicographically the smallest(though, if there are equal values, I make sure that when they are inserted, they are in increasing order of indexes in the final solution vector).

My solution is based on the following two observations:

1. The minimum distance between the first and the last tower is equal to the sum of all heights minus the minimum distance.

2. To obtain an arrangement of the towers that has the minimum distance between the first and the last towers we can go through the tower heights either from the maximum to the minimum element and add the current height to one of the extremities of the free space in the final vector, either from the minimum to the maximum and add the current height to the border of the existing vector.

My problem is that I can't prove these two(1. and 2.) statements. Will you please help me?

What would be the shortest piece of code that you would write in a contest for normalizing an array of distinct numbers? What about the most efficient?

e.g.: [102, 980, 2, 45] --> [2,3,0,1]

This is how I'm currently doing it — I'm looking for "better" ways of doing it:

vector<int> normalize(vector<int> A) {
    vector<int> S(A), N(A.size());
    sort(S.begin(), S.end());
    for(int i = 0; i < A.size(); ++i) {
        N[i] = lower_bound(S.begin(), S.end(), A[i]) - S.begin();
    }
    return N;
}

Please leave your solution in the comments section! Thank you!

I believe that it would be nice to have a link for each contest which would take us to a short description of that contest. This would be valid for both past contests and upcoming ones. Why do I ask for that? Well, new contests have appeared lately on the codeforces site, besides the beta rounds for the 1st and the 2nd division; for example school contests ( teams/personal ), testing rounds, alpha rounds, unknown language and, lately, Manhattan  Manthan 2011.
What is the Manhattan Manthan 2011 contest? This kind of questions should be answered in the description page. Also, after the contest, it would be nice to have on this page a link to a community written and aproved editorial. I think this features would bring a little more functionality to the site, because now people of the codeforces community have to do a lot of searches to find out some things that should be very easy to find. Thank you!

Contribution Game! These things make a good sociological study!
What do you think? Is the contribution rating a good indicator on how much you've helped the site - or it can be easily manipulated, by playing with other people and making them give you plus or minus?

Finally, another promotion ( chicken yellow :D )! I am a captain now! Lately(the last couple of months) things are goin pretty good in sports programming contests, but I am afraid I will not be able to maintain my new level.
So, open question:
 What should I do to maintain my rating and/or increase it now? I need to say that I'm not sure why things are going good in sports programming lately. Please leave comments!

Long time no hear!
Now I have a question, whose answer I don't know.

Take the following piece of code:

n>?=m;

How does it work? And why? Does this work in C? Or only in C++? Or viceversa? Or both?
Does the question mark have any connection with the ternary operator ( ?: ) and/or operator precedence ?
If you know the answer please leave a comment.

I have found something new on the matter, now that I have received some comments: see link

I'm writing a new post after a long time here ( and I have also participated in CF#41 ). In this post I would like to approach the problem of the code that is found in users'solutions and it is not used. I understand that this is a method of speeding up the process of writing a solution, but it is really annoying when trying to hack. I know that on TopCoder there is a very strict rule about this ( maybe too strict if you ask me ) and that here there doesn't exist such a rule. I have seen this extra code before, but it didn't bother me. This time it was just too much. One person in my room had hundreds, if not more than 1000 lines of code, of which less than 100 were actual code for solving the problem.

I'm writing this, hoping that some rules wich would prevent this from happenning again will be taken into consideration by the CodeForces Team.         Thank you.

Given two large natural numers A and B ( A, B >= 2⁶⁴ ) find their quotient q and remainder r, where A = B * q + r,
0 <=  r < B. How do you solve this problem? Please post comments ( solution, code ). I mention I would be interested in seeing the code for the schoolbook algorithm and in seeing what would be the simplest way to code division without using libraries for Big Integers.

A median problem - Solution

Finally, I post the solution to the problem from the Microsoft interview, that I, long ago, promissed to do. Sorry for the delay. I have received on my email solutions from SCQ =) and Vasya V. ( solution6 ), from Harta a solution similar to solution4 and solution7 due to Nyaz Nigmatullin. Thanks all.
Note: Read solution5 for the O ( lg n ) algorithm.

Statement

You are given two sorted sequences of 32-bit integer numbers. Find the median of the sequence obtained by concatening the two sequences.(Update: By sequence I don't mean the STL one; a simple C array would do - anything with constant random acces).

Solution1.

Simple and obvious: concatenate the two sequences( O ( n ) ) and sort them ( O ( n² ), O ( n lg n ) ). Then output the element in the middle.

Solution2.

Also simple and obvious: Merge ( O( n ) ) the two sequences and output the element in the middle. Merging can be done in-place and can be stable: see here.

Solution3.

As we only need the median element, we can adapt the simple clasical merging ( still O ( n ) time, but now O ( 1 ) additional memory ) to our problem. Instead of merging the whole amount of elements, we merge only half ( to get to our median element ) and instead of keeping the whole amount of merged elements in a separate array, we can keep only the last element in this sequence. Some code for this:

median(int a[], int b[], int n, int m)
    int i, j, k;
    i = j = 0;
    while ( i < n && j < m && i + j < ( n + m ) / 2 )
        if ( a [ i ] < b [ j ] )
            k = a [ i ]
            i ++
        else
            k = b [ j ]
            j ++
    if ( i < n && i + j < ( n + m ) / 2 )
        i = i + ( n + m ) / 2 - ( i + j )
        k = a [ i ]
    if ( j < n && i + j < ( n + m ) / 2 )
        j = j + ( n + m ) / 2 - ( i + j )
        k = a [ j ]
    return k

Solution4.

Suppose the 2 sequences are a and b, 0 indexed and have sizes m and n. Also suppose that the median element is in the first sequence. Then we can binary search it.
Given an element in the first sequence we can find out, also using binary search, which order of statistics it is.
Suppose we choose the k-th element in the first sequence( a [ k ] ). Then we know there are k elements in the first sequence that are <= a[k]. We can find, in the second sequence, using binary search, the position kp for which b [ kp ] <= a [ k ] < b [ kp + 1 ] ( if a [ k ] is smaller/greater than all elements in b the we take kp to be -1/n ), that is the position after which a [ k ] would be inserted in sequence b, such that the sequence remains sorted. Then we know there are kp + 1 elements smaller in the sequence b. So our element a [ k ] is larger than
 k + kp + 1 elements in the union of the two sequences a and b.
Now, given two elements a [ x ] and a [ y ] with x < y, we know that a [ x ] 's order of statistics is smaller than
a [ y ] 's( if x + kx is the order of statistics of a [ x ] then a [ y ] 's order of statistics is at least y + kx which is greater than x + kx ).
So we can binary search in the first sequence the element with order of statistics ( m + n ) / 2. If no such element is found then we search it in the second sequence.
Final complexity O ( lg² ( n ) ).

Solution5.

We notice, in solution4 that when we check if an element is the median, we do not need to find its order of statistics - we only need to check it its order of statistics is equal or not with n / 2.
Suppose that our element a [ k ] is the median => a [ k ] >= than ( ( m + n ) / 2 ) - 1 elements in the union of the sequnces a and b -- k elements in a and ( ( m + n ) / 2 ) - 1 - k in b.
So if b [ ( ( m + n ) / 2 ) - 1 - k ] <= a [ k ] < b [ ( ( m + n ) / 2 ) - 1 - k + 1 ] then our element
a [ k ] is the median. If the inequality doesn't hold our element is not the median.
As we know we can binary search in the first sequence the element with order of statistics
( m + n ) / 2 and if not found in the first sequence, we can search it in the second sequence,
the final complexity is O ( log ( n ) ).

Solution6.

Another solution would take advantage of the fact that the numbers are 32 bit integers. We can binary search our median in the interval [ - 2³¹, 2³¹ - 1 ]. For each number x in there we can find how many numbers are smaller than x in the two sequences by applying the binary search algorithm on each of them. We also need to be careful, because x must be in one of the two sequences. Final complexity O (lg n).
Note: This algorithm has a hidden constant of 32 which on the general case when integers that are restricted to an interval of size S the algorithm has a complexity of O ( lg ( S ) * lg ( n ) ).

Solution7.

The following solution I received via email and although I can see it is some form of binary search, I hadn't have the time to understand what it does. So here is the source code, as sent, without explanations.
Some java code for this(due to Niyaz Nigmatullin):

int solve2(int[] a, int[] b) {
        if (a.length > b.length) {
            int[] t = a;
            a = b;
            b = t;
        }
        int left1 = 0, right1 = a.length - 1;
        int left2 = 0, right2 = b.length - 1;
        int cur1 = 0, cur2 = (a.length + b.length - 1) / 2;
        while (true) {
            boolean ok = right1 == left1 + 1 && right2 == left2 + 1;
            if (a[cur1] == b[cur2]) {
                return a[cur1];
            }
            if (a[cur1] < b[cur2]) {
                int d = Math.min((cur2 - left2 + 1) / 2,
                                 (right1 - cur1 + 1) / 2);
                if (d == 0) {
                    return cur2 == 0 ? a[cur1] : Math.max(b[cur2 - 1], a[cur1]);
                }
                left1 = cur1;
                right2 = cur2;
                cur1 += d;
                cur2 -= d;
            } else {
                int d = Math.min((cur1 - left1 + 1) / 2,
                                 (right2 - cur2 + 1) / 2);
                if (d == 0) {
                    return cur1 == 0 ? b[cur2] : Math.max(a[cur1 - 1], b[cur2]);
                }
                right1 = cur1;
                left2 = cur2;
                cur1 -= d;
                cur2 += d;
            }
            if (ok && left1 + 1 == right1 && left2 + 1 == right2) {
                int[] c = { a[left1], a[right1], b[left2], b[right2] };
                Arrays.sort(c);
                return c[1];
            }
        }
    }

If you have any questions, requests, comments, corrections to make please feel free to post. Thanks and, again sorry for the delay.
Oh, and if you can explain solution7 please do.

At ACM ICPC SEERC 2009 was this problem:
   Problem E.
I need a hint to solve it. My instinct tells me that some sort of dynamic programming would do. But I can't figure it out.

On this site.
If I am on my profile page and click rating tab, someone else appears to me in the box on the top right. This ussually happens after a contest.
L.E.: Now I've tried it again and now there aren't any changes in the box. It's always me. Maybe something happens during the actualization of the ratings?

This is a sort of a bookmark entry for my use. It will mostly contain linksfrom this site that are/were/wiil be interesting to me. If you can use them it's fine, but I write this entry for myself. Hope that those that check the "Recent actions" table won't be annoyed if this pops out every now and then(or even more often).

PetrMitrichev SaoPaolo training
BBCup2010R2FatHobsSol
NiceDecompositionProblem?
TutorialsNStuff
SomeLinks
?
DP
More DP

P.S.: Why everytime I edit this it automatically inserts "календари" at tags?
           Well,  it seems that not everytime...

Today, 6th of  July at 4:21:58 AM uwi sent a solution in Java to Codeforces Beta Round #22's problem E-Scheme.
See wreckage.
HAHA!!!

A couple of weeks ago one of my colleagues at college asked me if I could find the solution to this problem that was in a Microsoft interview. I thought about it and later that night I had a couple of solutions including the O(NlgN)  O(lgN) one (reading the sequences is counted out ) that was required for it. Next morning I also had an implementation in C++ of the solution which worked fine. Now if you want to take a shot at it, the problem statement goes like this:

You are given two sorted sequences of 32-bit integer numbers. Find the median of the sequence obtained by concatening the two sequences.

I will later post the solutions I found, because I like the sort of trade-off that appears whilst you improve your solution's execution time. But I don't want to spoil all the fun. So, for now, I will leave you the time to solve it. If you want to step up, you can e-mail me the solutions at [email protected] and I will post the names of the best 10 solvers in the solution post.

P.S.: Regarding round #17 and #18, I was very busy with the exams and I didn't have the time to participate at them. But I took my shot at round #20 and came out 9th and hopefully I will be free to take my shot at round #19.

UPD1. Thanks to fcdkbear for pointing out that I requested an O(NlgN) algorithm.
UPD2. The two sequences are stored in arrays, so you have random acces to the elements.

There seems to be a limit in the number of  displayed solutions.