ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 2018. Дебютный альбом

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
Послано chomu1850 13 дек 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
Послано ToadMonster 15 дек 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
Послано nadinne 30 дек 2015 00:55
great idea!