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
- Public ranklist Link — Ranklist
- Date & Time — 04 January 2025, Saturday, 9:00 IST (Tentative start time)
- Problem statements — Statements
- Stream channels — CodeChef and aryanc403 channel
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$$$
Will there be any mirror contest?
Write your predictions for winner!
Top 3 Predictions:
Good to see a DandaDan fan here yo....
Editorial will hopefully be posted by tommorrow
will the problems be available for practice (on Codechef?) anytime soon?
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:
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:
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.
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 :)
aryanc403 ranklist list seems to be broken, can someone please post 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
Yeah i had participated in this contest too. Apologies for not catching it. We would have used the harder version then.
When will the official final rank list gonna be released ?
editorial and jury solutions have been released. There are also a few challenges for you. K is not present in the editorial.
When will the ranklist be out? Waiting for 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.
I have done it the exact same way in regional.
Can some red/yellow coder try to solve and help provide a solution for problem K?