PROBLEM LINK:Author: Kevin Atienza DIFFICULTY:Easy PREREQUISITES:Greedy PROBLEM:Find a matching between two arrays $S$ and $T$ that minimizes the number of pairs that are equal. QUICK EXPLANATION:For a value $v$, let $C_v$ be the number of times $v$ appears in $S$ and $T$ combined. Let $v'$ be the value with the maximum such count, i.e. $C_{v'} \ge C_v$ for all $v$. Then the minimum number of matches is $\max(C_{v'}  N, 0)$. To obtain such a matching, first match $v'$ with itself $\max(C_{v'}  N, 0)$ times. Then, select the value that appears the most number of times among all unmatched values, then match this with a different value in the other array. It is guaranteed that this value exists. So repeat this until all values are matched. EXPLANATION:As shown in the sample input, there are some cases where we can't avoid having equal pairs. One clear case is when the mostoccurring value appears more than $N$ times. In this case, we can show that this value will be paired with itself at least once: There are $N$ pairs, each pair having two values, so by the pigeonhole principle, this value appears twice in some pair. In fact, we can extend this argument to show that if the mostoccurring value $v$ appears $x > N$ times, then at least $x  N$ pairs match $v$ with itself. This gives us the lower bound of $\max(x  N, 0)$ on the minimum number of equal pairs. But is this bound tight? Well, let's see. if $x > N$, then certainly this can be achieved. Suppose $v$ appears $s$ times in $S$ and $t$ times in $T$. Note that $s + t = x$. Then:
Thus, we have found a matching where there are exactly $\max(x  N, 0) = x  N$ equal pairs. So this takes care of the case $x > N$. But what if $x \le N$? Can we achieve $\max(x  N, 0) = 0$ equal pairs? One idea might be to match the mostoccurring values first. However, depending on how you do it, it might not work. For example, consider the example $S = [1, 1, 1, 2]$ and $T = [3, 3, 3, 2]$. $1$ and $3$ are the mostoccurring, so we match them first. Unfortunately, if you do it this way, you'll be left with just $2$s for the final pair, giving you an equal pair! Fortunately, we can fix this algorithm. The mistake above is assuming that we can match all $1$s with $3$s. The problem with that is, after matching $1$ and $3$ twice, the mostoccurring value becomes $2$, so we need to switch to matching $2$ instead. The adjusted algorithm becomes:
Clearly, this produces a matching with no equal pairs, but this only works if in step 3 or 4, the value $w$ exists. During the first pass, it's clear that $w$ exists, but in later passes this isn't so clear. We can prove it by showing the following invariant: At any point during the algorithm, the mostoccurring value in $S$ and $T$ combined appears at most $S$ times. If this is true, then during step 3, $T$ cannot consist purely of $v$s because that would mean $v$ appears at least $T+1 > S$ times. Thus, there must be some value $w \not= v$ in $T$. A similar statement is true for step 4. We can show it with induction and casebycase analysis. For the base case, this is true by assumption. For the inductive case, assume it holds true at some point during the algorithm. We want to show that it still holds after performing either step 3 or step 4. Specifically, if the mostoccurring value appears at most $S$ times, then after doing step 3 or 4, the new mostoccurring value appears at most $S  1$ times.
This means that the algorithm above is correct! Time Complexity:$O(N^2)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 Jun '16, 06:18

I was getting wrong answer,although i believe the solution is correct(i have put an assertion for the same in my code too)..Can anybody get a case where it isn't working ? Solution Id: https://www.codechef.com/viewsolution/10486331 Thanks in Advance And one more thing,if the complexity of the solutoin provided in this editorial is O(N^2) then how is it supposed to work ? This is frustrating!!! answered 15 Jun '16, 14:51

O(N^2) is supposed to work, Check the constraints again, "The sum of the Ns in a single test file is ≤ 3×105"; answered 16 Jun '16, 14:32

I have same problem as everyone asked. How does O(N^2) solution works. Yes I have noted that sum of N is at max 3 x 10^5 . And N at max is 1000. So let us suppose there are 300 test case each with n 1000. Sum is still 3 x 10^5. So it is valid according to constraint. Now As it is O(T*(N^2)) where T is number of test cases. So in our case it will be O(300 x 10^6) that is O(3 x 10^8). How can we expect this to run in just 2 seconds? The reference for ACMICPC Competitive Programming Book also says in 3 seconds around O(100M) solution works. The above solution works only if CPU is faster. But we can't assume that. Am I wrong somewhere ? answered 19 Jun '16, 03:09

I found an algorithm that's way too simple to implement as well as understand the logic. See my code: https://www.codechef.com/viewsolution/10533045 Its simply scan the loop if student[i] matches with task[i] then first try to find suitable value on the left with which you can swap. Otherwise take the first different value on right side in task array and swap with it. If then also not found then keep it as it is and increment count of matches. All cases will be handled automatically. No edge case remains. Solution Accepted. Complexity O(N^2) answered 19 Jun '16, 04:13

How can O(N^2) get accepted ?? Say we have T = 1, and N = (3(10^5)),no of computations will be roughly (9(10^10)) which clearly can't get AC in 1s time limit...I guess there might be some problem with the test cases :(..Anyways did anyone found anysort of bug in my code ? Link of the code: https://www.codechef.com/viewsolution/10486331 answered 19 Jun '16, 19:26
