Problem: railroad_renovations (2020 round3)

Pennington has taken \(N\) trips on his favourite railroad line, which is 1 billion metres long.

When the line was first built, creaky wood was used to support the tracks, which made a terrible racket as the train ran along them. Pennington is aware that, since then, 0 or more renovations have been made to the line at various points in time (either before his first trip or in between some of his trips), each of which would have involved replacing the supports along some continuous, possibly-degenerate interval of the line with integer endpoints (for example, the intervals \([1m, 2m]\) or \([3m, 3m]\) could have been renovated, but not \([3.5m, 4.5m]\)). No renovations were made *during* any of his trips. No two renovations' intervals could have inclusively overlapped with one another (for example, if one renovation involved the interval of positions \([5m, 10m]\), then there could not have been another one involving \([6m, 8m]\) nor \([10m, 11m]\), but there could have been one involving \([11m, 12m]\)). Renovations would never have been undone; each one had a permanent effect on its interval of the line.

In general, Pennington just sleeps the entire time he's on the train (it is a long ride, after all). However, he did briefly wake up exactly once per trip he's taken. During his \(i\)th trip, he woke up while the train was at position \(P_i\) metres along the line, and he noticed whether the supports at that position had been renovated by that point in time — if \(R_i = 1\), they had been, while if \(R_i = 0\), they had not been.

Pennington suspects he might have misremembered the order of his trips, though. To get their actual order, it may be necessary to take up to \(K\) of them and insert them into other positions in the ordered list of trips (with each one moved to either before the first trip, between any two trips, or after the final trip). For example, if \(K = 1\), he could rearrange the 2nd trip to have actually occurred between the 4th and 5th trips (essentially shifting trips 3 and 4 to have been his 2nd and 3rd trips). It's possible that his observations would only be consistent with any possible sequence of renovations after some rearrangements of this sort, or even that they would be inconsistent after any possible set of \(K\) rearrangements.

What's the minimum possible number of renovations that could have been made by the end of Pennington's final trip which would have been consistent with all \(N\) of his observations (after rearranging at most \(K\) of the trips), if this would have been possible at all?

# Constraints

\(1 \le T \le 95\)
\(1 \le N \le 500\)
\(0 \le K \le N\)
\(1 \le P_i \le 1,000,000,000\)
\(0 \le R_i \le 1\)

The sum of \(N\) across all sets of train trips is at most 10,000.

# Input

Input begins with an integer \(T\), the number of sets of train trips. For each set there are \(N + 1\) lines. The first line contains the 2 space-separated integers \(N\) and \(K\). \(N\) lines follow, the \(i\)th of which contains the 2 space-separated integers \(P_i\) and \(R_i\).


# Output

For each set of train trips, print a line containing *"Case #i: "*, followed by a single integer, the minimum possible number of renovations which might have been made by the end of Pennington's final trip, or \(-1\) if no set of renovations would be consistent with his observations, after at most \(K\) trip rearrangements.




# Explanation of Sample

In the first case, there could have been a single renovation involving the interval \([1m, 1m]\) between Pennington's first and second trips.

In the second case, no sequence of renovations could explain the supports at position \(1m\) having been renovated by his first trip but no longer renovated by his second trip.

In the third case, if his first trip is rearranged to occur after his second trip, then a single renovation is once again possible as in the first case.

In the fourth case, there could have been two renovations involving the intervals \([1m, 1m]\) and \([3m, 3m]\) before any of his trips. It's impossible for fewer than two renovations to have occurred.

In the fifth case, if his third trip is rearranged to occur before his first trip, then a single renovation involving the interval \([1m, 3m]\) could have occurred just after it.


Sample input:
7
2 0
1 0
1 1
2 0
1 1
1 0
2 1
1 1
1 0
3 0
1 1
3 1
2 0
3 1
1 1
3 1
2 0
6 2
6 1
9 1
5 0
3 1
4 0
8 1
20 4
7 1
3 0
10 0
13 1
4 1
2 1
12 1
4 1
3 1
14 1
2 0
8 0
13 0
8 1
5 1
13 1
12 1
13 0
2 0
6 1


Sample output:
Case #1: 1
Case #2: -1
Case #3: 1
Case #4: 2
Case #5: 1
Case #6: 1
Case #7: 4


Solution: We'll begin by sorting the observations in non-decreasing order of position (ordering equal-position observations arbitrarily), and re-numbering them in this order. In addition to each observation \(i\)'s \(P_i\) and \(R_i\) values, we'll store the original trip index \(I_i\) which it corresponds to.

