aryanc403's blog

ICPC India Chennai 2024 Stream
By aryanc403, 4 days 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

Update 3 — Editorial and Jury Solutions have been released on the same Google Drive. K is missing from the editorial (and probably will not be added).

Further, there are 3 posted challenges. You may try them.

  • In A ABC Stamp, suppose the stamp was $$$1, 2, ... M$$$ with the constraint of $$$M \le N$$$. Can you solve the problem of checking if a sequence is possible and constructing the set of operations? The constraints on $$$N$$$ remain $$$\le 2 \cdot 10^5$$$

  • In D Bin Packing, find a O(N^3) worst case complexity solution.

  • In F Easy Counting Problem, Solve the problem for $$$|M - N| \le 5000, N \le 10^7$$$

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

»
3 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Will there be any mirror contest?

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

Write your predictions for winner!

→ Reply
  • »
    »
    3 days 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
    • »
      »
      »
      37 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good to see a DandaDan fan here yo....

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

Editorial will hopefully be posted by tommorrow

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
3 days 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
  • »
    »
    3 days 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
»
3 days ago, # |
  Vote: I like it +43 Vote: I do not like it

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

→ Reply
»
3 days 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
  • »
    »
    25 hours ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Yeah i had participated in this contest too. Apologies for not catching it. We would have used the harder version then.

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

When will the official final rank list gonna be released ?

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

editorial and jury solutions have been released. There are also a few challenges for you. K is not present in the editorial.

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

For L, there's a simpler solution. Note that the k-th bit forms a pattern $$$111..000...111..$$$, where each window has size $$$2^k$$$, and the pattern starts from $$$2^k - 1 + L$$$. Now, to induce the pattern, you just need to do a prefix sum twice. The first one is $$$pref[i] += pref[i - 2^k]$$$ and the second is $$$pref[i] += pref[i - 1]$$$ Do this over all bits, and you have an $$$O(nlgn)$$$ solution.

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

    I have done it the exact same way in regional.

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

Can some red/yellow coder try to solve and help provide a solution for problem K?

→ Reply