Translate average for a subsequence to difference_of_partial_sums/nr_of_elements.

s[i]=sum of first i elements.(s[i]-s[j])/(i-j)>=P with j<i. It reduces to s[i]-P*i>=s[j]-P*j. So the problem reduces to finding how many elements <= x there are,which can be done with BIT and compression(because numbers get very big)

I solve it with meet in the middle method. It came out very similar to merge sort.

I solved it z-function + hash.. But I don't know correct this solution or not.

I solved it using two Tries. One for the original strings, and one for the same strings but reversed. Not sure if my solution is right though.

Dynamic programming.

First observation. For a subset,the property stated has to be respected just for adjacent words,it's easy to prove. So for i1,i2,....,ik, word i2 has to end and begin with i1, i3 with i2.....

dp[i]=maximum subset from the first i elements where the last one is word i.

To calculate that,for every prefix of length x of word i which is also a suffix of word i ,you want those words j (j<i) equal to that prefix (so it respects the property).Those words can be hashed and put in maps. And also in M[word] you store maximum dp of words with that hash number,because you want to maximize your dp[i].

So briefly,dp[i]=max(1,max(M[word])),word being a prefix that is also suffix of word i

Without hashes:

Use trie. Let's put strings one by one in it, solving the problem for the given string at the same time. Once we added the string and calculated the answer for it, we will remember this answer in the node of the trie that corresponds to the end of this string.

Processing a string: mark all positions i such that the first i characters are equal to the last i characters of the string. You can do it with z-function (or KMP if you prefer so). While moving through the trie, take a maximum of all previously remembered answers that lie on nodes which correspond to the marked positions. The answer for the current string is this maximum value plus one.

Z-function + trie. BUT if there was more memory, at least 75 MB, then it can be solved with ONLY trie (no hash, no zf). Hint: try to decompose all strings, s[0]s[1]s[2]...s[n] -> s[0]s[n]s[1]s[n-1]...s[n]s[0].

I tried to use kd-tree, but it works too slow even on random tests. Maybe in C++ it would be faster.

One observation is that we never need more than K closest neighbours of the city (is it even correct? I only had 30 minutes to solve this task, so I didn't have much time to prove things). What I did is I took K closest cities by X, K closest cities by Y, and then merged the two lists and took K closest cities overall.

Then you can do binary search for the squared distance, finding the connected components using only edges found above, and trying to find solution for the problem for each connected component separately.

This works in N * K * log(MAX_DIST^2). Could still be too slow for 1 second, not sure.

Edit: looks like this solution is not fast enough, or my implementation is slow. 96 points

Here's my solution, which receives full points after a small bug-fix:

We binary search on D, so now we need to solve the problem of finding whether a given value of D works. This is in two parts: joining with union-find all points within distance D, and then applying knapsack to each component to test if some subset adds to 0 mod K.

Part 1: Scan by x-value, maintaining a set sorted by y-value of all points with x-value at most D behind the leading line. Now for each point (a,b) in our scan, we iterate in the set through all points in this set with y-value in (b-D,b+D), and join to (a,b) all points within distance D. These are the points in the rectangle [a-d,a]x[b-D,b+D]. Note that by Pigeonhole, if we ever find a component of size at least K, we may stop and return a YES. This short-circuiting means (I think) that there can only be ~180 points in this box without more than K points lying in close proximity, and in most cases there should be much less.

Part 2 modulo knapsack is quite easy, so of course this is where I made a bug.

This solution is O(N*K*log(MAX_DIST)) but runs in less than 0.5 seconds on the test data.

Don't be silly. Hashing is one of the most fundamental and most flexible techniques; that's why, it's as "real" as it gets.

You can just increment the bitmask, I think that will pass. I tried to optimize mine by adding the lowest bit and clearing the rest when there is a mismatch.

yes, it is. For any two segment, you check whether a segment has to be after the other segment and then sort them.

I think it's not that neat, but let me share my solution:

I first check if their projections on x axis intersect. If not, then they don't block each other. Then I think them as lines instead of line segments and find their equations. Then I choose the bigger one of left ends of segments as common x value that both have y values. I plug that common x into their equations. The line segment with the less value is the one which blocks the other, so we should remove it first. The only tricky situation is when a line segment doesn't have a slope. In that case, instead of using equation, we can use any value between y1 and y2 of that line segment.

My code

Maybe your algorithm is still correct. But some ARTUR test cases (e.g 10a) make the sticks touch each others at beginning. Therefore, the topological order determination make WA. I already send a clarification and hope for their correction of test data

double solvey(int p, int x) {
  if (x1[p] == x2[p]) {
    return min(y1[p], y2[p]);
  }
  return 1.0 * (y2[p] - y1[p]) / (x2[p] - x1[p]) * (x - x1[p]) + y1[p];
}
bool covers(int p, int q) {
  // requirement: x1[p] <= x2[p] and x2[p] <= x2[q]
  // x does not overlap
  if (min(x2[p], x2[q]) < max(x1[p], x1[q])) return false;
  int z = min(x2[p], x2[q]);
  double yp = solvey(p, z);
  double yq = solvey(q, z);
  return yp < yq;
}

It is Mle (Memory limit exceed)