CF - Preparing for Merge Sort

Explanation

Simply simulating the process described is potentially $\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 $i - 1$ numbers and we would like to insert the $i$-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 $i$-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 $i$-th number into!

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <iostream>
#include <vector>

using std::vector;

int main() {
	int n;
	std::cin >> n;
	vector<vector<int>> sequences;

Copy
import java.io.*;
import java.util.*;

public class PreparingForMergeSort {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		List<List<Integer>> sequences = new ArrayList<>();

		for (int i = 0; i < n; i++) {

Copy
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: