Editorial for Bubble Cup V8 C Party

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

To explain solution of this problem let's describe the scheme of Hungarian algorithm:

Hungarian()
{
    for (int i = 0; i < n; i++)
    {
        hungarian_iteration();
    }
}

So in this problem the only thing you had to do is to recursively go through all sets of binary masks with equal number of $0$ ~0~s and $1$ ~1~s (where $0$ ~0~ in $i^\text{th}$ ~i^\text{th}~ position means that $i^\text{th}$ ~i^\text{th}~ person would go partying on Friday, $1$ ~1~ – Saturday) and run Hungarian algo for this matrix. If done recursively complexity would be $\mathcal O(C(N+2,\frac N2+1) \times N^2) = \mathcal O(2^N \times N^{1.5})$ . DP cannot be used here because of low ML.

Comments

There are no comments at the moment.