spoj ⤑ classical ⤑ tug ⤑ Tug of War

I’m so lucky to get a chance to solve this wonderful problem.

The problem demands to check whether there are two disjoint sub sequences whose sums are equal in the given array.

The foremost key observation is the Problem Constraints, which are

1 <= testcases <= 200

1 <= given array length <= 100000

1 <= any element in the array <= 99

as it is given any element in the given array is between 1 and 99, if the size of array is greater than 99 then the answer is YES, now to solve the problem for which array length less than 100, we have to realize that sum of any combination of these numbers can only produce values over a range of 1…sum(array), so by applying a brute-force, that is 2^n algorithm we can report the result with at most sum(array) computations.

https://gist.github.com/32b2c82c500110420dff

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s