CF - Preparing for Merge Sort
Authors: Andi Qu, Prashanth Ragam, Rameez Parwez
Explanation
Simply simulating the process described is potentially , 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 numbers and we would like to insert the -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 -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 -th number into!
Implementation
Time Complexity:
C++
#include <iostream>#include <vector>using std::vector;int main() {int n;std::cin >> n;vector<vector<int>> sequences;
Java
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++) {
Python
n = int(input().strip())numbers = [int(x) for x in input().strip().split()]sequences = []for num in numbers:l = 0r = len(sequences)while l != r:mid = (l + r) // 2if 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!