Stock Exchange
Contest: Codeforces Global Round 4
Difficulty rating: 3500
Tags: binary search, flows, graphs

Warning: This problem has an unusual memory limit!

Bob decided that he will not waste his prime years implementing GUI forms for a large corporation and instead will earn his supper on the Stock Exchange Reykjavik. The Stock Exchange Reykjavik is the only actual stock exchange in the world. The only type of transaction is to take a single share of stock $$$x$$$ and exchange it for a single share of stock $$$y$$$, provided that the current price of share $$$x$$$ is at least the current price of share $$$y$$$.

There are $$$2n$$$ stocks listed on the SER that are of interest to Bob, numbered from $$$1$$$ to $$$2n$$$. Bob owns a single share of stocks $$$1$$$ through $$$n$$$ and would like to own a single share of each of $$$n+1$$$ through $$$2n$$$ some time in the future.

Bob managed to forecast the price of each stock — in time $$$t \geq 0$$$, the stock $$$i$$$ will cost $$$a_i \cdot \lfloor t \rfloor + b_i$$$. The time is currently $$$t = 0$$$. Help Bob find the earliest moment in time in which he can own a single share of each of $$$n+1$$$ through $$$2n$$$, and the minimum number of stock exchanges he has to perform in order to do that.

You may assume that the Stock Exchange has an unlimited amount of each stock at any point in time.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2200$$$) — the number stocks currently owned by Bob.

Each of the next $$$2n$$$ lines contains integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \leq a_i, b_i \leq 10^9$$$), representing the stock price of stock $$$i$$$.

Output format:
If it is impossible for Bob to achieve his goal, output a single integer $$$-1$$$.

Otherwise, output two integers $$$T$$$ and $$$E$$$, where $$$T$$$ is the minimum time in which he can achieve his goal, and $$$E$$$ is the minimum number of exchanges in which he can achieve his goal at time $$$T$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 16.0 MB

Note:
In the first example, Bob simply waits until time $$$t = 3$$$, when both stocks cost exactly the same amount.

In the second example, the optimum strategy is to exchange stock $$$2$$$ for stock $$$1$$$ at time $$$t = 1$$$, then exchange one share of stock $$$1$$$ for stock $$$3$$$ at time $$$t = 5$$$ (where both cost $$$15$$$) and then at time $$$t = 6$$$ exchange the second on for the stock number $$$4$$$ (when they cost $$$18$$$ and $$$17$$$, respectively). Note that he can achieve his goal also with only two exchanges, but this would take total time of $$$t = 9$$$, when he would finally be able to exchange the share number $$$2$$$ for the share number $$$3$$$.

In the third example, Bob can never achieve his goal, as the second stock is always strictly more expensive than the first one.

Example input:
1
3 10
1 16

Example output:
3 1

Example input:
2
3 0
2 1
1 10
1 11

Example output:
6 3

