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

Автор antontrygubO_o, 4 года назад, перевод, По-русски

Всем привет!

ozon

Мы рады пригласить вас на общий рейтинговый раунд “Ozon Tech Challenge 2020”, который состоится во 03.03.2020 17:35 (Московское время).

Этот раунд проводится по инициативе и при поддержке компании Ozon.

Ozon — один из ведущих игроков e-commerce, tech компания, которая активно развивает IT-подразделение. Ozon предоставляет своим покупателям более 2,5 млн. товарных наименований в 24 категориях, а еще в компании самая большая Golang команда в России, собственная WMS система управления фулфилментами, полностью написанная командой Ozon, 250 млн. строк логов в день, собирающихся на сайте и в мобильном приложении Ozon. Эксперты Ozon выступают на ведущих профильных конференциях GopherCon, Heisenbug, GoWayFest, GolangConf, а также на площадке компании проводятся митапы для IT сообщества.

Компания проявляет большой интерес к развитию сообщества разработчиков — для школьников работает школа Ozon Academy, для аудитории старше работает программа стажировок Ozon Tech Camp и программа обучения Ozon Masters.

Участникам будет предложено 2 часа 15 минут на решение 8 задач. Разбалловка будет объявлена ближе к началу раунда.

Задачи раунда были придуманы AkiLotus, Ari, Kuroni, zscoder, xuanquang1999, и antontrygubO_o

Мы хотели бы поблагодарить:

Спасибо компании Ozon за подарки участникам:

  • 10 лучших участников получат стильные фирменные рюкзаки и футболки раунда;
  • 11-20 участники получат компактные переносные зарядные устройства на 10000 mAh и фирменные футболки раунда;
  • 21-60 участники будут отмечены фирменными футболками раунда;
  • еще 30 футболок будут разыграны среди остальных участников, кто решил хотя бы две задачи, случайным образом.

Надеемся, каждый найдет для себя интересную задачу. Всем успешного раунда и повышения в рейтинге!

Удачи!

UPD1:

Разбалловка:

500 — 1000 — 1250 — 1750 — 2000 — 2500 — 3250 — 4000

UPD2: Разбор

UPD3: Поздравляем победителей!

  1. tourist
  2. maroonrk
  3. VivaciousAubergine
  4. ksun48
  5. Endagorion
  6. Benq
  7. gisp_zjz
  8. neal
  9. Um_nik
  10. yasugongshang

Информация о призах будет немного позже.

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

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

Is anybody going to talk about the "no subtasks" tag? :))

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

AC round #2

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

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

Finally prizes

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

No subtasks

No subtasks

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

![ ]()

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

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

In my opinion, a person who has a better rating should have a better chance of winning a prize! (For 30 T-shirts) This is fairer!

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

Will all sponsored rounds be combined? :(

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

    How to make round with prizes not combined?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -106 Проголосовать: не нравится

      Prizes only for div1, or for top30 of div1 and top2 of div2.

      And I didn't know what there will be prizes in all sponsored rounds.

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

        Only for Div1 sounds unfair and the round becomes just the usual round for majority of participants.

        If you make prizes for Div2, Div1 people are likely to create fake accounts.

        Sponsored rounds usually have prizes or are elections to some onsite competition, in which case it's also reasonable to make round combined.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится -70 Проголосовать: не нравится

          Only for Div1 sounds unfair

          Why? Making qualification rounds before most important (third) online round of Google Code Jam is also unfair?

          the round becomes just the usual round for majority of participants

          that's a plus :)

          If you make prizes for Div2, Div1 people are likely to create fake accounts.

          top2 div2 isn't much easier than top30 div1

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

            I don't know of this happens in reality, but when round is combined it makes sense for organising company to promote the competition on their own channels. If div2 is without prices it makes much less sense for them because newly registered users can't actually win

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

Official drink of the contest

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

Solve two problems! That's so great for me, maybe I will get my first T-shirt in these rounds.

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

.

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

Are there any previous Ozon Tech Challenge contests held on Codeforces?

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

what's the score distribution?

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

Can I participate in this contest? I don't know the full process. Anybody help me plzz.

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

.

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

A lot of problem setter and tester including 300iq.I think this contest will be interesting.

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

Sorry, but is any of authors or testers working in Ozon?

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

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

.

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

Ozon Ozone O 3 :)

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

