Four vertices of a square with side length a (and sides parallel to coordinate axis) are in this form: (x0, y0), (x0 + a, y0), (x0, y0 + a), (x0 + a, y0 + a).
Two vertices are given, calculate the two others (and check the ranges).
Total complexity : O(1)
Sample solution: 7495194
If all numbers are equal then answer will be n * (n - 1) / 2, otherwise the answer will be cnt1 * cnt2, where cnt1 is the number of our maximum elements and cnt2 is the number of our minimum elements.
Total complexity : O(n)
Sample solution: 7495202
For each student consider a sequence of d elements from 1 to k that shows the bus number which is taken by this student on each day. Obviously, there are kd different sequence at all, so if n > kd, pigeonhole principle indicates that at least two of this sequences will be equal, so that two students will become close friends and no solutions exist. But if n ≤ kd, then we can assign a unique sequence to each student and compute the answer. For computing that, we can find the first n d-digits numbers in k-based numbers.
Total complexity : O(n * d)
Sample solutions: 7495236
First of all, we can map the given numbers to integers of range [1, 106]. Let li be f(1, i, ai) and let ri be f(i, n, ai), we want to find the number of pairs (i, j) such that i < j and li > rj. For computing lis, we can store an array named cnt to show the number of occurence of any i with cnt[i]. To do this, we can iterate from left to right and update cnt[i]s; also, li would be equal to cnt[ai] at position i (ri s can be computed in a similar way).
Beside that, we get help from binary-indexed trees. We use a Fenwick tree and iterate from right to left. In each state, we add the number of elements less than li to answer and add ri to the Fenwick tree.
Total complexity : O(n * logn)
Also we can solve this problem using divide and conquer method. You can see the second sample solution to find out how to do this exactly.
In this problem, a directed graph is given and we have to find the length of a longest strictly-increasing trail in it.
First of all consider a graph with n vertices and no edges, then just sort the given edges by their weights (non-decreasingly) and add them to the graph one by one.
Let dp[v] be the length of a longest increasing trail which ends in the vertex v. In the mentioned method, when you're adding a directed edge xy to the graph, set dp[y] value to max(dp[y], dp[x] + 1) (because of trails which ends in y and use this edge). You need to take care of the situation of being some edges with equal weights; for this job we can add all edges of the same weights simultaneously.
Total complexity : O(n + m * logm)
Sample solution: 7495216