459A - Pashmak and Garden

Four vertices of a square with side length a (and sides parallel to coordinate axis) are in this form: (x₀, y₀), (x₀ + a, y₀), (x₀, y₀ + a), (x₀ + a, y₀ + a).

Two vertices are given, calculate the two others (and check the ranges).

Total complexity : O(1)

Sample solution: 7495194

459B - Pashmak and Flowers

If all numbers are equal then answer will be n * (n - 1) / 2, otherwise the answer will be cnt₁ * cnt₂, where cnt₁ is the number of our maximum elements and cnt₂ is the number of our minimum elements.

Total complexity : O(n)

Sample solution: 7495202

459C - Pashmak and Buses

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

459D - Pashmak and Parmida's problem

First of all, we can map the given numbers to integers of range [1, 10⁶]. 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_is, 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.

Sample solutions: 7495225 7495225

459E - Pashmak and Graph

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