Tampered Records
Source: aizu

Problem E
Tampered Records

In ancient times, the International Collegiate Puzzle Contest (ICPC) was held annually. Each of the annual contests consisted of two rounds: the morning round and the afternoon round. In both of the two rounds, the participants posed one puzzle made on their own to all the other participants, and then tried to solve as many puzzles as possible posed by the other participants.

The participants were ranked by the following rules.

The participant who solved more puzzles in the afternoon round is ranked higher.
For participants solving the same number of puzzles in the afternoon round, the one who solved more puzzles in the morning round is ranked higher.
For participants solving completely the same numbers of puzzles in both rounds, the order is decided by lot.

Recently, a historical document was found, which is said to be the standings of some year's ICPC. As in other similar documents, this document is assumed to list the number of puzzles solved by participants in each round, in the order of their ranks. However, the scholars suspect that someone tampered with the document overwriting some of the numbers. Your task is to find at least how many of the numbers were overwritten, assuming that the original document had records consistent with the rules described above. No parts of the document other than the numbers of puzzles solved were tampered with; addition and deletion of participants were impossible.

Input

The input consists of multiple datasets, each in the following format.

n
x1 y1
 ⋮
xn yn


n is the number of participants, an integer between 2 and 6000, inclusive.

xi and yi are the numbers currently on the document representing the numbers of the puzzles solved in the morning and the afternoon rounds, respectively, by the participant whose rank was the i-th highest. xi and yi are non-negative integers less than n. Some of these numbers might differ from the original ones.

The end of the input is indicated by a line consisting of a zero. The input consists of at most 100 datasets. The sum of n's in all the datasets in the input is at most 105.

Output

For each dataset, output in a line at least how many of the 2n numbers in the document were overwritten. Note that the numbers before the overwriting were all non-negative integers less than n.

Sample Input
2
1 0
1 1
3
2 2
2 0
0 1
4
0 3
0 2
3 1
2 0
5
0 3
0 3
1 2
4 2
4 2
3
1 1
2 2
2 2
4
0 0
1 1
2 2
3 3
0

Output for the Sample Input
1
1
0
1
2
4


