Send your feedback or ask for help here!
I think the statement is a bit too revealing - only the technical implementation remained as task.
I am not sure I would have found that such simple D&C method exists, probably would have tried a much more complicated and slower backtracking approach first…
if the algorithm choice was left to the user it wouldn’t have a unique solution as there are other ways to successfully layout the tiles.
I’m thinking about something, it’s not about the puzzle … but the puzzle shows that (2^n)²-1 is always multiple of 3.
a²-b²=(a+b)(a-b) => (2^n)²-1 = (2^n+1)(2^n-1)
2^n can’t be a multiple of 3, so 2^n = 3k+1 or 3k+2
If 2^n is 3k+1, 2^n-1 is 3k => multiple of 3
If 2^n is 3k+2, 2^n+1 is 3k+3 => multiple of 3
So (2^n+1)(2^n-1) is multiple of 3.
Ok that’s not obvious a priori, but it is true.
(2^n)^2−1=4^n−1. Modulo 3, it’s just 1^n−1=0.
Ok thanks, i didn’t know that (a^n)%b = (a%b)^n.
I’m not very familiar with modulo.
Modular arithmetic behaves just like regular arithmetic except for division and exponentiation.
For division, the problem is that there are way more zeros than in usual arithmetic (because
k * n = 0 (mod n) for all integers
n, k). But it’s not too complicated, actually. There are two basic ideas:
- If we have a congruence
a * b = a * c (mod n), then we can deduce that
b = c (mod n/gcd(a, n)). This can be proven using the definitions of congruence mod n and GCD.
gcd(a, n) = 1, then there exists an integer
a * b = 1 (mod n). This
1/a, i.e., you can divide by any number
athat shares no prime factors with
n, simply by multiplying with its inverse
For exponentiation, one direction is pretty intuitive: if
a = b (mod n), then
a^k = b^k (mod n). But you should keep in mind that the exponents are NOT to be taken
(mod n), e.g.
2 = 10 (mod 8), but
2^2 = 4 =/= 0 = 2^8 (mod 8). For dealing with exponents, you’ll need to consult Fermat & Euler’s theorems (they aren’t complicated; they really just make your life easier).
how exactly do you check for other solutions? there doesn’t necessarily have to be a single solution.
the following is a solution for test 4…but you seem to want a different solution. You might want the connections to be mirrored, but there’s no point in accepting a version just because your algorithm pulls it out first
+--+--+--+--+--+--+--+--+ | | | | | +--+ +--+ +--+ + +--+ | | | | | | | | | + +--+ +--+ +--+--+ + | | | | | +--+--+--+--+--+--+--+--+ | | | | | +--+ +--+ +--+ + +--+ | | | | | | | | | + +--+ +--+ +--+--+ + | | | | | +--+--+--+--+--+--+--+--+ |##| | | | | | +--+ + +--+ + +--+ + | | | | | | +--+--+--+--+--+--+--+--+
I would like to post a picture, but I can’t seem to do it
The statement explains why there is only 1 solution, after “Solve puzzle using divide and conquer method.”
There also is an example below.
a little weak this excuse. if a very specific procedure is required, the code can simply be in the description. if there are several solutions, these should always be allowed.
When you create an “in/out puzzle”, you can do only one solution for each test. When there are several solutions, the puzzle’s creator has to define how to choose between these solutions.
With this puzzle, it is well described.
therefore the puzzle has to be adjusted. just saying “solve it exactly like this” is pretty bad for a puzzle. it is simply a guide and has nothing to do with a puzzle.
either you make general statements and ask about the number of all possibilities, or you narrow down the space more.
updated statement :
“The goal of the puzzle is to apply the “divide and conquer” method in order to fill a square…”