Four vertices of a square with side length a (and sides parallel to coordinate axis) are in this form: (x 0, y 0), (x 0 + a, y 0), (x 0, y 0 + a), (x 0 + a, y 0 + 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 cnt 1 * cnt 2, where cnt 1 is the number of our maximum elements and cnt 2 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 k d different sequence at all, so if n > k d, 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 ≤ k d, 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 l i be f(1, i, a i) and let r i be f(i, n, a i), we want to find the number of pairs (i, j) such that i < j and l i > r j. For computing l i s, 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, l i would be equal to cnt[a i] at position i ( r i 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 l i to answer and add r i 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