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

Автор DK318, 3 года назад, По-русски

Привет, Codeforces!

Мы, DK318 и unreal.eugene, недавно присоединились к команде разработчиков Codeforces и Polygon, в данный момент являемся студентами Университета ИТМО. Чтобы лучше ознакомиться с Polygon, мы участвовали в подготовке этого раунда. Совсем скоро вы сможете увидеть первые результаты нашей работы в качестве разработчкиков.

Кроме нас в разработке раунда принимали не меньшее участие MikeMirzayanov, geranazavr555 и doreshnikov. Надеемся, что вы получите удовольствие от решения задач!

В 10.07.2021 17:35 (Московское время) начнется Codeforces Round 731 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы будем расстроены, если у многих попадают решения после окончания контеста.

Вам будет предложено 7 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо ashmelev, Monogon, CtrlAlt, Tzak, FelixArg, antontrygubO_o, bugdone и brian за помощь в тестировании раунда и улучшении задач.

Удачи!

UPD 1

Разбор задач.

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

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

I hope i could never give div 3 rounds officially after this :)

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

Hoping to get positive delta on my birthday!

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

I hope i solve A faster and not quit from contest.

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

Hope to get the cyan color again on my profile :) after this round .

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

Hope to be expert for the first time in my life. (UPD: WOW, DREAM COME TRUE)

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

Hopeforces

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

Hope I finally leave this drab, lifeless colour behind

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

I hope to be a pupil.

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

Hope I can enjoy the contest and get my first in-round-full-solve :)

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

I was just wondering why Mike Mirzayanov never give any contest!!

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

Hope to get my nickname colored

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

Hope to become blue this time :)

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

Hope I will continue hoping after this hopeful contest.

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

![ ]()

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

I was wondering who can create contests and how do you do it?

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

Hopefully I hope to hope

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

Hope i will learn some important thing from hopeful contest

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

Hope

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

2 contests back to back! Hoping to have a good weekend...

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

Hope that I will gain confidence after this.

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

orz

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

Hope to gain some confidence after a string of disastrous rounds.

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

I hope to become an LGM after this round.

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

I hope this will be my last official div 3 round

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

My first unrated contest ><. Feels awkward tbh, after giving every contest to gain rating.

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

Much waited for this but Clashing with Leetcode :( ,anyways preferred cf over all others :)

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

O, new authors, cool. This Div 3 promises to be interesting.

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

I got one wrong answer in the last div3 round because of just one #define int long long ,hope not to repeat the same mistake again.

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

Div3 is always High Hopes

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

Oh no.. I have to read for tomorrow's exam. But today is my long awaited Div 3 contest. Confused which to choose!

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

I wish everyone who work hard may get the positive delta

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

Good Luck Everyone

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

Wishing best to the new authors ! Hope they wont let me miss vovuh div3s

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

Hope to be specialist in this round

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

I really like these problems. Thank you for this round!

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

guess it's time to finally learn bit operations lol

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

Bring back King vovuh

vovuh orz

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

This is the first time I pass all problem's pretest in one round. Thanks for this round!

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

I used SCC compression in problem G. I wonder if this is an overkill.

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

    i dont know what youre talking about so i think it is. You can just do dfs and not pass through a vertex twice if it has infinite paths

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

      Could you elaborate on that? Do you mean just calculate the SCCs and then bfs out or something like that only counting the first two visits? Or do you mean avoiding SCCs altogether.

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

        Ok so my idea is that you do a dfs and mantain which vertices were in the path of the current path of the dfs. If you can go from that vertice v to a vertice p on the dfs path from 1 to v, then p has infinite paths to it.

        Then, you can call a dfs to p like it would normally do and for each vertice it goes through you mark that vertice as also having infinite paths. This doesn't explode into insanity because as mentioned in the other comment you can choose not to go on vertices marked as having infinite paths (you will pass at most twice for each vertice).

        You can also mark the other types of values like having 1, more than 1 or no paths pretty easily as well

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

    Yeah I also modified some scc compression code to solve this problem but it does feel overkill for a Div3.

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

      xD I used that same reference code when writing my solution. Definitely felt overkill, I've only seen SCC actually required on like GM+ level problems.

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

    Can you comment what is wrong in this solution?

    I was trying to make topological order of this graph, the nodes that do not appear in this are in some cycle. Then I found the number of paths of nodes in topological order and the nodes that are in cycle and get -1 ,if they are connected to 1, else 0. WA submission

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

    I also used SCC compression to get the dag. Then using bfs to count 2 visits at max. Then using if any node in a single SCC containing multiple nodes is reachable then all nodes present in that SCC are -1. Then every node which are reachable from those -1 nodes are also -1. This can be found using multisource bfs with the -1 nodes. Don't know if it is overkill.

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

