Автор awoo, история, 14 месяцев назад, По-русски

Привет, Codeforces!

В 24.01.2023 17:35 (Московское время) состоится Educational Codeforces Round 142 (Rated for Div. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Harbour.Space

Привет, Codeforces!

Полным ходом идет подготовка ко второму буткемпу по программированию «Hello Muscat 2023», продолжении серии буткемпов «Hello», организованном Harbour.Space University в сотрудничестве с PhazeRo, Gutech, UK Oman Digital Club, Leagues of Code, Gutech CS Club и Codeforces!

Довольно впечатляюще, не так ли? Пришло время глубже погрузиться в мир соревновательного программирования с 8-дневным интенсивом Hello Muscat 2023. Он будет проходить в Маскате, Оман, и онлайн с 8 по 16 марта 2023 года, доступны оба формата участия.

Наш тренерский состав сочетает в себе талант и опыт, в нем участвуют чемпионы мира ICPC, победители и финалисты, а также легендарные имена из области соревновательного программирования: Михаил Мирзаянов MikeMirzayanov, Егор Дубовик 244mhq, Артем Плоткин Rox, Максим Обозный MaksymOboznyi и Николай Будин budalnik.

Буткемп будет разделен на три дивизиона:

  • Дивизион A. станет зеркалом Петрозаводского лагеря программирования. Подходит для команд, которые уже прошли квалификацию на Финал ICPC или стремятся к этому.
  • Дивизион B. Разработан, чтобы помочь командам подготовиться к следующему сезону региональных соревнований ICPC. Подходит в качестве введения для команд и студентов, которые только начинают свой путь в мир ICPC и соревнований по программированию в целом.
  • Дивизион C. Предназначен для новичков в мире соревновательного программирования.

Типы участия: очное и онлайн

_Мы считаем, что участие в нашем буткемпе должно быть доступно для всех команд, где бы они ни находились, и именно поэтому мы сделали очную и онлайн-формы участия. Скидка 20% на раннее бронирование предоставляется университетам и участникам, которые зарегистрируются и оплатят до 31 января 2023 года.

  • Очное:

Цена: 1500 € — 1200 €

Что включено: обучение, контесты, доступ к записям лекций, проживание в течение 9 ночей в 4-звездочном отеле Mysk, завтрак и обед, трансфер из гостиницы к месту проведения буткемпа каждый день, развлечения и приветственный подарок.

  • Онлайн

Цена: 100 € — 80 €

Что включено: обучение, контесты и доступ к записям лекций.

Узнать больше о Hello Muscat 2023→

Удачи в раунде,

Harbour.Space University Team

UPD: Разбор опубликован

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

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

Welcome to slow-rating-update round #142!

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

Anybody noticed that quite hell unusual time of 26th Feb contest??!!

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

Hope to get BLUE today!

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

I feel like Educational Rounds are more Mathematical than usual rounds, is this the case?

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

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

Good luck! Wish every participant have higher ratings!

»
14 месяцев назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

»
14 месяцев назад, # |
  Проголосовать: нравится -62 Проголосовать: не нравится

Classic Mathforces.

None of A,B and C had anything to do with DSA

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

    A was greedy, B was a math problem, C use binary search. 1 out of the first 3 problems of a div 2 round being math problems doesn't imply that a contest is "Mathforces" dumbass. Also, atleast don't be green and talk shit about a contest not having enough DSA problems.

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

      Mind your language, this is not reddit/twitter. As for rating, I don't take these contest seriously nowadays. I at one point was Blue unlike someone who has never crossed 1500 xD

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

        "Mind your language"- What you say matters as much as how you say it, so that's pretty rich coming from a guy who spouts shit like there's no tomorrow.

        Also, I don't want to get into petty comparisons, but I have given like 7 contests till now, so I'm pretty sure my peak will be way above yours :)

        Edit: The part about "someone who has never crossed 1500" didn't age well

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

          Bro called me a dumbass for sharing my take on the contest and then preaching me.

          And then Bro says he doesnt do pity comparisons but advices me to get out of green and then give my analysis on the contest.

          Hypocrisy at its finest!

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

    Considering your past rating you shouldn't have had any trouble doing A, B, or C... idk man skill issue

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

      It's not about whether I am able to solve or not, its about the quality of questions. I was able to solve A and B but still complaining because there was no satisfaction solving those problems

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

        of course you didn't have any satisfaction solving them, they aren't supposed to be hard for anyone above 1k rating

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

