tag:blogger.com,1999:blog-29632375.post3330976783409964140..comments2023-06-19T19:45:40.281-07:00Comments on vexorian's blog: SRM 544: HehUnknownnoreply@blogger.comBlogger7125tag:blogger.com,1999:blog-29632375.post-26245067309633478242012-05-31T14:02:58.668-07:002012-05-31T14:02:58.668-07:00Ok, I got it.
It is a linear recurrence problem (...Ok, I got it.<br /><br />It is a linear recurrence problem (Read this tutorial: http://community.topcoder.com/tc?module=Static&d1=features&d2=010408 )<br /><br />There are two solutions using that approach, one uses a 4x4 matrix (4 linear functions) and the other a 13x13 matrix.<br /><br />Let f(n) be the total x*y sum after n steps. (Thus f(0) = 0).<br /><br />Can you write f(n) in terms of f(n-1) (Using the help of other 13 or 3 functions that are also linear).<br /><br />Try finding 4 functions like this:<br /><br />f(n) = a * f(n-1) + b * A(n-1) + c * B(n - 1) + d * C(n-1)<br />A(n) = e * f(n-1) + f * A(n-1) + g * B(n - 1) + h * C(n-1)<br />B(n) = i * f(n-1) + j * A(n-1) + k * B(n - 1) + l * C(n-1)<br />C(n) = m * f(n-1) + o * A(n-1) + p * B(n - 1) + q * C(n-1)<br /><br />( The coefficients in some places might be 0).<br /><br />For n=0:<br /><br />( f(0) A(0) B(0) C(0) ) = ( 0 ? ? ? ) (The ? are the initial values of those functions).<br /><br />With such a recurrence, you can calculate the solution in O( log(n) * 4^3), because:<br /><br /><br />( f(i) A(i) B(i) C(i) ) x (Some 4x4 matrix) = ( f(i+1) A(i+1) B(i+1) C(i+1) )<br /><br />More details in the official editorial, which I am writing.<br /><br />Spoilers: <br />A(n) is the sum of the x coordinate of each fox after n steps.<br />B(n) is the sum of the y coordinate of each fox after n steps.<br />C(n) is the total number of foxes after n steps.<br /><br />As far as linear recurrence problems go, this is, to me, the hardest of those problems I have solved in years.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-20681255604808885092012-05-29T20:01:30.522-07:002012-05-29T20:01:30.522-07:00I wish I could. I gave it a try during the match a...I wish I could. I gave it a try during the match and was confused.<br /><br />Solutions seem to first precalculate the first few steps, but I am not very good at reading them.<br /><br />It is too lame that the forum of 544 is not working, we could ask there.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-74370014107389951042012-05-29T17:47:01.877-07:002012-05-29T17:47:01.877-07:00Could you please tell me how to solve the div1 900...Could you please tell me how to solve the div1 900 problem?I am confused about that……This_poetnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-57241878371839912062012-05-29T07:24:57.654-07:002012-05-29T07:24:57.654-07:00The thing about practice is that results are never...The thing about practice is that results are never instantaneous.<br /><br />I might even say it takes 6 months before you'll notice the real effect of whatever method you use.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-61271847866797298022012-05-29T07:20:47.477-07:002012-05-29T07:20:47.477-07:00very disappointed about myself this round. I am ki...very disappointed about myself this round. I am kind of jealous your achievement today (just kidding ^^).<br /><br />I keep practicing but it seems that I havent make any progress. Maybe my practice method is bad. So disappointing T__Tdavenoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-51913933957007805242012-05-29T07:08:59.391-07:002012-05-29T07:08:59.391-07:00Yes, I just mis-copied what writer said about the ...Yes, I just mis-copied what writer said about the upper bound. But it seems 201 is the limit.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-54583157314959264962012-05-29T07:02:03.566-07:002012-05-29T07:02:03.566-07:00It is possible to have 201 voters in the "eas...It is possible to have 201 voters in the "easy" problem: percentages {0,0,99} and number of voters {1,1,199}.stubbscrollnoreply@blogger.com