CareerCup

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

void Print(vector<int> const &a)
{
	for (int i = 0; i + 1 < a.size(); i += 2) {
		cout << "[" << a[i] << ", " << a[i + 1] << "] ";
	}
	cout << "\n";
}

int CountRec(vector<int> &a, unordered_map<int, int> &seat, unordered_map<int, int> &partner, 
	unordered_map<int, int> &swaps, unordered_map<string, int> &memo, int idx = 0)
{
	if (idx < 0 ||
		idx > a.size())
	{
		return -1;
	}
	if (idx == a.size()) {
		Print(a);
		return 0;
	}

	string memo_key;
	for (int i = idx; i < a.size(); ++i) {
		memo_key += to_string(a[i]) + "\t" + to_string(swaps[a[i]]) + "\n";
	}
	auto it = memo.find(memo_key);
	if (it != memo.end()) {
		return it->second;
	}

	if (partner[a[idx]] == a[idx + 1]) {
		return CountRec(a, seat, partner, swaps, memo, idx + 2);
	}

	int min_count = numeric_limits<int>::max();
	vector<int> idxes = {idx, idx + 1};
	for (int i : idxes) {
		int j = seat[partner[a[i == idx ? idx + 1 : idx]]];
		if (swaps[a[i]] < 2 &&
			swaps[a[j]] < 2)
		{
			swap(a[i], a[j]);
			swap(seat[a[i]], seat[a[j]]);
			++swaps[a[i]];
			++swaps[a[j]];
			int count = CountRec(a, seat, partner, swaps, memo, idx + 2);
			if (count != -1) {
				count++;
				min_count = min(min_count, count);
			}
			--swaps[a[i]];
			--swaps[a[j]];
			swap(seat[a[i]], seat[a[j]]);
			swap(a[i], a[j]);
		}
	}
	if (min_count == numeric_limits<int>::max()) {
		min_count = -1;
	}
	memo[memo_key] = min_count;
	return min_count;
}

int Count(vector<int> a) {
	if (a.size() % 2) {
		return -1;
	}

	unordered_map<int, int> seat;
	for (int i = 0; i < a.size(); ++i) {
		seat[a[i]] = i;
	}

	unordered_map<int, int> partner;
	for (int i = 0; i < a.size(); i += 2) {
		partner[i] = i + 1;
		partner[i + 1] = i;
	}

	unordered_map<int, int> swaps;
	unordered_map<string, int> memo;
	return CountRec(a, seat, partner, swaps, memo);
}

void Shuffle(vector<int> &a)
{
	for (int i = 0; i < a.size(); ++i) {
		swap(a[i], a[i + (rand() % (a.size() - i))]);
	}
}

int main()
{
	srand(time(NULL));
	int size = 10 * 2;
	vector<int> a;
	while (a.size() < size) {
		a.push_back(a.size());
	}
	Shuffle(a);
	Print(a);
	cout << Count(a) << "\n";
}

Java Code

import java.util.HashMap;
import java.util.Scanner;

public class PairSwap {
	private static int counter = 0;
	private static Scanner inp;
	public static int  findIndex (int[] array, int t) {
        if (array == null) return -1;
        int len = array.length;
        int i = 0;
        while (i < len) {
            if (array[i] == t) return i;
            else i++;
        }
        return -1;
    }

	public static void main(String[] args) {
		inp = new Scanner(System.in);
		int n = inp.nextInt();// Total pair
		int m = 2 * n;// Total number
		int[] mapping = new int[2 * n];// array of random sittings
		for (int i = 0; i < 2 * n; i++) {
			mapping[i] = inp.nextInt();
		}
		HashMap<Integer, Integer> pairs = new HashMap<Integer, Integer>();// pair in key value form
		HashMap<Integer, Integer> rpairs = new HashMap<Integer, Integer>();// pair in value key form
		for (int i = 0; i < m; i += 2) {
			pairs.put(mapping[i], mapping[i + 1]);
		}
		for (int i = 0; i < m; i += 2) {
			rpairs.put(mapping[i + 1], mapping[i]);
		}

		int[] arr = new int[m];// array of random sittings
		for (int i = 0; i < m; i++) {
			arr[i] = inp.nextInt();
		}
		for (int i = 0; i < m; i += 2) {
			if (pairs.containsKey(arr[i])) {
				if (arr[i + 1] != pairs.get(arr[i])) {
					int ind = findIndex(arr, pairs.get(arr[i]));
					int temp = arr[i + 1];
					arr[i + 1] = arr[ind];
					arr[ind] = temp;
					counter++;
				}
			} else {
				if (arr[i + 1] != rpairs.get(arr[i])) {
					int ind = findIndex(arr, rpairs.get(arr[i]));
					int temp = arr[i + 1];
					arr[i + 1] = arr[ind];
					arr[ind] = temp;
					counter++;
				}
			}
		}
		System.out.println(counter);
	}
}

Java Code

import java.util.HashMap;
import java.util.Scanner;

public class PairSwap {
	private static int counter = 0;
	private static Scanner inp;
	public static int  findIndex (int[] array, int t) {
        if (array == null) return -1;
        int len = array.length;
        int i = 0;
        while (i < len) {
            if (array[i] == t) return i;
            else i++;
        }
        return -1;
    }

