We have decided to postpone the contest to 10th March,2023 — 08:00PM IST :)

Yes, accomodation would be provided to all the finalist teams.

And also will the travel be reimbursed to any amount?

Minimum squared sum: Notice that it's optimal to take X for a prefix and Y for a suffix. Iterate overall i such that X covers prefix of i. For some prefix, the cost for X is: summation((X — a[j])**2), just expand the summation and differentiate wrt to X, you'll get optimal X is (summation of A)/(i+1). Similarly for the suffix. (Also be careful of the N=1 edge case, which cost me around 1e9+7 penalty)

Bhawan distance: Suppose after adding some nodes, current diameter is P--Q, and current node is cur. Either the diameter stays the same, or becomes P--cur or Q--cur. We can find these distances using LCA

For Bhawan Distance: Consider a and b to be the nodes, whose distance is the maximum among all nodes. Now on adding a node c, the max dist will be max(dist(a,b), dist(a,c), dist(b,c)). This can be found using lca. dist(a,b) = dist(a)+dist(b)-dist(lca(a,b)) lca can be found in logN using Binary Lifting.

Some references:
https://codeforces.com/blog/entry/101271?#comment-899854 https://cses.fi/problemset/task/1135
I used above combinations to derive the final solution.

For the problem of finding the minimum squared sum, consider the following two arguments:

1.) To find an $$$X$$$ such that $$$\sum_{i=1}^n (X-a_i)^2$$$ is minimized, $$$X = \text{mean}$$$ is the optimal choice. To see this, differentiate the equation with respect to $$$X$$$ and set the derivative to zero:

Solving for X, we get

If we want $X$ to be an integer, taking the closest integer to $$$X$$$ will work. To prove this, suppose $$$X$$$ is the mean and $$${X'}$$$ is any other integer. Then we have

2.) Suppose you get some $X$ and $$$Y$$$, and let's say $$${X < Y}$$$. If for some $$$a_i$$$, $$$Y$$$ gives the minimum squared value, then for all $$${a_j > a_i}$$$, $$$Y$$$ will also give the minimum squared value. Similarly, if for some $$$a_i$$$, $$$X$$$ gives the minimum squared value, then for all $$$a_j < a_i$$$, $$$X$$$ will also give the minimum squared value. Hence, there exists an index $$$I$$$ in the sorted array such that for $$$1 \leq i < I$$$, $$$X$$$ is optimal, and for $$$I \leq i \leq n$$$, $$$Y$$$ is optimal. You can now just iterate on this index (on the sorted array), find $$$X$$$ as the closest integer to the mean of $$$[1..I]$$$ elements, and find $$$Y$$$ as the closest integer to the mean of $$$[I+1..n]$$$ elements. Use prefix sums to find $$$\sum_{i=1}^{I} (X-a_i)^2$$$ and $$$\sum_{i=I+1}^n (Y-a_i)^2$$$.

C++ Implementation

You can model the problem as a graph, where each sprinkler is represented by a node. Two nodes are connected by an edge if they overlap. Additionally make two new nodes, for the top of the field and the bottom of the field, and connect them with every sprinkler that overlaps with the top or bottom edge, respectively.

Now it can be solved as a flow problem, with top and bottom nodes as source/sink. We simply need to find the minimum cut of this graph. It can be done with any standard flow algorithm (my solution with Dinic's passes in < 10 ms).

I'm not sure how to move the problems to practice section, I'll have to ask Codechef about it. I'll update over here as soon as they're available (might take a few hours).

UPD: They've been added to practice section now!

https://codeforces.com/contest/379/problem/F

another similar problem

An integer is called Repunit if it only consists of ones in its decimal representation. For example, $$$1$$$, $$$11$$$, $$$111$$$, ... are Repunit.

It is easy to see that an integer is positive if and only if the integer can be represented as the sum of at most $$$9$$$ Repunit numbers. Thus, an integer $$$K$$$ can be written as the sum of at most $$$n$$$ positive numbers if and only if $$$K$$$ can be written as the sum of at most $$$9n$$$ Repunit numbers.

A Repunit number can be written of the form $$$(10^{r} − 1)/9$$$ using a non-negative integer $$$r$$$. Suppose that $$$-$$$

$$$K = \sum^{9n}_{i=1} (10^{r_i}-1)/9$$$

This is equivalent to $$$-$$$

$$$9K+9n= \sum_{i=1}^{9n} 10^{r_i}$$$

In order to check if such $$$r_{1}, . . . , r_{9n}$$$ exist, we need to check if the sum of digits of the decimal representation of $$$9K + 9n$$$ is at most $$$9n$$$.

Let $$$L$$$ be the number of digits of $$$K$$$. We can prove that the answer of the problem is at most $$$L$$$ (always choose the greatest integer of the form $$$i$$$, $$$i9$$$, $$$i99$$$, $$$i999$$$, ... ($$$1\leq i\leq9$$$) greedily and subtract it from $$$K$$$).

So, we need to find the smallest value of $$$n$$$ such that the sum of digits of the decimal representation of $$$9K + 9n$$$ is at most $$$9n$$$. This can be done using binary search in $$$O(L\cdot logL)$$$.

Task: https://atcoder.jp/contests/agc011/tasks/agc011_e

Editorial: https://img.atcoder.jp/agc011/editorial.pdf

Instead of fixing indexes, try to fix the characters occuring at the first position. When you are fixing the indexes your solution is resulting in an O(N^2) time complexity. Since there are only 26 possible characters you can reduce the complexity of your code from O(N^2) to O(26*N)