Блог пользователя niyaznigmatul

Автор niyaznigmatul, 5 лет назад, По-русски

UPD: Выложены разбор и контест в тренировки Отборочный этап Олимпиады Университета Иннополис. Второй тур. 2019-2020

Всем привет.

Второй отборочный тур на Олимпиаду Университета Иннополис для школьников по информатике перенесен на 14 декабря в 16:00 по московскому времени.

Тур длится 5 часов, в нем традиционно пять задач. Участники, показавшие высокий результат в отборочном туре, будут приглашены на заключительный этап, который пройдет 22-23 февраля 2020 года на нескольких площадках. Во втором туре также могут поучаствовать уже приглашенные в заключительный этап: призеры заключительного этапа прошлого года и приглашенные с первого отборочного тура.

Олимпиада входит в перечень РСОШ как олимпиада первого уровня по информатике. В олимпиаде могут принимать участие только школьники. Все остальные смогут порешать задачи в Тренировках на Codeforces после окончания тура.

Сейчас идет пробный тур олимпиады, он продлится до вечера 13 декабря. Тур очень полезен для новых участников: вы сможете познакомиться с форматом задач олимпиады, с тестирующей системой, это полезно сделать, чтобы не тратить на это время во время самого отборочного тура. Будьте внимательны, тур проходит не на сайте Codeforces. Чтобы начать участвовать в пробном туре и чтобы участвовать в отборочном туре нужно заранее зарегистрироваться на сайте.

Первый отборочный тур, который прошел несколько недель назад, можно порешать в Тренировках на Codeforces: Отборочный этап Олимпиады Университета Иннополис. Первый тур. 2019-2020.

Задачи прошлых лет также можно порешать в тренировках. Будьте внимательны, некоторые старые тренировки загружены в формате ICPC (без баллов и подзадач):

  • Проголосовать: нравится
  • +125
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Is there any kind of editorial for First Qualification Round?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    There is one in Russian + source codes: link, but we didn't translate it into English.

    We will be glad if someone from the community translates some of the ideas into English.

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

It sounds kinda strange, but how the checker for problem 4 at the first round is made? I think it is harder task to solve..

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

I have submited in the last minute before the time has finished and you did not judge it sorry for my poor english but could you please check what's wrong ? My name is Besher Islambouley.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

