Hi!

We are happy to invite you to participate in **International Coding League, 2023**, conducted by the students of BITS Pilani as the flagship event of our technical fest, APOGEE.

**Contest Link:**https://www.codechef.com/INCL2023**Registration Form:**https://forms.gle/andzSCu7A38jZFkVA**Date:**10th March, 2023 — 08:00PM IST (***UPD: Time has been updated**)

The first round of this contest would be hosted on Codechef, and would be in **teams of 1 or 2**. The cash prize for this round is **INR 10000 (5k + 3k + 2k)**. To be eligible for these prizes (and to participate in the next round), teams must fill the registration form.

The top 25 teams in this round would qualify to the second round, which would be held **offline at BITS Pilani, Pilani campus** on **1st April, 2023**. The cash prize for this round is **INR 30000 (15k + 10k + 5k)**.

The problem setters and testers are: mithilshah23, utk, AAK, sketkar, Jash_Ranipa, shashankag and brobat.

We thank CodeChef for providing us the platform to host our contest.

We hope you enjoy the contest, and happy coding! :)

**UPD 1:** Due to clash with the Reply Code challenge, we have postponed the contest by exactly 24 hours, to 10th March, 2023 — 08:00PM IST.

It clashes with Reply code challenge, any chance of rescheduling?

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

Will accomodation be provided for finalist teams?

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

And also will the travel be reimbursed to any amount?

Really, Sorry but it won't be possible to reimburse the travel expenses. However, we would be making bus arrangements to some Indian cities .

Cool thanks a lot!

Auto comment: topic has been updated by brobat (previous revision, new revision, compare).ReminderThe contest starts soon. Remember to fill the form to be eligible for prizes!Cool problems. First time got TLE due to #define int long long in Bhawan Distance. Lesson learnt :)

Amazing contest, good problemset. Can anyone tell the solution for Minimum Squared Sum and Bhawan's Distance. Couldn't seem to figure them out.

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++ ImplementationHow to do that sprinkler task?

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).

Can you share some resouces for learning flows?I want to upsolve this problem.

when can I submit for practice, or will the problems be not available for practice at all?

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!Bhawan Distance

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

another similar problem

a very nice problem set really liked the problem.bhawan distance

How Positive Arrays?

An integer is called

Repunitif it only consists of ones in its decimal representation. For example, $$$1$$$, $$$11$$$, $$$111$$$, ... areRepunit.It is easy to see that an integer is

positiveif and only ifthe integer can be represented as the sum of at most $$$9$$$Repunitnumbers. Thus, an integer $$$K$$$ can be written as the sum of at most $$$n$$$positivenumbers if and only if $$$K$$$ can be written as the sum of at most $$$9n$$$Repunitnumbers.A

Repunitnumber 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

In minimise operations , I tried to fix every index from 0 to n-1 of string and check if every other index before and after is right or not , If not right then cnt++ and minimum count should be the ans . I got tle though , something which can be changed to have it passed ?

Code...

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)

Valid APConsider the sequence

A, a1, a2, a3, a4 .... an, B. For the sequence to be a valid arithmetic progression, the difference between consecutive elements should be constant; say d.a1 — A = d, a2 — a1 =d, a3 — a2 = d .... B — an = d. Adding all these equations we get

a1 — A + a2 — a1 + a3 — a2 ...B — an= (n+1)d.

Simplifying the equation gives (n+1) * (d) = B-A. For an integral solution to exist (B-A) should be divisible by n+1.

C++ Implementation

Make SquareIn order to form a square from the given sticks, the length of all the sticks should be made equal. Since it is possible to only reduce the lengths of the sticks, it would be optimum to make all the sticks equal to the smallest stick in length. It can be argued that this would result in the minimum total wastage.

C++ implementation

Minimise Operations:The circular sequence is a sequence of consecutive characters which begin with any english alphabet. There are only 26 possibilities for the first character. For all the 26 possibilities the cost of converting the string to a circular sequence can be calculated. The final answer would be the minimum cost among all the 26 possibilities.

Time Complexity: O(26 * n)

C++ Implementation