Why some users appear with it's real name, cities and in Black?

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

I wish every round is combined

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

TFW you can't submit a solution because "You have submitted exactly the same code before", list of submissions is empty, and mirrors are not working, nice

// And it isn't a joke :(

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

Хотел пожаловаться на то, что не могу отправить решение:

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

I dislike this contest!

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

опять Тригуб

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

Me after solving A, B and waiting for the contest end to see if I win a T-shirt or no :

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

farewell, rating

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

    There is another contest tomorrow , you should be able to make it back.

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

    turns out, i disappointed the cf rating formula enough with my initial 4 rounds that I'm still getting rating even with poor performance:(

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

Was randomized solution supposed in F?

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

    Probably. I don't see any other way especially because it can be costly to even factor everything on the input.

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

      I have a deterministic solution for F — answer is always less then N + 1 (since we can always make everything even in at most N moves). Then it means we can only change smallest element d to (d — N, d + N). We can make a sieve upto 10^6 to find all primes in factorization of all numbers in this range, and then proceed with classic algorithm for each of those primes. I couldn't see what's the upper bound on number of primes like that, but I assume it's pretty small :P

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

        What if every element in array is big prime number and also elements in array are pairwise different? Do you proceed n times?

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

          I factorize all elements in range (d — n, d+n) for one element of the array (in my case minimum), so this test should not be a problem

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

        I just tried this solution, but n could be 2*10^5 and there're 17,986 prime numbers between 1~200,000. since we need O(n) time to obtain the sum of move counts for such prime number, it seems like 17,986 * 2*10^5(n) cause TLE. Do you have any idea about this?

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

          Yeah, my best improvement is saving global answer and terminating gcd check as soon as my partial answer is bigger. I think I can unpack my solution, so take it with a grain of salt :P

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

            So it's something like $$$O(N^2/\log)$$$ with constant optimisations?

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

              Probably yes, but I couldn't create a test where it would behave super badly. The "break when answer is bigger" check is pretty good in stopping almost all cases.

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

                Yeah, that complexity is already pretty good for many $$$O(N\log^2)$$$ problems if the constant factor is good. I'd rather not bet on it in-contest though.

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

      EDIT: This is wrong You can factor every number in O(nlogn) if you use a sieve like this:

          /**
           * Return an array of primes up to and including N. Takes only O(N) time!
           * Also generates an array of the minimum factor for every number
           * from 1 to N, which can be used to find all factors of any number up to N.
           */
          private static List<Integer> primeSieve(int n) {
              List<Integer> primes = new ArrayList<>();
              // minFact[i] contains the minimum prime factor of i.
              int[] minFact = new int[n + 1];
              for (int i = 2; i <= n; i++) {
                  if (minFact[i] == 0) {
                      primes.add(i);
                      minFact[i] = i;
                  }
                  // Find multiples of i where primes[j] is the minimum prime factor. This loop will go exactly once for each
                  // composite number. How it works: given a number i with prime factorization p1*...*pn, where p1<=...<=pn,
                  // we say that, for each prime p <= p1, the number i*p is composite with minimum prime factor p.
                  // Why this gets to every number exactly once: the number p1*...*pn will be generated only by p2*...*pn.
                  // That's because all of it's prime factors need to be higher than it.
                  for (int j = 0; j < primes.size() && primes.get(j) <= minFact[i] && i * primes.get(j) <= n; ++j) {
                      minFact[i * primes.get(j)] = primes.get(j);
                  }
              }
              return primes;
          }
      
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        But $$$a_i$$$ is up to $$$10^{12}$$$, so it will work too long

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

    Yes, choose any two element x, y, get all prime factor of gcd(x-1,y-1),gcd(x-1,y),..., gcd(x+1,y+1). Then try each factor. Each turn, you might get the correct answer with probability 1/4.

    Upd: choose any element x, get all prime factor of x-1,x,x+1. Then try each factor. Each turn, you might get the correct answer with probability 1/2.

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

    I don't know, but at least I solved with randomized solution.

    My Randomized Solution

    1. When $$$gcd = 2$$$, the number of operation must be less than or equal to $$$N$$$.
    2. Let $$$t_i$$$ be the number of operation that made for $$$i$$$-th element of array. It means: $$$t_i = |a_i - b_i|$$$ when $$$a_i$$$ is initial array and $$$b_i$$$ is final good array. You can prove easily, that in at least $$$\frac{N}{2}$$$ element, $$$t_i \leq 1$$$.
    3. Repeat 30 times as follows:

    • Choose random index $$$i$$$ from $$$1 \leq i \leq N$$$.
    • Let $$$t_{-1}$$$ be the set of prime factor of $$$a_i - 1$$$.
    • Let $$$t_{0}$$$ be the set of prime factor of $$$a_i$$$.
    • Let $$$t_{1}$$$ be the set of prime factor of $$$a_i + 1$$$.
    • Let $$$T$$$ be the union of $$$t_{-1}, t_{0}, t_{1}$$$. For all value $$$v \in T$$$, check the minimum cost when $$$gcd = v$$$ with complexity $$$O(N)$$$.

    Total Complexity is $$$30 \times O(\sqrt{a_i} + N)$$$. It fails with at most $$$2^{-30} \approx 0.0000000931322$$$% probability.

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