	public static void main(String[] args) {
		inp = new Scanner(System.in);
		int n = inp.nextInt();// Total pair
		int m = 2 * n;// Total number
		int[] mapping = new int[2 * n];// array of random sittings
		for (int i = 0; i < 2 * n; i++) {
			mapping[i] = inp.nextInt();
		}
		HashMap<Integer, Integer> pairs = new HashMap<Integer, Integer>();// pair in key value form
		HashMap<Integer, Integer> rpairs = new HashMap<Integer, Integer>();// pair in value key form
		for (int i = 0; i < m; i += 2) {
			pairs.put(mapping[i], mapping[i + 1]);
		}
		for (int i = 0; i < m; i += 2) {
			rpairs.put(mapping[i + 1], mapping[i]);
		}

		int[] arr = new int[m];// array of random sittings
		for (int i = 0; i < m; i++) {
			arr[i] = inp.nextInt();
		}
		for (int i = 0; i < m; i += 2) {
			if (pairs.containsKey(arr[i])) {
				if (arr[i + 1] != pairs.get(arr[i])) {
					int ind = findIndex(arr, pairs.get(arr[i]));
					int temp = arr[i + 1];
					arr[i + 1] = arr[ind];
					arr[ind] = temp;
					counter++;
				}
			} else {
				if (arr[i + 1] != rpairs.get(arr[i])) {
					int ind = findIndex(arr, rpairs.get(arr[i]));
					int temp = arr[i + 1];
					arr[i + 1] = arr[ind];
					arr[ind] = temp;
					counter++;
				}
			}
		}
		System.out.println(counter);
	}

}

import java.util.HashMap;
import java.util.Scanner;

public class PairSwap {
	private static int counter = 0;
	private static Scanner inp;
	public static int  findIndex (int[] array, int t) {
        if (array == null) return -1;
        int len = array.length;
        int i = 0;
        while (i < len) {
            if (array[i] == t) return i;
            else i++;
        }
        return -1;
    }

	public static void main(String[] args) {
		inp = new Scanner(System.in);
		int n = inp.nextInt();// Total pair
		int m = 2 * n;// Total number
		int[] mapping = new int[2 * n];// array of random sittings
		for (int i = 0; i < 2 * n; i++) {
			mapping[i] = inp.nextInt();
		}
		HashMap<Integer, Integer> pairs = new HashMap<Integer, Integer>();// pair in key value form
		HashMap<Integer, Integer> rpairs = new HashMap<Integer, Integer>();// pair in value key form
		for (int i = 0; i < m; i += 2) {
			pairs.put(mapping[i], mapping[i + 1]);
		}
		for (int i = 0; i < m; i += 2) {
			rpairs.put(mapping[i + 1], mapping[i]);
		}

		int[] arr = new int[m];// array of random sittings
		for (int i = 0; i < m; i++) {
			arr[i] = inp.nextInt();
		}
		for (int i = 0; i < m; i += 2) {
			if (pairs.containsKey(arr[i])) {
				if (arr[i + 1] != pairs.get(arr[i])) {
					int ind = findIndex(arr, pairs.get(arr[i]));
					int temp = arr[i + 1];
					arr[i + 1] = arr[ind];
					arr[ind] = temp;
					counter++;
				}
			} else {
				if (arr[i + 1] != rpairs.get(arr[i])) {
					int ind = findIndex(arr, rpairs.get(arr[i]));
					int temp = arr[i + 1];
					arr[i + 1] = arr[ind];
					arr[ind] = temp;
					counter++;
				}
			}
		}
		System.out.println(counter);
	}

}

import java.util.HashMap;
import java.util.Scanner;

public class PairSwap {
	private static int counter = 0;
	private static Scanner inp;
	public static int  findIndex (int[] array, int t) {
        if (array == null) return -1;
        int len = array.length;
        int i = 0;
        while (i < len) {
            if (array[i] == t) return i;
            else i++;
        }
        return -1;
    }

	public static void main(String[] args) {
		inp = new Scanner(System.in);
		int n = inp.nextInt();// Total pair
		int m = 2 * n;// Total number
		int[] mapping = new int[2 * n];// array of random sittings
		for (int i = 0; i < 2 * n; i++) {
			mapping[i] = inp.nextInt();
		}
		HashMap<Integer, Integer> pairs = new HashMap<Integer, Integer>();// pair in key value form
		HashMap<Integer, Integer> rpairs = new HashMap<Integer, Integer>();// pair in value key form
		for (int i = 0; i < m; i += 2) {
			pairs.put(mapping[i], mapping[i + 1]);
		}
		for (int i = 0; i < m; i += 2) {
			rpairs.put(mapping[i + 1], mapping[i]);
		}

		int[] arr = new int[m];// array of random sittings
		for (int i = 0; i < m; i++) {
			arr[i] = inp.nextInt();
		}
		for (int i = 0; i < m; i += 2) {
			if (pairs.containsKey(arr[i])) {
				if (arr[i + 1] != pairs.get(arr[i])) {
					int ind = findIndex(arr, pairs.get(arr[i]));
					int temp = arr[i + 1];
					arr[i + 1] = arr[ind];
					arr[ind] = temp;
					counter++;
				}
			} else {
				if (arr[i + 1] != rpairs.get(arr[i])) {
					int ind = findIndex(arr, rpairs.get(arr[i]));
					int temp = arr[i + 1];
					arr[i + 1] = arr[ind];
					arr[ind] = temp;
					counter++;
				}
			}
		}
		System.out.println(counter);
	}
}

static int countSwaps(int[][] seats) {
        int n = seats.length;
        HashMap<Integer, Integer> unmatches = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            if (seats[i][0] == seats[i][1]) {
                continue;
            }

            unmatches.put(seats[i][0], seats[i][1]);
        }


        int count = 0;
        while (!unmatches.isEmpty()) {
            int l1, r1, l2, r2;
            l1 = unmatches.keySet().iterator().next();
            r1 = unmatches.get(l1);
            l2 = r1;
            r2 = unmatches.get(l2);

            unmatches.put(l1, r2);
            unmatches.put(l2, r1);
            ++count;

            unmatches.remove(l2);

            if (l1 == r2) {
                unmatches.remove(l1);
            }
        }

        return count;
    }