tag:blogger.com,1999:blog-29632375.post1565163015766057755..comments2024-06-25T13:05:10.432-07:00Comments on vexorian's blog: SRM 595: And now , for something completely differentUnknownnoreply@blogger.comBlogger6125tag:blogger.com,1999:blog-29632375.post-63366698265704639792013-10-25T21:34:53.363-07:002013-10-25T21:34:53.363-07:00Maybe.Maybe.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-77866042215489107352013-10-25T05:55:19.453-07:002013-10-25T05:55:19.453-07:00Maybe this have wrong title 595(of yesterday at no...Maybe this have wrong title 595(of yesterday at now) instead of 525 ?tynoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-89364965300017663642011-11-29T09:46:56.335-08:002011-11-29T09:46:56.335-08:00Ok.
We have the following grid:
xxxxxxx
xooooox
...Ok.<br /><br />We have the following grid:<br /><br />xxxxxxx<br />xooooox<br />xooooox<br />xooooox<br />xxxxxxx<br /><br />The x represent rows/columns that we would like to "remove". There are some coins in some of the x locations.<br /><br />We will focus on rows first. Each move does not only remove a row. Let us say we move all the coins up <i>once</i>. This will remove any coin that was in the top row. However, something else will happen with our rectangle:<br /><br />xooooox<br />xooooox<br />xooooox<br />xxxxxxx<br />xxxxxxx<br /><br />There is now a whole new row at the bottom of the grid. So, we will need a new move down to get rid of it.<br /><br />This means that if we first do moves up then every (move up) we use will add a new (move down) that we will need to use later. And if we begin with moves towards the down direction, the opposite will happen.vexorianhttps://www.blogger.com/profile/09588316922172217808noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-38121885494900142572011-11-29T09:34:13.711-08:002011-11-29T09:34:13.711-08:00So, we have to make a decision, we will go up a X ...So, we have to make a decision, we will go up a X number of times and down a Y number of times. Minimize (X+Y). What is cool here is that every move up, will add a requirement for a move down (There will be a whole new column that we have to remove). And viceversa. Thus if we first do the moves up required to clear the top rows, we will need to do a similar amount of extra moves down to return the grid to normal before removing the bottom rows.<br /><br /><br />didnt undertand this partAnonymoushttps://www.blogger.com/profile/01550454341223442294noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-75711023499439722202011-11-29T08:29:00.005-08:002011-11-29T08:29:00.005-08:00It cannot be by constraints. But When k can be 0. ...It cannot be by constraints. But When k can be 0. The algorithm is almost the same but you need to enable "rectangles" with 0 width or 0 height.<br /><br />When width or height of a rectangle is 0, that means that you are removing all the rows or all the columns, and the formula won't work. But the minimum number of steps is the minimum between <b>c</b> and <b>d</b> or between <b>a</b> and <b>b</b>, respectively.<br /><br />Some rectangles with non-zero width or height could be the answer, too. The logic too end with the rectangle is the same too: Remove rows or columns.vexorianhttps://www.blogger.com/profile/09588316922172217808noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-60660135074371357652011-11-29T08:12:42.676-08:002011-11-29T08:12:42.676-08:00How would you do if k = 0 ?How would you do if k = 0 ?Anonymousnoreply@blogger.com