AHi, can anyone give me a hint on how to speed up my DP for this task ?
My submission : http://z-trening.com/submit.php?subm_stat=1&submit=7100189207
Complexity O ( M * 2 ^ ( 2 * M ) ) .
this can be done much simpler ... O( M*2^M ) ...
but let's try to improve you algorithm ( not sure will it work )
when you are doing calculations with some mask, you don't have to go 2^M each time ...
for example, when you have mask = 10010001 ...
you are doing 2^8, and you have to do just 2^3 operations ...
when idx = M, you don't have to go through all elements, you can calculate newMask on the way ...
not sure will it solve a task, but it will improve algorithm ...
well how do u actually get O(m*2^m)?
for each bitmask that has k passangers u need to check all bitmasks with k/2 or less.i dont think thats O(m*2^m):D
my mistake, complexity is O( M*3^M ) ...
is my idea good?if thats the case how come its O(m*3^m)??
I am not sure your idea is good ...
If you have some bitmask where 1 means that person is in group you are watching, and for that bitmask you have to take 1 group out, calculate for them time and weight and to sum it with rest of bitmask ...
so for taking 1 bitmask, there is 2^n combinations, and that is equal to \sum_{k=1}^N \binom{n}{k}.
Now for every bitmask you have to go 2^k where k is number of 1 in binary representation of that bitmask.
so now you have sum.
\sum_{k=1}^N \binom{n}{k}*2^k and that is equal to (1 + 2)^n and that is 3^n
yes that was my idea too.just dint know thats 3^m.but u dont need to take 2^k...u can take less cause some combinations will repeat
yes, every combination will repeat, but in every that state there is going to be different bitmask, so
I think you have to take 2^k ....