We'll proceed with dynamic programming. Let \(D_{i,j}\) be the minimum number of renovations which could have occurred if we consider only the first \(i\) observations in this ordered list, such that \(j\) of their trips have been rearranged. We'll only concern ourselves with indices \(i\) on boundaries between different positions (specifically, such that \(i = 0\), \(i = N\), or \(P_i < P_{i+1}\)). We know that \(D_{0,0} = 0\), and our answer will be \(\min(D_{N,0..K})\).

In order to compute \(D_{i,j}\), we'll consider each possible earlier index \(k\) such that \(k < i\) and either \(k = 0\) or \(P_k < P_{k+1}\), determine what can be done with observations \((k+1)..i\), compute a candidate value for \(D_{i,j}\) accordingly, and take the minimum of these candidate values.

If \(R_o = 0\) for each \(o \in [k+1, i]\), then no renovations nor trip rearrangements are required, and our candidate value will simply be \(D_{k,j}\).

Otherwise, there must be at least one renovation amongst these observations' positions, and we'll assume that there was exactly one renovation spanning that full interval of positions (noting that other possibilities would be captured by different choices of \(k\)). We must then determine the minimum number of trip rearrangements necessary for that to be possible.

Considering each possible original trip index \(t\) just after which the renovation was made (such that \(0 \le t \le N\), with \(t = 0\) representing the renovation having been before the first original trip), it's optimal to:

- Rearrange all 1-observations before that time (observations \(o\) such that \(k+1 \le o \le i\), \(R_o = 1\), and \(I_i \le t\)) to have occurred after that time
- Rearrange all 0-observations after that time (observations \(o\) such that \(k+1 \le o \le i\), \(R_o = 0\), and \(I_i > t\)) to have occurred before that time

Given the minimum number \(x\) of observations which need to be rearranged (across all possible choices of \(t\)), our candidate value for \(D_{i,j}\) will then be \(D_{k,j-x} + 1\) (or \(\infty\) if \(j-x < 0\)).

The most direct, naive implementation of the above approach would be too slow, taking \(O(N^5)\) time (considering \(O(N^4)\) quadruples of \((i, j, k, t)\), and iterating over \(O(N)\) observations each time to count the number of trips needing rearrangement). However, the time complexity may be reduced to \(O(N^3)\) through a combination of two optimizations each removing a factor of \(N\):

1. We can observe that the value \(x\) described above is independent of \(j\), meaning that we only need to compute it once per pair of \((i, k)\).
2. For each pair of \((i, k)\), if we sweep over all observations in non-decreasing order of \(I\) value (considering only ones in that interval of positions), while keeping track of the number of 0-observations and 1-observations already encountered. This is sufficient to compute \(x\) with no additional time.


Code: // Railroad Renovations
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x)
{
  char c, r = 0, n = 0;
  x = 0;
  for (;;)
  {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else
      if ((c >= '0') && (c <= '9'))
        x = x * 10 + c - '0', r = 1;
      else
        if (r)
          break;
  }
  if (n)
    x = -x;
  return(1);
}

#define LIM 501

int N, K;
pair<int, PR> O[LIM];

// dyn[i][j] = min. renovations after first i observations (by position),
//             with j rearrangements
int dyn[LIM][LIM];

int ProcessCase()
{
  int i, j, k;
  // input
  Read(N), Read(K);
  Fox(i, N)
  {
    Read(O[i].x), Read(O[i].y.y);
    O[i].y.x = i;
  }
  // sort observations by position
  sort(O, O + N);
  // DP
  Fill(dyn, 60);
  dyn[0][0] = 0;
  Fox(i, N)
  {
    // can start interval here?
    if (i - 1 >= 0 && O[i].x == O[i - 1].x)
      continue;
    // consider all intervals starting here
    int C[2] = { 0 };
    set <PR> S;
    FoxI(j, i, N - 1)
    {
      // update interval info
      S.insert(O[j].y);
      C[O[j].y.y]++;
      // can end interval here?
      if (j + 1 < N && O[j].x == O[j + 1].x)
        continue;
      // compute min. cost for this interval (all 0s before all 1s)
      int cst = min(C[0], C[1]);
      int pc[2] = { 0 };
      for (auto o : S) // consider all 0-1 splitting points
      {
        pc[o.y]++;
        Min(cst, pc[1] + C[0] - pc[0]);
      }
      // update DP values
      FoxI(k, cst, K)
        Min(dyn[j + 1][k], dyn[i][k - cst] + (C[1] > 0));
    }
  }
  // compute answer
  int ans = INF;
  Fox(k, K + 1)
    Min(ans, dyn[N][k]);
  return(ans == INF ? -1 : ans);
}

int main()
{
  int T, t;
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %d\n", t, ProcessCase());
  return(0);
}