How many contestants will qualify for the on-site contest?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

    One solution is to maintain set of possible sums, this is done by maintaining non-intersecting segments of sums, that is possible to get, initially only one segment $$$[0;0]$$$. After adding segment $$$[l;r]$$$, each segment of sums $$$[a;b]$$$ creates segment $$$[a + l; b + r]$$$, just merge intersecting ones. Observe, that if you sort segments of sums by $$$l$$$, then $$$1.4 \cdot l_i \le r_i$$$, $$$r_i < l_{i + 1}$$$. Therefore number of segments is at most $$$log_{1.4}(s)$$$. Another solution will be in tutorial, which is unfortunately in Russian. Idea is to divide segments into $$$2$$$ groups : $$$l_i > (1 - 1 / 1.4) \cdot s$$$ and others. Then from the first group you need at most $$$3$$$ segments, because if sum of $$$l_i$$$ of $$$3$$$ segments doesn't exceed $$$s$$$, then they're good set. Now consider only sets of at most $$$2$$$ segments from the first group. If those have sum $$$l_i$$$ at most $$$s$$$, then add some segments from first group until sum of $$$l_i$$$ is at least $$$s / 1.4$$$, or just all. You can notice, that it won't be more than $$$s$$$ at that point. So you need to pick $$$2$$$ segments with $$$l_1 + l_2 \le s$$$ and $$$r_1 + r_2$$$ being maximized, which is done by $$$2$$$ pointers.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you, the first solution is very nice! I didn't really get the second one at first, but now I think I got that one too. I think you wanted to write $$$l_i > (1-\frac{1}{1.4}) \cdot s$$$. Here's a description I wrote for myself to better understand the method:

      So basically we have 3 intervals $$$A=[0s;(1-\frac{1}{1.4})s]$$$, $$$B=[(1-\frac{1}{1.4})s;\frac{1}{1.4}s]$$$ and $$$C=[\frac{1}{1.4}s;s]$$$. If for some $$$l_i \in C$$$ we're done. Continuing with the second interval, because $$$1-\frac{1}{1.4}>\frac{1}{4}$$$, a solution with $$$4$$$ elements from $$$B$$$ cannot be valid, but also because $$$3 \cdot (1-\frac{1}{1.4}) > \frac{1}{1.4}$$$ if there's a solution with $$$3$$$ elements from $$$B$$$ the smallest $$$3$$$ must also form a solution. Thus we have three cases left, we either choose $$$2$$$, $$$1$$$ or $$$0$$$ elements from $$$B$$$. Here goes a handy claim that helps in all $$$3$$$ cases: let the sum of all left ends that lie in interval $$$A$$$ be $$$X$$$, if we choose some different elements from $$$B$$$ such that their sum $$$Y$$$ is smaller than $$$\frac{1}{1.4}s$$$, but $$$Y+X \geq \frac{1}{1.4}s$$$ then there is a solution, since if $$$Y+X \leq 1$$$ there is obviously one, but in the case $$$Y+X>1$$$ we can take out elements from $$$A$$$ until the sum will be smaller or equal than $$$X+Y$$$ and since all the elements we take out are $$$\leq 1-\frac{1}{1.4}$$$ we can't take out an element and then have a sum smaller than $$$\frac{1}{1.4}$$$ if before that the sum was greater than $$$1$$$. This claim immediately finishes the case when we examine the case when we take $$$0$$$ elements from $$$B$$$. If we take $$$1$$$ elements from $$$B$$$ we just loop over all the possibilities. If we take $$$2$$$ elements from $$$B$$$, we can use $$$2$$$ pointers as you mentioned.

      Did I understand correctly?

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve D for k=4 faster than expected $$$O(b^4)$$$ calls to sqrt?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Can you share your approach? Our approach does $$$O(b)$$$ sqrts on average.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      There are 2 observations:

      1) The prime gaps are $$$O(b)$$$ on average

      2) The difference between $$$\sqrt{n}$$$ and $$$\frac{p_1+p_2}{2} \cdot \frac{q_1+q_2}{2}$$$ is $$$O(b^2)$$$ on average.

      So we can loop over the prime gaps divided by $$$2$$$(let's call then $$$a$$$ and $$$b$$$) and $$$\frac{p_1+p_2}{2} \cdot \frac{q_1+q_2}{2}$$$(let's call it $$$e$$$). Let's call $$$\frac{p_1+p_2}{2}$$$ $$$c$$$ and $$$\frac{q_1+q_2}{2}$$$ $$$d$$$. Then $$$n=(c^2-a^2)(d^2-b^2)=c^2d^2-a^2d^2-b^2c^2+a^2b^2=e^2+a^2b^2-a^2d^2-b^2c^2$$$, so we can easily get $$$a^2d^2+b^2c^2$$$.

      $$$(a^2d^2+b^2c^2)^2=(a^2d^2-b^2c^2)^2+4abcd=(a^2d^2-b^2c^2)^2+4abe$$$ so we can easily get $$$a^2d^2-b^2c^2$$$ by square rooting and then finally get $$$a^2d^2$$$ and $$$b^2c^2$$$. Since we know $$$a$$$ and $$$b$$$ this allows us to easily get the values of $$$c$$$ and $$$d$$$, so now the factors are $$$c-a$$$, $$$c+a$$$, $$$d-b$$$ and $$$d+b$$$.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        An interesting solution! That's cool that you don't need any complicated factoring algorithms or knowledge for it, too bad it takes too long. Sadly, I don't see an easy way to improve it...

        Our solution is based on Fermat's factorization. Basically, whenever you have $$$n = rs$$$ and $$$|r - s|$$$ is small (to be precise, it must be $$$O(n^{\frac 14})$$$), you can find those $$$r$$$ and $$$s$$$ quickly. In our case, $$$n = p_1 p_2 q_1 q_2$$$ has two factorizations into close pairs: $$$p_1 q_2 \cdot p_2 q_1$$$ and $$$p_1 q_1 \cdot p_2 q_2$$$. Thus, we use Fermat's to find $$$p_1 q_1$$$, $$$p_1 q_2$$$, $$$p_2 q_1$$$, $$$p_2 q_2$$$, and then take pairwise GCDs to find primes.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Когда добавят второй отбор в тренировки? Очень жду)