Problem Link:- CodeChef: Practical coding for everyone
I have been trying hard to come up with a solution to this problem but I am unable to formulate the DP equation. Can someone please explain the approach for the problem along with the DP relation (plus a pseudo code is highly appreciated)?
My solution
For this I am using a freq array, it is a count array whos ith element stores the number of pair whos sum is i
What I am doing is first generating sum of all pairs till i and then updating the values in my freq array. Now for every pair, I just subtract its sum from T and find number of occurrences of that in my freq array. Also some slight optimizations for example every element of the array is greater than 1 so I am only storing numbers which are <= T - 3.
Hope this is helpful.
Can you please explain the logic behind your solution?
Ever tried searching on discuss for the editorial?
If not, you can view all zco editorials here
Also, the editorials are represented by their problem code and not by their name. So, you’d be searching for the editorial of ZCO17001 and not FOURSUM.
1 Like