backtracking
As the problem says, you should print all possible partitions of S into t co-prime numbers.
The order doesn't matter, so If you have to choose 1 & 2 & 5, you just need to print 1 2 5 not 5 2 1 or 2 5 1. This fact prunes backtracking and helped me pass time limit.
I implemented a function called solve( start, m, d ). In this function I start checking from start, and each time I find a number that is coprime to the selected items, I put it in the list and keep on backtracking with ( number, m-number, d+1 ), when the function reaches at ( d == numberOfPartitions ) and m is equal to zero( that means there are no values to choose and the partitioning is complete ), I completely print the selected list.
Subscribe to:
Post Comments (Atom)
-
Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se... -
Link to the problem on Timus Online Judge The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know...
-
Link to the problem on Timus Online Judge This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...
No comments:
Post a Comment