Rox's blog

By Rox, 2 years ago, translation, In English

Hello!

Currently, the qualification phase of Yandex Cup in the “Algorithm” track is taking place.
Qualification takes place in two formats: sprint and marathon.
Both competitions will end on Monday, November 7, 2022 at 23:59 (MSK).

As the author of one of the tasks, I invite everyone to participate.

Information about other Yandex Cup tracks can be found on the website.

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

As a tester, I invite you all to participate in the competition! :)

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What's the difference between sprint and marathon in Yandex Cup context, I couldn't find info on site

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sprint: you choose when to start and then you have 120 minutes to solve 6 algorithmic problems.
    Marathon: you have all the time until the end of the competition to solve one optimization problem.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And what the difference between them will be in final?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        There is no difference for the final round this year. Final will be short contest (from 120 till 180 minutes), so there are just two ways to qualify.

        I hope once Yandex Cup will have two separated algorithmic track as it was several years ago in Yandex Algorithm.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          And how marathon round will conduct? 5 hours for solving one problem? Or 3 days as Irunner challenge?

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Is there any T-shirts for finalists? :)

»
2 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I have several questions for the final round:

  1. What time is it going to be?
  2. What is the duration?
  3. Is it going to have flexible timer (like the qual round) as well?

The website seems to be lacking information.

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

    If you go back to the website now and log in, you will be able to click a button to confirm your attendance for the final round. After doing so, you get a button that brings you to the competition page which has the time and duration listed. Hope this helps!

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Right. I can access the competition page and it answers all my three questions above. Thank you! Take my upvote.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Wow. Problem A from hell in today's Final Round for me… Tried 2 super-convoluted DP approaches, and ultimately couldn't make it work. That was an unexpected level of complexity after solving 4 Qual problems. Any slight hints for A?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Greedy :)

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +24 Vote: I do not like it

    Problem A. Max and the erudite competition

    For solving this problem you should think as a coach. You can start from something simple.

    hint #1: simple start

    My C++ solution

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can we do the same strategy in strongest to weakest order for our team for winning stage? I think it will also give maximum wins possible but not sure about number of draws.

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

    Alternate approach cause I kept messing up my greedy lol:

    Spoiler
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Will there be an editorial? I want B and C. Thanks.

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

    C: Fix N mod 3 (let's call it r) and binary search on N. For each prime factor of A, calculate how many times p^a is a factor of N!!! for each a >= 1 and add them up to get the total exponent of p in N!!!.

    This can be done by counting the number of solutions to p^a | (3k + r). If p is 3, then we need r = 0 and k is a multiple of p^(a-1). If p is not 3, then the solutions will be k = p^a * anything + i, where i is whichever of (-r)/3, (-r + p^a) / 3, or (-r + 2p^a) / 3 is an integer.

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Will there be an awards ceremony? Also, will the problems be available for upsolving?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Open upsolving please.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Upsolving is opened here. Letters for problems are shifted by 6 problems from the qualification round.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

»
2 years ago, # |
Rev. 2   Vote: I like it +48 Vote: I do not like it

What's the intended time complexity for F? I managed to pass $$$O(N^{5/3})$$$ but it took quite a bit of constant optimization.

  • »
    »
    2 years ago, # ^ |
    Rev. 4   Vote: I like it +40 Vote: I do not like it

    I will assume that $$$n = q$$$, expected complexity is $$$O(n\sqrt{n})$$$, but TL wasn't strict.

    Let's replace $$$r$$$ by $$$\frac{r}{k}$$$ and name value that we need to calculate as $$$F(r, d)$$$.

    It's easy to calculate $$$F(r, d)$$$ from $$$F(r - 1, d)$$$, main trick is that we are able to calculate $$$F(r, d)$$$ from $$$F(r, d - 1), \ldots, F(r, d - k + 1)$$$.

    Do to this, let's notice that:

    $$$\binom{x}{d}=\sum^{i=k}_{i=0} \binom{x - k}{d - i}\binom{k}{i}$$$

    It's basically Vandermonde's identity.

    Let's sum both parts for $$$x$$$ divisible by $$$k$$$ and not greater than $$$(r + 1) \cdot k$$$, we will get:

    $$$\binom{(r + 1)\cdot k}{d} = \sum^{i=k}_{i=1} F(r, d - i)\binom{k}{i}$$$

    (I moved part with $$$i = 0$$$, because evething except $$$\binom{(r + 1)\cdot k}{d}$$$ will cancel out).

    From here, we can find $$$F(r, d - 1)$$$, if we know $$$F(r, d - 2), \ldots, F(r, d - k)$$$.

    Let's go back to original problem.

    We will also assume that $$$k \le \sqrt{n}$$$, otherwise we can calculate answer for each query in $$$O(\frac{n}{k})$$$ with total complexity $$$O(\frac{n^2}{k})$$$.

    To solve the problem, let's fix some value of $$$B$$$ and calculate all values of the form $$$F(i \cdot B, x)$$$ for $$$x \le n$$$.

    To do this, let's calculate $$$F(i \cdot B, x)$$$ for $$$x < k - 1$$$, we can easily do it in $$$O(\frac{n}{k} \cdot k) = O(n)$$$ for all $$$i$$$.

    Then, for each $$$i$$$ we can find the remaining values in $$$O(nk)$$$(recovering $$$F(i\cdot B, d)$$$ from $$$F(i \cdot B, d - 1), \ldots F(i \cdot B, d - k + 1)$$$), so in total this part takes:

    $$$O(nk \cdot \frac{n}{kB}) = O(\frac{n^2}{B})$$$.

    Then, if we have the query $$$r, d$$$, let's just find largest $$$i$$$ such that $$$i \cdot B \le r$$$ and calculate answer from $$$F(i \cdot B, d)$$$ in $$$O(B)$$$. So, total complexity for queries will be $$$O(nB)$$$. Choosing $$$B = \sqrt{n}$$$ gives the desired complexity.

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

      Cool, the implementation is very short.

      Where did you get $$$O(\frac{n}{kB}\cdot k)$$$ from? I know how to do it in $$$O(k^2)$$$ per $$$i$$$ using the formula you provided (for a total of $$$O(\frac{n}{kB}\cdot k^2)$$$).

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

        Sorry, it was wrong, I think it's easier just to do it naively for every fixed value of $$$x$$$ resulting in $$$O(\frac{n}{k}\cdot {k}) = O(n)$$$ (your way is faster, but of course it doesn't change complexity).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    another passed solution that runs in time complexity $$$\mathcal{O}(n \sqrt{q \log n / k})$$$, where $$$n = \max(r)$$$. also took a bit of constant optimization on it.

    let $$$T$$$ be the block size, and $$$F_u(x) = \sum_{i = 1}^{u T}(1 + x)^{i k}$$$. After preparing the first $$$n$$$ factorials and their inverse, we iterate for each $$$u = 0, 1, \ldots, \lfloor n / k / T \rfloor$$$ and process queries with $$$u k T \leq r < (u + 1) k T$$$ using $$$[x^d] F_u(x)$$$ and at most $$$T$$$ extra binomial coefficients, so the total complexity will be $$$\mathcal{O}(n + n^2 \log n / k / T + q T)$$$, which has a minimal value when $$$T = n \sqrt{\log n / k / q}$$$.