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.

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 that`b = 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 integer`b`

such that`a * b = 1 (mod n)`

. This`b`

is just`1/a`

, i.e., you can divide by any number`a`

that shares no prime factors with`n`

, simply by multiplying with its inverse`b`

.

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ā¦ā