Gud contest, the problems were amazing. I wasn't able to solve full of it but that's okay though.

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

Couldn't solve E. But the contest was amazing. Liked the problems... Any hints for E?

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

    You can see that after each move each array in A will contain one more element of it in the initial array. SO after n move => every element in A will contain the gcd of n + 1 element in the initial array (that's the worst case). If after k moves and we have an array which all of its elements are equals then that will also true for k + 1 and so on. So the main ideal here is to do a binary search on k and use sparse table to calculate the gcd from l to r in O(1) to make sure the complexity is O(nlogn). (sorry for my bad en)

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

    Can use multisource shortest path kinda thing for E..

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

    Actually, after a lot of thinking, I realized that the solution of E is pretty straightforward.

    We need to scroll from left to right, maintain the answer, and scroll from right to left and maintain the answer. It doesn't matter which way we scroll first.

    My solution LINK

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

I have solved Problem F using Segment Tree + Binary Search. Anyone who has solved this with the same approach? Just want to know.

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

    I thought the same but was really solving slow this contest!

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

    You can use a sparse table since the array is static. Mine passed in 155 ms. 121971699

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

    I used Sparse table + Binary search but I think segment tree should be sufficient. Because the time complexity of your algorithm should be O(nlog^3(n)) and n = 2e5, so you need 1.16*10^9 *C operations in total which should fit in the time constraints (4s).

    Upd:Forgot to include the gcd

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

      Mine didn't work. I tried Segment tree + binary search, but ended up with TLE. Had to change it to sparse table to get accepted.

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

        Hm I guess the constant for the segment tree and other operations is too big

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

      Correct me if I'm wrong, but how will segtree + binary search be $$$O(n log^2(n))$$$ here?

      We will have $$$O(log(n))$$$ steps of binary search. For each step, we will need to process the answer for $$$n$$$ positions. For each position, the segtree will make at most $$$O(log(n))$$$ "combinations" of answers of child nodes. Each of these combinations will require an $$$O(log (n))$$$ gcd operation. So won't the total be $$$O(n log^3(n))$$$? While this could still pass (needs around $$$10^9$$$ ops and 4s TL), it feels risky. Or are you using a different approach that only needs $$$O(n)$$$ queries of the segtree?

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

        Whoops, totally forgot about the gcd operations which costs O(logn) my bad

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

        doesn't exist a way to do binary search inside a seg tree? I think errichto mentioned something like that sometime. When you are in a node if gcd so far is small enough you try left at first, secondly right else you say the node is too big and you go up in the tree

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

        https://codeforces.net/blog/entry/63771

        apparently lots of gcds chained are fast I also did segtree + binarysearch, passed with 1300ms

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

    i solved using segment tree + two pointer.

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

    I think I might be the only one with a non-binary search and non-segtree approach for F. Could not get AC so I'm not even sure if it's the right approach.

    1. Divide a[i]/ gcd(a[0],a[1],...a[n-1]);
    2. Concat array A with A to make A[1..N],A[1..n] of length 2n.
    3. Now we know that the final gcd will be 1. All we need to find now is for a particular prime P, what is the longest continuous segment in the array where all numbers are divisible by P.
    4. Final answer is, over all the primes, what is the length of maximum continuous segment as defined above.
    5. Start from the index 2n-1 and move left to index 0. We can store the maxContinuous length of each prime in a separate array and update it (+1 if divisible, 0 if not) as we move left.

    I couldn't get AC in time, but does the approach sound correct?

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

      I asked anandOza it is too slow there is many primes 70000n is too slow. but you can improve it not many primes appears a lot so you must remember at which index a prime appears and compute the longer interval on that (not confirmed solution though) but give it a try

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

        For any prime p at appears in a[i] (ie, a[i]%p = 0) ,if p appears in a[i+1] too, then continousLen[p]++. Else contiuousLen[p] = 1.

        This way you don't have to look at all the primes, but only those that are appearing in the number a[i]. We also update the maxLen over such primes only. Consider this similar to lazy updates.

        So this should effectively pass in the the TL. This would be O(N * |max number of primes in one number|) Does this make sense?

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

          it definitely make sense to me, that's beautiful

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

            Thanks. Unfortunately thought of at the last minute so no AC. But i'm glad you liked the solution.

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

was F binary search with segment trees

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

Good contest

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

Choked so hard on F, had every single idea except for the right one until 15 minutes for the contest to end

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

Can someone explain what is wrong in my solution for problem E?

Code

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

найс тл в ф

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

can someone tell me why I am getting this error on C and what does it mean - wrong answer Cannot merge "a" and "b" to get given output (test case 1)

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

    Since we need to merge the actions of both programmers, we need to take actions (numbers) from already given sets i.e. 'a' and 'b' and merge them. So, every element from 'a' and 'b' must be present in your output, not more not less. Your output may have one or more of the following problems: - There maybe an extra element in your output or - Maybe some element is missing or - Maybe relative order of elements in 'a' or 'b' or both is being changed.

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

For me, problem statement in C was very big and boring, totally -> nice contest

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

This was a great contest. What was the idea on problem F? I only got to the point that the final array will have all elements = gcd(x1,x2,x3...xn). Can you tell me the thought process?

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

    After k processes, the element x_i will be: gcd(x_i ~ x_{i+k}). To calculate this, You can use sparse table.

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

A and C felt somewhat bashy but otherwise contest was fine... G was a decent problem but I kept bricking on it until I realized I needed to change like two lines :| guess that's what I get for not learning SCC.

Curious on how people solved F -- I ended up using segtree but this is obviously not intended.

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

    How did you solve F with the help of seg-tree? Can you explain, please?

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

      After $$$k$$$ steps $$$a_i = \gcd(a_i, a_{i + 1}, \cdots, a_{i + k})$$$ (indices taken $$$\mod n$$$). Thus you can binary search on $$$k$$$ to get the answer.

      Since $$$a_i$$$ is equal to a $$$\gcd$$$ range in the original range, for a given $$$k$$$ we query this value for each $$$i$$$. Solution thus takes $$$O(\log n * n \log n) = O(n \log ^ 2 n)$$$. Look at my solution if you're curious about implementation.

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

        Wouldn't the gcd add another log factor? Or am I missing something?

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

          SecondThread was touching upon this in his stream, he claims that it wouldn't because of the nature of $$$\gcd$$$ decreasing at most $$$\log \text{max}(a_i)$$$ times before it'll reach $$$1$$$ (or something like that). I'm not really sure how the analysis works, maybe he can shed some light on it.

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

            Oh, I always assumed segtree gcd queries would take O(log2 n)

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

              I could be totally wrong here, but this is what I was thinking. Maybe some LGM who has a bigger brain can either confirm/deny this:

              So like, the GCD can only actually change log(n) times. Each time the GCD call goes one iteration deeper, that means that the answer will decrease by a factor of about 1.6, and this happens across all layers.

              The more general version of my hypothesis here is that: if you are calling the GCD with the result of previous calls n times, I think your runtime is really O(n + log(maxVal)), rather than O(n*log(maxVal)). I haven't heard other people say this before, so it might be some huge holes in my logic that makes it not true, but it seems cool enough to be interesting.

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

The number of accepted solutions increased gradual way.

Proves that Level of question increased in a very uniform way. Loved this !!!

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

    Even if the problems were all of the same difficulty you could see a similar pattern.

    Let's assume that everyone approaches the problems in alphabetical order, and that different coders solve problems at different speeds. The first problems will be solved by a lot of people, and the last ones only by a few very fast participants.

    The distribution of the number of accepted solutions is not a proof that the problem difficulty was increasing in a uniform way.

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

How to solve F ?

Few observations I made :

Answer is gcd of whole array call it g.

The steps for a element ai are-> gcd<ai,ai+1>,gcd<ai,ai+1,ai+2>,...gcd<ai,...an,a1,a2...ai-1>

The minimum step# which gives g in above sequence let that number be y.

Answer is maximum over all y for all i.

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

    Observe that After performing a minimum number of steps each element of array will be equal to the gcd of the array.

    I used a segment tree with binary search. Note that gcd never increases, So suppose if I am finding the minimum number of operations that are required to make this element equal to gcd, then I can do a binary search on range $$$[i,n]$$$. If we are unable to make the element equal to gcd then do a binary search in the range $$$[1,i-1]$$$

    Our answer is equal to the maximum operations that any element needs.

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

Does it take time for the rating to appear on my profile? Thanks

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

    You gotta at least wait for the hacking phase to end (for educational rounds and Div 3 rounds) and then it will take another few hours for the final system test to come, so basically you have to wait 12~24 hours. But for other rounds, it takes about 2 hours for the rating to be updated.

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

I solved F without using segment tree/ sparse table/ binary search, although it may fail for some strong tests :(

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

I cannot locate error in my submission for Problem C?

Submission: https://codeforces.net/contest/1547/submission/121993312

Please help me out!

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

    imagine i=n, and it's possible to complete with b, your j will grow to m with the while and then make a runtime error in your else (in b[j]<=k) and the condition j<m, I think so it would work

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

Any idea for E?

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

    Or simply go once in the array from left to right, ans[i]=min(ans[i], ans[i-1]+1)

    Then do the same from right to left.

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

I was 1199, and cf predictor shows -5. Seems like I'm the cursed one

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

I noticed that top-ranked guys solved the first several problems within 20 mins. I was like, how is that possible...

I'd say that I came up with the solutions once I understood what the problem was saying. And I also didn't get any WAs for those problem, which would incur delays. But it still took me about 50 mins :(.

Is there any special techniques other than reading/coding speed that makes those guys incredibly fast?

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

    What I have observed is that there are many factors behind their incredible speed.

    First of all, they are quick at thinking and realizing what needs to be done to solve the problem. That usually comes with practice and experience.

    Second thing is that apart from clear thought process, they have a much simpler and smaller implementation than most others.

    I am not sure about this one but I think that high speed also comes from reading and understanding problems fast, leaving out the irrelevant details and focusing on what is important to solve the problem, hence reducing the effective problem reading time.

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

Why rating changes from Codeforces 730 were reverted and again evaluated ? Anyone please answer..

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

    sometimes cheater are found afterwards and their standing is decrease, sometimes the contrary happens, someone proves he's not guilty. and so it's necessary to recompute the ratings (I earned 1 point more) somebody obfuscated his code maybe he was considered a cheater

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

придумал $$$ \mathcal{O}\left(n \log^2 n \log C \left(1 + \frac{\log \log C}{\log n}\right)\right) $$$ для F

unreal.eugene как думаете, можно вообще упихать?

UPD: не, хуйню несу, там на самом деле все гораздо хуже, но ща подумаю, не выглядит неисправимым

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

I thought that problem C is a simple dfs but I got tle. Is there a specific pruning condition?

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

    It is more greedy like.

    You simulate the process, that is, whenever one of both people want to add a line, we add a line. Else the one with the smaller index changes that line.

    If there are not enough lines to change the current line then there is no solution.

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

hint/help for D

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

    think greedily what is the smallest value you can append to y. you start with 0. to know what the smallest think about each bit if it's needed

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

    Choose y[0]=0.

    Then choose for all subsequent y[i] the smallest possible value to set all bits of x[i-1]^y[i-1]

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

Something Weird happened with my submission for problem G, today. My initial submissions gave wrong answer on test 3 on submission. After the contest I found that the 4599th output of my answer differed from original answer. I made another submission and found that this was the test case my code was printing wrong answer to:
1
4 4
1 3
1 4
4 2
3 4
(Found using — this submission (See participants output for test case-3).
But when I ran this test case (in codeforces custom invocation) with my original solution it gave correct result, whatever was expected. (Original Submission Link).
Can someone help, where did I made the mistake. I am new to this platform, so any help would be appreciated.

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

Thanks for the round! Here's a link to my screencast.

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

Deleted

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

So after a long wait Division 3 contest is finally back. Solved 5 problems and I feel skipping the LeetCode Biweekly Contest 56 which was running at the same time as that of this contest was finally worth it!!

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

I Hope I reach another color this time .. just got bored from the gray color :(

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

I am the only one who feel nasty statement for Problem C :):), and ended up without solving :):)

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

    I did get confused when I first read C, especially when my perf was so high. I went straight to the example first, then went back and read the rest to check if I missed anything. The parts that that describe Monocarp and Polycarp's sequences are identical, so you can also skip those after a quick glance.

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

i missed vovuh

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

9206baf56572ebc9908e8ed4e798fe4513e47577 .

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

Are solutions with multiset or priority queue for F getting too?

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

This has been a very exciting contest for me. Thank you very much!

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

I wish i could finally be cyan.

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

Was this contest supposed to be unrated?

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

Why is the round unrated for me? I am at 1399 and trusted participant as well

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

    I don't think anyone has got their ratings for this round yet because it states that whether you're trusted or not this round is rated for everyone <1600

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

why r the ratings not yet updated??