Lesson: 14
Problem: 10168
Title: Summation of Four Primes
Difficulty Level: 2.5
Date: Jan 9, 2009
Site: UVA
Solution:
You are given an integer, say n, you have to print p1 p2 p3 p4, where p1+p2+p3+p4 = n.
How can we solve this problem ? Should we try back tracking ? or dynamic ? When i tried this problem first time, i used back tracking, and got TLE. But after thinking a while, i noted few points:
1. p1 p2 p3 p4 can be any order
2. any correct solution will be accepted.
That's enough to reduce the complexity of this problem.
Do you get it ?
Ok, think about problem 543( Lesson 9 ), where we have learned to find p1 and p2 for any even n, where n > 3.
For any even number, lets 12, we can write, 2 + 2 + p1 + p2 = 4 + (p1+p2). and p1+p2 = 8. So we have to find only p1 and p2 for 8 ( exactly same problem as 543).
For input 16, our answer will be 2 + 2 + (12). We have to find p1 and p2 for 12 and it may be 5 and 7. So our answer is: 2 + 2 + 5 + 7. Very easy, right ?
If input is Odd, answer will be 2 + 3 + p1 + p2. For example
9 = 2 + 3 + ( p1+ p2) = 2 + 3 + 2 + 2.
That is for odd number( lets n) , we have to find p1 and p2 for n - 5 and answer will be 2 + 3 + p1 + p2
and for even number, we have to find p1 and p2 for n - 4 and answer will be 2 + 2 + p1 + p2.
Another point to note: if the input < 8, print "Impossible." Why ? try to find answr yourself.
and don't forget to print period(.) after 'Impossible'.