CF - Preparing for Mergesort

Authors: Andi Qu, Prashanth Ragam


Simply simulating the process described is potentially O(N2)\mathcal{O}(N^2), so we can't just do that. What if instead of finding the sequences one at a time, we find them all at the same time?

Imagine that we already know the sequences for the first i1i - 1 numbers and we would like to insert the ii-th number into one of the sequences.

Which sequence should we insert this number into? We should insert it into the first sequence where the last number of this sequence is less than the ii-th number.

The key observation in this problem is that the last numbers of the existing sequences form a non-increasing sequence. (To prove this, use a proof by contradiction - what if there is an increase at some point?)

This means that we can simply binary search for the sequence that we should insert the ii-th number into!

This algorithm runs in O(NlogN)\mathcal{O}(N \log N) time.

Implementation

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<vector<int>> ans;
while (n--) {

Python

n = int(input().strip())
numbers = [int(x) for x in input().strip().split()]
sequences = []
for num in numbers:
l = 0
r = len(sequences)
while l != r:
mid = (l + r) // 2
if sequences[mid][-1] < num:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!