ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 2018. The Debut Album

can anyone tell me the solution to this problem i did it in n*a time complexity but for the space n*a it is giving memory exceeded
Posted by chomu1850 13 Dec 2015 01:12
can anyone tell me how to solve this question in short memory usage

which is less than o(n*a) or o(n*b)

here is my code

#include <stdio.h>
#include <stdlib.h>

int main()
{
int n,o,t;scanf("%d %d %d",&n,&o,&t);

int a={0};
int b={0};

int i,j,k;

for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
if(j>o)
break;

if(j==i)
if(j<=o)
a[i][j]=1; ///which shows it is valid

a[i][j]=a[i][j]+b[i-j];   ///as the places inc with j we will inc in the table of other above
}

for(k=1;k<=o;k++)
a[i]+=a[i][k]; ///total sum of all

for(j=1;j<=i;j++)
{
if(j>t)
break;

if(j==i)
if(j<=t)
b[i][j]=1; ///which shows it is valid

b[i][j]=b[i][j]+a[i-j];   ///as the places inc with j we will inc in the table of other above
}

for(k=1;k<=o;k++)
b[i]+=b[i][k]; ///total sum of all

}

printf("%d\n",a[n]+b[n]);

return 0;
}

Edited by author 13.12.2015 01:13
Re: can anyone tell me the solution to this problem i did it in n*a time complexity but for the space n*a it is giving memory exceeded
Posted by ToadMonster 15 Dec 2015 15:49
I used idea:
State is - for L songs album there are Sa1, Sa2, ... Saa - counts of albums ends with 1, 2, ... a "My love" songs; Sb1, Sb2, ... Sbb - counts of albums ends with 1, 2, ... b "I miss you" songs.

Total state size is a+b int counters. There is only L state required to calculate (L+1) state.
Re: can anyone tell me the solution to this problem i did it in n*a time complexity but for the space n*a it is giving memory exceeded
Posted by nadinne 30 Dec 2015 00:55
great idea!