Problem: bitstrings_as_a_service (2019 round2)

Carlos knows that the key to sustained customer loyalty is early customer
acquisition and constant re-engagement. With that in mind, he's setting his
sights on sugary cereals. Kids love it, and they keep coming back for more. He
has a proposal for Post, the well-known manufacturer of Alpha-Bits:

_ "For 60 years these bits have been made of letters, but kids today are tired
of letters for breakfast. Let me show you something truly revolutionary: bits
made of numbers!" _

The executives at Post would like to assess the feasibility of producing
numeric bits. In particular, they want to see if Carlos can create a string of
bits, **B**, of length **N**. In this string, each character is either `'0'`
or `'1'`.

Carlos has been given a list of **M** requirements. The _i_th requirement
states that the substring **BXi...Yi** must be a palindrome. The new cereal
surely won't succeed without appealing to children's acute sense of symmetry.

Furthermore, the number of zeroes and ones in **B** must be as close as
possible. In other words, if `C(b)` is the number of occurrences of bit _b_ in
**B**, then the absolute difference `|C(0) - C(1)|` must be minimized. The
margins on cereal are razor thin, and as everybody knows, bits are produced in
pairs, so it's wasteful to use more of one sort than the other.

Help Carlos build any bitstring **B** consistent with all of these
requirements (and with minimal difference between the number of zeroes and
ones). It's guaranteed that such a bitstring exists for every given set of
requirements.

### Input

Input begins with an integer **T**, the number of bitstrings that Post has
commissioned. For each bitstring, there is first a line containing the space-
separated integers **N** and **M**. Then, **M** lines follow, the _i_th of
which contains the space-separated integers **Xi** and **Yi**.

### Output

For the _i_th commission, print a line containing "Case #_i_: " followed by a
valid bitstring **B**.

### Constraints

1 ≤ **T** ≤ 350  
1 ≤ **N** ≤ 4,000  
0 ≤ **M** ≤ 10,000  
1 ≤ **Xi** ≤ **Yi** ≤ **N**  

### Explanation of Sample

In the first case, the minimum absolute difference between the number of
zeroes and ones is 0 (with 2 of each). **5 other outputs would also be
accepted** for this case: "0011", "0101", "0110", "1001", and "1010". **For
each of the remaining sample cases, various other outputs would similarly be
accepted.**

In the second case, the minimum achievable difference is 2.

In the third case, the minimum achievable difference is 2.

In the fourth case, the minimum achievable difference is 1.

In the fifth case, the minimum achievable difference is 0.

In the sixth case, the minimum achievable difference is 9.



Sample input:
6
4 0
6 1
1 6
4 2
1 2
2 4
5 3
3 5
2 2
2 4
10 5
3 6
1 4
6 8
5 9
9 10
25 10
17 20
11 15
2 3
20 22
8 8
24 25
7 12
1 8
14 18
15 21


Sample output:
Case #1: 1100
Case #2: 110011
Case #3: 1101
Case #4: 01010
Case #5: 1001100011
Case #6: 0001100011001000000000111



Code: // Bitstrings as a Service
// Solution by Jacob Plachta

#define DEBUG 0

#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 <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);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

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 4001

int N,M,K;
int comp[LIM],sz[LIM],val[LIM];
vector<int> con[LIM];
int dyn[LIM][LIM];

void rec(int i)
{
		if (comp[i]>=0)
			return;
	comp[i]=K;
	sz[K]++;
	int j;
		Fox(j,Sz(con[i]))
			rec(con[i][j]);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int i,j;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
				Fox(i,N)
					con[i].clear();
			// input, and create graph of bit equalities
			Read(N),Read(M);
				while (M--)
				{
					Read(i),Read(j),i--,j--;
						while (j>i)
						{
							con[i].pb(j);
							con[j].pb(i);
							i++,j--;
						}
				}
			// find all components of equal bits
			K=0;
			Fill(sz,0);
			Fill(comp,-1);
				Fox(i,N)
					if (comp[i]<0)
					{
						rec(i);
						K++;
					}
			// DP on component value assignments
			Fill(dyn,-1);
			dyn[0][0]=0;
				Fox(i,K)
					Fox(j,N)
						if (dyn[i][j]>=0)
							dyn[i+1][j]=dyn[i+1][j+sz[i]]=j;
			// trace back to assign values to components
				Fox(i,N+1)
				{
					if (dyn[K][j=N/2+i]>=0)
						break;
					if (dyn[K][j=N/2-i]>=0)
						break;
				}
				FoxR1(i,K)
				{
					val[i-1]=(dyn[i][j]==j ? 0 : 1);
					j=dyn[i][j];
				}
			// output
			printf("Case #%d: ",t);
				Fox(i,N)
					printf("%d",val[comp[i]]);
			printf("\n");
		}
	return(0);
}