Hi codeforces,
I'm struggling with a problem from a Greek contest which has no solution. The problem is as follows (it has only Greek problem statement):
There are N people (N <= 30). Peraon number i has A[i] oranges. You know for every person who are hus friends — you have a NxN table were if Table[i][j] is 1 then i is a friend of j. You want to make a group of people such that every person is a friend of every other in the group and the sum of the oranges they have is maximum. You must output this maximum number of oranges.
The problem has no solution and I'll be really thankful if you can help me.
"find a clique with maximal sum" Well. You can find it easily for N<=20 with bitmask DP.
For N<=30, use meet-in-the-middle approach to connect two smaller subproblems.
how to connect two problems? Am I right that I have to solve this with two halves — first N / 2 vertices and second N / 2 vertices and do 2^(N/2) bitmask dp for each of them?
That's right, look at the third task from the first day of JBOI 2015, it uses the same idea for 60 points but due to the lack of feedback nobody got it right (it's funny how I had 74 on it ten seconds before the end but then I decided to resubmit and lost my points :D)
Please explain in a little more detail how meet in the middle would work here?
How do we ensure that the people of group A have all the people from group B as friends?
For every subset of the left side you compute a mask of all people from the right side that are friends of everyone in this subset (basically bitwise AND of masks of neighbours). Now if you fix the left subset, you are given a subset S of the right side, and need to know — what is the most valuable clique that is a subset of S? You can compute such answers for every possible S by a DP.
Almost the same question is currently on HackerRank (Code Week 21 — fourth problem). Please don't discuss it now.
PS: link