Statement↵
------------------↵
The following problem was given at a Romanian national contest in 2016, I've solved it quite a long time ago but only now have i got around to showing it to you. You are given a positive natural number S <= 10^5 and you are required to print the number of non-decreasing sequences with sum S or less modulo 666013. For example if S = 4 the answer is 11 (the sequences are {1}, {1, 1} ,{1, 1, 1}, {1, 1, 1, 1}, {1, 1, 2}, {1, 2}, {1, 3}, {2}, {2, 2}, {3}, {4}). You've also got 1 second and only 8MB of memory. The solution has 3 parts so if you want to try it yourself you may read one paragraph at a time for hints.↵
[cut]↵
↵
↵
### The first DP to discover↵
Your first idea to attack this problem might be a DP[x][s] counting the number of sequences starting with x or more and total sum s or less. The reccurence relation is DP[x][s] = DP[x+1][s] + DP[x][s-x]. DP[x+1][s] counts the number of sequences starting with strictly more than x and DP[x][s-x] counts how many start with exactly x, thus substracting x from the total sum. Your answer will be at DP[1][S] and you will be delighted to have found a quadratic solution so quickly but soon will start to worry that there is no optimization for this reccurence. You may notice however that when x is large, say larger than sqrt(S) there will be very few numbers possible in the sequences, at most sqrt(S), so you may start looking for a solution that uses how many numbers you put in a sequence rather than how large is the first number in it.↵
↵
### A different approach to explore↵
After you decided to look for DPs with a set number of numbers in the sequence you quickly found DP2[n][s] counting the number of sequences with exactly n numbers and sum s or less. The reccurence for this one is DP2[n][s] = DP2[n][s-n] + DP2[n-1][s-1]. DP2[n][s-n] covers the case where you start the sequence with a 2 or more, thus you simply add 1 to every number in the sequences with sum s-n and are guaranteed to start with more than 1, the remaining DP2[n-1][s-1] covers the case where you start with exactly 1. You used a number and took 1 from the total sum, hence n-1 and s-1. The answer will be at DP2[1][S]+DP2[2][S]+..DP[S][S], but we're not actually interested in that. Our goal is to use this new dp to somehow fill an early row in our first dp and then to continue with that one towards the solution.↵
↵
### Combining the solutions and finishingour journeythe problem↵
We noticed long ago that DP[x][s] has very few numbers in its sequences for x larger than sqrt(S), so we want to calculate the entire row of DP[sqrt(S)+1] using DP2. Say we have calculated DP2 for a certain row r. They count the number of sequences starting with 1 or more, but if we add sqrt(S) to every number in it values count the number of sequences with r numbers starting with 1 or more, but if we add sqrt(S) to every number in it we ensure that the first number is at least sqrt(S)+1. Suddenly we realise that with each possible row we can construct DP[sqrt(S)+1][s] by adding DP2[r][s-r*sqrt(S)] to it for every s > r*sqrt(S). So after you've finished DP2[r] for some r you can do the following:↵
↵
for (int i = r*sqrt(S)+1; i <= S; ++i)↵
DP[sqrt(S)+1][i] += DP2[r][i-r*sqrt(S)];↵
Because DP[sqrt(S)+1] can only consist of sequences with at most sqrt(S) numbers, you need to run DP2 for only sqrt(S) values on the first dimension, after which you can run the first DP to find the answer at DP[1][S]. Finally, the time complexity for DP is O(nsqrtn) and for DP2 is the same O(nsqrtn), resulting in an overall O(nsqrtn). You may also keep only the last 2 lines in both DPs and use O(n) memory overall. Hopefully you have understood everything, but if not feel free to ask anything in the comments!. Thank you very much for reading and if you wish to practice the implementation here is a Romanian judge with this problem https://infoarena.ro/problema/crescator2.
------------------↵
The following problem was given at a Romanian national contest in 2016, I've solved it quite a long time ago but only now have i got around to showing it to you. You are given a positive natural number S <= 10^5 and you are required to print the number of non-decreasing sequences with sum S or less modulo 666013. For example if S = 4 the answer is 11 (the sequences are {1}, {1, 1} ,{1, 1, 1}, {1, 1, 1, 1}, {1, 1, 2}, {1, 2}, {1, 3}, {2}, {2, 2}, {3}, {4}). You've also got 1 second and only 8MB of memory. The solution has 3 parts so if you want to try it yourself you may read one paragraph at a time for hints.↵
[cut]↵
↵
↵
### The first DP to discover↵
Your first idea to attack this problem might be a DP[x][s] counting the number of sequences starting with x or more and total sum s or less. The reccurence relation is DP[x][s] = DP[x+1][s] + DP[x][s-x]. DP[x+1][s] counts the number of sequences starting with strictly more than x and DP[x][s-x] counts how many start with exactly x, thus substracting x from the total sum. Your answer will be at DP[1][S] and you will be delighted to have found a quadratic solution so quickly but soon will start to worry that there is no optimization for this reccurence. You may notice however that when x is large, say larger than sqrt(S) there will be very few numbers possible in the sequences, at most sqrt(S), so you may start looking for a solution that uses how many numbers you put in a sequence rather than how large is the first number in it.↵
↵
### A different approach to explore↵
After you decided to look for DPs with a set number of numbers in the sequence you quickly found DP2[n][s] counting the number of sequences with exactly n numbers and sum s or less. The reccurence for this one is DP2[n][s] = DP2[n][s-n] + DP2[n-1][s-1]. DP2[n][s-n] covers the case where you start the sequence with a 2 or more, thus you simply add 1 to every number in the sequences with sum s-n and are guaranteed to start with more than 1, the remaining DP2[n-1][s-1] covers the case where you start with exactly 1. You used a number and took 1 from the total sum, hence n-1 and s-1. The answer will be at DP2[1][S]+DP2[2][S]+..DP[S][S], but we're not actually interested in that. Our goal is to use this new dp to somehow fill an early row in our first dp and then to continue with that one towards the solution.↵
↵
### Combining the solutions and finishing
We noticed long ago that DP[x][s] has very few numbers in its sequences for x larger than sqrt(S), so we want to calculate the entire row of DP[sqrt(S)+1] using DP2. Say we have calculated DP2 for a certain row r. The
↵
for (int i = r*sqrt(S)+1; i <= S; ++i)↵
DP[sqrt(S)+1][i] += DP2[r][i-r*sqrt(S)];↵
Because DP[sqrt(S)+1] can only consist of sequences with at most sqrt(S) numbers, you need to run DP2 for only sqrt(S) values on the first dimension, after which you can run the first DP to find the answer at DP[1][S]. Finally, the time complexity for DP is O(nsqrtn) and for DP2 is the same O(nsqrtn), resulting in an overall O(nsqrtn). You may also keep only the last 2 lines in both DPs and use O(n) memory overall. Hopefully you have understood everything, but if not feel free to ask anything in the comments!. Thank you very much for reading and if you wish to practice the implementation here is a Romanian judge with this problem https://infoarena.ro/problema/crescator2.
