How to solve "Four Sum" ZCO17 Problem

help
, , , , ,
1

I am unable to solve

this problem

under given constraints. Can anyone can provide hints/ideas/or solutions on how to solve this?

Problem Statement:

In this problem you are given a sequence of N positive integers S1,S[2], … S[N].
In addition you are given an integer T, and your aim is to find the number of quadruples (i, j, k, l),
such that 1 <= i < j < k < l <= N, and S[i] + S[j] + S[k] + S[l] = T.
That is, the number of ways of picking four numbers from the sequence summing up to T.

Contraints:

1 <= N <= 5000

1 <= T <= 1000000

1 <= S[i] <= 1000000000 , for all i.

2

You can find all combinations(I hope you have knowledge of permutations and combinations) of the array having four elements.

If the sum of the array is T you can increment counter, which will give the answer after you have gone through all possible combinations.

A way to optimize this approach would be to sort the array before finding the combinations, by this we can stop making combinations for a particular case if the sum exceeds T.

Since, the constraints are not to big I think this program won’t give TLE.

3

By the way are you giving ZCO ?

4

I think you can use hashing(map/set/array) + O(n^2) loop to find all the combinations of sum
PS: I used hashing with array ( because it’s fastest)

5

I will let you know after trying this approach…
only have few issues/concerns in my mind about this approach…

6

This should give TLE I think if I understood what you meant

7

6222 submissions on 1st one… 7 submissions in this one… can’t be that simple XD

8

one more counter argument is ans can be 5000C4 at most… if you are doing ans++ for every sum=T then its definitely TLE…

9

See here. Find four elements with a given sum in O(n2log n)

1 Like
10

Has anyone been able to solve this? I wrote a brute force but even the brute force is giving wrong answers.

11

I was able to solve this problem for 60pts using the brute force algorithm that I had told about earlier, solution link: https://www.codechef.com/viewsolution/21727004

12

exactly… this has to give TLE…

13

ans can be 5000C4 at most… if you are doing ans++ for every sum=T then its definitely TLE…

14

#https://www.codechef.com/viewsolution/21727883

HERE is my accepted solution…

#you need hashing+n^2 loop to solve this…

I have commented few things in my solution… you can have a look

15

mine gives AC… have a look…

16

#quick explanation :

1)Select one(ith) element (O(n))

2) find all pairs of sum for index < i (hash it… O(i^2))

3) check every number index>i (O(n-i))

that, if it is possible to get sum=t using all hashed_value+arr[i]+arr[index] (index>i)

if yes then ans+=hash[t-arr[i]-arr[index]] (frequency of hashed value)

All over complexity after optimization O(n^2)