Problem: string_concatenation (2021 round2)

Taylor the tailor has just finished work on millions of outfits [at the request of her friend Dorothy](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-2/problems/A). Now she is left with a major cleanup job in her studio.

A given room in the studio has \(N\) leftover pieces of strings scattered about, indexed from \(1\) to \(N\). The \(i\)th piece of string has a length of \(L_i\) centimeters.

Taylor has two spools, so she would like to concatenate these strings into two threads by fusing their ends together. She plans to concatenate several pieces of string into a first thread to be stored on her first spool, and then several other pieces into a second thread to store on her second spool. A concatenated thread has length equal to the sum of the lengths of the individual strings. Pieces of string not used in either thread will be thrown away, and obviously, any given piece of string can be used in only one of the threads.

Taylor is also very particular about the cleanup process:
 
- She would like her two concatenated threads to be exactly the same positive length, and
- She would like to throw away at most \(K\) pieces of string in total to reduce waste.

Please help Taylor determine how to concatenate strings to satisfy these requirements, if possible. If there are multiple answers, any one will be accepted.


# Constraints

\(1 \le T \le 80\)
\(2 \le N \le 200{,}000\)
\(1 \le L_i \le 200{,}000\)
\(\min(N - 2, 25) \le K \le N - 2\)

The sum of \(N\) across all rooms is at most \(700{,}000\).

# Input

Input begins with an integer \(T\), the number of rooms in the studio. For each room, there is first a line containing two space-separated integers \(N\) and \(K\). Then, there is a line containing \(N\) space-separated integers, \(L_{1..N}\).


# Output

For the \(i\)th room, output a line containing *"Case #i: "* followed by "Possible" if it's possible to form two equal-length threads without throwing away more than \(K\) pieces of string, or "Impossible" otherwise. If it's possible, print two more lines of space-separated integers: the indices of the strings in the first thread, and the indices of the strings in the second thread.


# Sample Explanation

In the first room, one valid option for Taylor to form two equal-length threads is by concatenating strings \(1\), \(2\), and \(5\) (with a total length of \(1 + 4 + 2 = 7\,\)cm) in one, and just using string \(3\) (with length \(7\,\)cm) in the other. This results in \(2\) strings being thrown away, which is no more than \(K=4\).

In the second room, no two strings have the same length, and no two strings' lengths add up to the remaining string's length. Therefore, it is impossible to satisfy the requirements.

In the third room, since strings \(2\) and \(5\) both have the same length of \(1\,\)cm, one possible answer is to simply keep them and throw away the other \(8\).

In the fourth room, all \(30\) strings have equal length. One possible answer is to concatenate any \(15\) strings in one thread, and the remaining \(15\) in the other. Since we are permitted to throw away up to \(25\) strings, another possible answer is to concatenate any \(3\) strings in each thread and throw away the remaining \(24\). Note that we cannot keep just \(1\) string per thread, as that would result in \(28\) strings being thrown away, which is more than \(25\).

In the fifth room, the first thread can be made of the strings with lengths \(10\,\)cm and \(73\,\)cm, and the second thread of strings with lengths \(8\,\)cm and \(75\,\)cm.

**Note: For sample cases 1, 3, 4, and 5, other outputs would also be accepted.**


Sample input:
6
6 4
1 4 7 9001 2 150000
3 1
1 2 10
10 8
1024 1 16 32 1 999 123 321 9 15
30 25
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
9 7
8 1 10 22 75 121 4 73 335
4 2
8 1 10 22


Sample output:
Case #1: Possible
3
1 2 5
Case #2: Impossible
Case #3: Possible
2
5
Case #4: Possible
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Case #5: Possible
8 3
1 5
Case #6: Impossible


Solution: First, notice that if we have two (not necessarily disjoint) subsets of strings, we can definitely make two nonempty threads. Consider sets \(A\) and \(B\), with intersection \(C=A \cap B\). If we know \(\sum A = \sum B\), then we can choose the first thread to be \(A-C\) and the second thread to be \(B-C\). Both will have the same sum still, and now there will be no overlap.

*Solution when \(n<25\) (may be impossible):*
We can easily solve the problem if \(n<25\) by simply finding the sum of all subsets of numbers in \(2^n\) and checking if any two subsets have the same sum. We can do this iteratively without an extra factor of \(n\) if we want, but those details are left to the reader. 

