Posted:

**Tue Nov 02, 2004 12:30 am**I use a recursive formula:

f(n, k, m) = sum (1 .. m) f(n - i, k - 1, m)

f(n, k, m) = sum (1 .. m) f(n - i, k - 1, m)

Page **2** of **2**

Posted: **Tue Nov 02, 2004 12:30 am**

I use a recursive formula:

f(n, k, m) = sum (1 .. m) f(n - i, k - 1, m)

f(n, k, m) = sum (1 .. m) f(n - i, k - 1, m)

Posted: **Tue Nov 02, 2004 1:25 am**

That's it??!?!?!

And here I am doing it in such a complex way. I got every single valid sequence and then found all the combinations/permutations (never knew the difference ) of them...

And here I am doing it in such a complex way. I got every single valid sequence and then found all the combinations/permutations (never knew the difference ) of them...

Posted: **Mon May 23, 2005 2:46 pm**

I have TLE for this problem, because I use a Formula to calculate recursively the final number for this problem. How can I quit TLE?

Posted: **Mon May 23, 2005 3:49 pm**

If you solve it by a recursive formula, instead of coding a simple recursive function, you should store the value you get into a table so that you don't need to compute everything again and again each time.

Posted: **Mon May 23, 2005 4:34 pm**

My problem persist. I don't know how to reduce time.

This is my code for this problem

This is my code for this problem

Code: Select all

```
#include <stdio.h>
#include <stdlib.h>
long contador;
void Formula(int tot,int sep,int max){
int i;
if (tot<sep) return;
else if ((tot<=max)&&(sep==1)) { contador++; return;}
else if (sep==1) return;
for(i=1;i<=max;i++) Formula(tot-i,sep-1,max);
}
int main (int car, char** v) {
char linea[100];
int total,separaciones,maximo;
while(fgets(linea,100,stdin)!=NULL){
sscanf(linea,"%d %d %d",&total,&separaciones,&maximo);
contador=0;
Formula(total,separaciones,maximo);
printf("%ld\n",contador);
}
return 1;
}
```

Posted: **Mon May 23, 2005 5:09 pm**

You misunderstand what I mean. You should store the value in a 3D-table like:
This is a standard technique called dynamic programming. If you are computer science major, you will learn it in some intermediate/advanced algorithm course.

Code: Select all

```
int table[50][50][50];
int Formula(int tot,int sep,int max){
if(table[tot][sep][max]==-1)
{
// compute the value of Formula(int tot,int sep,int max)
// recursively here and assign it to table[tot][sep][max]
}
return table[tot][sep][max];
}
int main (int car, char** v) {
char linea[100];
int total,separaciones,maximo;
initialize all entries of the table to be -1;
while(fgets(linea,100,stdin)!=NULL) {
sscanf(linea,"%d %d %d",&total,&separaciones,&maximo);
printf("%ld\n", Formula(total,separaciones,maximo));
}
return 1;
}
```

Posted: **Mon May 23, 2005 8:15 pm**

Hello.

This problem also can be solved using 2D matrix or just can be found a formula using PIE.

Eduard.

This problem also can be solved using 2D matrix or just can be found a formula using PIE.

Eduard.

Posted: **Sun Jun 19, 2005 11:40 am**

Can you explain a bit what's the 2D approach. I've done it using a 4D array with dimensions [50][2][50][50].

Regards

Sanny

Regards

Sanny

Posted: **Sat Dec 15, 2007 5:48 pm**

I have used 3D memo .. I am getting WA ..

can u give me some I/O where my code fails ..?? Thanks in advance ...

can u give me some I/O where my code fails ..?? Thanks in advance ...

Code: Select all

`removed after AC..`

Posted: **Mon Oct 19, 2009 10:36 am**

I matched the very all outputs from Krzysztof Duleba and I get WA...

Why would that be?

Why would that be?

Posted: **Sat Aug 02, 2014 5:42 pm**

Hints:

-------

Complete search over all bar widths, in each recursive call you should try to add a bar with all allowed width.

Recursively do that until all your bars width = n and number of bars = k Here you found a solution.

You can use a 2D array to store answers. in order not to re-calculate any of them (DP).

-------

Complete search over all bar widths, in each recursive call you should try to add a bar with all allowed width.

Recursively do that until all your bars width = n and number of bars = k Here you found a solution.

You can use a 2D array to store answers. in order not to re-calculate any of them (DP).

Posted: **Tue Mar 17, 2015 7:01 am**

got ac on 1st submission actually 2D array is enough . as 'm' is not changing so we don't need 'm' as dp state