Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Better Understanding of states | Amil Khare | 2018. Дебютный альбом | 30 окт 2023 12:59 | 2 | 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? | Hints. Many hints for desperate people | Kirill~ | 2018. Дебютный альбом | 20 мар 2022 22:02 | 1 | 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! :) | My explanation | Vladimir Putin | 2018. Дебютный альбом | 22 янв 2021 04:11 | 2 | 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 But how do we eliminate duplicates ? | Wrong Answer Test Case #1 | skartik | 2018. Дебютный альбом | 17 мар 2020 11:41 | 1 | 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. | Python3 TLE 4 test | Desserg | 2018. Дебютный альбом | 10 янв 2020 16:34 | 2 | 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 You may recalculate total sum of list on every iteration, if that lists changes predictable for you. For example, if you shift you list to the left for one position, and add some other value, then you may substract that shifted value and add new one, thus you perform updation. | Anyone can tell me why is not working? (Test 4 Wrong answer) | Claudiu | 2018. Дебютный альбом | 4 янв 2020 18:02 | 1 | #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; } | No subject | Vladimir Putin | 2018. Дебютный альбом | 12 июл 2019 04:18 | 1 | Edited by author 12.07.2019 04:29 | what is the meaning of this problem? | Abbos Bo'kaboyev | 2018. Дебютный альбом | 24 ноя 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. Дебютный альбом | 22 ноя 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. Дебютный альбом | 8 май 2018 00:49 | 2 | //#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; } Have you read the rules? Your deed has no honor. | Example Testcase | Khanhhuy_19 | 2018. Дебютный альбом | 6 фев 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. Дебютный альбом | 18 янв 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. Дебютный альбом | 30 сен 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 | More test cases? | Anirudh | 2018. Дебютный альбом | 20 янв 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. Дебютный альбом | 15 сен 2016 19:21 | 6 | WA4 Carrot 12 окт 2014 12:32 some test please, with % 10^9 + 7 Re: WA4 Dawid Jewko 11 ноя 2014 20:16 50000 300 300 422791438 49999 299 299 505277419 25000 269 222 716603086 Re: WA4 eeshandhekane 5 июл 2015 08:09 Edited by author 05.07.2015 08:20 Re: WA4 Vladimir Li 29 июл 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. Дебютный альбом | 30 дек 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[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 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. |
|
|