Короче, Меченый, я тебе высрал div2 и в благородство играть не буду: посчитаешь n-е число A000311 — и мы в расчете. Заодно посмотрим, как быстро у тебя пукан после раунда загорится. А по твоей теме постараюсь узнать. Хрен его знает, на кой ляд тебе эти числа Эйлера 2 рода сдались, но я в чужие дела не лезу, хочешь отглиномесить, значит, есть за что....

»
14 месяцев назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

Problem C is the literal definition of million corner cases and i love it lol

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

Nice problem D, it took a while before I noticed the name of the problem :) great hint

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

Hints for question D

Hint 1
Hint 2

My solution[submission:190390614]

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

I quite liked problem C. I am pretty proud of an elegant solution I came up with inspired by some monotonic stack problems I was solving the other day.

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

how to solve 1st ?

My approach was to count the number of frequency and take their sum, and ans should be max to max n what is wrong in this?

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

    My solution is to count number of 1-s in array and print n — (count_1 / 2).

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

    Only double 1-s pair in the array can decrease operation times, so all you need to do is just count the pair's amount.

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

    You can kill monsters of health 1 in pairs and remaining you can kill individually.

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

After finishing it agrees with me that the problem D is easier than the problem C, lol

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

I was stuck with problem C. My code outputs correctly for samples and inputs I give. Perhaps I can't find the edge cases. Here is my code https://codeforces.com/contest/1792/submission/190399259 .

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

    Counterexample:

    8
    2 3 1 7 8 4 5 6
    

    Output should be 2. Pick (2, 7), then pick (1, 8). Your code seems to output 3.

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

leave it there is an easy way to solve D then my way

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

OMGGG solved E on 01.59.54 les goo

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

how to solve 2nd problem

my approach was if we can have a > 0 then one joke from b and one joke from c and alternating it till either b or c runs out . so it's min of (b , c) + min jokes in total . now these jokes will balance it and bring it back to a . now if d > 0 i can take the min of d , a extra jokes . if( b or c ) are not 0 . add one more joke .

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

    If $$$a = 0$$$, output $$$min(1, a + b + c + d)$$$.

    Else the answer is $$$a + min(b, c) * 2 + min(a + 1, b + c + d - min(b, c) * 2)$$$

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

      Can u explain how min(a+1,b+c+d-min(b,c)*2) come up .Beacause I am not able to figure it out

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        • Take all $$$a$$$

        • Taking $$$1$$$ $$$b$$$ then $$$1$$$ $$$c$$$ until $$$b = 0$$$ or $$$c = 0$$$.

        • Now both of them will have $$$a$$$ points and at least one of them cannot get anymore points. You can take at most $$$a + 1$$$ from $$$b + c + d$$$.

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