The gap from A to F is pretty good, but G and H are too hard..

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

FaIr aNd BaLaNcEd cOnTeSt!

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

It was a tough game, but it was great!

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

How to solve D ?

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

    Hint: Consider any $$$2$$$ leaves of the tree $$$u$$$ and $$$v$$$. Say $$$lca(u, v) = w$$$. Observe that $$$w \in $$${$$$u, v$$$} if and only if $$$w$$$ is the root.

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

How the heck is F solved? I passed pretests with what I presume is a nasty wrong solution, though I don't think I'm capable of generating tests that break it. Is there anything clean for that problem?

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

    We can always make gcd=2 by using <= n operations, so let's use only < n operations. Let's say we applied operation on i c[i] times in optimal answer, then at least for n / 2 indices c[i] <= 1(otherwise (n/2) * 2 >= n). So just pick some index i and try to prime divisors of a[i] — 1, a[i] and a[i] + 1. Not sure if it's good enough to fit into TLE though.

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

How to Solve E?

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

    I think you can construct the answer. Maximum possible number of triples is achieved in sequences like x, 2x, 3x, 4x, ..., kx, and you can calculate how many triples you can get for each k. If m > this number for n, the answer is -1. Otherwise you take the biggest number k less or equal to n, such that m is bigger than the maximum number of triples possible for this k. The first part of the answer would be 1, 2, 3, ..., k. Then you can add just one number: something like 2*k — 2*(how many more triples you need to get m in total), and you satisfy condition for m. If there are spare numbers left (n — k — 1), you can add a sequence of type (big number) * x — 1, which does not produce any more triples.

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

Great problems! What's the logic behind E?

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

how to solved D ??

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

    For every query, pick 2 from the current graph having degree 1. If the LCA is equal to any one of the 2 nodes you queried for, it is the root! Else remove these 2 nodes from the graph and repeat the same process.

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

Nice contest! I hope, i will get a T-Shirt ;)

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

In case I win a random T-shirt.

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

I don't think it's allowed to send portable chargers? (lithium batteries)

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

    You can ship it on flights, given they satisfy the maximum mAh criteria. And I guess 10000 mAh is pretty much fine.

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

      That's not true. Lithium batteries are only allowed to be hand carried in passenger planes or shipped in cargo planes. Since most mail services make use of passenger planes, they outright ban lithium batteries. Even if you use carriers like DHL you will need special approval.

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

    Tell that to bootleg Chinese sellers on EBay.

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

How to solve C?

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

    If a[i] % m = a[j] % m for some i < j, then answer is 0. Otherwise there are <= m numbers, so you can calculate answer in O(N^2).

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

