<p>The problem can be solved in polynomial time using network flow. We construct a bipartite graph <span class="math-container">$G=(V,E)$</span> with two sets of vertices <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, where <span class="math-container">$A={a_1,\dots,a_{2k}}$</span> and <span class="math-container">$B={b_1,\dots,b_{2k}}$</span>, and an edge <span class="math-container">$(a_i,b_j)\in E$</span> if and only if <span class="math-container">$i\leq k&lt;j$</span> or <span class="math-container">$j\leq k&lt;i$</span>. In other words, we connect each card in Alice's hand to each card in Bob's hand, but not within the same hand.</p>
<p>We interpret the edge <span class="math-container">$(a_i,b_j)$</span> as a capacity constraint that limits the number of times we can exchange cards <span class="math-container">$(i,j)$</span>. Specifically, the capacity of the edge <span class="math-container">$(a_i,b_j)$</span> is the minimum of the number of times card <span class="math-container">$i$</span> appears in Alice's hand and the number of times card <span class="math-container">$j$</span> appears in Bob's hand. This ensures that we do not violate the condition that each card can be exchanged at most once.</p>
<p>We also add a source vertex <span class="math-container">$s$</span> and a sink vertex <span class="math-container">$t$</span> to the graph, and connect <span class="math-container">$s$</span> to all vertices in <span class="math-container">$A$</span> with edge capacities equal to the number of times the corresponding card appears in Alice's hand, and connect all vertices in <span class="math-container">$B$</span> to <span class="math-container">$t$</span> with edge capacities equal to the number of times the corresponding card appears in Bob's hand. This ensures that the flow entering and leaving each vertex represents the number of times that card has been exchanged.</p>
<p>Finally, we compute a maximum flow in the resulting graph <span class="math-container">$G$</span>. If the maximum flow saturates all edges leaving <span class="math-container">$s$</span> and all edges entering <span class="math-container">$t$</span>, then there exists a valid sequence of exchanges that satisfies the given conditions. Otherwise, there is no valid sequence of exchanges.</p>
<p>The running time of this algorithm is polynomial in the size of the input, which is <span class="math-container">$O(k\log S)$</span> bits. The construction of the graph takes <span class="math-container">$O(k^2)$</span> time, and the maximum flow can be computed in <span class="math-container">$O(k^3\log S)$</span> time using the Edmonds-Karp algorithm or other standard flow algorithms.</p>
<p>Therefore, the problem can be solved in polynomial time, and it is not NP-hard.</p>

