Show all threads Hide all threads Show all messages Hide all messages  My explanation  Vladimir Putin  2018. The Debut Album  12 Jul 2019 04:29  1  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(i1) if 1< i <=a = C(i1)  B(ia1) i>a Notice that if i <= a there's no way to have more than a 1's, so we call C(i1) and 'append' 1 at position i. The number of ways to do this reminds the same as C(i1). If i>a you could have an invalid string of 1's. To counter this, we call B(ia1) 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  No subject  Vladimir Putin  2018. The Debut Album  12 Jul 2019 04:18  1  Edited by author 12.07.2019 04:29  what is the meaning of this problem?  Abbos Bo'kaboyev  2018. The Debut Album  24 Nov 2018 19:14  2  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 In the example, good albom can't contain two 2 together, because 2 > b = 1.  Is my approach correct?  Scaletta_Z  2018. The Debut Album  22 Nov 2018 18:10  1  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  accepted  Mikhail  2018. The Debut Album  8 May 2018 00:49  2  //#pragma GCC optimize("Ofast,nostackprotector") //#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; } Have you read the rules? Your deed has no honor.  Example Testcase  Khanhhuy_19  2018. The Debut Album  6 Feb 2018 18:47  2  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 It says: "in a row". It means that there can be any number of remixes of each song, the most important part it that the number in each row doesn't;t have to exceed a for 1st and b for 2nd  Is "1513.Lemon Tale" the same problem?  Mahilewets  2018. The Debut Album  18 Jan 2018 11:26  7  Yes, Lemon Tale is just the same problem. Even easier problem. Problem rating lies heavily : 106 vs 400. well it is true that this problem is harder in concept but that problem i think is just harder to implement in competition unless you use javabiginteger, but in c++ u must implement addition and diference with biginteger, and this problem is just done in about 10 lines of straight code There exists four or five lines python solution using only python lists 1513 has tighter limits though For this problem, you can implement a dp in O(n * (a + b)) but in Lemon Tale you can't There are another similar problems, where rank lies. Say, 1285 is formally harder, then 1075. But if one have already solved 1075, then, probably, one may need to change just single dimensionality constant from 3 to 8 to get solution of 1285. Rate of ACs should be slightly less for harder, but latter problem, for sure. Another factor is the optimistic one: people are getting smarter and smarter on an average. New problems are solved by less efforts. The technological singularity is coming! Edited by author 18.01.2018 11:30  Approach?  Saurav Kumar  2018. The Debut Album  30 Sep 2017 02:31  5  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. Problem is tagged with dynamic programming First, think about each possible configuration of the current state when you add next song Second, think about techniques of DP  compression well let x[n] be the number of sequences that finish with 1 and y[n] be the number of sequences that finish with 2 of the length n, x[0] = y[0] = 1, x[1] = y[1] = 1, the recurent formula for this is x[n] = y[n  1] + y[n  2] + y[n  3] + .. + y[n  b] and y[n] = x[n  1] + x[n  2] + x[n  3] + .. + x[n  a], basicly for a sequance of n + 1 you must think of the number of ways that the sequance will finish with 1 or with 2 Edited by author 11.08.2017 04:09 I am sorry but I still didn't understand, why x is dependent on y. Won't Y[] include cases having consecutive A times 1 and moreover won't Y[] Include duplicate cases ? I am sorry but I am new to this so that's why I am asking. well let's approuch one case where your array is finishing with 1 but no more than "a" times in a row, because the 1 array is dependent from array of 2 and array 2 is alwais finishing with 2 it will look like this 12.... that is y[n] = x[n  1], than 112... that is y[n] = x[n  1] + x[n  2], than 111...112.... which is y[n] = x[n] + x[n  1] + x[n  2] + ... + x[n  a] and is the same in the second case  Better Understanding of states  Amil Khare  2018. The Debut Album  17 Sep 2017 14:26  1  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?  More test cases?  Anirudh  2018. The Debut Album  20 Jan 2017 00:12  2  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? 24124 131 232 373638552 18000 234 279 653833015 34000 98 162 688357676 13452 134 245 900436780 10306 299 207 85275311  WA4  Carrot  2018. The Debut Album  15 Sep 2016 19:21  6  WA4 Carrot 12 Oct 2014 12:32 some test please, with % 10^9 + 7 Re: WA4 Dawid Jewko 11 Nov 2014 20:16 50000 300 300 422791438 49999 299 299 505277419 25000 269 222 716603086 Re: WA4 eeshandhekane 5 Jul 2015 08:09 Edited by author 05.07.2015 08:20 Re: WA4 Vladimir Li 29 Jul 2015 18:00 Somehow I get right values for 50000 300 300 and 25000 269 222 but wrong for 49999 299 299 check the final answer mod 1000000007  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  2018. The Debut Album  30 Dec 2015 00:55  3  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[ij][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[ij][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 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. 

