wu :: forums « wu :: forums - GRID Problem » Welcome, Guest. Please Login or Register. Apr 17th, 2025, 5:59pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: william wu, Eigenray, towr, Grimbal, ThudnBlunder, SMQ, Icarus)    GRID Problem « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: GRID Problem  (Read 1405 times) witee Newbie     Posts: 48 GRID Problem   « on: Jul 22nd, 2010, 11:55am » Quote Modify Each cell of an N x N grid is either a 0 or a 1. Given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column. You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation.   Most efficient solution is required IP Logged nakli Junior Member     Gender: Posts: 62 Re: GRID Problem   « Reply #1 on: Jul 22nd, 2010, 8:43pm » Quote Modify I don't think all initial configurations can be necessarily converted to final configurations. Consider changing 1 0 0 0 to 0 0 0 0 IP Logged I was born naked on a bed with a lady. towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: GRID Problem   « Reply #2 on: Jul 23rd, 2010, 12:32am » Quote Modify XOR the starting state with the desired end state, then apply http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1253641163;start=2#2 IP Logged Wikipedia, Google, Mathworld, Integer sequence DB witee Newbie     Posts: 48 Re: GRID Problem   « Reply #3 on: Jul 23rd, 2010, 6:00am » Quote Modify I m not getting the solution..can u provide some more explanation or Pseudo code?? IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: GRID Problem   « Reply #4 on: Jul 23rd, 2010, 12:19pm » Quote Modify Given a[i,j] is the starting grid, b[i,j] is the ending grid. compute c: c[i,j] = a[i,j] xor b[i,j].   for j=0 to max    if c[0,j]=1, reverse column j for i=1 to max    if c[i,0]=1, reverse row i   That is one way.  If that amounts to reversing more than max times, then you should start with reversing row 0.   This is based on the fact that just setting the first row and the first column right determines almost completely what rows and column to reverse.  The only choice is whether or not to reverse the first row. IP Logged birbal Full Member     Gender: Posts: 250 Re: GRID Problem   « Reply #5 on: Jul 24th, 2010, 3:57am » Quote Modify on Jul 22nd, 2010, 8:43pm, singh_sukhu wrote: I don't think all initial configurations can be necessarily converted to final configurations. Consider changing 1 0 0 0 to 0 0 0 0 Yes, its not possible to convert every configuration to every other configuration.   And as Grimbal has explained, if it is not possible, you will come to know before 2*max steps. IP Logged The only thing we have to fear is fear itself! witee Newbie     Posts: 48 Re: GRID Problem   « Reply #6 on: Aug 1st, 2010, 10:02pm » Quote Modify @grimbal   what is the max in ur algo?? IP Logged birbal Full Member     Gender: Posts: 250 Re: GRID Problem   « Reply #7 on: Aug 1st, 2010, 11:19pm » Quote Modify on Aug 1st, 2010, 10:02pm, witee wrote: what is the max in ur algo??   max is N, the dimension of the grid. IP Logged The only thing we have to fear is fear itself! Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: GRID Problem   « Reply #8 on: Aug 2nd, 2010, 1:00pm » Quote Modify Uh, yes, sorry for the confusion. IP Logged newb Newbie     Posts: 38 Re: GRID Problem   « Reply #9 on: Aug 7th, 2010, 6:08am » Quote Modify It may sound dumb. But still I am  not able to get it full extent.       Please anyone help me out. at least with a example. say for ex: 0 0 0 1 1 0 1 1 0 to 1 1 0 1 1 1 1 1 1   IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: GRID Problem   « Reply #10 on: Aug 8th, 2010, 2:02pm » Quote Modify First establish what you need to change (xor the two):  1 1 0  0 0 1  0 0 1   Case A: you don't toggle row 1  1 1 0  0 0 1  0 0 1 To clear the 1st row, you need to toggle columns 1 and 2.  (2 moves)  0 0 0  1 1 1  1 1 1 To clear the 1st column, you need to toggle rows 2 and 3.  (2 moves)  0 0 0  0 0 0  0 0 0 All cells are 0, so it is a solution.  The solution: (c1, c2, r2, r3) in 4 moves.   Case B: you do toggle row 1 (count 1 move)  0 0 1  0 0 1  0 0 1 To clear the 1st row, you need to toggle columns 3 only.  (1 move)  0 0 0  0 0 0  0 0 0 To clear the 1st column, you don't need to toggle anything.  0 0 0  0 0 0  0 0 0 All cells are 0, so it is a solution.  The solution: (r1, c3) in 2 moves.   B is shorter than A, so retain solution B: (r1, c3).   Actually case B is the complemennt of case A (i.e. in B you toggle the rows/columns you don't toggle in case A).  B is preferable to A when the number of moves in A is >N. « Last Edit: Aug 8th, 2010, 2:04pm by Grimbal » IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board