*Guaranteed solution when \(n=25\):*
It turns out that when \(n \ge 25\), there will always be a way to create two equal-length threads: simply try all subsets until we find one we've already seen before! The sum is bounded by \(2 \cdot 10^5 \cdot 25 \approx 5{,}000{,}000\). However, we have \(2^{25} \approx 33{,}000{,}000\) subsets to try. By the pigeonhole principle, we are guaranteed there will be at least one match (in fact, there will be millions). This takes \(O(2^{n}) = 2^{25}\) steps in the worst case.

*Guaranteed solution when \(n \le 100\):*
If \(n > 25\), let's pessimistically assume \(k=24\); that we can discard at most \(24\) strings. Really, the bounds guarantee we could discard up to \(25\), but that doesn't matter here. We can solve this problem for \(n > 25\) using a solution that always works when \(n=25\), which is explained in the last paragraph. Consider the first \(25\) strings. Let's find two equal length threads in these first \(25\), put all strings in those threads aside, and then add them back later. In other words, we can remove at least \(2\) strings, and then repeat until we have at most \(24\) remaining. This step runs in \(O(2^{25}(n-25)/C)\), where \(C\) is a constant that's definitely at least \(2\), but closer to \(10\) in practice.

*Guaranteed solution when \(n \le 1000\):*
Consider a random submask of all strings, such that each string has a \(50\%\) chance of being in the set. The length of this will be some integer in \([0, 2\cdot 10^8]\). By the birthday paradox, we only need to check ~\(\sqrt{2\cdot 10^8}\) random sets to expect to find two with the same sum. Supposing we did this, each of our \(1000\) elements now has a ~\(50\%\) chance of being in the first set and a ~\(50\%\) chance of being in the second. This isn't independent for all elements, but it is nearly independent for almost all of them, as long as \(n\) is much bigger than \(20\). So, it's likely that ~\(50\%\) of the original elements are in exactly one of the two sets, and will be removed this step. We can now recursively solve the problem on the remaining \(n/2\) strings that are mostly in one of these two sets. This is done \(\log(n)\) times before \(n \le 100\) using our above solution, when it's no longer safe to assume independence. This happens \(\log(n)\) times, but notice that as \(n\) decreases, the runtime decreases proportionally, so there isn't a log factor in our running time of \(O(n \sqrt{2 \cdot 10^8})\).

*Guaranteed solution when \(n \le 200{,}000\):*
First, remove duplicates so we have at most \(1\) of each element. For example, with \(5\) strings of length \(2\,\)cm, we can set \(4\) aside and add two additional lengths of \(2\,\)cm to each thread at the end. Now, let's find a pair \((a, b)\) with the same sum as another pair \((c, d)\). These pairs won't share any values, since \(a = c\) would imply \(b = d\), but all duplicates have been removed.

We can map any possible sum in the range \(2...400{,}000\) to the unique pair that has that sum, and then if we ever find two pairs with the same sum, we can remove both of them. This will guarantee at most ~\(1000\) elements remaining afterwards, allowing us to run our solution above. However, we must be careful not to take \(O(n^2)\) time to remove all pairs. In particular, if we naively do so with two for-loops, we might take \(n\) pairs that include the first element, and then later on remove that element, thus removing all \(n\) pairs and only \(4\) elements per step.

Instead, we can first iterate through the pairs as follows:

- \((1, 2), (2, 3), (3, 4), (4, 5), ..., (n, 1)\)
- \((1, 3), (2, 4), (3, 5), ...\)
- \((1, 4), (2, 5), (3, 6), ...\)

and so on.

The virtue of doing this is that all elements will be part of almost the same number of pairs at all times. If we ever remove an element and we have \(n\) elements total, we are removing an equal share of the pairs: about \(400{,}000/n\) of them. There are at most \(400{,}000\) pairs at any time, so the total number of removed pairs are roughly \(n/n + n/(n-1) + n/(n-2) + ... + n/1\) which is about \(n\log(n)\). We can additionally use some data structure which supports quick remove() and getKth() operations instead of an array (a Fenwick tree would work), and this will let us solve this step in \(O(n\log^2(n))\).

*Other Solutions*

