10694 - Combinatorial Summation

[alex[LSD]]

Larry, you really dang smart. I d never see fibonacci here, but I see em now!

[anupam]

The difference increases at a fibonacci number rate (I may forget). But, Definitely a very good problem from sajjad bhai.
Anupam

[Yarin]

I'm curious, how does one evaluate everything as fast as most people seem to have done? I don't believe almost everyone has precalced the results.

[Adrian Kuegel]

My solution calculates all answers with dp at the beginning of my program.
Here a pattern can be observed in the differences of adjacent entries in the table (like mentioned before by Larry, similar to fibonacci numbers). So to fill up the table, only a constant number of bigint operations for each entry is necessary.
But I would be interested in how to solve this problem in another way. I do this pattern guessing far too often without knowing for sure why it works.

[abishek]

there is a simple recurrence relation relating a[n] to a[n-1], a[n-2] and some simple function f(n).
so a[n]=g(a[n-1], a[n-2], f(n))
the functions f, g are very simple, so i don't want to give them away.
bye
abi

[Adrian Kuegel]

That sounds exactly what I did; but I just guessed this formula.
It seems Yarin has found a different approach.

[Yarin]

Okay, I have O(N^2) bigint add operations in the beginning. Explains my slow solution then if you can do it on O(N) operations. Ah well, it worked within the time limits...

[Cho]

Sorry...
Can anyone show me why the answer for input 4 is 14?

[shamim]

If you write all terms for n = 4, you will get some like this:

C(4,1) +
C(3,1) + C(3,2)+
C(2,1) + C(2,2) +
C(1,1)

I hope you get the pattern.

[emotional blind]

where is the problem
i got wa

Code: Select all

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

#define max 220
#define l 1000

char *add(char *nm1,char *nm2)
{

    char res[max];
	int i,j,k,op=0,len1,len2;
    len1=strlen(nm1);
    len2=strlen(nm2);
    if(len2>len1)
         return add(nm2,nm1);
	k=len1+1;
	res[k--]='\0';

    for(i=len2-1,j=len1-1;i>=0;i--,j--){
		op = nm2[i]-'0'+nm1[j]-'0'+op;
		res[k--]= (op%10)+'0';
		op=op/10;
	}
    for(;j>=0;j--){
		op=nm1[j]-'0'+op;
		res[k--]=(op%10)+'0';
		op=op/10;
	}

    if(op){
		res[k]=op+'0';
		return res;
	}

    return &res[1];

}

int main (void)
{
	char seq[l][max], *p;
	int i,n, num;
	char one[]={"1"};
	//strcpy(seq[0],"0");
	strcpy(seq[1],"1");
	strcpy(seq[2],"2");
	
	for(i=3;i<l;i++){
		p=add(seq[i-1],seq[i-2]);
		p=add(p,"1");
		strcpy(seq[i],p);
	}
	cin>>num;
	
	while(num--){
		cin>>n;
		if(n<1)cout<<"0"<<endl;
		else
		cout<<seq[n]<<endl;
	}
	return 0;
}

problem description says input will less than 999
why you try with input 1000

help me