 # What are the solutions to PSUM and DODGERS?

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.

You can use fft/ntt to reduce that K^2 to KlogK.
Hence O(N.S.K.logK)

1 Like

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

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.

Reality is often disappointing.

2 Likes

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.

2 Likes

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)

1 Like

Thanks! Looks like a concise and comprehensive article! I’ll have a read (probably to forget again )