tag:blogger.com,1999:blog-29632375.post5004660284754555564..comments2023-04-30T13:56:10.923-07:00Comments on vexorian's blog: SRM 554Unknownnoreply@blogger.comBlogger10125tag:blogger.com,1999:blog-29632375.post-81515056943300473662012-09-06T05:29:12.877-07:002012-09-06T05:29:12.877-07:00That's lame. Thanks.
I had min(bc, rc) during...That's lame. Thanks.<br /><br />I had min(bc, rc) during the match and before. Somehow I "figured" I could simplify the code by saying C=B, but never actually tested it. That was dumb.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-13928960641817318652012-09-06T03:32:07.244-07:002012-09-06T03:32:07.244-07:00I think your 250 fails for:
1 3 3 3.
Your answer: ...I think your 250 fails for:<br />1 3 3 3.<br />Your answer: 2<br />Correct answer: 3 (r, b, brb)<br /><br />I think the correction to your idea must be to subtract the min(B, C) when rh = bh, and not C everytime.Ravi Kirannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-11755711900447230502012-09-04T10:45:07.441-07:002012-09-04T10:45:07.441-07:00thanks for answering F'Ola Yinka I already che...thanks for answering F'Ola Yinka I already check allamnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-43064448571880614852012-09-04T10:44:25.988-07:002012-09-04T10:44:25.988-07:00thanks for answering vexorian It was very useful thanks for answering vexorian It was very useful amnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-66790389201718402612012-09-03T08:51:05.478-07:002012-09-03T08:51:05.478-07:00you can use the same solution I posted for the div...you can use the same solution I posted for the div1 version.<br /><br />But the low constraints allow the following solution:<br /><br />- Find the height of a tower that has X bricks and begins with a red brick:<br /><br />(X/2) * (bh + rh) , (if X is even)<br />(X/2) * (bh + rh) + rh ( if X is odd).<br /><br />(You alternate bricks of each color X/2 times. You might have an extra red brick if the number of bricks is odd)<br /><br />Likewise, if you begin with a blue brick:<br /><br />(X/2) * (bh + rh) , (if X is even)<br />(X/2) * (bh + rh) + bh ( if X is odd).<br /><br />Since the maximum number of bricks is small, you can manually try all the valid values of X. Find the height of each of the two kinds of towers of X bricks, and MARK THE HEIGHT YOU FIND IN A BOOLEAN ARRAY. After that, just count the number of heights you marked in that array. You will need a boolean array of at most [47*47] length.<br /><br />You can also use recursion, like this:<br /><br /><br />struct TheBrickTowerEasyDivTwo<br />{<br /> set towers;<br /> <br /> int rec(int h, int rc, int rh, int bc, int bh)<br /> {<br /> towers.insert(h);<br /> if (rc > 0) {<br /> rec(h + rh, bc, bh, rc-1, rh);<br /> }<br /> }<br /> <br /> int find(int rc, int rh, int bc, int bh)<br /> {<br /> rec(rh, bc, bh, rc-1, rh);<br /> rec(bh, rc, rh, bc-1, bh);<br /> return towers.size();<br /> }<br />};vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-84218337284937570762012-09-03T08:50:31.568-07:002012-09-03T08:50:31.568-07:00I dunno if Vexorian approves of this: if you don&#...I dunno if Vexorian approves of this: if you don't understand what he has written, check http://folayinkacodes.blogspot.com/2012/09/topcoder-srm-554.htmlF'Ola Yinkahttp://folayinka0607.tumblr.com/noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-44637691123908490592012-09-03T08:43:52.827-07:002012-09-03T08:43:52.827-07:00i misinterpreted the question. The elements of the...i misinterpreted the question. The elements of the return vector represent the indices in "heights" of the element of "heights" at a nth position, n being any index of the return vector. But I interpreted it to be them to be the positions of the elements of "heights" with corresponding indices in the return vector. Thank you for your explanation, it helped me solve the algorithm.F'Ola Yinkahttp://folayinka0607.tumblr.com/noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-80715486726309474822012-09-03T07:07:25.319-07:002012-09-03T07:07:25.319-07:00Hello vexorian, I am pretty new at algorithms in t...Hello vexorian, I am pretty new at algorithms in topcoder, I still learning, my question is how do you solve the 250 div2?, any special algorithm??amnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-27080775062006663292012-09-03T05:38:12.477-07:002012-09-03T05:38:12.477-07:00You can choose any tower for the left-most one and...You can choose any tower for the left-most one and still be able to have optimal distance.<br /><br />Demostration.<br /><br />Let us say the tower has height X.<br /><br />- Place tower of height X to the left most position.<br />- There are some towers of heights less than or equal to X, place them all next to tower X in non-increasing order.<br />- The remaining towers of heights greater than X are placed next, in non-decreasing order.<br /><br />(The condition for optimality is for the ordering to be the opposite of a convex ordering:<br /><br />x<br />x x<br />xx x<br />xxxx<br />)<br /><br />Since we can place any tower we want in the first position, and the problem asks us for the lex-first ordering, then it is always better (and possible) to place tower 0 in the left-most position.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-43036154276519196602012-09-03T04:41:54.497-07:002012-09-03T04:41:54.497-07:00I still don't understand the 500-point, does t...I still don't understand the 500-point, does the first tower always have index 0 after rearrangement?F'Ola Yinkahttp://folayinka0607.tumblr.com/noreply@blogger.com