Is there a deterministic solution for F ?

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

If anyone's interested, the solution to F is described here.

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

Another bloody lesson on CF Round: rand() only generate [0,65536) on codeforces......

I got 6 wa and debugged for 20mins...Now I only hope that I can pass the system test...

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

    The real lesson would've been to not have this covered by pretests.

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

      Kinda tough to do that without keeping $$$N$$$ small in pretests.

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

      We decided to be nice, it's a bit less unfun to fail in pretests compared to failing on a hack :)

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

        Bro, Thank you for being nice and preparing this excellent round~

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

      Very good point! I am very grateful now.

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

      Just realized I haven't touched pretests of F. Completely forgot what I've done last year with hacking rand() lul, good thing someone else covered that.

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

This round was one of the most interesting rounds I've participated!! Sooooo Amazing!!!!!

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

I think it's better to give a warning in the blog if the contest contains any interactive problem(s).

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

    I guess there is no rule as such.
    Usually the problem setters are kind enough to let us know before-hand so that anyone who is new to such problems, will take a look at it. :)

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

      Yeah. Actually that's why I am talking about this. Anyone who is not familiar with such problems may learn before participating and solve more problems.

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

        Why only interactives? Just make the problemsetters announce all the problem topics so those who aren't familiar with them can learn them beforehand.

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

