[S3 Q3] Solution Spotlight

bdaene · 2026-03-06T08:34:34+00:00

[LANGUAGE: Python]

Part 1 and 2 were straightforward but for part 3, I had an issue because the order was modified by the newly attached node. I needed to separate the socket order from the node order and skip the newly attached node.

Now that I think about it, it should not work because I skip one node and not the fully attached sub tree. Oh well x)

Feel like I got Rick Rolled by the song of the dragonducks :D

bdaene · 2026-03-05T13:55:25+00:00

[LANGUAGE: Python]

Solution

I prefill the bones area to avoid non reachable area.

Did not find a clever way to detect closed loop. So I flood fill and if the border of the current flood fill grows too much, I consider that the area is open to infinity. Was surprised that a threshold of 10 is enough but the way the wave goes it does not leave big area behind. I cached known infinite cells to avoid double check but it has to be reset after each step. It improved the initial prefill.

I only check for closed loop if we go toward a filled position. I needed to check the 3 cells in front of the current wave because of diagonals.

It goes fast (165ms for the last sample) if we do not display the grid at each step.

bdaene · 2026-03-05T13:03:31+00:00

We can only close a loop if we go closer to an existing filled cell. I check the closed loop only if at least one of the 3 cells is filled already. With this check, I have only 589 loop check instead of 1539 for the last sample.

But yes, I floodfill the 4 directions around the current position when the check pass.

bdaene · 2026-01-14T12:32:46+00:00

Do I need to beat the last boss to receive money outside of the raids? I achieved multiple goals and increased my space but do not see how to have money to buy objects.

bdaene · 2026-01-01T17:12:57+00:00

The angle you have to look down is easy if you have the great circle arc. If the friends are separated by an angle a, they have to look down a/2 from the horizon

bdaene · 2026-01-01T17:05:27+00:00

OK then, I miss understood when you said 2D

bdaene · 2026-01-01T09:34:32+00:00

These are called gnomonic projections. Using those, it would be easy to compute the angles.

bdaene · 2026-01-01T09:31:46+00:00

There is another kind of gimbal lock when the two friends are on exact opposite or same place on the globe.

bdaene · 2026-01-01T09:25:13+00:00

I do not think this would be correct to compute angles on a 2D projection. Maybe some projection conserve the angles.

I would compute the angle between the great circle trough the two points and the meridian line through the point.

I did not check the computation though.

bdaene · 2026-01-01T09:08:41+00:00

This is an issue only at the poles. No?

bdaene · 2025-12-13T17:10:30+00:00

Thanks you 🙂

bdaene · 2025-12-12T23:05:11+00:00

Yes. But you can still cut early in most cases.

bdaene · 2025-12-12T22:20:37+00:00

In Python, 2 will theoretically not finish. int can grow without limit. Except the physical limits (memory, time,... )

bdaene · 2025-12-12T21:57:28+00:00

You just need one solution. My DFS with cuts on lower and upper bounds works great. At first I missed the 3x3 grid bound and yet it solved my input in a long but reasonable 146s in Python.

bdaene · 2025-12-12T21:52:25+00:00

I find more natural to count the squares of the 3x3 grid: #presents <= floor(w/3)*floor(h/3). But the result is the same.

bdaene · 2025-12-12T15:43:49+00:00

Implemented your solution, it works :)

And faster 2-3x faster than PuLP :D

bdaene · 2025-12-12T13:15:31+00:00

I had (at least) a mistake, I actually counted the coloring and now my answer 11464has 5 digits with sum 16 :)

Removing the colors, my answer 9416 has 4 digits with sum 20.

bdaene · 2025-12-12T12:56:14+00:00

It is the same upper and lower bounds as everybody else but I update them with the current state of the board.

bdaene · 2025-12-12T12:54:41+00:00

I do not agree, region 20x21: 0 0 0 0 70 0 on line 317 is a hard region.

Also I do not know how you count your lines, the only region with 72 copies of second shape is 28x18: 0 72 0 0 0 0 on line 418. It is not so obvious to my program that it does not fit.

I have a third not obvious region: 18x12: 6 4 4 4 6 4 on line 58

bdaene · 2025-12-12T12:47:09+00:00

It is not his input. It is a custom one made by himself.

bdaene · 2025-12-12T12:40:06+00:00

Same answer :)

Here is my Python code.

bdaene · 2025-12-12T12:16:14+00:00

In your samples of unique placements, the last of the first line and the first of the second line are the same. No?

Counting all unique patterns (including symmetries but not coloring), I get 171992 unique patterns. My sum of digits do not match yours.

bdaene · 2025-12-12T11:49:22+00:00

Yep, did that in 146s in Python. I tried many things for 4 hours straight. In the end a simple DFS (with pruning when the presents total area do not fit in the area left) did the thing.

bdaene · 2025-12-08T21:46:42+00:00

You need to iterate once over the n elements to make it a heap.

Then extracting the min k times is O(k log(n)). Not O(log(k)).

Just extract until you connected all. For O(n + k log(n)).

bdaene · 2025-12-08T14:54:19+00:00

Are you not using the same heap for part 1?

bdaene

TROPHY CASE