brobat's blog

By brobat, history, 15 months ago, In English

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.

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

Banner.jpeg

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.

  • Vote: I like it
  • +65
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Will accomodation be provided for finalist teams?

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And also will the travel be reimbursed to any amount?

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by brobat (previous revision, new revision, compare).

»
14 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Reminder The contest starts soon. Remember to fill the form to be eligible for prizes!

»
14 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Cool problems. First time got TLE due to #define int long long in Bhawan Distance. Lesson learnt :)

»
14 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it +24 Vote: I do not like it

    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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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:

    $$$\frac{d}{dX} \sum_{i=1}^n (X-a_i)^2 = 2\sum_{i=1}^n (X-a_i) = 0$$$

    Solving for X, we get

    $$${X = \frac{1}{n} \sum_{i=1}^n a_i}$$$

    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

    $$$\sum_{i=1}^n (X'-a_i)^2 = \sum_{i=1}^n (X'-X+X-a_i)^2 = \sum_{i=1}^n (X-a_i)^2 + n(X-X')^2$$$

    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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do that sprinkler task?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

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

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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!

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it
»
14 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +24 Vote: I do not like it

How Positive Arrays?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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)

»
14 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Valid AP

Consider 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 Square

In 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