Discussion @ 1017. Staircases @ Timus Online Judge

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)

Nikita Mogilevets 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((

Nikita Mogilevets 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.

Nikita Mogilevets 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

Nikita Mogilevets 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

Nikita Mogilevets 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?

Discussion of Problem 1017. Staircases