Connection Status:
Competition Arena > OddPairRemoval

OddPairRemoval

2020 TCO Semi 1 · 2020-11-12 · by majk

2020 TCO Semi 1 · 2020-11-12 · by majk · Brute Force, Dynamic Programming
Class Name: OddPairRemoval
Return Type: long[]
Method Name: waysToRemove
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You are given the int[] a of length 2*n. This array contains each of the integers 1 through n exactly twice.

A removal is the following action:

  • choose two indices i and j such that j-i is odd and a[i] = a[j]
  • delete a[i] and a[j] from the array
  • concatenate the remaining parts of a into a shorter array
For example, consider the array a = {1, 2, 4, 1, 2, 3, 4, 3}.
  • You may pick i = 1, j = 4 to remove both occurrences of the integer 2 and obtain the new array {1, 4, 1, 3, 4, 3}.
  • You may not pick i = 1, j = 2, as a[i] != a[j].
  • You may not pick i = 2, j = 6, as j-i is even.

You may perform zero or more removals, with the additional constraint that the removed values must be strictly increasing.

Return the long[] res of length n+1, where res[i] is the number of ways to remove exactly i pairs of integers from a.

Constraints

  • n will be between 1 and 52, inclusive.
  • The length of a will be exactly 2*n.
  • Each integer between 1 and n, inclusive, will have exactly two occurrences in a.
Examples
0)
{1, 2, 1, 3, 2, 3}
Returns: {1, 1, 1, 0 }

We have the following options: We don't remove anything. We remove the 2s and then stop. We remove the 2s, producing the array {1, 1, 3, 3}, and then we remove the 3s. There is 1 way to remove no pairs, 1 way to remove one pair, 1 way to remove two pairs, and 0 ways to remove all three pairs. Therefore, the correct return value is {1, 1, 1, 0}. Note that in the beginning we cannot remove the 1s because their distance is even. Once we remove the 2s, the distance between the 1s becomes odd. However, now we cannot remove them due to the additional constraint that removed values must be increasing.

1)
{1, 2, 3, 1, 2, 3}
Returns: {1, 3, 0, 0 }

We can remove any number. Afterwards, all the other pairs will be at even distance and further removal will be impossible.

2)
{1, 1, 2, 2, 3, 3, 4, 4}
Returns: {1, 4, 6, 4, 1 }

The numbers are independent, hence any subset can be removed.

3)
{2, 3, 1, 6, 2, 5, 3, 7, 4, 1, 4, 7, 5, 6}
Returns: {1, 3, 5, 6, 6, 6, 4, 1 }
4)
{1, 1}
Returns: {1, 1 }

Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OddPairRemoval with a public method vector<long long> waysToRemove(vector<int> a) · 64 test cases · 2 s / 256 MB per case

Submitting as anonymous