tag:blogger.com,1999:blog-7577992710153214359.post3754004480375486535..comments2023-06-11T19:12:22.917+05:30Comments on Journey of CP with DP: Way to solve Tiling ProblemsMohit Raihttp://www.blogger.com/profile/02073873130319389765noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-7577992710153214359.post-56071561848677777582022-06-05T13:53:24.534+05:302022-06-05T13:53:24.534+05:30f(n)=f(n-2)+2*g(n-1)
g(n)=f(n-2)+g(n-2)f(n)=f(n-2)+2*g(n-1)<br />g(n)=f(n-2)+g(n-2)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-80413586172489748192021-04-28T02:46:55.818+05:302021-04-28T02:46:55.818+05:30t is nothing but the number of test cases. You can...t is nothing but the number of test cases. You can ignore t if you want to run your code for one test case.Mohit Raihttps://www.blogger.com/profile/02073873130319389765noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-79314504371638891982021-04-27T23:38:41.997+05:302021-04-27T23:38:41.997+05:30What does the t represent in the code for Question...What does the t represent in the code for Question 2?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-67034814269574330172021-01-16T12:44:00.735+05:302021-01-16T12:44:00.735+05:30okay thanks..
GOT IT..
okay thanks..<br />GOT IT..<br /><br />Anonymoushttps://www.blogger.com/profile/12357838003013641364noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-39769598541851911802021-01-16T12:11:40.921+05:302021-01-16T12:11:40.921+05:30These recurrences giving wrong answer on SPOJ.
Can...These recurrences giving wrong answer on SPOJ.<br />Can you please post your corrected code.<br />Anonymoushttps://www.blogger.com/profile/12357838003013641364noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-72511388677033614042020-05-30T15:40:13.029+05:302020-05-30T15:40:13.029+05:30thank you :)thank you :)Mohit Raihttps://www.blogger.com/profile/02073873130319389765noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-88873354989226419752020-05-30T07:46:26.811+05:302020-05-30T07:46:26.811+05:30Atlast a clear explanation of tiling problems have...Atlast a clear explanation of tiling problems have been found. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-29255318945559310912020-05-29T00:21:02.157+05:302020-05-29T00:21:02.157+05:30https://codeforces.com/topic/60968/en2?locale=enhttps://codeforces.com/topic/60968/en2?locale=enutkarsh_bansalhttps://www.blogger.com/profile/17931854004718722626noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-29637431625695331062020-05-29T00:13:29.196+05:302020-05-29T00:13:29.196+05:30equations can be of the form:
f(n)=f(n-1) + f(n-2...equations can be of the form:<br /><br />f(n)=f(n-1) + f(n-2) + g(n-1) + g(n-1) + h(n-1)<br />g(n)=g(n-2) + f(n-1) + f(i-2)<br />h(n)=h(n-2) + f(n-1)<br /><br />initial values:<br />f[0]=1; f[1]=1;<br />g[0]=0; g[1]=1;<br />h[0]=0; h[1]=1;utkarsh_bansalhttps://www.blogger.com/profile/17931854004718722626noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-3334063264728504942020-05-29T00:09:22.387+05:302020-05-29T00:09:22.387+05:30This comment has been removed by the author.utkarsh_bansalhttps://www.blogger.com/profile/17931854004718722626noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-13539081204330618982020-05-29T00:08:33.211+05:302020-05-29T00:08:33.211+05:30This comment has been removed by the author.utkarsh_bansalhttps://www.blogger.com/profile/17931854004718722626noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-1046099184195630232020-05-27T13:19:33.930+05:302020-05-27T13:19:33.930+05:30Actually what i mean is, if you observe images of ...Actually what i mean is, if you observe images of g(n) and g(n-1) then they are not of same type. I think there should be some horizontal 2x1 tiles added to g(n-1) so that it becomes g(n-2) whose pattern look like that of g(n) initially.<br /><br />also if possible then can you give link to this problem.Sanyam Singhalnoreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-7272667872121561192020-05-27T13:10:35.332+05:302020-05-27T13:10:35.332+05:30Hi, one more doubt in the 2nd example you explaine...Hi, one more doubt in the 2nd example you explained above for 4xn using 2x1.<br /><br />In this when you are finding g(n), then can the recurrence relation can be like:-<br />g(n) = f(n) + g(n-2).<br />why you have taken g(n-1), here g(n-1) as you shown in image, will be the case when the upper 2x1 is empty but here we are taking the cases for g(n) in which the lower 2x1 part is empty. <br />Are you getting my point?Sanyam Singhalnoreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-73078522021029942612020-05-27T12:31:35.845+05:302020-05-27T12:31:35.845+05:30I think your base cases are wrong.
The base cases ...I think your base cases are wrong.<br />The base cases are:<br />f[0] = g[0] = 1<br />f[1] = g[1] = 0<br /><br />and recurrence relations are:<br /><br />f[i] = f[i-2] + 2 * g[i-2];<br />g[i] = f[i] + g[i-2];Mohit Raihttps://www.blogger.com/profile/02073873130319389765noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-31171077926142407392020-05-27T12:23:12.111+05:302020-05-27T12:23:12.111+05:30Hi, i was just trying the bonus problem M3TILE on ...Hi, i was just trying the bonus problem M3TILE on spoj, i am not getting the mistake in my recurrence relation. Can you please have a look and help me out at it.<br /><br />ll solve(ll n) {<br /> ll f[n+10]={0}, g[n+10]={0};<br /> <br /> f[0]=1, f[1]=0, f[2]=3, f[3]=0;<br /> g[0]=0, g[1]=1, g[2]=0, g[3]=1;<br /><br /> if(n<4){<br /> return f[n];<br /> }<br /><br /> for(int i=4;i<=n; i++) {<br /> f[i] = f[i-2] + 2*g[i-1];<br /> g[i] = f[i-1] + g[i-2];<br /> }<br /><br /> return f[n];<br />}Sanyam Singhalnoreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-70219527426267657672019-12-19T12:58:56.275+05:302019-12-19T12:58:56.275+05:30no, it will be g(n-2) and h(n-2) because in both c...no, it will be g(n-2) and h(n-2) because in both case we are putting the tile horizontally and then tile will cover 2 length. So we left with n-2 space.<br />Hope It will help you :)Mohit Raihttps://www.blogger.com/profile/02073873130319389765noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-13800618777313982492019-12-19T10:17:32.344+05:302019-12-19T10:17:32.344+05:30Hi,
Below equation:
f(n) = f(n-1) + f(n-2) + g(n-...Hi,<br /><br />Below equation:<br />f(n) = f(n-1) + f(n-2) + g(n-2) + g(n-2) + h(n-2)<br /><br />it should be g(n -1) and h (n-1) right ?<br /><br />can you please explain ?Anonymoushttps://www.blogger.com/profile/01561250172910152888noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-60750552773175642122019-08-22T16:40:33.825+05:302019-08-22T16:40:33.825+05:30Thanks :)Thanks :)Mohit Raihttps://www.blogger.com/profile/02073873130319389765noreply@blogger.comtag:blogger.com,1999:blog-7577992710153214359.post-61337610078411379542019-07-24T06:58:26.168+05:302019-07-24T06:58:26.168+05:30Great Explanation. Thanks :DGreat Explanation. Thanks :DAnonymousnoreply@blogger.com