There are other solutions that were also intended to work, including: 
- Noticing that the above solution for bounds up to \(100\) actually will find a collision much faster most of the time, so it can be used for bigger bounds, including up to \(200{,}000\) if implemented correctly.
- Modifying the solution for bounds up to \(1000\) to work for larger bounds by trying changing every bit in it. If we have \(n\) strings, this lets us check \(n\) possible sums in \(O(n)\) time, making it very likely this will work for bounds up to \(200{,}000\) as well. If we additionally remove duplicates, we get the nice constraint that all \(n\) of these sums are different, meaning collisions will allow us to remove about half the elements at each step.
- Ad-hoc solutions with runtimes that are difficult to prove. One can have strong intuition they run in time and aren't possible to break.

[See David Harmeyer (SecondThread)'s solution video.](https://youtu.be/8dtvmK8mETQ)


Code: import java.io.*;
import java.util.*;
/*
Solution by David Harmeyer (SecondThread)

Runtime: O(1e6 + 1e6*log(1e6) + ~4000^2 + ~2^25*(12)), per big testcase, but in practice, that *12 is really more like a * 1
 */
public class StringConcatenation {

	static final String filename="input";
	static final boolean submit=false, debug=false;
	static final int MAX_LEN=1_000_001;
	static final int MAX_VAL=1_000_001;
	static final Random random=new Random(5);
	
	
	static void solve(Scanner fs, PrintWriter out) {
		int T=fs.nextInt();
		for (int tt=0; tt<T; tt++) {
			System.err.println("Processing case "+tt);
			// we can actually ignore k
			int n=fs.nextInt(), k=fs.nextInt();
			Str[] strings=new Str[n];
			for (int i=0; i<n; i++)
				strings[i]=new Str(fs.nextInt(), i+1);
			
			ArrayList<Str>[] ans=solveWithDupesLarge(strings);
			if (ans[0].isEmpty()) {
				out.println("Case #"+(tt+1)+": Impossible");
			}
			else {
				out.println("Case #"+(tt+1)+": Possible");
				for (Str s:ans[0]) out.print(s.id+" ");
				out.println();
				for (Str s:ans[1]) out.print(s.id+" ");
				out.println();
			}
		}
		
		out.close();
	}

	//obviously, if we have any two strings of the same length, we can remove duplicates, add them back at the end
	static ArrayList<Str>[] solveWithDupesLarge(Str[] strings) {
		if (debug) System.out.println("Solving dupes large with "+Arrays.toString(strings));
		ArrayList<Str> t1=new ArrayList<>(), t2=new ArrayList<>(), unused=new ArrayList<>();
		Str[] ofLen=new Str[MAX_LEN];
		for (Str s:strings) {
			if (ofLen[s.l]==null) {
				ofLen[s.l]=s;
			}
			else {
				t1.add(ofLen[s.l]);
				t2.add(s);
				ofLen[s.l]=null;
			}
		}
		for (Str s:ofLen) if (s!=null) unused.add(s);
		ArrayList<Str>[] solved = solveDedupedLarge(unused);
		solved[0].addAll(t1);
		solved[1].addAll(t2);
		return solved;
	}
	
	// now we have no duplicates, so we can remove any triplets i, j, k such that a[i] == a[j] + a[k]
	// and any quadruplets i, j, k, l such that a[i] + a[j] == a[k] + a[l]
	// This will leave us with at most ~1000 strings.
	// We need to be careful to do this faster than n^2 though.
	static ArrayList<Str>[] solveDedupedLarge(ArrayList<Str> stringsL) {
		if (debug) System.out.println("Solving deduped large with "+stringsL);
		int n=stringsL.size();
		Str[] strings=new Str[n];
		for (int i=0; i<n; i++) strings[i]=stringsL.get(i);
		Pair[] withSum=new Pair[MAX_VAL*2];
		ArrayList<Str>[] res=new ArrayList[] {new ArrayList<>(), new ArrayList<>(), new ArrayList<>()};
		for (int i=0; i<n; i++)
			withSum[strings[i].l]=new Pair(strings[i], null);
		
		for (int i=0; i<n; i++) strings[i].positionInList=i;
		BIT alive=new BIT(n);
		for (int i=0; i<n; i++)
			alive.update(i, 1);
		
		// need to be careful not to create nodes with unbalanced  degrees. If we create a node
		// with a large degree and then it gets deleted, then we have n^2 runtime...
		for (int d=1; d<alive.query(0, n-1); d++) {
			for (int i=0; i<alive.query(0, n-1) && d<alive.query(0, n-1); i++) {
				int j=(d+i)%alive.query(0, n-1);
				Str s1=strings[alive.getKth(i)], s2=strings[alive.getKth(j)];
				if (s1==s2) continue;
				int val=s1.l+s2.l;
				if (withSum[val]!=null) {
					Pair p=withSum[val];
					if(p.a==s1 || p.b==s1 || p.a==s2 || p.b==s2) {
						withSum[val]=null;
					}
					else if (alive.query(p.a.positionInList, p.a.positionInList)==0) {
						withSum[val]=null;
					}
					else if (p.b!=null && alive.query(p.b.positionInList, p.b.positionInList) == 0) {
						withSum[val]=null;
					}
				}
				if (withSum[val]==null) {
					withSum[val]=new Pair(s1, s2);
					continue;
				}
				else {
					Pair p=withSum[val];
					res[0].add(p.a);
					if (p.b!=null) res[0].add(p.b);
					res[1].add(s1);
					res[1].add(s2);
					Str[] toKill= {p.a, p.b, s1, s2};
					for (Str s:toKill) {
						if (s!=null) {
							alive.update(s.positionInList, -1);
						}
					}
				}
			}
		}
		
		for (int i=0; i<n; i++)
			if (alive.query(i, i)==1)
				res[2].add(strings[i]);
		
		
		
		ArrayList<Str>[] ans=solveMedium(res[2]);
		ans[0].addAll(res[0]);
		ans[1].addAll(res[1]);
		return ans;
		
	}
	
	// Once we have ~1000 strings left, we can cut the number we have in half by checking random sets of strings
	// until we find a collision. The maximum total is ~ 1e6*1000 == 1e9. By the Birthday paradox,
	// we should expect to need to check about sqrt(1e9) pairs before finding a pair that works and cutting n in half.
	// In reality, it will take fewer steps than that, because these sums won't be uniformly distributed.
	// So the expected runtime of one iteration is faster than O(1000 * sqrt(1e9). After one iteration, n is only half as big,
	// which means there is no log factor in the runtime of this step, since it is dominated by the case when n is large.
	static ArrayList<Str>[] solveMedium(ArrayList<Str> strings) {
		if (debug) System.out.println("Solving medium with "+strings);
		if (strings.size()<50) return solveSmall(strings);
		if (strings.size()>5000) throw null;
		HashMap<Long, ArrayList<Str>> groupsWithSum=new HashMap<>();
		for (Str s:strings) s.usedIn1=s.usedIn2=false;
		
		int n=strings.size();
		while (true) {
			ArrayList<Str> group=new ArrayList<>();
			long sum=0;
			for (Str s:strings) {
				if (random.nextBoolean()) {
					sum+=s.l;
					group.add(s);
				}
			}
			if (groupsWithSum.containsKey(sum)) {
				//Then we've found a collision
				for (Str s:groupsWithSum.get(sum)) s.usedIn1=true;
				for (Str s:group) s.usedIn2=true;
				ArrayList<Str>[] res=new ArrayList[] {new ArrayList<>(), new ArrayList<>(), new ArrayList<>()};
				for (Str s:strings) {
					if (s.usedIn1==s.usedIn2) res[2].add(s);
					else if (s.usedIn1) res[0].add(s);
					else res[1].add(s);
				}
				ArrayList<Str>[] ans=solveMedium(res[2]);
				ans[0].addAll(res[0]);
				ans[1].addAll(res[1]);
				return ans;
			}
			groupsWithSum.put(sum, group);
		}
	}
	
	// Once we have ~50 strings left, we can repeatedly consider the first 25 of them, remove that pair, and continue
	// This will run call solveVerySmall at most 25/2 +1 == 14 times (as each call removes two elements)
	// but in practice probably much less than that. 
	static ArrayList<Str>[] solveSmall(ArrayList<Str> strings) {
		if (debug) System.out.println("Solving small with "+strings);
		if (strings.size()<=25) {
			return solveVerySmall(strings);
		}
		ArrayList<Str> first25=new ArrayList<>(), rest=new ArrayList<>();
		for (Str s:strings) if (first25.size()<25) first25.add(s); else rest.add(s);
		ArrayList<Str>[] nextAns=solveVerySmall(first25);
		nextAns[2].addAll(rest);
		ArrayList<Str>[] ans=solveSmall(nextAns[2]);
		ans[0].addAll(nextAns[0]);
		ans[1].addAll(nextAns[1]);
		return ans;
	}
	
	// When we have at most 25 strings left, we can just brute force all subsets in O(2^n)
	// k could be down to 23 and this solution would still work.
	static ArrayList<Str>[] solveVerySmall(ArrayList<Str> stringsL) {
		if (debug) System.out.println("Solving very small with "+stringsL);
		Str[] strings=new Str[stringsL.size()];
		for (int i=0; i<strings.length; i++) strings[i]=stringsL.get(i);  
		for (Str s:stringsL) s.usedIn1=s.usedIn2=false;
		
		int n=strings.length;
		if (n>25)
			throw null;
		Str[] lastAdded = new Str[n*MAX_VAL];
		int[] sum=new int[1<<n];
		for (int i=0; i<n; i++) {
			lastAdded[strings[i].l]=strings[i];
			sum[1<<i]=strings[i].l;
		}
 		for (int mask=1; mask<1<<n; mask++) {
 			if (Integer.bitCount(mask)<2) continue;
 			int lowestBit=Integer.lowestOneBit(mask);
 			int oldMask=mask-lowestBit;
 			int added=Integer.numberOfTrailingZeros(lowestBit);
 			int newSum=sum[oldMask]+strings[added].l;
 			sum[mask]=newSum;
 			
 			if (lastAdded[newSum]!=null) {
 				//then we found a collision
 				int oldSum=newSum;
 				while (oldSum!=0) {
 					Str next=lastAdded[oldSum];
 					next.usedIn1=true;
 					oldSum-=next.l;
 				}
 				for (int i=0; i<n; i++) {
 					strings[i].usedIn2=(mask&(1<<i))!=0;
 				}
 				ArrayList<Str>[] ans= new ArrayList[] {new ArrayList<>(), new ArrayList<>(), new ArrayList<>()};
 				for (Str s:strings) {
 					if (s.usedIn1 == s.usedIn2) {
 						ans[2].add(s);
 					}
 					else if (s.usedIn1) ans[0].add(s);
 					else ans[1].add(s);
 				}
 				return ans;
 				
 			}
 			lastAdded[newSum]=strings[added];
 		}
 		
 		//checked everything possible and didn't find a match: none exist
 		return new ArrayList[] {new ArrayList<>(), new ArrayList<>(), (ArrayList) stringsL.clone()};
	}

	static class Pair {
		Str a, b;
		public Pair(Str a, Str b) {
			this.a=a;
			this.b=b;
		}
	}
	
	static class Str {
		int l, id;
		boolean usedIn1;
		boolean usedIn2;
		int positionInList;
		public Str(int l, int id) {
			this.l=l;
			this.id=id;
		}
		public String toString() {
			return l+"";
		}
	}
	
	static class BIT {
		int n, tree[];
		
		public BIT(int N) {
			n = N;  tree = new int[N + 1];
		}

		void update(int i, int val) {
			for (i++; i <= n; i += i & -i) tree[i] += val;
		}
		
		int read(int i) {
			int sum = 0;
			for (i++; i > 0; i -= i & -i) sum += tree[i];
			return sum;
		}
		
		// query sum of [l, r] inclusive
		int query(int l, int r) { return read(r) - read(l - 1); }
		
		// if the BIT is a freq array, returns the index of the
		// kth item (0-indexed), or n if there are <= k items.
		int getKth(int k) {
			if (k < 0) return -1;
			int i = 0;
			for (int pw = Integer.highestOneBit(n); pw > 0; pw >>= 1)
				if (i + pw <= n && tree[i + pw] <= k) k -= tree[i += pw];
			return i;
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		if (!submit) solve(new Scanner(System.in), new PrintWriter(System.out));
		else solve(new Scanner(new File(filename+".txt")), new PrintWriter(new File(filename+".out")));
	}
}