One of the easy problems, problem C, was a good example of the argument that leads to square roots in asymptotic complexity of various algorithms. The problem statement was very simple: you are given two types of candy, one costs X per item and each item brings P units of joy, and the other costs Y per item and each item brings Q units of joy. What's the maximum amount of joy you can get after spending at most Z? Of course, you can't buy partial items, as otherwise we can simply buy the candy with the best joy/cost ratio. Can you solve this problem in O(sqrt(Z))? How about O(poly(log(Z)))?
One of the problems I've described last week was about counting strings of given length with the given value of a polynomial hash. The way to solve it was to notice that after we know the hash of the first n/2 characters, let's say it's equal to X, and the hash of the last n/2 characters, let's say it's equal to Y, then the hash of the entire string is simply X*pn/2+Y. In other words, in order to find the number of ways to reach the given hash value, we need to sum the products of numbers of ways to reach two hash values for the halves that sum to the given value - now we can notice that this is equivalent to multiplying polynomials. Polynomials can be multiplied in O(NlogN) using Fast Fourier Transform. Moreover, very conveniently (but not suprisingly), one needed to output the answer modulo a prime 998244353=223*119+1, which means that there exists a 223-th root of unity modulo that prime, and thus the FFT algorithm can work just fine.
Here's an interesting addition: this comment (in Russian) describes a way to multiply two polynomials modulo some number that does not have a nice root of unity, so this problem would actually be solvable just fine modulo 109+7 or any other modulo of that order of magnitude.
Thanks for reading, and check back next week!
No comments:
Post a Comment