Can I ask for some guidance in solving this algorithm related problem?

Question

Hello,

In my free time I like polishing my algorithm / programming skills (well, my skills suck and I try to improve them) by solving problems on pages like topcoder.com or uva.onlinejudge.com. Usually I can write and code correct algorithm for simpler problems - I understand most of the basic concepts regarding things like recursion or graphs.

The problem is, that most of the time, I fail at solving harder problems. As for now, I stumbled across this one (on spoj.pl):

Little Johnny is playing with his small magical stamp, trying to draw a bunny on a piece of paper that is a square k by k divided into unit squares with side 1. Johnny’s stamp is a square with side 3 and consists of smaller squares with side 1. Exactly two of these squares are protuberant. Moreover, both protuberant squares are in the same row or in the same column. If Johnny wants to draw pictures using this stamp, he presses it to the piece of paper in such a way that its protuberant squares exactly match some squares of the piece of paper. If some protuberant square touches the piece of paper, the touched square on the piece of paper changes its color — from black to white or from white to black. The small stamp may lay partially outside the piece of paper, but the protuberant squares always have to lay inside. The stamp can be shifted in any way, but it cannot be rotated.

In the beginning the piece of paper is whole white. The bunny consists of some number of squares that are black (all the remaining ones have to be white). Johnny tried to draw the bunny with his small stamp for quite a long time, but he did not succeed (this does not necessarily mean that the bunny cannot be drawn, but only that it is very difficult to draw pictures on such a large piece of paper using such a small stamp!). So he asked his older brother, big John, for help.

Big John can help little Johnny by giving him his big magical stamp. The big stamp has size s by s and has an arbitrary number of protuberant squares (these squares do not necessarily need to be located in the same row or column). This stamp works just like the small stamp, but enforces one additional constraint — it can only be pressed at the piece of paper if it lies totally inside the piece of paper.

Before big John gives little Johnny his big stamp, he would like to make sure that the stamps used together are sufficient to draw the bunny. He asked you for help in determining that. Input

The first line of the standard input contains one integer t (1 ≤ t ≤ 10) denoting the number of test cases.

A description of a single test case starts with a line with two integers s and k (1 ≤ s ≤ k ≤ 1000, 1 ≤ s ≤ 200) separated by a single space. They denote the size of big John’s stamp and the size of the piece of paper.

The following three lines contain a description of the little Johnny’s stamp. Each of these lines contains three characters 0 or 1. Such a description shows how does a white piece of paper look like after pressing the small stamp: 0 represents a white square, and 1 — a black square. Exactly two characters in these three lines are ones and are both located either in the same row or in the same column. Please note that such description does not illustrate the design of the stamp itself — the stamp is symmetric to the figure drawn by it on the piece of paper.

The following s lines contain a description of the big John’s stamp in a similar format; this description may, however, contain an arbitrary number of ones. The following k lines describe the bunny, in the same format as the one used in the descriptions of stamps. A one represents a black square, whereas a zero — a white square.

Output

For each test case write out to the standard output a single line with a word "YES" (without quotation marks) or "NO", depending on whether the bunny from the test case can be drawn using the stamps from the test case (together).

Example

For the input data:

2 
3 8
010
000 
010
000
010
011
01100000   
00100000   
00010000   
00001100   
00011110   
10111100  
01111100   
01111110  
5 10  
001   
001  
000 
00000  
10100 
00001
00001
00100
0011110000
0000111000
0010011100
0111001110
1110000000
1101001000
1000001100
0110110110
0001001000
0000110000

the correct output is:

NO
YES

The trick is, that the fact that I can code simple solutions, doesn't mean, that I can code the hard ones. It is similar to the fact, that in some games, after reaching certain level, killing weak enemies doesn't give you any(or very low amounts) experience.

I don't want any solutions nor ready algorithms - but can I ask for some guidelines?

What is a correct way of thinking when trying to solve this kind of problems (or this specific one)?

Answer 1

The nature of problem solving is that it's a combination of applying knowledge you currently have and flashes of insight. I don't think there can be a "correct" way of thinking. Rather, I suggest that you assemble a range of strategies for dealing with problems. Things such as (and these don't necesserily apply to this problem, but I observe myself doing these things when addressing problems)

• Make really sure you understand the problem, play with it a bit (In fact, I'd say that this is a "correct" thing to do)
• Make a list of what you know, look for patterns in the list
• Try to solve the opposite problem, instead of proving what can be done, determine what can't be done
• Solve a few by hand, see whether some common patterns emerge
• Solve a simpler problem - divide and rule

One of the interesting things that happens with problems is that if you "play" with them enough unexpected ideas come to mind, often just after you stop thinking about the problem.

In this case I'm wondering, given a couple of stamps how you could identify a pixel that cannot be set ... hmm must depend on the pattern of white space ... look we're thinking about the inverse problem - what we don't draw.

Answer 2

I took magic lessons in a group setting when I was twelve years old. The magician's name was Joe Carota. He did a trick one time and I blurted out, "How did you do that?" He said something that day that has stuck with me ever since.

Joe's response, "Michael, if you really want to know how that trick is done you must figure out how you would do it yourself."

Well of course that's not what I wanted to hear but it did get my mind focused on problem solving. Not just any problem solving but problem solving from my perspective. If my first attempt at solving the problem took seventeen steps and was really klunky, the good news was I solved the problem.

Then by looking at the solution I had developed and looking for ways to refine that solution I would learn how to streamline the end result. Later on in my computer programming life I found out that this process was called "Stepwise Refinement".

It worked then it still works now.

Answer 3

i solved it this way: first i checked whether the two black entries in the small stamp are in the same or or in the same column. for simplification, i rotated all stamps if the are in the same row i.e. i just have to consider the case when they are in the same column.

next, i simplified the given kxk picture by using only the small stamp. i tried moving the black pixels away from the top and bottom border and merged them in the middle. you then should end up with one or two rows containing black pixels, depending on whether the distance between your black pixels on the small stamp is one or two.

next, i applied the same simplification on the big stamp (simplify the big stamp with the small stamp). then you can simplify the picture from left to right, by repeatedly applying the big stamp. between these steps, use the small stamp to ensure that you don't have more than two rows containing black pixels.

finally, it should be quite easy to do the check...