Hi, I’m having trouble understand Ben’s solution here: https://usaco.guide/problems/poi-2004maximal/solution
What I (think I) understand:
CO is a list of primes, with repetition for each power
co is a vector of primes to their powers
ans and tmp are dp arrays, and tmp is the new one
z is used to recover the primes and their multiplicities
There is a separate element for each multiplicity in the primes array, which is what lets Ben use a bitset
The size of z is 1300 becuase sum(floor(log(10**4) / log(p)) for p in primes) is 1280
What I don’t understand:
Why is there no use of logarithms? Do long doubles offer enough precision to where you don’t have to take logs?
Does the bitset speedup outweigh the log factor from storing prime multiplicities? (I guess yes because you only add ~50 primes, so this isn’t really a question).
Writing up this post helped me figure out some of my questions, so I hope if anyone has similar questions they will find this post and it will help them.