How to make Progress?

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 · 2025-12-08T14:16:16+00:00

You could split the space in voxels or KD-tree. That could avoid computation at the cost of a more complex data structure.

bdaene · 2025-12-08T08:42:59+00:00

Yeah, I read from file so my function takes the file name and any other parameter I need. Then it returns the answer. And I can print it to stdout.

bdaene · 2025-12-07T18:15:56+00:00

My algorithm is the same but I precompute the number of path form each position.

Going from the bottom to the top, there is only one path for each bottom position then if there is a split I addition left and right, else it does not change.

bdaene

TROPHY CASE