ALCATRAZ2 - GO GOA GONE
So , it was winter and Me and 8 of my friends decided to plan a trip to GOA . Since the Bars ans Clubs are too Expensive out there , we decided to pool money together for our whole trip expenses . Now since every group has some internal politics going on , same aplies to our group also :P . 2 Members that are having a cold war between them won't go to the trip if the other one is going . But Since we want to enjoy a lavish party , we want to maximize the pooled money . So , for this task I've chosen my marwari friend Mohit to solve this problem ( He's good at money matters ) . Your task is to help Mohit achieve the maximum pooled money .
First Line will contain 8 space seperated integers denoting the money contributed by each member in order .
The next line will contain the total number of pairs having a cold war in between them . Let us denote this by P .
The next P lines will contain 2 numbers seperated by a space showing the members having a cold war . Numbers used to denote members will be ( 1-8 ) for each 8 members .
Everything is guarenteed to easily fit in 32 bit integer type .
Output will give the maximum amt of money that can be pooled .
Input: 3 14 5 2 3 4 1 9
Can this be solved using graph coloring?
suppose money contributed by 1 and 3 respectively are 8 and 9.
Something might be wrong with the input, with Kotlin i got NZEC, though with C the same solution got accepted..
Nice problemLast edit: 2020-05-15 08:55:30
Easy solution as the given constraints are very less. Just generated all the possibilities using recursion. We can do the same thing using Bitmask.
Using bitmasking.Last edit: 2020-05-01 19:53:22
mostafiz_53: Optimal selection is 2 (even though that means neither 1 nor 3 can go), 5 (this eliminates 4), 6 (no conflicts with anyone) and 9. 14+3+4+9 = 30.
Can someone explain this output?
All I can say is - thanks for this problem. Thanks a lot.
AC in one go! Bitmasking :)