Hello,
I am trying this question, however, I am unable to understand how to construct the solution. My Dp is weak so I thought to practice here, however I am having a tough time.
Can someone please help in describing how to start thinking about such problems?

Hint 1: How many sequences end with '1' or '2'

Hint 2: s_a[0] = 1;         s_b[0] = 1;

Hint 3: s_a[i+j] = (s_a[i+j] + s_b[i])%inf;
Where i+j <=n and i<n and j<= a
 Repeat this with s_b

Good luck! :)

I defined three functions:
C(i) - the number of ways to make the album if it consists of only i songs.
A(i) - the number of ways ending in 1.
B(i) - the number of ways ending in 2.

C(i) = A(i) + B(i)

A(i) = 1 if i <= 1
     = C(i-1) if  1< i <=a
     = C(i-1) - B(i-a-1) i>a

Notice that if i <= a there's no way to have more than a 1's, so we call C(i-1) and 'append' 1 at position i. The number of ways to do this reminds the same as C(i-1).

If i>a you could have an invalid string of 1's. To counter this, we call B(i-a-1) to know exactly how many sequences would be invalid if we 'append' a 1 at position i. When i=a+1, there's only one invalid string resulting of appending 1 at a+1, the sequence consisting of only 1's.

B is analogous to A (calls A instead of B and uses b instead of a).

Edited by author 12.07.2019 04:31

I don't know why my solution is failing on test case 1,
I have tested against all available test cases with correct answer , but cannot pass test case 1, can anybody please tell what is test case 1.

if test 50000 300 300
My solution takes about 1.9 seconds (time library). the test fails.

almost all the time spent on summarizing lists:

"ncalls  tottime  percall  cumtime  percall filename:lineno(function)"
"99402    1.773    0.000    1.773    0.000  {built-in method builtins.sum}"

Maybe there is a way to more quickly summarize than the built-in function "sum"?

Edited by author 12.12.2019 15:42

Edited by author 12.12.2019 15:42

Edited by author 12.12.2019 15:42

#include <iostream>

using namespace std;
long long maxi,sum=1,sum1=1,n,a,b,i,v[100000],v1[100000];
int main()
{
    cin>>n>>a>>b;
    if(a>b)
        maxi=a;
    else
        maxi=b;
    v[maxi]=1;
    v1[maxi]=1;
    for(i=maxi+1;i<n+maxi;i++)
    {
        v[i]=sum1;
        v1[i]=sum;
        sum=sum+v[i]-v[i-a];
        sum1=sum1+v1[i]-v1[i-b];
    }
    cout<<sum+sum1;

    return 0;
}

Edited by author 12.07.2019 04:29

I am not able to understand the problem fully. In the first test  why 221 or 122  are not included. But 212 is included.
If somebody got this problem, please explain

I am trying to solve this problem by using the same approach that I used yesterday to solve this http://acm.timus.ru/problem.aspx?space=1&num=1009 problem.
Is my approach correct? Someone give me a little hint , please..... I am stuck here

Edited by author 22.11.2018 18:12

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> _tree;

const int maxn = (int) 5e4 + 10;
const int mod = (int) 1e9 + 7;
int dp[maxn][2];

inline int sum (int a, int b) {
    re (a + b) % mod;
}

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    dp[0][0] = dp[0][1] = 1;
    fo(i, n) {
        for (int j = 1; j <= a && i + j <= n; ++j) dp[i + j][0] = sum (dp[i + j][0], dp[i][1]);
        for (int j = 1; j <= b && i + j <= n; ++j) dp[i + j][1] = sum (dp[i + j][1], dp[i][0]);
    }
    cout << sum (dp[n][0], dp[n][1]) << endl;
    re 0;
}

i think 212 in the Example test is wrong cause we have 2 remix of "I miss you" when the most remix that we can reach is 1 .

Edited by author 21.01.2018 23:56

http://acm.timus.ru/problem.aspx?space=1&num=1513
It seems that those are the same problem.  In 1513,  just b=INF.
But that problem is of rating of 100, and Lemon Tale is of rating of around 500.

I want to know how to approach this question in what direction to think so that i can solve it on my own.
Thank you.

My code is giving WA on test1.
 But it is giving correct ans for all these:-

50000 300 300
422791438

49999 299 299
505277419

25000 269 222
716603086

Can anyone provide more test cases?

some test please, with % 10^9 + 7

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