There are some nice solutions from other guys (http://mirror.codeforces.com/blog/entry/9071) but they actually are not very handy. However, codeforces api provides us with a useful set of methods that makes tasks like this much easier.

So, you can download the script here and have fun with it.

Happy New Year, guys!

UPD: There were some IndentationErrors (github for some reason changes indentation). Thanks to Determinism who pointed to that. Now it should be fine.

First let's write a naive O(n^2) dynamic programming :

for (int i = 1; i <= n; i++) {
	d[i] = 1;
	for (int j = 1; j < i; j++) 
	  if (abs(a[i] - a[j]) >= k && d[j] + 1 > d[i]) 
	     d[i] = d[j] + 1;
}

Array d can be splitted into blocks(same value of d[i]). Let's consider second sample test, for example.
h = [2, 1, 3, 6, 9, 11, 7, 3, 20, 18]
d = [1, 1, 1, 2, 3, 3, 4, 5, 6, 6]
Blocks:
h: |2 1 3| 6| 9 11| 7| 3| 20 18|
d: |1 1 1| 2 | 3 3| 4| 5| 6 6|.

How can we optimize our DP? Well, after drawing samples on the paper one can notice that we are interested only in two largest blocks (two blocks that have the largest value of d ) at every moment (I will call them first and second). Let me show you exactly what I mean. We want to calculate d[i]. How can we do it? We either jump from the pillar that belongs to second block and then d[i] is d[second] + 1 or we jump from the pillar of the first block and d[i] = d[first] + 1 which equals to d[second]. But there is one more option. What if we can't get to i-th pillar from the two largest blocks..? Then we say we aren't interested in calculating d[i] because it is less than the values of d in our blocks. It can be strictly proved that we can avoid jumping to the i-th pillar, but take pillars from our blocks instead, by ananlyzing cases(h[i] is the largest among two blocks, smallest or inbetween).
So, the question is how can we check whether we can jump from the block to the current pillar. Just keep two variables id1 and id2 for every block, where id1 is position of the minima(smallest height) and maxima position in the block. After processing i-th pillar update id's.

There's a tricky case when d = 0(I was a bit surprised when I got ML 83 on the contest, lol ), then the answer in n. Hope you liked the solution. Good luck! =)

http://acm.mipt.ru/twiki/bin/view/Algorithms/BipartiteControllingSet Я читал здесь, но возникли проблемы с пониманием того, как мы добавляем свободную вершину. Знаю, что для многих это очевидно, тем не менее отпишитесь пожалуйста.