Editorial:
Lemma: If there is a solution $$$S$$$ for time $$$T$$$, there is also a solution $$$S'$$$ for time $$$T$$$ using not more exchanges than $$$S$$$, in which all exchanges occur either in time $$$0$$$ or in time $$$T$$$.
Proof: Induction on $$$n$$$ - the number of exchanges not happening in time $$$0$$$ or $$$T$$$. If $$$n = 0$$$, we are done.
Otherwise, pick an arbitrary exchange $$$i \rightarrow j$$$ at time $$$t$$$. There are a few cases:
• There is an exchange $$$j \rightarrow k$$$ at time $$$t$$$. We can substitute both by exchange $$$i \rightarrow k$$$.
• There is an exchange $$$k \rightarrow i$$$ at time $$$t$$$. We can substitute both by exchange $$$k \rightarrow j$$$.
• If $$$a[i] \geq a[j]$$$ and   there is an exchange $$$j \rightarrow k$$$ in time $$$t < t_1 < T$$$. We substitute both with exchange $$$i \rightarrow k$$$ in time $$$t_1$$$.  otherwise, postpone the exchange to time $$$T$$$
• there is an exchange $$$j \rightarrow k$$$ in time $$$t < t_1 < T$$$. We substitute both with exchange $$$i \rightarrow k$$$ in time $$$t_1$$$.
• otherwise, postpone the exchange to time $$$T$$$
• If $$$a[i] < a[j]$$$ and   there is an exchange $$$k \rightarrow i$$$ in time $$$0 < t_1 < t$$$. We substitute both with exchange $$$k \rightarrow j$$$ in time $$$t_1$$$.  otherwise, prepone the exchange to time $$$0$$$
• there is an exchange $$$k \rightarrow i$$$ in time $$$0 < t_1 < t$$$. We substitute both with exchange $$$k \rightarrow j$$$ in time $$$t_1$$$.
• otherwise, prepone the exchange to time $$$0$$$
Thanks to this lemma, and the fact that we can get rid of transitive exchanges happening at the same time, we can model this problem as min-cost max-flow on $$$4N+2$$$ vertices. Let there be vertices $$$u_i$$$ and $$$v_i$$$ for each stock, and $$$s$$$ and $$$t$$$ are source and sink, respectively. There are edges of six types:
1. Edge $$$s \rightarrow u_i$$$ for all $$$0 \leq i < N$$$ with capacity $$$1$$$ and cost $$$0$$$ (representing the starting stock).
2. Edge $$$u_i \rightarrow v_i$$$ for all $$$0 \leq i < N$$$ with capacity $$$1$$$ and cost $$$0$$$ (representing stock not exchanged at $$$t = 0$$$).
3. Edge $$$u_i \rightarrow v_j$$$ for all $$$0 \leq i < N$$$ and $$$j$$$ such that $$$B[i] \geq B[j]$$$, with capacity $$$1$$$ and cost $$$1$$$ (representing an exchange at $$$t = 0$$$).
4. Edge $$$v_i \rightarrow u_i$$$ for all $$$N \leq i < 2N$$$ with capacity $$$1$$$ and cost $$$0$$$ (representing stock not exchanged at $$$t = T$$$).
5. Edge $$$v_i \rightarrow u_j$$$ for all $$$0 \leq i < 2N$$$ and $$$N \leq j < N$$$ sucht that $$$A[i]*T + B[i] \geq A[j]*T + B[j]$$$, with capacity $$$1$$$ and cost $$$1$$$ (representing an exchange at $$$t = T$$$).
6. Edge $$$u_i \rightarrow t$$$ for all $$$N \leq i < 2N$$$ with capacity $$$1$$$ and cost $$$0$$$ (representing desired stock).
If the flow size equals $$$N$$$, then there exists a strategy. The number of exchanges equals to the cost of the flow.
This combined runs in $$$O(N^3 \log N \log MAX)$$$ using e.g. preflow-push. Even when considering the fact that the bounds on flow algorithms are often not tight, this is not very promising. Furthermore, it uses $$$O(N^2)$$$ memory, which is clearly too much. Let's improve it.
Removing $$$\log MAX$$$ factor: The first observation is that we don't need to run the MCMF for every iteration of the binary search – we don't need the cost, all that is required is deciding whether max-flow size is $$$N$$$. There are many approaches to this, perhaps the simplest one is to solve it in $$$O(N \log N)$$$:
• At time $$$T$$$, exchange each stock to the most expensive stock at $$$t = T$$$ that we can afford to exchange at $$$t = 0$$$.
• Check whether at time $$$t = T$$$ the prices of stocks obtained this way dominate the prices of the desired stocks.
Reducing the space complexity:  Note that the edges of type $$$3$$$ and $$$5$$$ connect a stock $$$i$$$ to some subset of stocks $$$j$$$. This subset of stocks is a prefix of the array of stocks sorted by their price. We can thus connect each stock only to the most expensive stock to which it can be exchanged, and connect these in order of decreasing price with edges of capacity $$$N$$$ and cost $$$0$$$ (make sure the ties are broken correctly).
This way, we reduce the number of edges from quadratic to $$$12N$$$, improving the space complexity.
Reducing to $$$O(N^2 \log N)$$$ time: The maximum flow is capped by $$$N$$$. In such a setting primal methods such as Ford-Fulkerson, respectively it's MCMF version called Successive Shortest Paths Algorithm, behave quite well, needing only $$$O(f \cdot |E| \log |E|) = O(N^2 \log N)$$$ time.
Reducing to $$$O(N^2)$$$ time: However, in our problem, the costs are also bounded by a small constant, namely $$$0$$$ or $$$1$$$. In Dijsktra's algorithm, the subroutine of SSPA, one can use a fixed size array instead of a priority queue, reducing the complexity even further. This last optimisation is difficult to separate, so with a reasonable implementation it is not necessary to get AC.
The total complexity is thus $$$O(N \log N \log MAX + N^2)$$$.