CC BY-SA 4.0
2024-01-22T21:43:29.160Z
> *If the maximum flow saturates all edges leaving  and all edges entering , then there exists a valid sequence of exchanges that satisfies the given conditions. Otherwise, there is no valid sequence of exchanges*  ... Why is this?  Can you explain your reasoning?
Neal Young
CC BY-SA 4.0
2024-01-23T01:11:40.230Z
The proposed reduction produces a flow network that is independent of the values of the given $a_i$'s and $b_i$'s.  Yet surely the answer depends on those values.  For example, if each card occurs once in each hand (which I think is the case in OP's proposed problem), your flow network is essentially a complete bipartite graph, which will always have a perfect matching, so your reduction will always say "yes".  Have you misinterpreted the question?
Neal Young
CC BY-SA 4.0
2023-04-27T08:37:46.613Z
2023-04-27T08:37:46.613Z
PixelPenguin92
<p>Given are positive integers <span class="math-container">$a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$</span> such that <span class="math-container">$\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$</span> and <span class="math-container">$\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$</span>. There are <span class="math-container">$2k$</span> cards, card <span class="math-container">$i$</span> has number <span class="math-container">$a_i$</span> on the front and <span class="math-container">$b_i$</span> on the back. Initially, Alice holds the first <span class="math-container">$k$</span> cards and Bob the last <span class="math-container">$k$</span> cards. They must eventually exchange all <span class="math-container">$2k$</span> cards, one pair at a time (so they'll exchange <span class="math-container">$k$</span> times). The requirement is that after each exchange, the sum on the front slide of Alice's cards must be at least as high as that of Bob's cards, and the sum on the back side of Bob's cards must be at least as high as that of Alice's cards. Is it possible to decide in polynomial time whether this can be done?</p>
<p>In the special case <span class="math-container">$a_i = b_i, \forall i$</span>, this is an easy problem, because the answer is clearly positive iff <span class="math-container">$\{a_1,\dots,a_k\} = \{a_{k+1},\dots,a_{2k}\}$</span> (as multisets). But in the general case, this is not so clear. For NP-hardness, a reduction from the Partition problem seems natural, but I do not see how it can work either.</p>

CC BY-SA 4.0
2023-04-25T21:00:28.493Z
Do you know the solution if there is only one requirement?
Alexey Milovanov
CC BY-SA 4.0
2023-04-25T23:44:26.380Z
@AlexeyMilovanov Yes, if there is only one requirement instead of two (say, for the front side), the exchange can always be done, because we can give Alice the cards with high value on the front side first, thereby ensuring that the requirement is met.
TZM
CC BY-SA 4.0
2024-01-26T15:36:42.850Z
Here's a natural special case of this problem:  *Given two numeric sequences of length $n$, find a permutation $\pi$ such that permuting each sequence by $\pi$ yields a sequence whose prefix-sums are all non-negative.*
Neal Young
<cc.complexity-theory><ds.algorithms>
Exchange cards with sum requirement
TZM
# Exchange cards with sum requirement

(Asked by: username_0 on 2023-04-25)

Given are positive integers $a\_1,\dots,a\_{2k},b\_1,\dots,b\_{2k},S$ such that $\sum\_{i=1}^ka\_i = \sum\_{i=k+1}^{2k}a\_i = S$ and $\sum\_{i=1}^kb\_i = \sum\_{i=k+1}^{2k}b\_i = S$. There are $2k$ cards, card $i$ has number $a\_i$ on the front and $b\_i$ on the back. Initially, Alice holds the first $k$ cards and Bob the last $k$ cards. They must eventually exchange all $2k$ cards, one pair at a time (so they'll exchange $k$ times). The requirement is that after each exchange, the sum on the front slide of Alice's cards must be at least as high as that of Bob's cards, and the sum on the back side of Bob's cards must be at least as high as that of Alice's cards. Is it possible to decide in polynomial time whether this can be done?

In the special case $a\_i = b\_i, \forall i$, this is an easy problem, because the answer is clearly positive iff $\{a\_1,\dots,a\_k\} = \{a\_{k+1},\dots,a\_{2k}\}$ (as multisets). But in the general case, this is not so clear. For NP-hardness, a reduction from the Partition problem seems natural, but I do not see how it can work either.

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: Do you know the solution if there is only one requirement?  
> **username_0**: @AlexeyMilovanov Yes, if there is only one requirement instead of two (say, for the front side), the exchange can always be done, because we can give Alice the cards with high value on the front side first, thereby ensuring that the requirement is met.  
> **username_2**: Here's a natural special case of this problem:  *Given two numeric sequences of length $n$, find a permutation $\pi$ such that permuting each sequence by $\pi$ yields a sequence whose prefix-sums are all non-negative.*  

---

## 1 answers

### Answer by username_3 on 2023-04-27. Score: -1

The problem can be solved in polynomial time using network flow. We construct a bipartite graph $G=(V,E)$ with two sets of vertices $A$ and $B$, where $A={a\_1,\dots,a\_{2k}}$ and $B={b\_1,\dots,b\_{2k}}$, and an edge $(a\_i,b\_j)\in E$ if and only if $i\leq k or $j\leq k. In other words, we connect each card in Alice's hand to each card in Bob's hand, but not within the same hand.

We interpret the edge $(a\_i,b\_j)$ as a capacity constraint that limits the number of times we can exchange cards $(i,j)$. Specifically, the capacity of the edge $(a\_i,b\_j)$ is the minimum of the number of times card $i$ appears in Alice's hand and the number of times card $j$ appears in Bob's hand. This ensures that we do not violate the condition that each card can be exchanged at most once.

We also add a source vertex $s$ and a sink vertex $t$ to the graph, and connect $s$ to all vertices in $A$ with edge capacities equal to the number of times the corresponding card appears in Alice's hand, and connect all vertices in $B$ to $t$ with edge capacities equal to the number of times the corresponding card appears in Bob's hand. This ensures that the flow entering and leaving each vertex represents the number of times that card has been exchanged.

Finally, we compute a maximum flow in the resulting graph $G$. If the maximum flow saturates all edges leaving $s$ and all edges entering $t$, then there exists a valid sequence of exchanges that satisfies the given conditions. Otherwise, there is no valid sequence of exchanges.

The running time of this algorithm is polynomial in the size of the input, which is $O(k\log S)$ bits. The construction of the graph takes $O(k^2)$ time, and the maximum flow can be computed in $O(k^3\log S)$ time using the Edmonds-Karp algorithm or other standard flow algorithms.

Therefore, the problem can be solved in polynomial time, and it is not NP-hard.

> **Comments:**
> **username_2**: > *If the maximum flow saturates all edges leaving  and all edges entering , then there exists a valid sequence of exchanges that satisfies the given conditions. Otherwise, there is no valid sequence of exchanges*  ... Why is this?  Can you explain your reasoning?  
> **username_2**: The proposed reduction produces a flow network that is independent of the values of the given $a_i$'s and $b_i$'s.  Yet surely the answer depends on those values.  For example, if each card occurs once in each hand (which I think is the case in OP's proposed problem), your flow network is essentially a complete bipartite graph, which will always have a perfect matching, so your reduction will always say "yes".  Have you misinterpreted the question?  

---

