| ENG RUS | Timus Online Judge |
Discussion of Problem 1017. StaircasesPage 4 Anton some test cases // Problem 1017. Staircases 3 Aug 2021 02:42 n = 228 -> ans = 2509198527 n = 121 -> ans = 2368799 n = 10 -> ans = 9 n = 150 -> ans = 19406015 n = 201 -> ans = 517361669 n = 300 -> ans = 114872472063 n = 500 -> ans = 732986521245023 🙂 Nayami_[PermSU] How to optimize dp? // Problem 1017. Staircases 2 Apr 2021 02:02 I've found dp[sum][last][k] as cnt of make sum with k numbers and last number is last, but calculation of this dp is too long, so i've just precalculated it. Can you give me a hint? Page 3 Bekmuhamet Right algo but too slow [1] // Problem 1017. Staircases 11 Sep 2020 13:23 import java.util.Scanner; public class Staircases { public static void main(String... args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); System.out.println(find_Q(N, N)); } static int find_Q(int X, int Y) { int U = X-1; if(Y<X) { U = Y; if(Y == 0 || Y ==1) return 1; } if(Y<=1) return 0; int A = 0; for(int i = U; i > 0; i--) A += find_Q(i, Y-i); return A; } } Mariouz Re: Right algo but too slow // Problem 1017. Staircases 9 Apr 2021 19:01 Use bottom-up approach, calling function and return rakes huge amount of time Erin More test cases? // Problem 1017. Staircases 18 Aug 2020 20:02 For some reason, my code gets the right answer for all small inputs (<12) but is 1 greater than both the large test cases I've found. It gets that s(212) = 995645336, as compared to 995645335, and s(500) = 732986521245024, as compared to 732986521245023 given before. Anyone have any test cases with an input between 11 and 212 to help me pinpoint this problem? Edited by author 18.08.2020 20:03 lnxdx How to solve this problem in o(n^2)? [1] // Problem 1017. Staircases 11 Sep 2019 01:43 How to solve this problem in o(n^2)? Игор Re: How to solve this problem in o(n^2)? // Problem 1017. Staircases 9 Feb 2020 17:08 Let's start from the beginning: Let R(n) will be the function that returns count of unique staircases. Now let's introduce function G(n,j) that returns count of unique staircases each first step of which has more than j bricks. Then R(n) = G(n,0) - 1 . We have to subtract one because it is the case when all bricks are spent on the first step. G(n,j) = (n>j ? 1 : 0) + (G(n-j-1, j+1) + G(n-j-2, j+2) + ... +G(0,n)) G(n,j-1) - G(n,j) = (n == j ? 1 : 0) + G(n-j, j) => G(n,j) = G(n,j-1) - G(n-j,j) - (n == j ? 1 : 0) We know that in the case when n<=j G(n,j) = 0, so we can solve upper equation only for cases when j<n, in such cases upper formula will transform to G(n,j) = G(n,j-1) - G(n-j,j). But we still have to solve the cases when j == 0 and i > j as G(n, 0) = 1 + G(n-1, 1) + G(n-2, 2) + ... + G(0,n) //Alloc and init matrix g with zeroes //Calculat g matrix for(i = 2; i<=N; ++i){ g[i][0] = 1; for(j=1; j<i;++j){ g[i][0] += g[i-j, j]; } for(j=1; j<i;++j){ g[i][j] = g[i][j-1] - g[i-j,j]; } } cout<<g[N][0]-1; Edited by author 09.02.2020 17:14 Navin anymore testcases? // Problem 1017. Staircases 24 Sep 2018 15:51 Gokul Solving using the height of last step // Problem 1017. Staircases 21 Apr 2018 01:10 Hi All, Just want to share my experience solving this problem. I did it like this let the i be the number of bricks available and j be the height of the last step. S[i][j] = sum(S[i-j][:j]) + (1 if (i-j) < j else 0) So basically all i am doing is the number of stairs with i bricks and height j is also the same number of stairs with i-j bricks and max height of j - 1(hence the array stops at index j) and one more if i - j bricks are less than height j. There might be more slick solution avaiable, but this worked for me :) Edited by author 21.04.2018 01:11 ComebackSeason Need help [1] // Problem 1017. Staircases 8 Jul 2017 10:01 Could someone explain this idea? tbl[0] = 1; for (int i = 1; i <= N; i++) { for (int j = N; j >= i ; j--) { tbl[j] += tbl[j-i]; } } cout<<tbl[N]-1<<endl; Mahilewets Re: Need help // Problem 1017. Staircases 8 Jul 2017 16:20 It is compressed 2-dimensional dynamic programming state. It is like we take staircase from 1,2,...,N cubes and add one more step. Subtract one to not count zero len staircase. Edited by author 08.07.2017 16:20 "Compressed " means that say dp[x] = Sum(dp[x] [i]) {i = 0,1,...,N} Edited by author 08.07.2017 16:20 Edited by author 08.07.2017 16:22 Andrew1703 Code don't works with big numbers, Python 3.4 [9] // Problem 1017. Staircases 23 Jun 2017 02:00 k=int(input()) a=[] a.append(0) a.append(1) a.append(1) a.append(2) a.append(2) s=0 for j in range(5,k+1): if j%2==1: for i in range(1,j//2+1): s+=a[i] a.append(s) else: for i in range(1,j//2): s+=a[i] s=s+a[j//2]-1 a.append(s) s=0 print(a) Mahilewets Re: Code don't works with big numbers, Python 3.4 [8] // Problem 1017. Staircases 23 Jun 2017 09:35 You are printing a, print(a). A is a LIST. Andrew1703 Re: Code don't works with big numbers, Python 3.4 // Problem 1017. Staircases 23 Jun 2017 22:10 FUUUCK, thanks, its so stupid error( Andrew1703 Re: Code don't works with big numbers, Python 3.4 [6] // Problem 1017. Staircases 23 Jun 2017 22:17 but code still not works, starting with the second test, and in example program gives WA, but I check code at least 3 times, I cant find errors(( Mahilewets Re: Code don't works with big numbers, Python 3.4 [5] // Problem 1017. Staircases 23 Jun 2017 23:25 I don't understand how does your algorithm work. My AC - program is calculating values sequentially for different ladders. Time complexity is O(N*N*N). So, it is basically two dimensional dynamic programming. Mahilewets Re: Code don't works with big numbers, Python 3.4 [4] // Problem 1017. Staircases 23 Jun 2017 23:28 And your algorithm has time complexity just O(N*N). It is not surprising that I can't understand it without explanation. It is extremely optimized solution, with heavy math behind. Edited by author 23.06.2017 23:28 Grandmaster Re: Code don't works with big numbers, Python 3.4 [3] // Problem 1017. Staircases 11 Aug 2017 05:17 you don't need heavy math you can in O(n^2) time and O(n^2) space i don't know how u got O(n^3) cin >> n; for(int i = 0; i < n; i++) dp[i][0] = 1; for(int i = 1; i < n; i++) for(int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j]; if(j >= i) dp[i][j] += dp[i - 1][j - i]; } cout << dp[n - 1][n]; Edited by author 11.08.2017 05:18 Edited by author 11.08.2017 05:19 Mahilewets Nikita [BSUIR] Re: Code don't works with big numbers, Python 3.4 [2] // Problem 1017. Staircases 11 Aug 2017 09:07 When I was solving it I thought There is a staircase consists of X cubes and it's height is Y Then just add some new stair with height Z Z is strictly greater than Y Get new staircase with X+Z cubes and height Z Mahilewets Nikita [BSUIR] Re: Code don't works with big numbers, Python 3.4 [1] // Problem 1017. Staircases 11 Aug 2017 09:11 But also I know There is a solution based on generating functions I can't understand generating functions theory So I have AC on task but don't understand generating functions and that guy didn't had AC at the moment So probably generating functions are hard for him just like they are hard for me That is why I have called generating functions "heavy math" Grandmaster Re: Code don't works with big numbers, Python 3.4 // Problem 1017. Staircases 14 Aug 2017 18:39 tell me more, do you know a good article for this? Drunken Statue If answer too big...clarification here // Problem 1017. Staircases 17 Mar 2016 14:11 Problem ambiguous but finally solve! I scratched head for longest time, so clarification here to help others Do not worry, no answer writed, only clarification: IMPORTANT 1: One step = one grid COLUMN. Example show 2 steps: * ** Example show 2 steps: * ** ** Example show 4 steps: * * * ** *** **** IMPORTANT 2: Step HEIGHT > before step height. Example show all VALID N = 7: VALID Staircase #1 of 4 * * * * * ** VALID Staircase #2 of 4 * * * ** ** VALID Staircase #3 of 4 * ** ** ** VALID Staircase #4 of 4 * * ** *** Example of INVALID N = 7: INVALID Staircase: * * * * * * * Invalid because only 1 step INVALID Staircase: * *** *** Invalid because 2 steps same height (height 2, height 2, height 3) INVALID Staircase: * * * * *** Invalid because step height not > before step (height 3, height 1, height 3) Kirino Dp [1] // Problem 1017. Staircases 21 Feb 2016 20:47 dp[i][j] - represents number of staircases with i cubes and with the height of last block j. Answer is dp[n][1] + dp[n][2] + dp[n][3] ... dp[n][n]. Saurav Kumar Re: Dp // Problem 1017. Staircases 11 Jul 2016 03:57 can u help me with some algorithm better than dp(which works in O(n^2)) Edited by author 11.07.2016 03:57 Ankit Tripathi My approach-will it be correct // Problem 1017. Staircases 4 Dec 2014 10:45 I construct vertical blocks made of bricks. Now, blocks are of height 1,2,3,...n-1. Now, to make these many i need n*(n-1)/2 bricks. But, I have n bricks so I have to remove former minus latter number of bricks, which is n(n-3)/2. Now, the problem can be changed to number of ways of obtaining n(n-3)/2 from numbers 1,2,3,...n-1 while each number can be used only once. If you find the approach to be correct, please tell me how to obtain this number.(I am a newbie in coding..:)). Najmaddin Akhundov WA 7, WHY? // Problem 1017. Staircases 28 Nov 2014 12:14 mhg problem with w7 [2] // Problem 1017. Staircases 8 Aug 2014 13:01 for accepting you should consider something like long long int as input and ... but w7 is something different can anybody help for this... Sunkyu Hwang Re: problem with w7 [1] // Problem 1017. Staircases 26 Feb 2017 20:03 I got WA #7 as well.. not sure what went wrong anyone has the input n and expected output? Thanks Sunkyu Hwang Re: problem with w7 // Problem 1017. Staircases 26 Feb 2017 20:10 Ok, I figured it out. Internal cache values should be long long for storing large count. For n = 500 answer = 732986521245023 wensheng If you know please tell me. // Problem 1017. Staircases 13 Jun 2014 11:03 What the main of this problem?I can't understand it.Help,help! Raven Don't use unsigned long long, use simple long long. (was WA7) [1] // Problem 1017. Staircases 29 Apr 2014 18:31 Used unsigned long long. At result got WA7. Just clear unsigned everywhere and i got AC. Strange behavior. There was no negative numbers, it's really strange. suryansh Re: Don't use unsigned long long, use simple long long. (was WA7) // Problem 1017. Staircases 25 Jun 2016 18:37 i used unsigned but didn't get any wrong answer Arsen Babakhanyan (AUA) test case // Problem 1017. Staircases 23 Jul 2013 21:12 >>500 732986521245023 :) candide Wording is unclear // Problem 1017. Staircases 27 Jun 2013 16:05 Consider for instance the first drawing : in my perception, the staircase has 4 steps because there are 4 horizontal levels. So the first step (ie the lower one) is made up with 4 blocks, the second with 3 blocks, the third one with 2 blocks and the fourth with 2 blocks again ; so the sizes of the steps are not in _strictly_ descending order (the sizes are 4 3 2 2). So what does "size of a step" really mean? the number of blocks between two consecutive horizontal levels ? the height from the ground of a given level? the height between two consécutive levels? "descending order" : how do you count the steps? from right to left? from top to bottom? The task is no more than finding the number of partitions of n into at least two distinct parts. Edited by author 29.06.2013 04:27 thefourtheye How can I improve this program? [1] // Problem 1017. Staircases 23 Jun 2013 10:27 Num = int(raw_input()) Array = [0] * (Num + 1) def Rec (Sum, Start): global Array if Start == Num + 1 or Sum + Start > Num: return if Sum + Start <= Num and Sum != 0: Array[Sum + Start] += 1 Rec (Sum + Start, Start + 1) Rec (Sum, Start + 1) Rec (0, 1) print Array[Num] It produces following output (first column input, second column output) 0 0 1 0 2 0 3 1 4 1 5 2 6 3 7 4 8 5 9 7 10 9 11 11 12 14 13 17 14 21 15 26 16 31 17 37 18 45 19 53 20 63 But it exceeds 1 sec limit when the input is 88. Edited by author 23.06.2013 10:28 Edited by author 23.06.2013 10:28 thefourtheye Re: How can I improve this program? // Problem 1017. Staircases 23 Jun 2013 16:06 thefourtheye wrote 23 June 2013 10:27 Num = int(raw_input()) Array = [0] * (Num + 1) def Rec (Sum, Start): global Array if Start == Num + 1 or Sum + Start > Num: return if Sum + Start <= Num and Sum != 0: Array[Sum + Start] += 1 Rec (Sum + Start, Start + 1) Rec (Sum, Start + 1) Rec (0, 1) print Array[Num] It produces following output (first column input, second column output) 0 0 1 0 2 0 3 1 4 1 5 2 6 3 7 4 8 5 9 7 10 9 11 11 12 14 13 17 14 21 15 26 16 31 17 37 18 45 19 53 20 63 But it exceeds 1 sec limit when the input is 88. Never mind. Memoization did the trick. sylap WA 10 ? // Problem 1017. Staircases 17 Jun 2013 23:46 My mistake : Incorrect : dp[500][500]; Correct : dp[501][501]; So be careful with array boundaries.
|