aryanc403's blog

ICPC India Chennai 2024 Stream
By aryanc403, 47 hours ago, In English

Hi everyone,

The third Indian ICPC Chennai onsite regional round will be held tomorrow in Chennai.

We plan to host a stream covering the round. The stream links will be posted shortly. The problems will be posted in this blog when the contest starts. The editorial will be posted after the contest ends.

Hope you enjoy the contest!

Contest Details

Update 1 — Stream links CodeChef and aryanc403

Update 2 — Statements have been released on the Google Drive

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

»
33 hours ago, # |
  Vote: I like it +8 Vote: I do not like it

Will there be any mirror contest?

→ Reply
»
33 hours ago, # |
  Vote: I like it +8 Vote: I do not like it

Write your predictions for winner!

→ Reply
  • »
    »
    33 hours ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Top 3 Predictions:

    1. on_the_spectrum
    2. Ice shard
    3. hehe i do cp
    → Reply
»
29 hours ago, # |
  Vote: I like it +19 Vote: I do not like it

Editorial will hopefully be posted by tommorrow

→ Reply
  • »
    »
    20 hours ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    will the problems be available for practice (on Codechef?) anytime soon?

    → Reply
»
22 hours ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

For F, we were able to solve the case when $$$M \ge N$$$ in contest. The approach is as follows:

let $$$dp[i][j]$$$ denote the number of arrays of length $$$i$$$ with total deletions $$$j$$$.

The transition will be as follows:

$$$ dp[i][j]=dp[i-1][j-1]*j+dp[i-1][j]*(M-1-j) $$$

This dp can be calculated in $$$O(N^2)$$$, but we can optimize it as follows:

Let $$$A[i]=\sum_{j=0}^{N}dp[i][j]*j$$$ and $$$B[i]=\sum_{j=0}^{N}dp[i][j]$$$, The transition for these states will be as follows:

$$$ A[i]=(M+1)*A[i-1]+B[i-1]\\ B[i]=M*B[i-1]\\ $$$

You can calculate this in $$$O(N)$$$.

We ended up focusing on K in the last 30 mins and didn't pursue it further for the other case, Thanks for the problemset!!! it had some unique problems.

→ Reply
  • »
    »
    20 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    there is a expected value argument for a neat combinatorical solution for M >= N.

    Let prob[i] = probability i gets deleted.

    i will get deleted if and only if it lies in [i — d, i] where d is number of deleted elements in prefix till i, so the probability is (d + 1) / M

    we can write a direct transition, prob[i] = (1 + sum(prob[j], j < i)) / M. I am really surprised by the amount of people who missed this idea.

    After this, the problem becomes much more tractable for M < N case as well. Note that for indices i <= M, the above probability calculation is correct.

    For indices i > M, it is not correct because the interval [i — d, i] is not fully within [1, M]. The subtracted length of the interval to account for the excess portion beyond M is min(d + 1, i — M). Since i — M is guaranteed to be small, the subtracted length is nearly always i — M except for when d is even smaller.

    We can now do your dp state with dp[i][j] denoting the number of array with j deletions in the prefix of i, and only store states j <= N — M, solving the problem in O(N (N — M))

    It is even solvable in more optimal complexities but I will leave that for now :)

    → Reply
»
20 hours ago, # |
  Vote: I like it +35 Vote: I do not like it

aryanc403 ranklist list seems to be broken, can someone please post it?

→ Reply
»
19 hours ago, # |
  Vote: I like it +9 Vote: I do not like it

The contest was interesting. Although I would like to point out one thing :

Problem A : ABC Stamp

Is an easier version of an old Atcoder problem also named "Stamp" XD.

This problem gave 2 input string one is the string to be constructed and other is the stamp string which was given by default as "ABC" in Chennai regionals.

The only difference was that in regionals we also had to print the order of operations which can simply be done by creating a vector and pushing the start index whenever we explore another stamp. (2 extra lines of code).

Link to problem: https://atcoder.jp/contests/abc329/tasks/abc329_e

→ Reply