Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @VilBoub,validated by @jujurocking,@EricMoret and @Cr3aHal0.
If you have any issues, feel free to ping them.
Nice puzzle!
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ā¦
1 Like
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.
5 Likes
Iām thinking about something, itās not about the puzzle ā¦ but the puzzle shows that (2^n)Ā²-1 is always multiple of 3.
EDIT
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.
3 Likes
(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.
4 Likes
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 thatb = c (mod n/gcd(a, n)). This can be proven using the definitions of congruence mod n and GCD. - If
gcd(a, n) = 1, then there exists an integerbsuch thata * b = 1 (mod n). Thisbis just1/a, i.e., you can divide by any numberathat shares no prime factors withn, simply by multiplying with its inverseb.
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ā¦ā