435 - Block Voting

[sidky]

Can any one plz help me with block voting. I couldn't figure out, how in input1, party 1 had power index1, and in input 2, party 1 with power index 18, party 4,5,6 with power index 2?

[UFP2161]

For the first sample input, here are all the possible party combinations that would make a majority:

1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 5
1 2 4
1 2 4 5
1 2 5
1 3 4
1 3 4 5
1 3 5
1 4
1 4 5
1 5
2 3 4 5
2 4 5
3 4 5

Now, for each line, consider each party. If the other parties don't make a majority vote, then you can increment the power index of the party by one.

[stcheung]

I thought hard on this problem and couldn't come up with an intuitive way to solve it efficiently. I seriously doubt you should solve this problem by generating all possible combinations and going through them one by one, because there may be up to 20 parties which means 2^20 different combinations.

So any hint on this? Like can it be solved by dynamic programming? Or should I still generate all combinations but try to prune some of them? Thanks.

[little joey]

You can use both approaches. My first solution, dating almost 3 years back, used exhaustive search with pruning and needed more than one second to solve the problem. I just made a DP solution and it solves the problem in one hundredth of that time.

[theemathas]

I got a strange WA (expected only TLE or AC)
please give me a testcase to debug

Code: Select all

deleted after AC

this passes all example cases
P.S. memset is a trick to reset an array with a 1-line code (I don't understand why it is in cstring)

[brianfry713]

the third argument to memset is the number of bytes. An int is 4 bytes. Instead write something like:
memset(mem,-1,sizeof(mem));
memset(counter,0,sizeof(counter));

[theemathas]

seems like the bug is actually at the memset. I rewrote it without using memset and got TLE instead!

Code: Select all

deleted after AC

did it go into an infinite loop?

[theemathas]

yet another WA after reverting to memset

Code: Select all

deleted after AC

[brianfry713]

print a blank line after the last testcase.

[gautamsingh]

Code: Select all

code removed

I am getting WA. I have tried a lot of random test cases on udebug.com

[brianfry713]

Change line 41 to:
for (int p = 0; p < n; ++p) {

[gautamsingh]

Thanks a lot brainfry713.