Mosaic ICPC Challenge

[kevinkjt2000]

So I am preparing for this year's ICPC and have been practicing old problems. I just ran into this really "fun" mosaic problem... http://acmicpc-live-archive.uva.es/nuevoportal/data/p4608.pdf

I haven't even begun to start coding, because I don't even know of a way to solve this problem. Has anyone done a problem like this before or have any ideas on how to solve it?

*Edit* Not to mention if you look at the top scores/times the program that made it to number one could solve this in 0.002 seconds... http://acmicpc-live-archive.uva.es/nuevoportal/rankprob.php?p=4608

[PanGalactic]

This is all algorithmic. If you don't know the most efficient algorithm, it's going to be hard to solve it. And I certainly don't know the right algorithm to use for this. A little google-fu might help: "computer generated patterns".

What I hate about programming challenges like this is that you basically have to know the right algorithms and techniques to use for all problems in order to "win".

What I like about programming challenges like this is that knowing the right algorithms and techniques to use is often critical for addressing business problems in a cost-effective manner.

Good luck!

[kevinkjt2000]

Our teacher doesn't even know how to solve this problem. She suggested a dynamic programming approach to solve the problem. The math required for dynamic is way above my head and all my classmate's heads. *bangs head* *sighs* Oh well I guess I'm just going to have to ask around and visit the library :( I do hope that someone on this site does come up with a helpful hint to solve this problem. I just know it has to be simple if a program can handle multiple inputs in 0.002 seconds including the 10x500 case.

[jsmith]

Basically it means that any kind of trial-and-error or brute force algorithm is a non-starter.

[kevinkjt2000]

Have any of the math geniuses on this site figured out a formula I could use yet? My theory is that there is only so many possible way the tiles can fit together on a small grid, and that larger grids are just repetitions of said smaller grids. Its just that there seems to be too many smaller grids for it to be true.

[R0mai]

I guess this is very simple. Let the result be f(N, M) where N and M are the dimensions. I think f is going to be a relatively simple function, and your program doesn't even have to know about tiles, and stuff. You just have to precalculate the f function.

[jsmith]

Given that the fastest solution posted required 20ms to run, I would disagree, unless the author was using
an 8088 processor.

EDIT: er, 2ms. In which case I still disagree, simply based on the number of instructions the CPU can execute
in that amount of time.

[R0mai]

@jsmith
You mean my method (if possible) would run much faster than that?

[jsmith]

I would assume that evaluating a simple, non-recursive function would take less than 1ms.

[kevinkjt2000]

So what could go in the f function? I have been considering different formulas for low n and m. For example if n and m are both even you always add 1 for the combination of all squares. If n or m is 3 and the other input is odd then there are no possible combinations. I have little formulas like this for all the 2, 3, and 4 size dimensions, but once I get to just size 5.... It gets kind of hard to come up with a formula past that point.

[kevinkjt2000]

*bump

[R0mai]

I was thinking to generate all possible outcomes for N and M, then study the result. Some mathematical program might be able to generate an approximation of the function f.

[kevinkjt2000]

Just 4 x 16 is already 366,318... even small grids like that aren't even able to studied :(
But what is this about mathematical program? I have Maple 13, but I wouldn't know how to approximate a random function f with it. I don't think it is exponential, I think it is factorial.

[CQQL]

Why are you supposed to modulo your result by 10^6?

I have just brain-brute-forced ;) some small test cases with 1 dimension fixed to see if there is a relation at all. Dont know if this is the right way to approach this problem:
Dimensions | Combinations
2x2 | 1
2x3 | 2
2x4 | 1
2x5 | 4
2x6 | 5
2x7 | 6
2x8 | 12
2x9 | 16

[kevinkjt2000]

CQQL Not a bad idea. I could post all the combos I have counted so far as well.
2x10 | 25
3x2 | 2
3x3 | not possible
3x4 | 4
3xodd | not possible
3xeven | 2^(even/2)=answer
4x2 | 1
4x3 | 4
4x4 | 6
4x5 | 16
4x6 | can fit two 4x3s and a 4x4 with 4x2
If all the little tile sets are the same making up the big one they exhaust symmetric possibilities. You can't take the 4x3s and arrange them any other way (at least with the small mxn problems). 4x4 and 4x2 is an example of using differently sized tile sets to make a bigger one. When you do that you have to multiply by how many little tile sets you are using.
| back to the solution(ignore things in brackets): 4[4x3]*4[4x3]+6[4x4]*1[4x2]*2[4x4 and 4x2 is two tile sets]= 16+18 = 34
oh almost forgot there is this weird way to do this:
0033 1111
0223 1111
1255 1122
1165 1122 (its like a larger 2*3 looking thing made of bigger L shaped tiles)
4667 2222
4477 2222

so have to add those 4 combos as well

so after that large mouthful I will conclude the answer is 34+4=38

[dserbia]

CQQL: The numbers can probably be very large, so you modulo them by 10^6 so they can fit in an integer type.

I think it is not so simple, in that amount of time you might even fit N^2*M complexity or something similar. Probably something involving logarithms (sort). Dynamic programming is probably doable. However, I can't think of a solution now, but it may be possible :)

In other words: it is not a mathematical formula. If I'm not wrong.

[kevinkjt2000]

dserbia: The answers do get very large very quickly. I mean just a 4x16 is 366,318. Imagine 16x16........ Oh dear.
I still like my idea with build larger tile sets with smaller ones and just multiplying the smaller ones together. (Except for the fact that I just discovered a 7x7 combination, so I have no idea how many "smaller" tile sets are out there.)
By the way 5xodd is not possible. And 5xeven=4^(even/2) (I am not quite sure about this last formula, but it seems to be the case.)

[CQQL]

I couldnt sign in because of a mistake in the javascript of this forum. -.-

Is it possible that oddXodd is not possible at all? Because you can build parts of it, but ultimately there will always be a 3x3 left, which is not solvable.

[kevinkjt2000]

I made a 7x7 by hand so oddxodd is possible but only if both dims are greater than or equal to 7.