Thread: Stabilizing Array 2D-ON

  1. #1
    Banned
    Join Date
    Apr 2015
    Posts
    596

    Stabilizing Array 2D-ON

    Hi guys !
    I really in need for help; I'm not new in C programming but still having gaps!
    I've a problem in dynamic programming which given a matrix with N*N size which I've to add ones to the matrix to be stable. to be stable must satisfied those two rules: (( assuming weight is the sum of number 1))
    1) its left and right halves must carry the same weight
    also
    2)its front and left halves must carry the same weight


    for example: lets assume I have this matrix(As an input):
    1 1 1
    0 0 0
    1 1 1
    for first condition(rule), the half is the second column, this matrix is stable because the first column weight (3) is the same weight as the third column which's also 3.
    for second condition(rule), the half is the second row, the first row is weighting "3-number of ones" the same as the third row which it's also weight 3. So, the matrix is called stable!

    Second example:
    lets assume I have this matrix
    1 - -
    0 0 0
    - 1 -
    I've to fill the matrix with maximum weight (fill maximum number of ones) that can ensure the matrix will be stable(stable means
    satisfying the two conditions respectively) - by the way for filling the matrix in my second example .. the output must be the the same matrix on the first example because it's the maximal way to stable the matrix ..

    third example: lets assume the given input matrix is:
    - - -
    - - -
    0 0 -

    then I need to assign into that matrix max number of ones that can ensure stabilization of my matrix, for third example the output must be:
    1 - -
    1 1 1
    0 0 1
    the "-" is free space or whatever neglected value "-1" .. doesn't matter ..



    Any help please? I've started coding the problem but I have no clue which direction to go, how to think about it properly !


    I want solve it in an optimal way and not in iterative way!!

    thanks alot for your cooperative!!
    Last edited by RyanC; 05-01-2019 at 03:42 PM.

  2. #2
    Banned
    Join Date
    Apr 2015
    Posts
    596
    I'm not succeeding to figure out the recursion rule to state my solution upon it ..

  3. #3
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,877
    So just to clarify - the amount of 1s in the first column must equal the amount in the 3rd, and the centre doesn't matter for a balanced matrix?

    What have you tried?

  4. #4
    Banned
    Join Date
    Apr 2015
    Posts
    596
    It doesn't matter; assume that the dont care is 1(central filled with 1); we need to fill max number of 1 into the matrix and keeps it stable

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,170
    > I've started coding the problem but I have no clue which direction to go
    You stop coding, and grab a pencil and paper.

    Then you keep doodling and thinking of ideas until you come up with an approach that does what you want.

    Then (and only then) do you grab the keyboard and start coding.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Banned
    Join Date
    Apr 2015
    Posts
    596
    about five days and I didn't arrive to any sokution before coding and then posted it here to get help ..*not helping me in code* .. In which approach to go with .. how I determine direction to go with?

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,170
    Well it seems you need to maintain both horizontal and vertical symmetry (despite you using 'left' twice in your description).

    So maybe start at opposite corners.
    * * *
    * * *
    * * *


    So you start with * then do * until you meet in the middle.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by Salem View Post
    Well it seems you need to maintain both horizontal and vertical symmetry (despite you using 'left' twice in your description).

    So maybe start at opposite corners.
    * * *
    * * *
    * * *


    So you start with * then do * until you meet in the middle.
    I didn't understand your suggestion.
    you mean I start from first * then I go to next * then I go to * so first row is visited .. and then I go to second row .. and then third row?

    what do you mean until I meet in the middle?!

    thanks for your help, much appreciated

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,170

    Compare 0,0 with 2,2
    Compare 0,1 with 2,1
    Compare 0,2 with 2,0
    Compare 1,0 with 1,2
    Compare 1,1 with 1,1
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by Salem View Post

    Compare 0,0 with 2,2
    Compare 0,1 with 2,1
    Compare 0,2 with 2,0
    Compare 1,0 with 1,2
    Compare 1,1 with 1,1
    I got your point ! then there's no need for backtracking ..no?

  11. #11
    Banned
    Join Date
    Apr 2015
    Posts
    596
    but lets assume I have like this input matrix :
    input:
    - - -
    1 1 1
    - 0 -

    the output must be :
    1 - 1
    1 1 1
    1 0 1

    the sign "-" is indicates free space (I can fill it with 1 or 0 accordingly to ensuring stabilizing) .. your concept wouldn't work on that input because I have "free spaces" so how I compare with them? thanks alot salem!!

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,170
    My concept works fine.
    Code:
    $ ./a.out 
    Before
    - - - 
    1 1 1 
    - 0 - 
    After
    1 - 1 
    1 1 1 
    1 0 1
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  13. #13
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by Salem View Post
    My concept works fine.
    Code:
    $ ./a.out 
    Before
    - - - 
    1 1 1 
    - 0 - 
    After
    1 - 1 
    1 1 1 
    1 0 1
    but it's not backtracking ..yeah? I mean there's no need to do backtracking .. if so, then that concept would be faster than backtracking in aspect of time complexity ..yeah? because backtracking is about doing recursive calls which they must have time complexity than the iterative approach that you suggested .

  14. #14
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by Salem View Post
    My concept works fine.
    Code:
    $ ./a.out 
    Before
    - - - 
    1 1 1 
    - 0 - 
    After
    1 - 1 
    1 1 1 
    1 0 1
    what about this input?
    1 - -
    - - -
    - - 0
    I didn't think it will work! am I wrong? thanks alot for your help

  15. #15
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,170
    > what about this input?
    Have you specified what should happen when 1 and 0 are opposite one another?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 12
    Last Post: 07-31-2013, 12:15 AM
  2. Replies: 4
    Last Post: 05-30-2013, 05:45 PM
  3. Replies: 2
    Last Post: 03-20-2012, 08:41 AM
  4. Replies: 9
    Last Post: 08-23-2010, 02:31 PM
  5. Replies: 6
    Last Post: 11-09-2006, 03:28 AM

Tags for this Thread