D was nice combination of DP and trie.. loved the question

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

    How is DP being involved? Do you store the answers so that you do not insert a permutation again?

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

      no, You create dp[i][j] = Indices of all the permutations, which has '1' on i'th index and 2 on j'th index .

      Then, for each permutation, u can loop. this will give you ( 5 * 10^4 * 8! ) roughly... Also, u need to put break statement if you already found the ans of length 'm' .

      You can follow my solution here.

      ALAS, I was just 2 minutes late from finishing my final solution :( ...

      If you need understanding my solution, feel free to ping me.

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

i freaking could not implement trie, i chocked and even forgot dynamic allocation !!!

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

    If you are talking about D, straightforward polynomial hashing (without the mod) would do.

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

      you mean rolling hash right? I could not think of this in contest, wasted an hour googling dynamic allocation and still could not do because of the stress of the contest.

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

      Can you explain what polynomial hashing is? or post a link please. I'm having a hard time implementing D as well

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

        polynomial hashing is basically encoding an array/string into a number. So for example the permutation $$$5, 3, 1, 4, 2$$$, you just encode it into the number $$$53142$$$. This way, you can easily compare array in $$$O(1)$$$, in order to binary search/use map

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

    If you use map with vector it also works

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

      Can you explain how that would work, I saw many submissions with maps but I can't seem to comprehend them? Im not able to understand how the map solutions are working.

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

        Map remembers a value by their key, a key can be almost anything, even vector, so when you are itterating over an array and you are looking at what prefix should the other array have to get beauty of A with the array we are looking at, you can remember that prefix as a vector and use that vector as a key in map, and remember value 1 in map at that key. after doing that for all arrays, you are now looking for an answer for an array lets say C, you itterate over its prefixes, push them in vector, and for every prefix vector you check if you have written 1 in the map at the place of this vector( so you use this prefix vector as a key) if you have then you can get the beauty of the lenght of the prefix vector

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

I think I had an interesting approach for C, curious if anyone else had the same idea:

  1. Push all elements in the permutation into a queue. Initialize variable 'min' as 1, 'ans' as 0.

For i = 1 : n:

  1. While queue.front() == min or queue.front() == selected, queue.pop(), min++ if queue.front() == min

  2. Selected.insert(i, n-i-1), ans++;

Done! Return answer.

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

Damn. beethoven97 hacked LGM turmax's solution

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

For me C > E > D. I Spent more than 40 min on C and am still not able to solve it. What's the solution?

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

    Think in terms of binary search. Can we solve the problem with $$$i$$$ operations? Now think what should the last operation be? What should the second to last operation be, and so on so forth ...

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

    My reasoning was that if we select some elements, we will always select 1, n, 2, n-1, etc... The order we select them should not matter because some optimal ordering should exist anyways. So I created a queue and popped off elements while it was sorted. Then, whenever it was unsorted, I removed elements i and n-1-i from the array and continued to pop while it was sorted. The number of times you remove i and n-1-i is the answer.

    Submission: 190357765

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

    You can see that you can not use operation on numbers that are close to each other and ordered for example 4,5,6. 4,5,7 and 6,5,4 will not go. So if array is like this 4,8,7,5,3,2,1,6 you can do operation on every other number except these 3 numbers = 4,5,6, and answer will be max(min(numbers)-1, n-max(numbers)) = max(4-1, 8-6) = 3.

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

    Just do n/2,n/2+1;n/2-1,n/2+2;... if n%2==0 or do n/2,n/2+2;... if n%2==1 and skip the first operations if they are already in place.

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

    You have to find the longest MIDDLE subarray.

    5
    1 2 5 3 4
    

    The longest you can find is 2 3 4.

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

Amazing system testing.So fast.

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

Would C Problem be solved by 2 Pointers ? if not, then what?

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

Can someone give stress test for 2nd testcase on E? 190401625

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

A: Use first spell for 1-health monsters and second spell for others.

B: First tell all type-1 jokes, then tell type-2 and type-3 jokes alternately, until one type of jokes run out. Then tell all remaining jokes until someone leaves.

C: Take n=6 as example. First let ans=3=n/2, and check if the order of {3,4} is correct (which means, 3 appear earlier than 4 in the initial permutation), here 3,4 are "central" elements of 1-6. If it's not, we need ans=3 operations. Otherwise, we need to do ans--, and check the order of {2,3,4,5}. Do this repeatly until we fail at any check or we've checked the whole permutation. If n id odd, let k=(n-1)/2, start at ans=k and checking {k,k+1,k+2}.

D: We need to check the longest common prefix of ai and aj^(-1) (where aj^(-1) is the inverse of aj), we could store all aj^(-1) in a trie and find for all ai.

E: Didn't solved. Maybe we can let set s={d: m1*m2%d==0 && 1<=d && d<=n} and do loop for(d1:s) for(d2:s && d2>=d1) but I don't know if this approach will get TLE (for cases like n=1e9, m1=m2=735134400).

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

    Stored all aj in a trie and searched for aj^-1, didn't realize the solution during contest. :(

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

    D: Sort the permutations and For every prefix of every permutation, binary search permutations that match this prefix and use segment tree to update range (l <= i <= r) a[i] = max(a[i], x). 190359788

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

Any hints for E?

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

    two pointers

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

      In defense of this hint, my submission passed system testing with a two pointer-like approach: https://codeforces.com/contest/1792/submission/190397103.

      Although upon further reflection, the analysis I had of its time complexity was not correct, so if anyone can come up with a proof of correctness (or a hack), that would be cool!

      The main idea was to process the divisors in ascending order. Let the current divisor be $$$a$$$. We will maintain a pointer to the minimum divisor, $$$b$$$ such that $$$a / b <= n$$$. Then we just search from $$$b$$$ until the last divisor <= $$$n$$$. It feels like there might be an argument that the average number of elements we check is not too high, but I can't find it.

      The dp solution seems much more straightforward to understand, so apologies for the misdirection.

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

    Don't know for sure that this is the intended solution.

    First, find all the divisors by brute force as the maximum number of divisors for (large) n cannot exceed cube root n. And for every divisor x below 1e9, remove the divisors of x until x*1e9 iteratively and update the answer.

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

    Generate all divisors of $$$m$$$ (there's about $$$10^5$$$ of them in the worst case). For every divisor, instead of the minimum row where it appears, let's search for the maximum column (it's easy to see that these two are equivalent). So, for every divisor, we need to find its maximum divisor which is not greater than $$$n$$$.

    This can be done with the following dynamic: $$$dp[d]$$$ is maximum divisor of $$$d$$$ not exceeding $$$n$$$. If $$$d \le n$$$, then $$$dp[d] = d$$$, otherwise iterate on the prime divisor $$$p$$$ in the factorization of $$$d$$$ and find the maximum of $$$dp[d/p]$$$.

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

      Could you mention the time complexity of this approach? It's not immediately clear this solution can fit into time limit?

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

        Something like $$$O(D \log D \log m)$$$, where $$$D$$$ is the number of divisors of $$$m$$$. There are $$$D$$$ states in the dynamic programming, each state has up to $$$\log m$$$ transitions (each transition corresponds to dividing by a prime from the factorization of $$$m$$$), and an extra logarithm because everything is stored in a map.

        upd: Plus $$$\sqrt{m_1} + \sqrt{m_2}$$$ to factorize $$$m$$$.

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

          More accurately, $$$D \le 105\,000$$$, "$$$\log{m}$$$ transitions" is actually $$$\le 15$$$.

          And don't use maps for $$$dp$$$, use vectors.

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

            How to not use maps? The factors of m could be large right?

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

      I generated all divisors of $$$m$$$ . For each divisor $$$a$$$ , I brutely searched minimal row number within the range $$$[\lceil \frac a n \rceil,min(n, \sqrt a)]$$$ among divisors of $$$m$$$ .This naive solution seems to run very fast.

      Is it reasonable to let this solution pass? I mean, this solution is unbelievably too simple, meanwhile hard to know exact time complexity.

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

        My best guess is that for each divisor $$$a$$$, there's a big chance that you have to go through like $$$50$$$ divisors on average (maybe much less I don't really know) before finding an answer. You see, for highly composite numbers, aka numbers that has a lot of divisors, its divisors are also expected to have a lot of divisors, thus it is likely for the algorithm to encounter a divisor of $$$a$$$ in very few loops. For number that has less divisors, I think that there simply isn't enough divisors to make a simple $$$O(n^2)$$$ getting TLE

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

      Why dp[d] = std::max(dp[d], dp[d / p]), I don't understand this, please explain it to me.

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

D could have been a really nice binary search + trie task if bounds were N<=1e5, NxM <= 1e5

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

    Why binary search tho? You can just DFS down the trie, and the answer would simply be where the DFS end.

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

I feel bad when I heard that $$$O(n^2)$$$ solution can pass F2.

I feel worse when I really pass it after the contest. Here

I guess the author think D&C + fft is too slow, but it is not that slow, and is it reasonable to let $$$n^2$$$ solutions pass?

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

    The problem F of last contest also be passed by some O(n^2) solutions.

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

    Unfortunately, looks like really fast templates for modular arithmetics do the trick. I haven't come up with the D&C+FFT solution, the model one has slower asymptotics than D&C+FFT. So, basically, I could try one of the following two things:

    • let only solutions with very optimized FFT and modular arithmetics pass;
    • let solutions with more "normal" implementations of FFT and modular arithmetics pass, but risk that someone with a very strong modular template will squeeze $$$O(n^2)$$$ in

    I still think that 2nd is better choice. Maybe my mistake was even trying to distinguish $$$O(n^2)$$$ and $$$O(n \sqrt{n \log n})$$$. I am sorry for that, but I hope not a lot of participants were affected by the issue.

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

      The formula is like $$$f_{i} = \sum{f_{j}\times f_{i-j}}$$$, in my memory it can be solve by D&C and fft(since $$$f_{i}=\sum{f_{j}\times g_{i-j}}$$$ for fixed $$$g$$$ can be solved) , but maybe I remember it wrong(I feel sorry), and I didn't figure it out during the contest.

      However, OEIS A000311 shows that $$$ans = exp(f(x)) = 2f(x) - x + 1$$$, thus we can solve it by Polynomial Newtonian iteration($$$O(nlogn)$$$ maybe?).

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

      I squeezed in $$$O(n^2)$$$ by precomputing for biggest n and putting it into the source code and running the $$$n^2$$$ normally for small $$$n$$$. I didn't use any very optimized modular arithmetic. 190408679 (there seems to be no test with a number in range of [3.5e4,4e4), so the runtime is misleading but testing the worstcase on custom invocation gives 4500 ms.

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

    In fact we can directly get a formula using lagrange inversion. the final result (plus 2) is the $$$x^{n-1}$$$ coefficient of $$$2(n-1)!(\frac{x}{2x+1-e^x})^n$$$

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

Did any1 use strings for D?

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

    I concatenated values in array and stored them in hashmap, but I did it because golang doesn't support custom key types in hashmap.

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

    Yup! I did.

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

https://codeforces.com/contest/1792/submission/190405242

Could anyone help me understand why my code gives incorrect output in this question?

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

Could anyone help me understand why my code for D gives incorrect output here:

https://codeforces.com/contest/1792/submission/190405242

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

    your answer would have been fine if rj = pqj

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

      Thanks for helping. What makes this hurt more is that I would have got last 5 second AC instead of WA, had I not done that silly mistake xD.

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

      Wait a minute, but wont p(q(j)) and q(p(j)) be like the inverse of each other, ie. they will produce each other?

      For example, wouldn't the product of p = 3142 and q = 2413 be 1234 whether you take r = p.q or r = q.p?

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

        No take this for example
        2 4 1 3
        2 1 4 3

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

          In the first sample test case, the optimal p for i = 1 such that k for ai * p is maximised will be [3 1 4 2] right? But none of the given arrays have a prefix 3, So how is the answer 1 and not 0?

          I'm extremely sorry if I'm asking dumb questions rn, I'm a bit sleep deprived.

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

            You are getting confused 💀, take a vector of pair store the values of "p" in that vector along with index ({value,index}), sort it and then take the prefix of indexes , what you are doing is you are still finding pqj 💀 💀

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

The One Piece is real!!!

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

Is E solved by observing numbers of divisors is relatively little(milion or so cause max 20 diferent primes in numbers) and then searching through primes?

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

What's wrong with my solution for problem C? 190408656

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

    Test Case
    1
    5
    4 1 5 3 2

    your output
    expected output
»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In C what I did for every index I find the fine permutation till that then I will find the left portions towards left and right of the this range 3 1 2 4 5 here fine permutation of index 4 will be 3 4 and then in final permutation 1 2 should come on left of it and 5 in right so greedily we pick 2 and 5 first then 1 and 5 My submission https://codeforces.com/contest/1792/submission/190407907

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

Why so many hacks of B? Is there any edge case?

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

    I think people are simulating it, which is too slow. Most of the hacks are TLEs.

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

    I think it's becaues of the $$$1e18$$$ upper limit of $$$a1,a2,a3,a4$$$, which causes the TLE

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

      You scared the heck out of me when I read 1e18 because I used ints in my program, but thankfully I rechecked the constraints and saw that they were 1e8.

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

        oops, I guess I misread it xd, anyway it will still TLE regardless

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

Am I the only one who solve D with trie!

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

Am I the only one who solve problem D with trie and later see that it has an easy solution?

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

Can someone give a failing TC for this submission of Problem B?

190391460

Thanks.

Upd: Found the TC.

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

F1 can be cheesed since $$$n$$$ is small and the answer is required modulo a fixed number, You can pre-compute the answers in $$$O(n ^ 3)$$$ and copy the array into your code.

My solution 190420429

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

Yesterday I was practicing hashing, but I tried to don't think biased and made a solution with custom sorting and binary search in D :)

My solution
»
14 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

D was really standard...even using simple map for counting will pass for me C>D

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

I passed E in 15 minutes after the match,it didn't seem like a difficult problem,what a pity

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

I understood that problem D can be solved by trie, and I was having some difficulty so I looked at some submissions. I see that many people have implemented trie (or something similar) using map. Can anyone explain the logic behind the implementation?

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

any hints for D

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

C can also be solved using DP: 190339025

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

    what's the meaning of vector d and statues shifting funcion

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

      $$$d_i$$$ means the length of Longest Continious Subsequence ($$$...,i-2,i-1,i$$$) (End with number $$$i$$$)

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

    Oh this $$$O(n)$$$ is better than std's $$$O(n\log n)$$$ :)

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

Hi guys if you are still stuck on the problems or want a editorial on it you might wanna check this out: https://youtu.be/TOotS4TDzTI

happy coding!

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

Bad F due to oeis.org/A006351.We can search exsamples+2 to get this

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

    how is that related to the problem, ur solution to the problem (F1) doesn't use the formula mentioned in the link, how could someone possibly use it ?

    also i dont think someone possibly would search first two samples + 2 in oeis and if so, it displays 316 results found, i dont see any reason calling it "Bad" because of such a reasoning.

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

      i dont think someone possibly would search first two samples + 2 in oeis

      Several participants did search the answers for $$$n$$$ between $$$1$$$ and $$$4$$$, found the formula, and had their solutions accepted. Moreover, one could find these values with simple combinatorial considerations.

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

      look at this: a(1) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k). — Ilya Gutkovskiy, Aug 28 2020

      use this recursive, we can solve F1 and then the recursive is a convolution, while module is 998244353, which means it is easy to brainstorm NTT. And let me tell you why I searched answer+2. the problem said that at least one edge should be painted as red/blue, that means when n>=2, there are two illegal answer(all red or all blue) being removed, while n=1, one illegal answer(no edge) will be removed, so let's search 1,2,8,52(see samples) in oeis.

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

Did anyone try to solve D using polynomial hashing and got AC? My solution keeps getting TLE in test case 6. I'm trying to maintain HashSet over all possible subsequences keeping their own position intact. After that, for each i I'm calculating q putting numbers one by one, and calculating the hash. 190454887

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

hope to get green

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

About E.Divisors

Does this problem have too strict time limit?This is my solution https://codeforces.com/contest/1792/submission/190443658 and it has been hacked for 3 times, I think this problem may need to have more loose time limit like 4 seconods.

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

    There are some better solutions that don't iterate over divisors of every single divisor of m. See this. Also your code is T^2 (T is the number of divisors of m), which is even worse...

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

    The question is, you only need to make a few changes to your code to pass all testdata.

    I raised my question here , but still no one answered.

    vector<ll> s3;
    for (const auto &x1 : s1)
        for (const auto &x2 : s2) s3.push_back(x1 * x2);
    sort(s3.begin(), s3.end());
    s3.erase(std::unique(s3.begin(), s3.end()), s3.end());
    int ans1 = 0, ans2 = 0;
    for (const auto &x : s3) {
        for (auto pos = std::lower_bound(s3.begin(), s3.end(), (x + n - 1) / n); pos != s3.end(); ++pos)
            if (*pos > n or *pos * *pos > x) break;
        elif (x % (*pos) == 0) {
            ans1++, ans2 ^= *pos;
            break;
        }
    }
    
    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      We knew about such solution and it passes. We suspect that either the number of divisors is small (so $$$divs(m)^2$$$ is fine) or divisors are "packed" close, so it's near enough.

      Add here that divisors, you actually need to find their own divisors, are in the segment $$$(n, n^2]$$$. So if $$$n$$$ is big, many divisors $$$\le n$$$. If $$$n$$$ is small, many divisors $$$> n^2$$$.

      Anyway, we decided that it's okay if some participants gamble and get AC.

      P.S.: Even so, you need to write it accurately enough.

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

        I'm not saying that a naive solution needs no skill. I'm saying that, such solution needs obviously less skill than people always expect for E.

        If you attribute my not_pass to my cowardice or bad strategy, that's right.

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

        In addition, the naive solution is not only "near enough", but far more.

        I found all factors during the contest. Now I added two for-loops. Guess what, it costs 156 ms only.

        156 ms

        If you say that this solution requires some advanced mathematical knowledge, which you had already used to prove the time complexity, so this solution can be an alternative. I would blame me for my lack of knowledge.

        But you said otherwise. Emm... whatever, it was history.

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

        thanks,i will write it more detailed soon

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

      OK,i will try it soon,thanks so much

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

There will be only 6 hrs before next round begin. Maybe the rating update of the next round will be earlier than this round.

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

When will the Editorial be published ?

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

This is to address the concerned authorities about my submission 190353992, which got skipped because the system considered it similar to another submission by BoosterImpulse , submission id 190386013.

I think the major reason why these 2 codes appear similar, is because of the use of a template of MOD INT (MINT), which I have used many times in my code and is clearly written before the contest and you can clearly see my code is completely different from the other person's code, my code is a normal implementation of two pointers. You can also check the timings of the submission and other persons' submissions. Please look into this matter as soon as possible cause I will become an expert if my solutions are been judged fairly. awoo BledDest Neon MikeMirzayanov adedalic

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

.

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

Rating updated :D

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

When will the editorial be published?

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

System said that I cheated but I did not.

wsyear/190368291, LXH-cat/190370101 we used a similar template of modint and checked oeis to find a formula:

a(0)=0, a(1)=a(2)=1; for n >= 2, a(n+1) = (n+2)*a(n) + 2*Sum_{k=2..n-1} binomial(n, k)*a(k)*a(n-k+1).

With the same formula, our codes are similar.

The code that I used modint before this contest.

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

IMO the problems were great. I enjoyed thinking about and solving them. Also I got caught on the special case for B (a1 == 0) haha.

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

Through this comment, I want to address the cheating charges levied on me and Numinous , for having a coinciding solution to problem C in Educational Round 142. The submissions are 190386013 and 190353992. The reason for getting plagiarised was having a similar template, going through solve function for both speaks out the difference clearly. I hereby in my humble opinion ask MikeMirzayanov Neon BledDest adedalic vovuh awoo to provide us justice and the ratings we deserve . Thank You for your time and effort .