But they failed to provide it during contest time. Hope good luck for next time.

I coded in c++ and have +220. Feeling WOW!!

It is easy to see that you need send car from left leaf to second left, from third left to fourth left, and so on. So, two bottom levels are removed, and repeat.

UPD: And so we have something looks like

its dp[0]=1; dp[1]=1; for all i=2 to n dp[i]=dp[i-1]+2*dp[i-2];

its Jacobsthal sequence sequence http://oeis.org/A001045

Alternatively:

If you run one car from the leftmost leaf to the rightmost leaf of the tree, what's left is a sequence of pairs of smaller trees with heights 0,1,..,treeHeight-2.

А можешь описать идею в общих чертах?

о, я только после прочтения коммента понял что тоже решал не то

Задача "на сколько возрастающих подпоследовательностей можно разбить последовательность" решается за n log n, ответ — длина максимальной невозрастающей подпоследовательности.

"На сколько" это просто длина наибольшей убывающей подпоследовательности.

Теорема Дилворта тогда.

Её можно и без переформулировки решать. Надо просто идти слева направо и поддерживать множество последовательностей на которые разбит префикс(оптимальное), а дальше жадно добавлять куда можем(кстати такой алгоритм даёт и наибольшую неубывающию последовательность)

А как решается с оригинальной формулировкой?

same here I used OEIS :)

step 1 . choose 3 color

step 2 . choose 1 point for each 3 color O(n^3)

step 3 . check them . if this triangle covers black points increase ans ;

in step 3 if u dont know how to check any point is inside the triangle trick is if any pair of points in triangle (p1,p2) if ccw(p1,p2,p3)!=ccw(p1,p2,point) point is outside else inside

more eficient way is choose 2 points and use binary search for 3.point or another way is for each pair of colors find pair of points that not divides black points O(n^2)

Here is another algorithm in O(MMN). I observed that for all valid triangles, two of the three pairs of the vertices are chosen from the two perpendicular sides of the M*M square. Thus we can count them by going through all pairs of the two vertices on the sides colored (R, G), (G, B), (B, Y), (Y, R). For each pair, we can check if it can contain all the points in O(N) and also count the number of the possible third vertices in O(lgM) by using binary search to find the boundary of the possible third vertices on the other two sides of the M*M square. So in the end, the total needs to be divided by 2, because we double count each triangle.

Yesterday I had the same problem. I've cleaned java cache (found this tip at topcoder forum).