|
|
back to boardI got AC, but my algorythm is standart( O(m*2^n) ). How solve faster? (i need in idea) Re: I got AC, but my algorythm is standart( O(m*2^n) ). How solve faster? (i need in idea) Posted by Sirko 3 Feb 2017 21:05 Hi. I've also got AC with O(m*2^n), but it seems that it's a bit more fast. Here's an idea.
Each set of taps or a combination of sets has corresponding bit mask. We have an array int minPrice[2^N]. Obviously, index is a mask, element — min price for buying such combination of taps. Initially the only !=0 elements are those each corresponding to one of predefined M sets.
Then the DP comes. We go from 0-th element to the last (11...1 target). If i-th element !=0, we process it: a) if i corresponds to one of M predefined sets, we try to OR "i" with all younger mask with !=0 price. b) if i doesn't correspond to any predefined set, thus, it's a combination of some predefined sets, then we OR this "i" with younger predefined masks ONLY (not all younger "j" !=0). Re: I got AC, but my algorythm is standart( O(m*2^n) ). How solve faster? (i need in idea) Posted by Sirko 3 Feb 2017 21:08 However, there's still a question to those guys who got AC in less than 0.1 second. Especially to those who did it in ~200 KB. |
|
|
