ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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)

i will be very thankful to you please help me :D


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[500][300]={0};
    int b[500][300]={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][0];   ///as the places inc with j we will inc in the table of other above
        }

        for(k=1;k<=o;k++)
        a[i][0]+=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][0];   ///as the places inc with j we will inc in the table of other above
        }

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

    }

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


    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!