10202 - Pairsumonious Numbers

[newhh2002]

i've checked my program, but wa, why?
would you help me? thanks!
[c]
//pairsumonious numbers
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>

int result[9];
int data[37];
int count;
unsigned char used[37];

int SortFunction(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}

int Check(int first)
{
int i,j,k,cur,t;
result[0]=first;
cur=1;
memset(used+1,0,count);
for (i=1;i<=count;i++)
{
if (!used)
{
result[cur]=data-first;
used=1;
for (j=1;j<cur;j++)
{
t=result[j]+result[cur];
for (k=i+1;(k<=count && data[k]<=t);k++)
{
if (data[k]==t && !used[k])
{
used[k]=1;
break;
}
}
if (k>count || data[k]>t)
return 0;
}
cur++;
}
}
return 1;
}

void main()
{
int i,p;
char line[400];
while (gets(line))
{
i=0;
while (sscanf(line,"%d %[^\0]",&data[i++],line)==2);
if (i<4)
continue;
count=i-1; //equals data[0]*(data[0]-1)/2
qsort((void*)(data+1),count,sizeof(int),SortFunction);
for (i=3;i<=count;i++)
{
p=data[1]+data[2]-data;
if (p&1) //odd number
continue;
if (Check(p/2) && result[1]>=result[0]) //result[1]>=result[0] is needed?
break;
}
if (i>count)
printf("Impossible\n");
else
{
printf("%d",result[0]);
for (i=1;i<data[0];i++)
printf(" %d",result);
printf("\n");
}
}
}
[/c]

[DJWS]

hi all, I have a question.
Could this problem solve with DP?

I have tried to solve this with DFS, finding out all possibility.
but it seems that my method waste a lot of time.
I ponder if a more efficient way exists, just like DP.

Anyone have an idea about solve Q10202 with DP?

----
DJWS, a newbie in programming

[Larry]

http://www.topcoder.com/index?t=statist ... rm182_prob

It's the division 1 Hard..

[DJWS]

Thanks for the info, Larry
I will give a try with this method.

----
DJWS, a newbie in programming

[DP]

can anyone tell me what will be the approach for this problem??
i couldnt model this problem for coding. Is it a backtraking problem or mathematical?
Give some hints.

thnx

[Moha]

I use backtracking approach, but I think there is a good solution for this problem without backtracking. I guess this from the ranklist!

[DP]

hi moha thnx for your reply.
But it could be helpfull if you give some hints.

thnx

[Moha]

A hint in backtracking approach? you can always assume that the first number is 0 and the last one is the largest one.

So we need to find out the others. a simple backtraking method is select the numbers from the given numbers and check all of pairs if they make a solution.

A hint for another solution is: the smallest number is always the second one!

[DP]

thnx Moha.

[stcheung]

Oh my god this problem becomes so easy to implement if you read the solution here:
http://www.topcoder.com/tc?module=Stati ... &d2=srm182

[darkseed]

The TopCoder links are broken. Could someone point or explain a better solution than exhaustive search?

Perhaps solving the implicit linear equations system?

Thanks in advance.