Considering that d[i][j] indicate the number of i bricks divided into j columns steps.So if we cut away the downmost brick of every steps, and we can get d[i][j] = d[i-j][j-1](if the 1st step only have one brick) + d[i-j][j](if the 1st step have more than one brick). Thus q = d[n][2->max_j] really smart! how can you get that dude? Hello, Thank you for your hint, it was very useful for me
and yes, your solution is awesome! really nice idea, i like it. But how does this transition ensures that the next column always has more bricks than the current column? 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 My solution is fast! valery@uni.lg.ua Ha! My solution: only 0.001 sec and 70 Kb! And it's normal solution (no cheating). I sent it some minutes ago. PS: It's very good that your solution works fast but Always there is better one :) Ha-Ha! My solution works sometimes too 0.001, but how many iterations of your cycle on N=500? Ha-ha-ha! My solution is O(n^2) but I know O(sqrt(n)*n) one. My solution is O(1) :) sorry to bother u on such an old post...but can u help me on a better approach to this question my solution is O(0) :) Jokes on you! My solution is O(-∞) So, your solution travels back in time or make the time in the Universe acting backwards?:) 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 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? 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)? 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 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 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? 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 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 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]. can u help me with some algorithm better than dp(which works in O(n^2)) Edited by author 11.07.2016 03:57 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 Hello. I have a question, but it is not really about this problem. Generally asking, if you would be grateful to tell me how can I solve this type of dynamic programming problems, could you tell me how can i find the reccurrence easier? Till now I've made backtrackings on small numbers and I tried to search for a reccurrence between the elements, but I find it out pretty hard. Thank you! So am I.. But sometimes I am trying to calculate how many new figures give us each of them for any N. I don't know is it correct or is it the easiest way, but it sometimes works) 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) Autors! you are wrong. fix please. It's allright! You cannot have two neighbour stair steps with horizontal difference more than 1. const n=500; var a:array[1..n]of string; i,j,k,l,m,rk,v,t,z,pus:longint; sum,ss,zz:string; function mmm(p:longint):longint; begin v:=1; while ((v+1)*(v+2)) div 2<=p do v:=v+1; mmm:=v; end; function plus(pluss1,pluss2:string):string; {only pozitive!!!} var plusi,pluscode,plusi1,plusi2,plusna,plusba:integer; pluss,plusss:string; begin if pluss1='' then pluss1:='0'; if pluss2='' then pluss2:='0'; pluss:=''; while length(pluss1)<length(pluss2) do pluss1:='0'+pluss1; while length(pluss2)<length(pluss1) do pluss2:='0'+pluss2; plusna:=0; plusba:=0; for plusi:=length(pluss1) downto 1 do begin val(pluss1[plusi],plusi1,pluscode); val(pluss2[plusi],plusi2,pluscode); plusba:=(plusi1+plusi2+plusna) mod 10; plusna:=(plusi1+plusi2+plusna) div 10; str(plusba,plusss); pluss:=plusss+pluss; end; if plusna<>0 then begin str(plusna,plusss); pluss:=plusss+pluss; end; plus:=pluss; end; begin readln(m); for i:=1 to m do a[i]:='1'; sum:='0'; rk:=mmm(m); for i:=2 to rk do begin {ЇҐаҐЎ®а Ї® k} for j:=1 to i do begin t:=i+j; while (t<(i+1)*i div 2)and(t<=m) do t:=t+i; ss:='0'; while t<=m do begin zz:=a[t]; a[t]:=plus(a[t-i],ss); t:=t+i; ss:=zz; end; end; if m<((i+1)*i div 2)-1 then pus:=m else pus:=((i+1)*i div 2)-1; for z:=1 to pus do a[z]:='0'; sum:=plus(sum,a[m]); end; writeln(sum); end. > const n=500; > var a:array[1..n]of string; > i,j,k,l,m,rk,v,t,z,pus:longint; > sum,ss,zz:string; > function mmm(p:longint):longint; > begin > v:=1; > while ((v+1)*(v+2)) div 2<=p do v:=v+1; > mmm:=v; > end; > function plus(pluss1,pluss2:string):string; {only pozitive!!!} > var plusi,pluscode,plusi1,plusi2,plusna,plusba:integer; > pluss,plusss:string; > begin > if pluss1='' then pluss1:='0'; > if pluss2='' then pluss2:='0'; > pluss:=''; > while length(pluss1)<length(pluss2) do pluss1:='0'+pluss1; > while length(pluss2)<length(pluss1) do pluss2:='0'+pluss2; > plusna:=0; plusba:=0; > for plusi:=length(pluss1) downto 1 do begin > val(pluss1[plusi],plusi1,pluscode); > val(pluss2[plusi],plusi2,pluscode); > plusba:=(plusi1+plusi2+plusna) mod 10; > plusna:=(plusi1+plusi2+plusna) div 10; > str(plusba,plusss); > pluss:=plusss+pluss; > end; > if plusna<>0 then begin > str(plusna,plusss); > pluss:=plusss+pluss; > end; > plus:=pluss; > end; > begin > readln(m); > for i:=1 to m do a[i]:='1'; > sum:='0'; > rk:=mmm(m); > for i:=2 to rk do begin {ЇҐаҐЎ®а Ї® k} > for j:=1 to i do begin > t:=i+j; > while (t<(i+1)*i div 2)and(t<=m) do t:=t+i; > ss:='0'; > while t<=m do begin > zz:=a[t]; > a[t]:=plus(a[t-i],ss); > t:=t+i; > ss:=zz; > end; > end; > if m<((i+1)*i div 2)-1 then pus:=m else pus:=((i+1)*i div 2)- 1; > for z:=1 to pus do a[z]:='0'; > sum:=plus(sum,a[m]); > end; > writeln(sum); > end. You turned out to be a lamer yourself. go learn C or C++. your solution is verry stupid. I think only one lamer could solve the problem like this. I wrote only 22 lines. Of course, Pascal suks. what does your program mean? program ural1017; var q:array[0..500]of int64; n,i,j:integer; begin fillchar(q,sizeof(q),0); readln(n); q[0]:=1; for i:=1 to n do for j:=n downto i do inc(q[j],q[j-i]); writeln(q[n]-1); end. This code is beautiful. Can you explain it please? Thanks This code is beautiful. Can you explain it please? Thanks This code is sux. I wrote it with C++. It answers 0 with any input =\ And, yes, I wrote it right. #include <iostream> using namespace std; int main(void) { short n; cin >> n; long long a[501]; for (short i=0; i<501; i++) a[i]=0; a[0]=1; for (short i=1; i<=n; i++) for (short j=n; j>=i; j--) a[j]+=a[j-1]; cout << a[n]-1; return 0; } It writes 0 with any input cuz we n times doing operation a[j]=a[j-1] for j from n to i. Of course the 1 we placed in the beginning goes to the a[n]. Then we are outputting a[n]-1, witch of course will be 1-1=0. The only good in this code that I saw was that this code can generate Pascal's triangle. Artem, good one! Красава) Доставил твой пост:) This works. How did you come to this short solution:)? haha, why anyone use array with length 500? just try to think a little, program need array with length no more 32! LOL! the only lamer here is "Yuriy Frolov (ufrolov@ukr.net)"-:D :D :D Your program is worst i've ever seen :D :D :D You chose stupidest way to solve and you think that others are lamers??? :D it would be better to hide this solution except to submit it :D 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..:)). |
|