Check if a sequence is composed of two identical sequences

Question

The problem is to find for a 1<=n<=50000-element sequence of numbers (1 to 10^5) if such a subsequence can be chosen that the remaining elements will create another copy of the chosen subsequence. In other words, if the original sequence was made by intertwining two copies of some subsequence. If so, we have to additionally print the original subsequence. My idea was to naively seperate every other number of the same kind into two subsequences. So, for example, the first subsequence would get 1st 5, 3rd 5 and 1st 4 and the second one would get 2nd 5, 4th 5 and 2nd 4. I thought the sequence cannot be expressed as a combination of two copies like that iff it has an odd number of some numbers in it. However, the entire approach is faulty and very rarely gives good answers;

Please help me find a more clever algorithm that will actually solve the problem. My implementation of the naive approach for better understanding (C++):

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<short> arr(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }

    vector<vector<unsigned short>> positions(10001, vector<unsigned short>(0));

    for (int i = 0; i < n; ++i)
    {
        positions[arr[i]].push_back(i);
    }

    vector<unsigned short> out;

    for (int i = 0; i <= 10000; ++i)
    {
        if (positions[i].size() % 2) 
        {
            cout << "NO" << "\n";
            return 0;
        }

        for (int j = 0; j < positions[i].size(); j += 2)
        {
            out.push_back(positions[i][j]);
        }
    }

    sort(out.begin(), out.end());

    cout << "YES" << "\n";
    for (int i = 0; i < out.size(); ++i)
    {
        cout << arr[out[i]] << " ";
    }
}

Answer 1

You can solve this using backtracking. There is also some optimization possible. You know that the first number has to be the first number of the sequence. So all letters between the first and the second occurence of this number have to follow in the sequence. Similarly for the last number in the sequence. Additionally you could check whether there are enough numbers left to complete the sequence.

public int[] solve(int[] arr) {
    if (arr.length % 2 != 0)
        return null;
    int[] solution = new int[arr.length / 2];
    if (solve(arr, 0, 0, solution))
        return solution;
    return null;
}

private boolean solve(int[] arr, int i, int j, int[] solution) {
    if (i == j) {
        solution[i] = arr[i + j];
        return solve(arr, i + 1, j, solution);
    } else if (i == solution.length) {
        for (int k = 0; k + i + j < arr.length; k++)
            if (arr[k + i + j] != solution[j + k])
                return false;
        return true;
    } else {
        for (int k = 0; i + k <= solution.length; k++) {
            if (arr[i + j + k] == solution[j] && solve(arr, i + k, j + 1, solution))
                return true;
            if (i + k < solution.length)
                solution[i + k] = arr[i + j + k];
        }
        return false;
    }
}

This is only checking left to right and not from both ends. Other possible improvements:

• Check if the count for each number is even at the start
• Keep track of the number count so you know earlier when a number cannot go into the first sequence any more because it has already half of them

It is Java code, but it can easily be translated to C++. Arrays are passed by reference. I tested some simple cases and for those it worked.

With memoization I could easily solve problems up to 50000 in some ms. But I had to increase the stack size to 100M. You may want to rewrite this to an iterative solution instead of a recursive one.

public static int[] solve(int[] arr) {
    if (arr.length % 2 != 0)
        return null;
    int[] solution = new int[arr.length / 2];
    if (solve(arr, 0, 0, solution, new Node(null, null)))
        return solution;
    return null;
}

private static boolean solve(int[] arr, int i, int j, int[] solution, Node node) {
    if (node.checked)
        return false;
    if (i == j) {
        if (node.children.containsKey(arr[i + j]))
            node = node.children.get(arr[i + j]);
        else
            node = new Node(node, arr[i + j]);
        if (node.checked)
            return false;
        solution[i] = arr[i + j];
        Node n = new Node(node, solution[i]);
        if (solve(arr, i + 1, j, solution, n))
            return true;
        n.checked = true;
        return false;
    } else if (i == solution.length) {
        for (int k = 0; k + i + j < arr.length; k++)
            if (arr[k + i + j] != solution[j + k]) {
                node.checked = true;
                return false;   
            }
        return true;
    } else {
        Node n = node;
        for (int k = 0; i + k <= solution.length; k++) {
            if (arr[i + j + k] == solution[j] && solve(arr, i + k, j + 1, solution, n))
                return true;
            if (i + k < solution.length) {
                if (n.children.containsKey(arr[i + j + k]))
                    n = n.children.get(arr[i + j + k]);
                else
                    n = new Node(n, arr[i + j + k]);
                if (n.checked)
                    return false;
                solution[i + k] = arr[i + j + k];
            }
        }
        node.checked = true;
        return false;
    }
}

private static class Node {
    public boolean checked;
    public Map<Integer, Node> children = new HashMap<>();
    public Node(Node parent, Integer value) {
        if (parent != null)
            parent.children.put(value, this);
    }
}