The firewall hasn't been built yet.

There already problems in en, ru, fr.

deleted. I think that my comment doesn't give any hint to this problem. Anyway, excuse me)

My solution: Angular sort, radial sweep, range query.
Complexity: O(n³log(n)).

Is there O(n³) solution or better exists?

You can pick a point say the point leftmost of all points (point P) and fill a pre_process array dp[i][j] that means in the triangle with vertices P,i,j how many dots are there we can fill this array naively O(n^3) and then for any triple (a,b,c) we can easily find out the number of dots inside it O(1) for example the number of dots inside(a,b,c) can be equal to : dp[a][c] — dp[a][b] — dp[b][c] — 1 OR dp[a][b] + dp[b][c] — dp[a][b] (if b is between a,c if we look at it from P) so the overall complexity will be O(n^3)

(filling up the array and finding out which point is in between to other points by looking at it from P can be easily implemented by cross product)

Let's use trapezoidal decomposition. Loop through all segments and compute the number of points inside the trapezoid formed with the x-axis. Now, for any query triangle, lets pick the longest segment forming it and look at the third point not forming this segment. Depending on which side of the segment this third point is, we either add 2 trapezoids and subtract 1, or subtract 2 trapezoids and add 1. Either way, it's O(n³).

You can solve third problem by bfs. Here is the code.

gold 2 ==> DP[1000][1000][2]

wtf of down?! :/

About problem 2 gold :

I decide to go to through the all options and get the best answer.

Situation (x, y, k) :

. k = 1 — Holsteins cow, 2 — Guernseys cow.

. the last Holsteins cow was Holstein cow by number x,

. the last Guernseys cow was Guernsey cow by number y,

and we now near cow type k.

The ansewr for situation (x, y, k) it's minimum energy which we need fo going from (x, y, k) to (h, g, 1)

Let calculate answer for situation (x, y, k) and we want go to the (h, g, 1)

So where we can go from there ?

1) if x == h and y == g

. a) k == 1 then nowhere ( ans = 0 )

. b) k == 2 then go to the h-th Holsteins cow.

2) if k == 1

. a) we can go to ( x + 1, y, 1)

. b) if y < g we also can go to ( x, y + 1, 2 )

3) if k == 2

. a) we can go to ( x + 1, y, 1 )

. b) if y < g we also can go to ( x, y + 1, 2 )

One point : if we walked out from [1; n][1; m] then the answer will be BIG NUMBER.

So we will calculate the answer for (1, 0, 1), and it will be the answer for the problem.

First I just write recursion "go through the all options" ( and got 2/10 AC)

Then I saw that some positions (x, y, k) we calculated several times, and decided to use map for optimization ( we calculated answer for each position one time and save the answer, and each another time we will use saved answer ). ( it got 5/10 AC ).

And I decided to change map to the array because the problem has no big limitations [1000][1000][2]

( it got 8/10 AC ).

This problem helped me to understand how to convert some DFS solutions in to the BFS solutions, and I convert my DFS solution in to the BFS solution and got 10/10 AC.

I think this problem was very interesting and useful for me.

If you are interesting here is my DFS and BFS solutions.

Thank you for attention. And sorry for my bad English.

From what I have heard, the problem is a harder version of Problem A in this competition: http://cs.stanford.edu/group/acm/slpclive/problems/problems_2016.pdf

I've also heard that one can use Eppstein's algorithm to solve it.

My solution is O(nlg^2n). I will only explain some key ideas, since the full algorithm is hard to explain....

• Let's run some sort of Dijkstra here. we start from (0, 0, 0, 0 ....), and increase one element from each of N entry. This is NKlgN and I remember it didn't rewarded much.
• Observe that Kth pick differs for at most lgK elements from the 1st pick.
• We want to reduce state to N entry -> K entry, but it's not clear till now.. So, dismiss all rows with one elements, and sort every rows by order of M[1] — M[0].
• Still it's not clear, so let's fix the number of changed elements (say C), and solve each problem independently.
• Now think about the two ways of state transition.

In contest, I was short of time, and I just submitted optimized O(nlg^3n). This misses two TC as TLE. (956/1000) This is my code. http://ideone.com/s08eao

Also, ainta told me that there is nlgn solution. I think it won't be really hard to optimize mine to nlgn...

Link to my solution of C (it got AC). It's an easy to understand DPlike bruteforce which runs in .

My solution is O(n log n) and it's really simple to code:

1. Let's sort pairs (value, row) for all elements in all rows (except for the smallest ones), where value is the differences between the element and the smallest element in its row.

2. Let's say that a state is a vector of positions (in the sorted array) and run Dijkstra's algorithm (starting from an empty vector). We need only two transitions: creating a new position immediately after the last one and increasing the last position by one.

3. There's one problem here: we can take two elements from the same row. It's bad. Let's fix it by moving the last element until all rows are unique (we touch only the last element, so it's the only one that could break). That's it.

And the people discussing it early are probably the ones downvoting you.

Can you please explain your method with more details ? Thanks in Advance.