| Show all threads Hide all threads Show all messages Hide all messages | | Page 4 | | some test cases | Anton | 1017. Staircases | 3 Aug 2021 02:42 | 1 | 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 | | How to optimize dp? | 🙂 Nayami_[PermSU] | 1017. Staircases | 2 Apr 2021 02:02 | 1 | 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 | | Right algo but too slow | Bekmuhamet | 1017. Staircases | 9 Apr 2021 19:01 | 2 | 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;
}
} Use bottom-up approach, calling function and return rakes huge amount of time | | More test cases? | Erin | 1017. Staircases | 18 Aug 2020 20:02 | 1 | 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 | | How to solve this problem in o(n^2)? | lnxdx | 1017. Staircases | 9 Feb 2020 17:08 | 2 | How to solve this problem in o(n^2)? 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 | | anymore testcases? | Navin | 1017. Staircases | 24 Sep 2018 15:51 | 1 | | | Solving using the height of last step | Gokul | 1017. Staircases | 21 Apr 2018 01:10 | 1 | 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 | | Need help | ComebackSeason | 1017. Staircases | 8 Jul 2017 16:20 | 2 | 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; 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 | | Code don't works with big numbers, Python 3.4 | Andrew1703 | 1017. Staircases | 14 Aug 2017 18:39 | 10 | 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) You are printing a, print(a). A is a LIST. FUUUCK, thanks, its so stupid error( 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(( 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. 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 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 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 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" tell me more, do you know a good article for this? | | If answer too big...clarification here | Drunken Statue | 1017. Staircases | 17 Mar 2016 14:11 | 1 | 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) | | Dp | Kirino | 1017. Staircases | 11 Jul 2016 03:57 | 2 | Dp Kirino 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]. Re: Dp Saurav Kumar 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 | | My approach-will it be correct | Ankit Tripathi | 1017. Staircases | 4 Dec 2014 10:45 | 1 | 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..:)). | | WA 7, WHY? | Najmaddin Akhundov | 1017. Staircases | 28 Nov 2014 12:14 | 1 | | | problem with w7 | mhg | 1017. Staircases | 26 Feb 2017 20:10 | 3 | for accepting you should consider something like long long int as input and ...
but w7 is something different can anybody help for this... I got WA #7 as well.. not sure what went wrong anyone has the input n and expected output? Thanks Ok, I figured it out.
Internal cache values should be long long for storing large count.
For n = 500
answer = 732986521245023 | | If you know please tell me. | wensheng | 1017. Staircases | 13 Jun 2014 11:03 | 1 | What the main of this problem?I can't understand it.Help,help! | | Don't use unsigned long long, use simple long long. (was WA7) | Raven | 1017. Staircases | 25 Jun 2016 18:37 | 2 | 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. i used unsigned but didn't get any wrong answer | | test case | Arsen Babakhanyan (AUA) | 1017. Staircases | 23 Jul 2013 21:12 | 1 | test case Arsen Babakhanyan (AUA) 23 Jul 2013 21:12 | | Wording is unclear | candide | 1017. Staircases | 27 Jun 2013 16:05 | 1 | 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 | | How can I improve this program? | thefourtheye | 1017. Staircases | 23 Jun 2013 16:06 | 2 | 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 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. | | WA 10 ? | sylap | 1017. Staircases | 17 Jun 2013 23:46 | 1 | My mistake :
Incorrect : dp[500][500];
Correct : dp[501][501];
So be careful with array boundaries. |
|
|