C++ solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define all(A) A.begin(),A.end()
#define rep(i, n) for (int i = 0; i < (int) (n); i++)
template<class T>
void chmax(T &p,T q){if(p<q)p=q;};
ll solve(ll N) {
    vll X(N), Y(N);
    rep(i, N)cin >> Y[i] >> X[i];
    vector<pair<ll, ll>> DP(3,{ -1,-1 });
    DP[0] = { X[0],Y[0] };
    DP[1] = { N-1,Y[0] };
    DP[2] = { N-1,N-1};
    for (ll i = 1; i < N; i++) {
        vector<pair<ll,ll>> NDP(min(N+1,2*i+3),{-1,-1});
        rep(j, min(N + 1,2*i+1)) {
            if (DP[j].first<0)continue;
            auto [x,y]=DP[j];
            if (x>X[i]||(x==X[i]&&y>=Y[i]))chmax(NDP[j], { X[i],Y[i]});
            if(j+1>N)continue;
            if(x>=X[i])chmax(NDP[j+1],{X[i],y});
            if(x> X[i])chmax(NDP[j+1],{X[i],N-1});
            if(y>=Y[i])chmax(NDP[j+1],{x,Y[i]});
            if(x>0)chmax(NDP[j+1],{x-1,Y[i]});
            if(j+2>N)continue;
            chmax(NDP[j+2],{x,y});
            if(x>0)chmax(NDP[j+2],{x-1,N-1});
        }
        swap(DP,NDP);
    }
    rep(i, N + 1)if (DP[i].second >= 0)return i;
    return 0;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll H;
    while (cin >> H) {
        if (H == 0)return 0;
        cout<<solve(H)<<endl;
    }
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	for {
		var n int
		scanner.Scan()
		line := scanner.Text()
		if line == "0" {
			break
		}
		n, _ = strconv.Atoi(line)

		dp := make([][2]int, n+1)
		for i := range dp {
			dp[i] = [2]int{-1, -1}
		}
		dp[0] = [2]int{n - 1, n - 1}

		for i := 0; i < n; i++ {
			scanner.Scan()
			parts := strings.Fields(scanner.Text())
			b, _ := strconv.Atoi(parts[0])
			a, _ := strconv.Atoi(parts[1])

			ndp := make([][2]int, n+1)
			for j := range ndp {
				ndp[j] = [2]int{-1, -1}
			}

			for j := 0; j <= n; j++ {
				c, d := dp[j][0], dp[j][1]
				if c == -1 {
					continue
				}

				xOptions := []int{a, c, c - 1}
				yOptions := []int{b, d, n - 1}

				for _, x := range xOptions {
					if x < 0 {
						continue
					}
					for _, y := range yOptions {
						if y < 0 {
							continue
						}
						if c > x || (c == x && d >= y) {
							cost := j
							if x != a {
								cost++
							}
							if y != b {
								cost++
							}
							if cost <= n {
								if ndp[cost][0] == -1 || (x > ndp[cost][0] || (x == ndp[cost][0] && y > ndp[cost][1])) {
									ndp[cost] = [2]int{x, y}
								}
							}
						}
					}
				}
			}
			dp = ndp
		}

		for i := 0; i <= n; i++ {
			if dp[i][0] != -1 {
				fmt.Println(i)
				break
			}
		}
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static class Pair {
        int a, m;
        Pair(int a, int m) {
            this.a = a;
            this.m = m;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            String line = br.readLine();
            if (line == null || line.isEmpty()) {
                continue;
            }
            int n = Integer.parseInt(line.trim());
            if (n == 0) {
                break;
            }
            List<int[]> participants = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                participants.add(new int[]{x, y});
            }
            Pair[] dp = new Pair[n + 1];
            for (int i = 0; i <= n; i++) {
                dp[i] = new Pair(-1, -1);
            }
            dp[0] = new Pair(n - 1, n - 1);
            for (int[] participant : participants) {
                int b = participant[0];
                int a = participant[1];
                Pair[] newDp = new Pair[n + 1];
                for (int i = 0; i <= n; i++) {
                    newDp[i] = new Pair(-1, -1);
                }
                for (int j = 0; j <= n; j++) {
                    Pair current = dp[j];
                    if (current.a == -1) {
                        continue;
                    }
                    int[] xOptions = {a, current.a, current.a - 1};
                    int[] yOptions = {b, current.m, n - 1};
                    for (int x : xOptions) {
                        if (x < 0) {
                            continue;
                        }
                        for (int y : yOptions) {
                            if (y < 0) {
                                continue;
                            }
                            if (current.a >= x && (current.a > x || current.m >= y)) {
                                int cost = j;
                                if (x != a) {
                                    cost++;
                                }
                                if (y != b) {
                                    cost++;
                                }
                                if (cost <= n) {
                                    if (newDp[cost].a < x || (newDp[cost].a == x && newDp[cost].m < y)) {
                                        newDp[cost] = new Pair(x, y);
                                    }
                                }
                            }
                        }
                    }
                }
                dp = newDp;
            }
            int answer = -1;
            for (int i = 0; i <= n; i++) {
                if (dp[i].a != -1) {
                    answer = i;
                    break;
                }
            }
            System.out.println(answer);
        }
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
let currentLine = 0;

rl.on('line', (line) => {
    input.push(line.trim());
});

rl.on('close', () => {
    processInput();
});

function processInput() {
    let idx = 0;
    while (idx < input.length) {
        const line = input[idx++];
        if (line === '0') break;
        const n = parseInt(line, 10);
        const participants = [];
        for (let i = 0; i < n; i++) {
            const [x, y] = input[idx++].split(' ').map(Number);
            participants.push({ morning: x, afternoon: y });
        }
        solve(n, participants);
    }
}

function solve(n, participants) {
    let dp = Array(n + 1).fill().map(() => ({ a: -1, m: -1 }));
    dp[0] = { a: n - 1, m: n - 1 };

    for (const p of participants) {
        const newDp = Array(n + 1).fill().map(() => ({ a: -1, m: -1 }));
        const aCurrent = p.afternoon;
        const bCurrent = p.morning;

        for (let changes = 0; changes <= n; changes++) {
            const current = dp[changes];
            if (current.a === -1) continue;

            const candidatesA = [aCurrent, current.a, current.a - 1].filter(x => x >= 0);
            const candidatesB = [bCurrent, current.m, n - 1].filter(y => y >= 0);

            for (const a of candidatesA) {
                for (const b of candidatesB) {
                    if (current.a >= a && (current.a > a || current.m >= b)) {
                        const newChanges = changes + (a !== aCurrent ? 1 : 0) + (b !== bCurrent ? 1 : 0);
                        if (newChanges > n) continue;
                        if (newDp[newChanges].a < a || (newDp[newChanges].a === a && newDp[newChanges].m < b)) {
                            newDp[newChanges] = { a, m: b };
                        }
                    }
                }
            }
        }
        dp = newDp;
    }

    for (let i = 0; i <= n; i++) {
        if (dp[i].a !== -1) {
            console.log(i);
            return;
        }
    }
    console.log(n);
}

Python solution:
while True:
    n = int(input())
    if n == 0:
        exit()
    dp = [(-1, -1) for i in range(n + 1)]
    dp[0] = (n - 1, n - 1)
    for _ in range(n):
        b, a = map(int, input().split())
        ndp = [(-1, -1) for i in range(n + 1)]
        for j in range(n + 1):
            c, d = dp[j]
            if c == -1:
                continue

            for x in [a, c, c - 1]:
                if x < 0:
                    continue
                for y in [b, d, n - 1]:
                    if y < 0:
                        continue
                    if (c, d) >= (x, y):
                        cost = j
                        if x != a:
                            cost += 1
                        if y != b:
                            cost += 1
                        if cost <= n:
                            ndp[cost] = max(ndp[cost], (x, y))
        dp = ndp
    for i in range(n + 1):
        if dp[i] != (-1, -1):
            print(i)
            break

Ruby solution:
while true
  n = gets.to_i
  break if n == 0

  dp = Array.new(n + 1) { [-1, -1] }
  dp[0] = [n - 1, n - 1]

  n.times do
    b, a = gets.split.map(&:to_i)
    ndp = Array.new(n + 1) { [-1, -1] }

    (0..n).each do |j|
      c, d = dp[j]
      next if c == -1

      [a, c, c - 1].each do |x|
        next if x < 0

        [b, d, n - 1].each do |y|
          next if y < 0

          if c > x || (c == x && d >= y)
            cost = j
            cost += 1 if x != a
            cost += 1 if y != b
            if cost <= n
              if ndp[cost][0] == -1 || x > ndp[cost][0] || (x == ndp[cost][0] && y > ndp[cost][1])
                ndp[cost] = [x, y]
              end
            end
          end
        end
      end
    end

    dp = ndp
  end

  (0..n).each do |i|
    if dp[i] != [-1, -1]
      puts i
      break
    end
  end
end