Finding sequence of pairs with second element of previous pair matching first element of next pair

I am interested in efficient ways of doing certain problem.

I have list of $ n$ pairs, where $ n$ is usually a few houndred thousands and each pair’s element is an integer (let’s assume it is integer from $ 0$ to $ 10000$ ) and I am trying to find a sequence such that it start and ends at chosen integer (we can assume it is eg. $ 0$ ) and second element of previous pair matches first element of next pair. So as an example, if we have set of pairs $ \{(0,1), (1,3), (3, 2) (3,0)\}$ the valid sequence would be eg. $ (0,1), (1,3), (3, 0)$ . If there is a few answers then I can find arbitrary one. Moreover it is no certain that my list of pairs actually has a solution. If it does not have solution, then the method should return no valid solutions.

I think that maybe some kind of dynamic programming could be useful here, but I don’t really have an idea for something better than just checking all the options, which I am almost certain is quite bad. Do you have any interesting insight about this problem?

Prove that if you pair arbitrarily pair up the elements of an array A of size n to get n/2 pairs,

then you discard pairs of unequal elements and keep just one from the pairs of matching elements. Then the resulting collection will have a majority if and only if A had a majority, i.e. there exists an element with more than floor(n/2) occurrences.

I am very confused about how to go about proving this. It is from a textbook DPV problem 2.23. I am trying to prove it but I end up disproving it.

I.e. Suppose we have an array of n elements A[], that has a majority of element x. that means A.count(x) > floor(n/2). Now suppose that if we add two different elements, [a, b] to array A, x is no longer the majority. Then: A.count(x) <= floor(n/2) + 1 -> A.count(x) = floor(n/2) + 1. But now if we apply the same procedure and pair [a, b] together, then by definition the resulting array should have a majority, even though the original [….] o [a, b] did not.

Count number of pairs of elements whose product is a perfect square

Given two arrays whose elements lie between $ [1,10^5]$ and the size of arrays is $ [1,10^5]$ , how can we find the total number of pairs of elements from these arrays such that their product is a perfect square? The arrays may have same elements.

For example:

Array 1: {1, 2, 4, 5}

Array 2: {4, 8, 16, 125}

Output : 6

The pairs are (1, 4), (1, 16), (2, 8), (4, 4), (4, 16), (5, 125).

If the array size is $ 10^5$ , an $ n^2$ algorithm would be inefficient.

Time complexity of combinations of n pairs of parentheses

I have the following code snippet for combinations of n pairs of parentheses.

def parens(n):     if n <= 0:         return ['']     else:         combinations = []         helper('', n, n, combinations)         return combinations   def helper(string, left, right, combinations):     if left <= 0 and right <= 0:         combinations.append(string)     else:         if left > 0:             helper(string + '(', left - 1, right, combinations)         if right > left and right > 0:             helper(string + ')', left, right - 1, combinations) 

What’s the reasonable estimation of the time complexity of it?

My trial:

  1. (2n)!/n!n! since it’s full permutation with the same elelment with more limitation:(upper bound)
  2. Resolve recurrence: T(n) = 2T(n-1) => O(2^n)

Algorithm for sorting pairs of items

I have a real world problem where I have a list of nodes. Each ones contains a name and the name of the node before it in order. I am trying to devise an algorithm to sort these in order. The problem is that any two random nodes will not tell my anything about their order unless they happen to be lie next to each other, so I can’t use a traditional sorting algorithm.

When I try to work through through ideas everything basically comes down to “grab the node at the start and then place it after the correct node” then repeat with the next node at start of the list. Problem is this has worse case O(n^2) complexity if the items are reversed. Any ideas of how to effectively sort a problem like this?

$O(k)$ Algorithm to find the first $k$ pairs of Magic numbers $a$ and $b$ such that $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $, with restrictions

Provide an $ O(k)$ algorithm to find $ k$ – magic pairs of positive integers a and b of type signed int where a magic pair is defined as $ \sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $ . You can’t use the summation formula $ \frac{N \cdot (N+1)}{2}$ as it would result in an overflow. Even you can’t run sums such as sum1 and sum2, it’s still going to overflow.

Example: (6,8) (35,49) (204,288) are the first three Magic Pairs.
P.C: This was our recent examination question, I am curious to know the algorithm.

Partition into pairs with minimum absolute difference, NP-hard?

I have a set $ S$ of an even number of positive elements $ 2m$ and $ m$ values $ t_1,t_2,\ldots,t_m$ where each $ t_i\leq1$ for all $ i$ .

The question is: can you select $ m$ pairs $ (a_i,b_i)$ from $ S$ such that $ |a_i-b_i|\geq t_i$ ?

I was trying to prove that this problem is NP-hard by a reduction from 3-Partition Problem. I failed because if I choose the numbers as in 3-partition I cannot guarantee that their absolute difference is at least $ t_i$ .

Do you have any hints?

Partition a multiset into pairs that sum up to given numbers?

Given a multiset of $ 2m$ positive numbers, $ S=\{s_1,s_2,\ldots,s_{2m}\}$ and given $ m$ targets $ t_1,t_2,\ldots,t_m$ . Can we partition $ S$ into $ m$ pairs $ (a_i,b_i)$ such that $ a_i+b_i=t_i$ , where $ a_i\ne b_i$ and $ a_i,b_i\in S$ ?

For example for $ S=\{1,4,6,1,2,5\}$ and $ t_1=7$ , $ t_2=t_3=6$ . The answer is YES and the pairs are $ (1,6)$ , $ (2,4)$ , and $ (1,5)$ .

Minimizing the iterative sum of pairs of numbers in a list

Given the tuple (list, value):

$ $ \left(\left[x_1, x_2, \cdots x_n\right], y\right)$ $

You may choose two adjacent values in the list to modify the tuple as:

$ $ \left(\left[x_1, x_2, \cdots x_{i-1}, (x_i + x_{i+1}), x_{i+2} \cdots x_n\right], y + x_{i} + x_{i+1}\right)$ $

Iterate until:

$ $ \left(\left[\sum_i x_i\right], y + z\right)$ $

What is the optimal set of choices that minimizes $ z$ ?

Intuitively, you never want to operate on the largest number in the list. But the largest number in this list changes as you add values together. In other words, the optimal solution is not necessarily obtained by an optimal solution of a sub-problem.

A greedy solution would start by taking the smallest number in this list and adding it to the smaller of its adjacent numbers. This solution, while close, is not equivalent to the value returned by brute force search. This points to the fact the some locally optimal step is not globally optimal, which could be connected to the fact that the largest element of the list changes as values are added together.