go goa gone

general
1

http://www.spoj.com/problems/ALCATRAZ2/

Can Any One Suggest some approach for the go goa gone problem spoj?

1 Like
2

Since there are only 8, you can use simple recursion to choose best. Start with the first pair, try removing both of them one by one recursively for further pairs and choose best outcome. Feel free to ask if any doubt!!

3

Yes, simple recursion got ac.
Thanks for your opinion.

1 Like
4

At least, you should upvote/accept if you find helpful

5

i tried but it says “i don’t have enough reputation.”

1 Like
6

Suppose I give you some data about 8 persons going to goa.
let amount be contributed by 8 of them be:(respectively)
8 14 9 2 3 4 1 9

No. pairs having problem with each other: 3

The pairs are:
1 2
2 3
7 8

Now,according to ur logic first pair is 1 2 so i remove 1 . So 2 is going.
Further, I compare 2 3 now i remove 3 . So 2 is going.
And out of 7 8 , I remove 7. So 8 is going.
So, the people going are: 2 4 5 6 8
so total amount collected: 14+2+3+4+9=32

But if we keep 2 out of the trip then both 1 and 3 can go.(1 3 4 5 6 8 )
Therefore, total amount collected in that case: 8+9+2+3+4+9=35

so by which algo we ignore 2 to maximise our profit,please reply.Also case becomes more complex when one individual has problem with many others .

7

Just bitmask over all possible combos. Same as recursion