islingr's blog

By islingr, 7 months ago, In English

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:


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.

The problems were set and tested by 33_arsenic_75, ajmeraraghav99, Azm1t, BladeRunner, islingr, MridulAhi, PROELECTRO444, sahilkumar_1, sai_kamal, and Surver.

Prize Distribution

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.


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!

Top 15
IITD Top 3

UPD4: ICPC-de-Tryst editorial has been released.

Announcement of ICPC-de-Tryst 2024
  • Vote: I like it
  • +115
  • Vote: I do not like it

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

Clashes with AGC :(

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

    Not much choice, had to clash with AGC or Asia-West :/

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

      all asia-west teams teams will be travelling on 31st anyways

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

        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

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

can you do it on 30th march?

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

Is there a mirror for Codemod, or maybe even just a way to view problems when they are released?

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

    We can post the problems online, we'll update the blog in time. Though we won't be accepting any online submissions.

»
7 months ago, # |
  Vote: I like it +35 Vote: I do not like it

As a contest co-ordinator of icpc-de-tryst, can surely say the problemset is fun and worth spending your 4 hours on :)

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

Virtual Mirror of math round CodeMod on Codeforces would be highly recommended. Please consider this.

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

Sorry, but I cannot register an account on Unstop?

»
7 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Contest Link?

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

Contest Link??

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

Is randomized solution intended for problem D ?

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

I was able to reduce K into a final summation, couldn't figure out how to calculate it, Sol for K?

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

    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.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Is there a deterministic solution for problem D?

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

    Yep!

    Here's a lemma, if you have a chain $$$C$$$ of students where you know that

    1. there is at least one honest student
    2. the previous student claimed that the next student is honest

    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.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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]

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        Algorithm
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +7 Vote: I do not like it

          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

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

            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.

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

              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

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

          I enjoyed solving this problem the most. Kudos to the setter. Thanks for the contest.

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

        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.

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

Can you make the solutions public?

»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

can you please increase the prizes for more top teams (like top 40), or if not prizes just some certificate of some kind

»
7 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Kudos to the problem setters, the set was very engaging and challenging at the same time,

Also any hints for I?

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

    Try to find the max possible value of y for each value of x from 0 to n

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve [problem:514988H] ?

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

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

    • if leaf, just compute and store answer at $$$l$$$.
    • $$$m = (l + r) / 2$$$
    • solve($$$m$$$, $$$r$$$, $$$T$$$)
    • compute linear transform $$$S$$$ such that $$$S(Z(X)) = T(P_{[m, r)}(x) Z(x))$$$.
    • solve($$$l$$$, $$$m$$$, $$$S$$$)

    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.

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

      For skill issue brute force with memoisation works

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

        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.

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

          just iterate over only those bitmask that you can actually reach

          https://pastebin.com/1EkHYTMh

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

            RIP, and we kept thinking during the whole contest that we are missing some non trivial observation.

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

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

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

            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?

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

              My rating doesn’t allow me to understand it.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
            Rev. 2   Vote: I like it +18 Vote: I do not like 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)}$$$

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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.

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

              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

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

                There can be a lot of them (in particular, you need to at least account for semiprimes).

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

            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.

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

      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.

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

        For "Weightiest Watermelon" soln by IceKnight1093

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

          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

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +21 Vote: I do not like it
      Skill Issue

      Following are my solutions as a tester for the other two problems. The intended (kevinsogo's) solutions might differ a bit.

      Inverse modular square sum
      Fiendish Five
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think the hardest part of Fiendish Five was just proving 4 is enough, the rest could be checked by code.

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

          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.

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

        For Inverse modular square sum, could you elaborate on how you're iterating over $$$x / lpf(x)$$$?

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

        Were u able to get a bound for the x/lpf(x) part?

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

        where can we find the intended kevinsogo sols ?

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

Can Anyone Pls tell why My submission Is getting TLE for problem F ? [submission:254370910]

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Use fast input output for C++, here.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I am using fast input output But still getting TLE.(I have used it in above submission)

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

        Instead of using endl, use "\n" to avoid flushing the buffer after each query.

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

Can anyone explain the solution of problem K (ab ba count)?

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

Why is this giving TLE for G : link.

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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.