JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Algorithm Matches SRM 534 Re: Editorial Revision History (3 edits)
 Re: Editorial (response to post by espr1t) Well, I think division 1 level 2 have another solution, and the complex can reduce to O(S*2^K):In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.my code:```HASH hash; for_each x in special number if n mod x == 0 and gcd(x, n / x) == 1 { for_each element i in hash { if (n mod (i->first * x) == 0) { hash[i->first * x] += i->second; } } hash[x] ++; } return hash[n]; ```It is not difficult to proof that at every moment the size of hash will always not larger than 2^K.for example, let's assume N = 2^1 * 3^3 * 5^2 * 7^4and your bit status may be: 0 1 1 0but I directly use their product: 3^3 * 5^2 as an status in my hashmap.
 Re: Editorial (response to post by espr1t) Well, I think division 1 level 2 have another solution, and the complex can reduce to O(S*2^K):In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.my code:```-------------------------------------------- HASH hash; for_each x in special number if n mod x == 0 and gcd(x, n / x) == 1 { for_each element i in hash { if (n mod (i->first * x) == 0) { hash[i->first * x] += i->second; } } hash[x] ++; } return hash[n]; ```
 Re: Editorial (response to post by espr1t) Well, I think division 1 level 2 have another solution, and the complex can reduce to O(S*2^K):In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.my code:--------------------------------------------HASH hash;for_each x in special number if n mod x == 0 and gcd(x, n / x) == 1 { for_each element i in hash { if (n mod (i->first * x) == 0) { hash[i->first * x] += i->second; } } hash[x] ++; }return hash[n];
 Re: Editorial (response to post by espr1t) Well, I think division 1 level 2 have another solution, and the complex can reduce to O(S*2^K):In your DP solution, you use a bitmask DP to represent the status. But I think maybe it is not necessary.At first, I check every "special number" x, if n mod x != 0 or gcd(x, n/x) != 1 then we erase x from the special number list, because they will never show up in the result. Then I just run brute force algorithm. The complex will be O(S*2^K). And the implement can be as simple as brute force algorithm.