Hello Codeforces!
The Algorithms and Coding Club, IIT Delhi (ANCC) in collaboration with Tryst, IIT Delhi, will host the following three events and would like to invite you all for the same:
- Codemod in collaboration with MathSoc IITD, onsite on Friday March 29, 2024 at 14:00 IST
- Lockout Finals, onsite on Saturday March 30, 2024
- ICPC-de-Tryst, online on Sunday March 31, 2024 at 19:30 IST
ICPC-de-Tryst
ICPC-de-Tryst is an ICPC style team contest where you would be given 11 problems to the solve in the span of 4 hours, for teams of at most 3 members.
- Date & Time: Sunday March 31, 2024 at 19:30 IST
- Mode: Online
- Platform: Codeforces, Contest Link
- Registration Link
- Each participant is allowed to use their own computer, no 1PC per team rule
- Prizes: 2L INR total (1.8L for top 15 Indian teams and 20K for top 3 IITD teams)
The problems were set and tested by 33_arsenic_75, ajmeraraghav99, Azm1t, BladeRunner, islingr, MridulAhi, PROELECTRO444, sahilkumar_1, sai_kamal, and Surver.
Codemod
Organised in collaboration with MathSoc IITD, Codemod is a Project Euler-style individual contest where you would be given 6-7 challenging mathematical problems with an integer answer to solve in the span of 2 hours. You can optionally write programs in your favorite programming language to aid in computing the answers.
- Date & Time: Friday March 29, 2024 at 14:00 IST
- Mode: Offline
- Venue: LHC, IIT Delhi
- Registration Link
- The computer can only be used to code and compute.
- Prizes: 50K INR for top 10 onsite participants
Visit our website to know more about other events happening at Tryst!
UPD1: Problems from Codemod
UPD2: Contest link for ICPC-de-Tryst
UPD3: Congratulations to the winners!
UPD4: ICPC-de-Tryst editorial has been released.
Clashes with AGC :(
Not much choice, had to clash with AGC or Asia-West :/
all asia-west teams teams will be travelling on 31st anyways
but like icpc ends on 30th afternoon, and contest is on 31st night, so 1.5 days gap. I guess since their fest ends on 31st, keeping it on 31st is the optimal choice
can you do it on 30th march?
Is there a mirror for Codemod, or maybe even just a way to view problems when they are released?
We can post the problems online, we'll update the blog in time. Though we won't be accepting any online submissions.
As a contest co-ordinator of icpc-de-tryst, can surely say the problemset is fun and worth spending your 4 hours on :)
BladeRunner orz sir
Virtual Mirror of math round CodeMod on Codeforces would be highly recommended. Please consider this.
Sorry, but I cannot register an account on Unstop?
TRASH WEBSITE!
Contest Link?
Contest Link??
Is randomized solution intended for problem D ?
I was able to reduce K into a final summation, couldn't figure out how to calculate it, Sol for K?
View the input pairs as the edges of a graph $$$G$$$. Let $$$S$$$ be the set of characters in the string. We can do arbitrary swaps for characters in the same connected component in $$$G[S]$$$ (ie the subgraph of $$$G$$$ induced by $$$S$$$).
Now, $$$f_S(n)$$$ be the answer for strings of length $$$n$$$ which contain all the characters $$$S$$$ at least once. Answer is $$$\sum_{S \subseteq [k]} f_S(n)$$$.
We can get a recurrence for $$$f_S$$$ as follows. Let $$$v = \max(S)$$$, $$$T$$$ be the connected component of $$$v$$$ in $$$G[S]$$$. Then, $$$f_S(n) = \sum_{r = \lvert T\rvert}^n f_{S \setminus T}(n - r) \binom{n}{r} \binom{r - 1}{\lvert T\rvert - 1}$$$. By fixing $$$r$$$, the number of times characters in $$$T$$$ occur in the string, $$$\binom{n}{r}$$$ the ways to fix the positions of these characters and $$$\binom{r - 1}{\lvert T\rvert - 1}$$$ the ways of distributing the characters in $$$T$$$ in these positions (since we can freely swap characters in $$$T$$$ their position doesn't matter, and we get the term by stars and bars).
This gives a $$$O(2^k n^2)$$$ solution which should TLE. Finally note that if you define $$$Q_t(x) = \sum_{r \ge t} \binom{r - 1}{t - 1} \frac{x^r}{r!}$$$ and $$$F_S(x) = \sum_{n \ge 0} f_S(n) \frac{x^n}{n!}$$$. Then $$$F_S(x) = Q_{\lvert T\rvert}(x) F_{S \setminus T}(x)$$$. So you can do the transitions in $$$O(n \log n)$$$ by FFT giving a $$$O(2^k n \log n)$$$ solution.
Thanks
Is there a deterministic solution for problem D?
Yep!
Here's a lemma, if you have a chain $$$C$$$ of students where you know that
Then the last person in the chain has to be honest. Use this to create an algorithm taking $$$\le n$$$ queries to find a single honest student.
Now, once you have the honest student and the absolute value of every student's marks. Then just sort by decreasing absolute value and ask the honest student about everyone's marks, the first positive value must be the answer and you'll hit it in $$$(n + 1) / 2$$$ queries.
That's the idea I was thinking too.
But how do we find the absolute value of every student's marks and one honest student in N queries?
I thought I did the same thing, but I get WA if I remove the random shuffle. [submission:254343677]
Make a stack, iterate through the students
At the end of the process, the stack would be non-empty and the last student on the stack honest (prove it!).
No student has been queried more than once. Just query all the unqueried students using the honest student at the end.
Makes sense. My contest solution was similar, but instead of asking about a current student from the top of stack, I asked about the top of the stack from a current student.
But this stack idea is the intended solution of ARC 070: F — HonestOrUnkind
Yep, seen this problem before. That's how I got some of my mathematically inclined friends to do Atcoder problems. :P
This problem's setter was ajmeraraghav99 though.
Bruh....it is the same exact problem, and he copied it except he just added one extra trivial thing. Very disappointing. Now i know how there were so many solves on D
I enjoyed solving this problem the most. Kudos to the setter. Thanks for the contest.
In your solution, you're actually making $$$> n$$$ queries in the first half of the algorithm.
In this test, the liars always lie and the values are $$$1, 2, 3, -4, -5$$$. The queries are $$$2 \to 1, 3 \to 2, 4 \to 3, 3 \to 4, 5 \to 2, 2 \to 5$$$ and then again $$$2 \to 1$$$.
In your algo, you're asking the new student about the top of the stack (opposite happens in our algo) so the invariant that every thing gets queried at most once doesn't really hold.
Can you make the solutions public?
can you please increase the prizes for more top teams (like top 40), or if not prizes just some certificate of some kind
Kudos to the problem setters, the set was very engaging and challenging at the same time,
Also any hints for I?
Try to find the max possible value of y for each value of x from 0 to n
How to solve [problem:514988H] ?
Compute the sum instead of expected value. You do some math to get that for $$$v \neq 1$$$, the sum of scores is $$$(v-1)a_v \sum_{s = 1}^n f(s) \sum_{S \subseteq [v + 1, n]}^{\lvert S\rvert = s - 1} \prod_{u \in S} a_u$$$ where $$$f(s) = (s - 1)! (n - s - 1)!$$$.
Notice that the inner sum of products is $$$[x^{s - 1}] \prod_{i > v} (1 + a_ix)$$$. So if you define the linear transform $$$T$$$ mapping polynomials to numbers given by $$$T(x^{s - 1}) = f(s)$$$, the answer is $$$(v-1) a_v T(\prod_{i > v} (1 + a_ix))$$$.
We'll show how to compute $$$T(\prod_{i > v}(1 + a_ix))$$$ for all $$$v$$$ fast for a general linear transform. Naively, this is $$$O(n^2)$$$. We'll do D&C and compute it in $$$O(n \log^2 n)$$$.
Notice that the function $$$S$$$ given by $$$S(P(x)) = T(Q(x) P(x))$$$ (where $$$Q$$$ is a polynomial) is also a linear transform, boils down to a convolution, you can compute it in $$$O(n \log n)$$$.
Now you can D&C,
Define $$$P_{[l, r)}(x) = \prod_{i \in [l, r)}(1 + a_ix)$$$. solve($$$l$$$, $$$r$$$, $$$T$$$) computes $$$T(P_{[i, r)}(x))$$$ for all $$$i \in [l, r)$$$,
solve($$$l$$$, $$$r$$$, $$$T$$$):
I'll flesh out the details in the proper editorial.
rivalq, magga, Kira_1234 had the same idea but rather than D&C they sqrt decomped it, I had set the TL to let these solutions pass as well.
Shouldn't it be (v — 1) instead of v in the summation?
Yep had stuff 0-indexed in my code.
How to solve Skill Issue? Also, Fiendish Five and Modular Inverse Square Sum
For skill issue brute force with memoisation works
Can you please elaborate? All I could think of was a naive $$$O(2^n*n)$$$ bitmask dp, where we assign $$$s_i$$$ to $$$t_i$$$ in decreasing order of $$$s_i$$$ and store the set of $$$t_i$$$'s already assigned in the mask.
just iterate over only those bitmask that you can actually reach
https://pastebin.com/1EkHYTMh
RIP, and we kept thinking during the whole contest that we are missing some non trivial observation.
Like it or not, but that's the model solution for "Skill Issue".
Although there is a way to remove constant due to an unordered map by using 2 pointers, it was not required.
jtnydv25 had a proof on the bound of no of states.
- Using two pointers takes ~0.7s.
- Using a based map takes ~1.6s.
- Unordered map passes in ~8s.
For "Modular Inverse Square Sum", I don't know the exact details but it boils down to S(N) is always 0, N/2, N/3 or 2N/3. One can find which case it is based on powers of 2 and 3 in the prime factorisation.
Idk how to solve "Fiendish Five".
I don't know the exact details but it boils down to S(N) is always 0, N/2, N/3 or 2N/3. One can find which case it is based on powers of 2 and 3 in the prime factorisation.
How math?
My rating doesn’t allow me to understand it.Oh damn, I missed S(n)mod n which seems to be very important. The rest simply follows with inclusion exclusion, similar to what one would do for totient function, just with sum of squares.
S(n)= $$$n^2phi(n)/3 + nk(n)/6$$$
the first part is always divisible by n, the second part is 0,n/2,n/3,2n/3
however it is also dependenent on other primes, case n=15 is 5, n=21 is 0, is if n is not a multiply of 3 then s(n)=n/2 if n=2^k else 0, when n is divisble by 3, we have to check if n contains any prime that is 1 mod 3, if yes then 0 else if number of primes in factorisation of n is odd then 2n/3 else n/3.
$$$k(n)=\prod_{p \in prime;p|n}{(1-p)}$$$
I think $$$S[n]$$$ is a multiplicative function. We can evaluate $$$S[p^k]$$$, where $$$p$$$ is a prime. $$$S[p^k] = \frac{(2*p^{2k - 1} - 1) * (p - 1) * (p^k)}{6}$$$. But I don't know how to simplify it further. UPD := $$$S[n]$$$ is not multiplicative.
even after s(n), I guess just finding all good l is hard or if we can even enumerate them, seems intuitive that there should not be a lot of l that divide m! but hard to prove
There can be a lot of them (in particular, you need to at least account for semiprimes).
We also came up with the proof after the contest but the number of states was in some sum of C(a,b) terms so my thought was if any team had done it the problem in first four hours you would see a lot more solutions, something similar happened in the kanpur regional as well, one of the problems though hard to prove time complexity wise follows almost the brute force code implementation.
For the rest we had naive ideas, nothing concrete.
For modular square sum,S(n) was a sum of two drichlet functions
For Fendish five we proved that solution existed only if the sum was divisible by 5. The solution could be done within 6 moves. Checking became exponentially hard with number of moves, and would have required us to implement a linear eq solver so we didnt think it was intended or is worth trying given as we still hadn’t completed the already solved problems.
For the problem I guess you also upsolved a simple OESIS should have worked, I think that problem had contest bias and if even one team would have gotten in the first four than a lot more would have too. Same with Skill Issue, though one of the teams did do it in the last one hour.
For "Weightiest Watermelon" soln by IceKnight1093
Submission
We reached the f(n-1) part quickly however from there the best we could remember was n^3 for f(n-1) so in the interest of doing already solved problem we missed it. I think what actually this accounts for is the topic distribution among teammates and contest bias that no one has done it lets focus on already done problems. For eg in my team we distributed pnc and ds to me, so H was completely my responsibility, which again was easy to mess up given that the solver is always going to go back and forth between whether to think about the problem a little more or to implement the high ds implementation, even in our initial attempts I had a much complicated allowance to the structure of the graph, and then decided the constraints of the problem allow a lighter ds, so it is better to do that than fixing the complicated one
Assume $$$s$$$ and $$$t$$$ are sorted. Let $$$dp[k][mask]$$$ be the weighted sum over all matchings of $$${t_1, t_2, \ldots t_k}$$$, to $$$ { s_i: i \in mask } $$$, where you need to multiply by $$$\frac{1}{(t_j - s_i)!}$$$ for matching $$$t_j$$$ to $$$s_i$$$.
Now, what is the number of possible states for a given $$$k$$$? $$$\binom{n}{k}$$$ is an obvious upper bound. Another upperbound is $$$\binom{N + k - n}{k}$$$, where $$$N = 33$$$ is the number of available positions. (To see this, note that the number of states is maximized when $$$s_i = i$$$ for all $$$i$$$ and $$$t_i = N - n + i$$$ for all i). So, for a given $$$k$$$, the number of states is at most $$$\binom{\min(n, N + k - n)}{k} \leq \binom{\frac{N+k}{2}}{k}$$$. Over various $$$k$$$, this quantity is maximized at $$$k \approx N / \phi$$$, and hence the number of states for a given $$$k$$$ never exceed $$$\binom{24}{15} \approx 1.3 \times 10^6$$$
Although not required, you can get rid of the map based (high constant or log) factors by a two pointers-ish approach. More details can be seen in the code:
Code
Following are my solutions as a tester for the other two problems. The intended (kevinsogo's) solutions might differ a bit.
Let $$$U$$$ be the set of positive integers $$$< N$$$ , coprime to $$$N$$$. $$$S(N) = \sum_{u \in U} \frac{1}{u^2} = \sum_{v \in U} v^2 \pmod N $$$, as there is a one to one matching between elements and their inverses.
Now, we only want to sum over $$$v$$$, that have $$$gcd(v, N) = 1$$$. So, applying inclusion exclusion, we have:
Let $$$N = 2^{e_2} 3^{e_3} n$$$, where $$$n$$$ is coprime to $$$6$$$. Clearly, $$$S(N) = 0 \pmod n$$$. Also, for any $$$p \in { 2, 3}$$$, such that $$$e_p \neq 0$$$,
This is because, only the $$$Nd / 6$$$ term would matter, and $$$\sum_{d | N} d \mu(d) = \displaystyle \prod_{\text{prime } q \vert N} (1 - q)$$$.
Call a prime $$$q$$$ invalid if $$$q = 1 \pmod {3}$$$. If $$$N$$$ is a power of $$$2$$$, $$$s(N) = N/2 \pmod {N}$$$. Else, if $$$3 \nmid N$$$ or if an invalid prime divides $$$N$$$, then $$$S(N) = 0 \pmod {N}$$$. Otherwise, $$$ S(N) = \frac{N}{2} - \frac{N}{6} (-1)^{\omega(N)} \pmod N $$$.
So, once we fix the power of $$$3$$$ in $$$N$$$, we need to iterate over powers of all primes that are $$$2$$$ modulo $$$3$$$. The number of such numbers can be huge. However, we can iterate over $$$\frac{x}{lpf(x)}$$$, where $$$lpf(x)$$$ denotes the largest prime factor of $$$x$$$. This part is probably better explained in the code.
Code
Fiendish Five
Note that, the sum remains the same modulo 5. Since, we eventually want all numbers to be the same, we need that the initial sum is also divisible by 5. Let the numbers be $$$a_1, a_2, a_3, a_4, a_5$$$. Let $$$b_i = a_i - \sum_{j=1}^{5} a_i / 5$$$. Then, each operation is equivalent to adding $$$1$$$ to two indices and subtracting $$$1$$$ from two other indices. Hence, each operation can be represented by a column vector with one $$$0$$$, two $$$-1$$$'s and two $$$1$$$'s. There are $$$30$$$ such column vectors, but they exist in pairs since for each column vector $$$v$$$, $$$-v$$$ is also considered in these 30 vectors. Hence, we need to consider only $$$15$$$. Now, we need to select a subset of these $$$15$$$ columns, such that a given vector can be represented as an integer weighted sum of those. (Here, we allow negative weights as well, because again the negation of each vector is also a valid operation). There are two important observations:
It is always possible to achieve the objective in $$$4$$$ operations. Hint: At least $$$3$$$ of the $$$5$$$ numbers must have the same parity.
Any $$$3$$$ of the $$$15$$$ column vectors are linearly independent. Hence, if the answer is $$$< 4$$$, we can simply iterate over all subsets of size $$$\leq 3$$$ and find the unique solution corresponding to that subset if it exists, and see if that is integral. An optimization in this step is that we can preprocess the gaussian elimination for the corresponding matrices and store the sequence of row operations, and the final matrix in RRE form, and at the time of queries, just apply those operations on the target vector.
Code
I think the hardest part of Fiendish Five was just proving 4 is enough, the rest could be checked by code.
After upsolving Fiendish Five, an easy way to prove $$$4$$$ is enough, is to try some combinations of $$$4$$$ vectors, and try to find the inverse of the $$$4 \times 4$$$ matrix, where you remove the last element (it does not matter, as all entries in a vector sum to $$$0$$$). Once you find an inverse which is fully integer, that's a proof.
For Inverse modular square sum, could you elaborate on how you're iterating over $$$x / lpf(x)$$$?
Were u able to get a bound for the x/lpf(x) part?
where can we find the intended kevinsogo sols ?
Can Anyone Pls tell why My submission Is getting TLE for problem F ? [submission:254370910]
Use fast input output for C++, here.
I am using fast input output But still getting TLE.(I have used it in above submission)
Instead of using endl, use "\n" to avoid flushing the buffer after each query.
Thanks A lot! It Got accepted now.
Can anyone explain the solution of problem K (ab ba count)?
Why is this giving TLE for G : link.
I think for problem H, you guys inherently discovered reverse cdq. Although, I believe the initial coder to discover cdq also stumbled upon it in a similar fashion. The transformation with T, I guess is well known and is generally solved by $$$[x^n]H(x)*P_i(x)$$$, though to get the desired time complexity one needs to store the suffixes of the intermediate polynomials rather than storing complete polynomials.