"**The resulting string does not have to be empty**." due to this statement i got 2WA + late submission in B problem anyone faced same issue

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

    oh wow so i will get WA since i just deleted all the possible brackets...... (()) would fail for me :/

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

      actually i just realized i did solve it correctly since the number of deleted brackets dont matter , it is only the number of operations that matter.

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

    I did the same mistake. My answer should fail on cases like () but got an AC instead

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

    You should be grateful that the pretests covered it.

    I FSTed. :(

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

Всё ясно, автору 0 лет

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

Does D involves finding longest diameter of the tree, then query end points of that dia, if output of the interactor is one of the 2 ends, return that as that root. If not, then if interactor's output is a vertex not lying on the longest dia, return that vertex. Else (if lca returned is on the dia (but not the ends)), then check recursively the same process in the subtrees of that lca (by removing connection of lca and its neighbors that are not on the dia)?

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

    It is more simple. Query two leaves, if response if one of those leaves, thats ans. Else remove those two leaves. Repeat.

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

    this approach will fail if all the nodes are connected to the same node

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

      in that case you can output the last input we receive from interactor since that is the only vertex which will be left as we have removed all other vertex by removing 2 vertex n/2 times .

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

    If the output of interactor, say w, is not one of the 2 ends(say n1 and n2) then you remove the edges connecting w to n1 and n2. You find the longest diameter again and repeat the process.

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

    I did something related to diameter of the tree.

    You may notice you want to remove a lot of nodes, which are not candidates to be the root in each query, until you are left with one, which is done (fitting exactly in queries) by the approach in the editorial, too.

    I, instead, went on querying the ends of the diameter, and removing all nodes (and of course all other nodes in "subtrees" of the diameter nodes, except the LCA returned in the query, because all of them except the "w" returned in the query, are no longer candidates to be the root as all of them have atleast one vertex "above" them), and continued to do so until I have one node remaining.

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

Systest when, fellow Stalker?

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

How to solve G?

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

Tests are strong (at least not shitty) this time, yes?

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

    Pretty sure making strong tests for F is a difficult problem in and of itself. My shitty solution passed pretests, we'll see about tests.

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

      I also have something what I'm not sure about in E.

      Also was close in G, we'll see in upsolving.

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

      Well, your solution definitely can't get WA because the last part of your code checks all large divisors of (some number)$$$\pm n$$$ and every number will be modified at most $$$n$$$ times. The only thing I'm not 100% sure of is whether it's fast enough.

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

        Yes, in worst case scenarios it can check ridiculous amounts of primes (millions) and it checks each linearly. However, lots of optimizations and early stops make it very fast on most data.

        P.S.

        Accepted in 561ms. I am not capable of generating tests against it even if I strongly believe it's slow. Can't prove any good complexity either, but oh well, it passed.

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

          There are at most (78498 (number of primes <= 1e6) + 2 * n) primes in the factorization of numbers in [x-n, x+n] and that's a kinda loose upper bound anyway so it's not millions.

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

Hacks for C:

Hack Test Case

You can prove that when $$$M < N$$$ the answer is $$$0$$$. But, even if your source code assumes that when $$$M \leq N$$$ the answer is $$$0$$$, you will get pretest passed. (There is some hack cases like above)

For me, first, my source code assumed that when $$$M \leq N$$$ the answer is $$$0$$$, and then I resubmitted. So I was able to notice hack case earlier, but there is no such source code in my room :(

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

    I checked that for all N < M the answer is 0 but how to formally prove it ?

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

      There exist i,j i!=j such that a[i]%m==a[j]%m, hence (a[i]-a[j])==0 (mod m).

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

      If a and b have the same result after modulo m, |a — b| mod m = 0. Then it's pigeonhole principle.

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

      I guess you meant M < N. According to the pigeonhole principle, among >M numbers there will be at least two (call them a_i and a_j) with the same remainder upon division on M. Since there will be |a_i — a_j| or |a_j — a_i| in the product, the entire product will be divisible by M.

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

        Does that mean we assume all numbers given will be distinct?

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

          Well, if some two are not distinct, that still have the same remainder. Moreover, then the product will be 0 automatically.

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

            Ok now I get it that for n > m even if we all are distinct there will be 2 that have same modulo by m. Thanks for your help

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

    After staring at C for a good 20 mins, I had an epiphany. Pigeonhole principle! I smirked like the ninja in https://www.youtube.com/watch?v=pKO9UjSeLew

    And then wrote m>=n in my pigeonhole condition instead of m>n

    FML

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

Nice problems with clear statements.

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

TFW B is harder than F >:/

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

Weak.Pretests on C

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

Prepare for Polish Mafia in uphacking ;_;

mnbvmar, show them what you think about them.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Hiiii Can you check this submission. Is this agreed in contest? https://codeforces.com/contest/1305/submission/72343610

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

      As idea looks just like a solution from editorial. Of course, it looks like full of bugs, but it's typical obfuscation, which can be found in many places in CF (and is against rules!). Ofc I'm talking about #define int long long.

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

    Please hack 72364530 72364506 72364194 72364859 . They all are same with a change in constant.

    72364859 and 72364466 are exact same but one got WA on tc93. P̶r̶o̶b̶a̶b̶l̶y̶ ̶a̶ ̶h̶a̶c̶k̶.̶ Dori added them ~20 mins before start of round.
    These are my ugly brute forces which survived system tests during testing. Idea was to run sieve and check all primes up to a constant (5e7 in the present case.) and then randomly pick a no and try to factorise it up to primes 1e4 then assume leftover prime and gcd and check it.
    The intent was to break solutions which doesn't check factors $$$a_i+1$$$ or $$$a_i-1$$$ .

    pajenegod has some similar solns which sieve up to 4e8 (using some superfast sieve.) and runs under 2s.

    One plan to break them was to increase $$$a_i$$$ up to $$$10^{14}$$$ but we didn't want to force factorisation in O(primes up to $$$10^7$$$) instead of O($$$\sqrt a_i$$$)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      You know that there is no rating limit for uphacking, yes? You can also try.

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

        We tried hacking them during testing of the round.

        Btw only div1 users can up hack.

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

Неужели было так сложно добавить максимальный тест в претесты к задаче C?

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

shouldnt n^2 solution for C fail?

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

    yes it would, however a (n <= 1000)^2 solution wouldn't, all answers for n > 1000 are always 0's. this is why you only calculate the answer for (n <= m).

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

For anyone interested in detailed analysis of problem C -- Here you go!

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

А можно призы доставлять доставкой Озона, а не почтой россии? У меня даже премиум есть.

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

I had the proper idea for F, but my deterministic solution of course got TLE, but didn't realize I can do a randomized solution. I have never solved a contest problem with randomization till date. Can someone help me how to get started with such randomized solutions, so that it gets intuitive when I see a question in future to use a randomized solution with high probability. :)

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

Does anything faster than $$$O(N^2)$$$ exist for C if the modulus was large?

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

    from what i've seen the absolute difference instead of a normal difference ruins most possibilities of coming up with mathematic solution. ++ for an answer.

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

      If you sort the numbers in decreasing order then you can remove the absolute.

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

    I can only present a polylog solution, which should run way slower than the $$$O(n^2)$$$ solution in practice. After sorting the array we can get rid of the absolute value part. Then use divide and conquer, split into two subproblems of size $$$n$$$, then we need to multiply something which can be done using multipoint evaluation of a polynomial, which is a typical problem that can be solved using D&C and FFT in $$$O(n\log^2{n})$$$, therefore the overall complexity is $$$O(n\log^3{n})$$$.

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

      By understanding how multipoint evaluation works, you can make it in $$$O(n \log^2 n)$$$. Assume for simplicity that $$$n$$$ is a power of two. In fact, for each $$$i$$$, we want to find the remainder of the division of $$$(x - a_{i+1})(x - a_{i+2})\dots(x - a_n)$$$ by $$$(x - a_i)$$$.

      For each interval $$$[L, R]$$$ of the form $$$[2^i \cdot j, 2^{i} \cdot (j+1) - 1]$$$, compute $$$(x - a_L) \dots (x - a_R)$$$. Call it $$$P_{[L, R]}$$$. (This is in fact needed in multipoint evaluation as well.)

      Now, a recursive function $$$f(L, R)$$$ will compute all the results for $$$i \in [L, R]$$$. This function will receive $$$(x - a_{R+1})(x - a_{R+2})\dots(x - a_n) \mod{P_{[L, R]}} =: Q$$$. If $$$L=R$$$, we're done. Otherwise, let $$$m := \left\lceil \frac{L+R}{2} \right\rceil$$$ and notice we can call $$$f(L, m-1)$$$ with $$$(Q \cdot P_{[m, R]} \mod{P_{[L, m-1]}})$$$, and $$$f(m, R)$$$ with $$$(Q \mod{P_{[m, R]}})$$$. Each multiplication and modulo operation can be done in $$$(R - L) \log (R - L)$$$ time, hence $$$O(n \log^2 n)$$$ total runtime.


      Edit: notice that the "normal" multipoint evaluation does almost exactly the same stuff, only that $$$f(m, R)$$$ is called with $$$(Q \cdot P_{[L, m-1]} \mod{P_{[m, R]}})$$$; so that in each step, $$$f(L, R)$$$ will receive $$$\prod_{i \not\in [L, R]} (x - a_i) \mod{P_{[L, R]}}$$$.

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

      Can you provide links to some similar questions?

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

I don't understand why my sub idleness

Plz help me

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

    I think that you need to send a new line when you print the answer.

    cout << '!' << " " << ans;
    cout.flush();
    

    vs

    cout << '!' << " " << ans << "\n";
    cout.flush();
    
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I have found out why it was idleness, when i used

      cout << flush;

      its no longer idleness. Btw tks bro.

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

Comment on problem C: Next time, when $$$O(nm)$$$ solutions didn't suppose to pass the TL and $$$n=200000$$$, choose your $$$m$$$ like $$$3000$$$ or something!

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

Hello, my solution for "B" got an Runtime Error on Test 24, where the String was all "(" (length;1000). The code gives correct answer on this case ("0", that is) on my editor, as well as some online editors too, when checked upon.

Can someone please, check out and tell where it could have got a Runtime Error, because I don't think it (the code) can give Runtime Error.

Thanking you with anticipation!

Solution Link: https://codeforces.com/contest/1305/submission/72323474

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

    ll i=0, j=close.size()-1; This will init j to huge value if close is empty.

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

      Got your point,

      But actually j's value is saved "-1" through this statement, in most of the editors, as I told, above.

      Then, why does it assign a large value of "j" on the Editor and Compiler of CodeForces? Please explain the reason, if you know!

      Thanks!

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

        The vector.size() returns size_t, which is unsigned.

        However, if it is -1 the code still is undefined, since j is used as an index, and -1 is not allowed there, too.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится -6 Проголосовать: не нравится

          The "while" loop condition is there for not allowing the neg. value of "j".

          j>=0

          This condition will stop that, anyways.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 3   Проголосовать: нравится -16 Проголосовать: не нравится

          Now, the code works, when I write the equations as follows:

          ll j=close.size();

          j--;

          Then, it works!

          Why is it happening like that?

          MikeMirzayanov

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

          Also, when I write "int", instead of "ll", it works!

          int i=0, j=close.size()-1;

          Can someone explain, why?

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

            The type of .size() is size_t which is an unsigned integer type, so if the size is 0 and you subtract it by one, it will overflow (it may become a large integer). Therefore, you should not subtract the size without type casting.

            If you use ll j = close.size();j--; or int j = close.size();j--;, close.size() will be cast to ll or int, which is a signed integer, before you subtract it, so it works.

            If you use ll j = close.size() - 1, close.size() will be subtracted before it is cast, so it is wrong. But if you use int instead of ll, it "may" (since overflowing is an undefined behavior) be correct. size_t is a 4-bytes integer type and so is int. The binary result of subtracting an unsigned integer is as same as a signed integer type with the same size commonly, so the binary value of (size_t)0 - 1 is as same as (int)-1. (The value is the maximum value of a 4-bytes unsigned integer which is $$$2^{32}-1$$$, but the maximum value of a signed 4-bytes integer is $$$2^{31}-1$$$, so it will overflow to -1 when you cast it to int.)

            ll is not like that. Although the value of (size_t)0 - 1 is -1 when we regard it as an int, it cannot be cast correctly to ll.

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

              Got the point.

              Thank you so much, for such a nice explanation!

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

when we get the result of random t-shirt winner

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

    I guess they first have to eliminate those hundreds of smart people who, after solving A and B, started modifying their codes to send from other accounts, instead of solving C.

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters and update them again!

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

    Excuse me, I don't know how to report the cheating behavior, but it seems like the User Qingyu98821, who got the second place in Contest Codeforces Round 624 (Div. 3), is suspected of making his code obfuscated.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -31 Проголосовать: не нравится

    In problem B of todays contest it is clearly mention ed in the question that after applying the operations the string does not have the empty size. So naturally for test cases in which string is Simple string any answer is not possible.Kindly check the question..

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

      The resulting string does not have to be empty.

      "Does not have to be empty" meant it could be empty, or non-empty, will not affect the verdict.

      Mind your English, please. And if you were unsure about the statement, what prevented you from asking?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -52 Проголосовать: не нравится

        the resulting string does not have to be empty means that after the operations the remaining string must be of non-zero size.

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

          Actually not. That'd be "the string cannot be empty" or "the string must not be empty".

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

How to get test cases for D?

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

    How is it possible?

    Time: 15 ms, memory: 148 KB

    Verdict: OK

    Input

    6 4

    1 4

    4 2

    5 3

    6 3

    2 3

    Participant's output

    3

    Jury's answer

    1

    Checker comment

    ok Passed.

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

      when the prize is T-shirt Its possible

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

      Interactive test data is quite different from normal problems.

      In this problem specifically, the "input" showed in the submission details is equivalent to the hack format described in the statement, and the "output" here is number of queries used (actually this part is quite a placeholder, since I implemented the process of judging the answer to be in the interactor, not the checker).

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

I solved 2 problems in the whole contest. I was relieved by this . My submission was accepted so I started thinking about next problem. Now I only got 1 correct submission . What is this ???? Who should I report to for this incident? :(

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

    Looks like your solution on B failed on system test.

    To make it clear, ịn a contest your solution will be judged by a smaller set of tests (called "pretests"). After contest time, it'd be judged again.

    We tried our best to make the pretests strong, but it's certain that not every case can be covered. :(

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

    Btw your error was on this line

    while(open[o]<close[o] && o<close.size() && o<open.size())
    

    You should have checked o<close.size() && o<open.size() before doing open[o]<close[o]. That would have given you AC, 72370968.

    One good thing about making this mistake is that you know now how to avoid it in the future!

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

I am just wondering what tourist does with all those T-shirts and iPads that keep piling up...

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

Im so sad because i miss the last one second to submit my D answer.And after the contest ,i checked it's right...

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

Great round, really nice non-standard problems.

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

When t-shirt winner will be announced?

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

this contest broke my record: the previous greatest rating change(with the maximum absolute value) is +131 and now it's -145. QWQ

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

My rank go up about 200 after the system tests...

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

When the t-shirt winners will be announced?

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

Why Rollback, any valid reason please?

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

I guess removal of fake account done by team codeforces. Waiting for tshirt winner announcement

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

And the winners of t-shirts are (congratulations!):

List place Contest Rank Name
1 1305 1 tourist
2 1305 2 maroonrk
3 1305 3 VivaciousAubergine
4 1305 4 ksun48
5 1305 5 Endagorion
6 1305 6 Benq
7 1305 7 gisp_zjz
8 1305 8 neal
9 1305 9 Um_nik
10 1305 10 yasugongshang
11 1305 11 izban
12 1305 12 boboniu
13 1305 13 mnbvmar
14 1305 14 yhx-12243
15 1305 15 NoLongerRed
16 1305 16 I_love_Tanya_Romanova
17 1305 17 yosupo
18 1305 18 Radewoosh
19 1305 19 Marcin_smu
20 1305 20 E869120
21 1305 21 vepifanov
22 1305 22 BigBag
23 1305 23 icecuber
24 1305 24 ohweonfire
25 1305 25 cuizhuyefei
26 1305 26 Martin53
27 1305 27 Golovanov399
28 1305 28 qazswedx2
29 1305 29 receed
30 1305 30 ashmelev
31 1305 31 Kostroma
32 1305 32 ainta
33 1305 33 Petr
34 1305 34 SkyDec
35 1305 35 Hazyknight
36 1305 36 DCXDCX
37 1305 37 KAN
38 1305 38 cwise
39 1305 39 chemthan
40 1305 40 Quang
41 1305 41 Reyna
42 1305 42 isaf27
43 1305 43 molamola.
44 1305 44 fastmath
45 1305 45 wrinx
46 1305 46 Elegia
47 1305 47 jijiang
48 1305 48 orz
49 1305 49 poisonous
50 1305 50 cerberus97
51 1305 51 mnaeraxr
52 1305 52 AndreySergunin
53 1305 53 Maksim1744
54 1305 54 endless-chase
55 1305 55 wucstdio
56 1305 56 voidmax
57 1305 57 Noam527
58 1305 58 Alex_2oo8
59 1305 59 yashChandnani
60 1305 60 darnley
114 1305 114 Marckess
215 1305 215 olphe
386 1305 386 idxcalcal
475 1305 475 HCPS42
579 1305 579 CarrotCarrot
765 1305 764 nicoing
866 1305 866 Wesam
921 1305 921 raja1999
1488 1305 1488 Hitesh_0301
1556 1305 1555 arshad2117
1920 1305 1920 killer_lsy
2025 1305 2025 crazy__1234
2026 1305 2026 neat
2325 1305 2324 mutinner2
2427 1305 2427 zmy123456
2467 1305 2467 ssvirk
2570 1305 2569 volkov179
2690 1305 2689 vaibhavsarda
2711 1305 2711 sachitb
2932 1305 2932 Chintan_295
2961 1305 2962 wangjingting
3777 1305 3770 shreyas.mandade
3933 1305 3930 plnn
3943 1305 3944 garadu18
4188 1305 4186 StrawHatWess
4264 1305 4265 MadWarlock
4306 1305 4306 uddeshya.singh
4340 1305 4344 usertab34
4500 1305 4495 Anuj_0911
4652 1305 4657 Icewill
»
4 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Congrats to Pajaraja for his 11th consecutive rating increase, all the way from Specialist!

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

When will the T-Shirt winners be announced ?