Educational Round 15 — Haskell version. I can't solve E and F. :P
I think it's trivial, so just see: 19483133
One thing to mention is that you don't need to hold all integers in memory. You can process integers one by one, thus space complexity can be reduced to O(1), but in this case the problem size is small (N <= 100000) so I reused my previous code that reads whole string at once.
Time complexcity : O(N)
All of n integers satisfy 1 <= a[i] <= 10^9. Then possible sums that are any power of 2 are 2 <= 2^x <= 2^30.
justification:
- 1 + 1 = 2
- 10^9 = (10^3)^3 < (2^10)^3 = 2^30
Therefore for each a[i] and 2^x (1 <= x <= 30), we count the number of a[j] such that a[i] + a[j] = 2^x.
First, traverse the input and map each integer to the number of appearence of it. Let's call this mapping book. I used Data.Map.Strict.
Second, for each a[i] and 2^x, count the combinations.
- If
a[i] >= 2^x, then there is no solution. - If
2^x - a[i]is not in the book, there is no solution. - If
2^x - a[i] == a[i], then there isbook[2^x - a[i]] - 1solutions. - Otherwise, there is
book[2^x - a[i]]solutions.
Sum up all solutions and divide by 2 (We didn't consider i < j constraints, so all combinations have been counted twice), then print it: 19513379
Because the answer can be pretty big, I used Integer rather than Int. I always forgot this. In my computer Int is 64-bit, but It seems in Codeforces Int is 32-bit. So always use Data.Int.Int64 or Integer for big answers.
Time complexity: O(N)
Let's consider the line as a 1D Voronoi diagram. That is, we assign for each tower an area in which any city is related to that tower. Because it's 1D situation and all towers are given sorted, this is very easy: the boundaries are just the middle of consecutive two towers.
Sorted boundaries given, for each city we binary search the tower it relates to, calculate the distance between them, update the maximum distance so far: 19530243
It's annoying that Haskell doesn't allow O(1) destructive update of an array, but in this case we only need reading array. Happy array time!
Time complexity: O(N + MlogM)
This is a math problem, nothing specific to Haskell. See the official editorial: http://codeforces.net/blog/entry/46324?locale=en
