These are the two I could not solve and am very curious.
7 Likes
I couldn’t solve those two as well. But here are my 2 cents for solving subtask 2 for PSUM.
The idea is to use a DP[n][s], where DP[i][j] stores the ans (summation of all possible v^k) for A1 to Ai with a cost exactly j.
Now I guess the DP part is obvious. For finding DP[i][j], you either take ignore the ith element, in which case it is same as DP[i-1][j] or you take the ith element, in which case you use DP[i-1][j - C[i]] to create the solution for DP[i][j].
Now the problem is how to get (a1+b)^k + (a2+b)^k + (a3+b)^k + … from a1^k + a2^k + a3^k + …
You can see that the former sum is equal to a1^k + a2^k + a3^k + … + C(k, 1) * (a1^{k-1} + a2^{k-1} + …) b + … + C(k, k) * (a1^0 + a2^0 + …) b^k
So if you have all powers (0 to k) of the previous ans, you can create all powers of the current ans (ie. adding V[i] to all the previous v-s) in O(K^2) time
Hence, this is a O(N . S . K^2) solution.
P.S. I don’t know how to use markdown in comments. Someone please let me know if it’s possible.
Oh man. If only I remembered what FFT is and where it’s used, even after having read it a couple times in the past!
I used fft/ntt. I was coding it in java. It was giving tle. I don’t anyone who got AC in java. I even saw @taran_1407 's soln. He was doing in java . Got TLE. Switched to cpp and got accepted. I think the problems should be rejudged with more time limit.
I tried many optimizations like to reduce modular operations and and doing some precomputation where possible. But all failed .Here is one of my soln
https://www.codechef.com/viewsolution/26596991
My other solutions-
The editorial for PSUM is out, and it should be easy to understand
But actually we need to store dp[i][j][l], where l runs from 1 through k, right? I got this far too, but did not think to use FFT/NTT. How exactly do we use it? I still do not see…
Language shouldn’t be a factor for getting AC’s I think. The problem setter should have tested for all languages (at least the common ones java,c++, python). It feels very bad when you give in a lot of effort, get the correct soln and don’t get an AC. Also to your question about switching to C++. I don’t know cpp much. Otherwise I would happily switched to cpp. I just want to say that the time limit should have been set appropriately. If possible rejudge the solutions
3 Likes
Yes yes. DP[n][s] in my post is just for explanation purposes. As for FFT, I hope the official editorial explains it well.
As far as I know, there is no way to individually set time limits for individual languages, it’s just a constant multiplicative factor of some base time. Therefore, it is not possible for setters to set a time limit which works best in all languages (eg. if you increase it slightly, O(NlogN) might pass in some language where O(N) was expected).
Even it you could set time limits individually, I don’t think it is very feasible for problem setters/testers.
And finally, in my opinion, the ability to choose the language for the job is also tested in competitive coding. Plus, it let’s us think about actual runtime as opposed to asymptotic time complexity.
1 Like
But here the difference is not O(N) and O(NlogN). Its about O(K^2) and O(KlogK). If you calculate KlogK is approx 2x10^4 and K^2 is 4x10^6. That is a factor of 200. So increase in time limit shouldn’t have been a problem.
Oh!! If the expected complexity was O(N.K.S) then really good job to the author. Surely will look into the approach.
I’m sorry, the inteded complexity is O(NSK \log K ) not O(NSK)
Thanks! Looks like a concise and comprehensive article! I’ll have a read (probably to forget again 
)