help me with the acm question

This is a discussion on help me with the acm question within the C++ Programming forums, part of the General Programming Boards category; Today,I have a problem with this acm quetion,Who can help me? Maybe you wonder what an annoying painting tool is? ...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    1

    Unhappy help me with the acm question

    Today,I have a problem with this acm quetion,Who can help me?
    Maybe you wonder what an annoying painting tool is? First of all, the painting tool we speak of supports only black and white. Therefore, a picture consists of a rectangular area of pixels, which are either black or white. Second, there is only one operation how to change the colour of pixels:

    Select a rectangular area of r rows and c columns of pixels, which is completely inside the picture. As a result of the operation, each pixel inside the selected rectangle changes its colour (from black to white, or from white to black).

    Initially, all pixels are white. To create a picture, the operation described above can be applied several times.
    Can you paint a certain picture which you have in mind?

    Input

    TThe input contains several test cases. Each test case starts with one line containing four integers n, m, r and c. (1 <= r <= n <= 100, 1 <= c <= m <= 100), The following n lines each describe one row of pixels of the painting you want to create. The ith line consists of m characters describing the desired pixel values of the ith row in the finished painting ('0' indicates white, '1' indicates black).

    The last test case is followed by a line containing four zeros.

    Output

    For each test case, print the minimum number of operations needed to create the painting, or -1 if it is impossible.

    Sample Input


    3 3 1 1
    010
    101
    010
    4 3 2 1
    011
    110
    011
    110
    3 4 2 2
    0110
    0111
    0000
    0 0 0 0

    Sample Output


    4
    6
    -1

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Looking at the second example: at each move choose area where all pixels are 1, or choose mixed area which after the transformation yields a new area with all pixels 1. Of course, I may be completely off with this greedy solution attempt but it would work for the sample cases.

    Edit: it won't work just like that. For example the following position with 2x2 rectangles is solveable even though there isn't any transformation that leads to an all black area:

    0110
    1001
    1001
    0110


    However, all 2x2 sections contain at most 2 black pixels and there are transformations that lead to rectangles with 3 black pixels. May-be that would help?
    Last edited by anon; 09-04-2009 at 06:46 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    First of all, notice how you will never have to use exactly the same rectangle on the same position more than once: applying it X times is the same as applying it (X%2) times (!!a = a).

    Now we can use the fact that the rectangle must be inside the image. If the upper-left bit is not the initial color, there's only one rectangle that can be used to fix that. Now since we know we never have to use the same rectangle, we can move one pixel to the right. Again, there's only one rectangle that can invert it if we must, since the only other option is one pixel to the left, but we already know whether we had to select that.

    That results in quite an easy algorithm, but I believe it should be efficient enough. It's only O((n-r+1)*(m-c+1)*r*c). So the maximum is about 6.502.500 operations. During the contests, you could usually fit 1 to 10 million operations per test case. Since these operations are fairly simple, I imagine it'll be fast enough.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Sounds brilliant, except practically solves the challenge for the OP
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,158
    I don't get it. Can't you just use rectangles of size 1x1 to control individual pixels? All images are possible and can be drawn in at most O(n) time.

    EDIT: Ah, you don't get to choose r and c. I see now.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by anon View Post
    Sounds brilliant, except practically solves the challenge for the OP
    I know... Puzzles like these always get me excited and whatever I'm doing, I put down my work until I fix the problem...

    @brewbuck: Yeah, I had to read the problem statement twice as well before I understood that point .

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Alice....
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  2. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  3. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 12:47 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21