These are the two I could not solve and am very curious.

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.

You can use fft/ntt to reduce that K^2 to KlogK.

Hence O(N.S.K.logK)

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-

https://www.codechef.com/SEPT19A/status/PSUM,vatsal1998

The editorial for PSUM is out, and it should be easy to understand

Reason @taran_1407 to c++. He knew in past uwi(?) failed to get ntt/fft AC. Java doesnâ€™t support pointers. Hence constant is large.

Why didnâ€™t you switched to C++ after seeing @taran_1407 instead of complaining about Java?

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â€¦

Oh wait I didnt read properly.

My DP[i][j][l] is summation of v^l in range a[1â€¦i] such that their total cost is j.

Then transition from dp[i][j] to dp[i+1][ai] is just using ntt.

Editorial is out.

This is more complex approach https://codeforces.com/blog/entry/69561?#comment-543173

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

Yes yes. DP[n][s] in my post is just for explanation purposes. As for FFT, I hope the official editorial explains it well.

Reality is often disappointing.

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.

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.

Expected soln is O(N.S.K) they even wanted O(N.S.K.logK) to get tle. And believe me getting AC on O(N.S.K.logK) is a tough job.

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 )