WA in "Bank Cooperation" (CDUTSV01)

help
1

This recent problem Bank Cooperation, from Heist is solved using bit manipulation in editorial but i think it is solvable by my approach too.

I thought of all 8 items as nodes in graph, where the paired up elements will form one component, now in components we cannot take neighbouring nodes, as they cant be put together. I found the maximum value that we can take from a component by doing modified dfs, and then added the maximum values of all the components.

I have thought of many cases but cant figure out why its wrong, please help…

link to my code

2

Here’s a random testcase your solution fails on:

29 4 1 12 6 24 21 41
6
3 6
1 3
1 8
2 3
5 7
1 7

The answer should be 102.

Edit:

Best solution: 
Bank # 2 amount: 4
Bank # 4 amount: 12
Bank # 6 amount: 24
Bank # 7 amount: 21
Bank # 8 amount: 41
Total: 102
2 Likes
3

You are complicating things a bit. All you gotta do is generate all subsets of 8 elements and check the subsets which are valid. If a subset is valid, note down its sum , and finally output the max. sum from all the valid-subsets.

To generate all subsets of given 8-elements, you can check Google/Gfg. :slight_smile:

1 Like
4

Thanks, extremely grateful :slightly_smiling_face:

1 Like
5

yes, Thanks

1 Like