• Deletion Sort – Why the Answer is Either 1 or n?*

  Problem Summary

We are given an array of positive integers.

In each move:

If the array is non-decreasing → the game ends.

Otherwise, we can remove any single element.

We must determine the minimum number of elements remaining once the array becomes non-decreasing.

Constraints:

1 ≤ t ≤ 1000

1 ≤ n ≤ 10

1 ≤ ai ≤ 100

Key Observation

A very important fact:

A single-element array is always non-decreasing.

So no matter what the array looks like, we can always delete elements until only one element remains.

But the game stops immediately when the array becomes non-decreasing.

This leads to only two possible outcomes.

Case Analysis

Case 1: The array is already non-decreasing

Then the game stops immediately.

We cannot delete anything.

Answer = n

Case 2: The array is NOT non-decreasing

Then at least one pair violates:

ai > ai+1

Since we can remove any element, we can keep deleting elements until only one remains.

A single element is always sorted.

Answer = 1

Final Conclusion

The answer is:

n if the array is non-decreasing

1 otherwise

That’s it.

No DP. No LIS. No greedy complexity.

Just observation.

Implementation (Java)

import java.util.*;

public class B_DeletionSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            boolean ok = true;
            for (int i = 0; i < n ; i++) {
                if (a[i] > a[i + 1]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                System.out.println(n);
            } else {
                System.out.println(1);
            }
        }
    }
}

Why This Problem Is Nice

cuz this teaches u some great techniques and stuff like makishima-san teaches onoda-kun.