How to solve day 2 problem 4?

Idk, but the first query is probably $$$(b, b), (b, -b)$$$, do you have a solution for $$$w=3$$$?

If you have a point with a maximum $$$x$$$ as a candidate, you can query $$$(x+d,y)$$$. Delete this candidate, and ban all distances $$$d$$$ between this query point and candidates.

if you find $$$d$$$ in the distances you can delete that candidate and the distances to the query points.

For full points, choose the smallest $$$d$$$ that is not banned and check for which candidate $$$(x,y)$$$ distance $$$d$$$ is unique for one of the points $$$(x+d,y), (x-d,y), (x,y-d), (x,y+d)$$$ which are inside the box.

You will always find it since $$$d\times k = O(k^5) \lt 2\times10^8$$$

What are some key points/ concept one must know to tackle Day1, P1, in general how can it be solved for N points, it is really hard since the trade-off between choosing a good radii or moving some distance with a bad radii.

I like the problem, but I haven't competed in the open contest.

Yes, you are wrong :) I think this problem looks very fun and I take it over almost any DS problem :p

Can you provide hints for day1 P1?

Imagine the sequence backward: it starts from $$$N$$$ and it "spreads out", in the form of $$$N - 1$$$ or $$$x, y$$$ such that $$$xy = N$$$. Let $$$DP(S)$$$ be the minimum cost to create a sequence that contains the set $$$S$$$. Transitions are: Decrement one element, or divide one element into two smaller ones. Complexity estimation is tough, but using unordered_map makes it pass.

Let $$$DP[i]$$$ be the minimum time to leave the shelter $$$i$$$, given that you intend to avoid periodical damage from there. $$$DP[i] = min(DP[j] + \lceil (x[i] - x[j]) /p \rceil (p + d))$$$ plus something.

If we can replace the fractional part to $$$\lfloor x[i] / p \rfloor - \lfloor x[j] / p \rfloor$$$, then the problem is easy. But If $$$x[j] \% p \lt x[i] \% p$$$ you have an error term of $$$1$$$. Therefore, those cases should be done separately.

To do this, you can maintain an RMQ with key $$$x[i] \% p$$$. If the queried part has a smaller modulo, add an error term, otherwise just do it normally. Remember to do coordinate compression over $$$x[i] \% p$$$.

an alternate solution with a less clean implemenation but a more obvious dp definiton than ko osaga's :

define Dp[i][j] = minimum time to reach the shelter i at time t, such that t % p = j

then, there are 2 types of transitions :

1) Dp[i][(j + x[i] — x[i-1])%p] = Dp[i][j] + damage taken in interim

2) dp[i][j] = min(dp[i][j], dp[i][(j-1}%p] + 1) (because you can wait before leaving a shelter)

This gives an easy n * p solution.

To improve it, you note that the 2nd kind of transition is just a range set on dp[x] — x, and the first kind of transition is range add (ill leave you to figure out the details).

Then, you just store the dimension of p in a segment tree with range set and range add, and do n * log p updates

For full, use dynamic segment tree

At https://boi23.kattis.com/contests/boi23day1open and https://boi23.kattis.com/contests/boi23day2open.

Sorted sequence always better than unsorted

Are you sure your problem isn't this?

If that doesn't work, the problems should be uploaded on CSES (hopefully) in a couple of weeks.