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

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

Привет! В 25.07.2023 17:35 (Московское время) начнётся Codeforces Round 888 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

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

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

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

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

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

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи были придуманы и написаны нашей командой: myav, Aris, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо:

  1. MikeMirzayanov за системы Polygon и Codeforces.

  2. tute7627 за красное тестирование раунда

  3. oversolver, sevlll777, pavlekn, zwezdinv, Sokol080808, 74TrAkToR, vladmart, EJIC_B_KEDAX, Vladithur, KseniaShk, Be_dos за жёлтое тестирование раунда
  4. moonpie24, FBI, meowcneil, NintsiChkhaidze, Phantom_Performer, SashaT9, spike1236, Kalashnikov за фиолетовое тестирование раунда
  5. TheGoodest, Pa_sha, Sasha0738 за синее тестирование раунда
  6. Syuzi777, Tahseen за бирюзовое тестирование раунда

Всем удачи!

UPD: Разбор

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

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

May 19, 2023 what

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

//I don't know why, but my comment got sent 2 times, don't pay attention

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

hoping to solve atleast 3 problems

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

it's ironic that all the testers are not actually eligible for div 3...

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

Hoping to become Expert in this round

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

why is there no cyan, green or gray testers?

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

i hope to be blue this time

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

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

I have a really good feeling about that this would be my last rated Div. 3 contest and I would have become a blue expert after this 888ᵗʰ round of Codeforces!! May the Force be with us

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

I have exam (TT — TT)

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

    Obviously, exams cannot be compared to codeforces :) Give up exams and choose to fail, embrace Div. 3

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

      yaaaa Now,Let's ditch the exams and embrace our coding superpowers! (っ▀¯▀)つ

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

Hopefully, we will see a problem connected with number $$$8$$$, lol.

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

I think most of Div.3's are made by Vladosiya

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

div3

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

best part of the comment section is I see anime pfpS and discover new interesting animes

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

I think this will be a good one

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

I hope this round will be the great round of Div.3!

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

Good luck

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

Out of competition, but I'll try my best to do it ^_^

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

It is so good to have a contest every few days, hopefully i can cross 1500 today

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

I don't know if this is the right place to say this, but I've noticed for a while now that div3 round announcements say that you can only qualify as a trusted div3 participant if you "do not have a point of 1900 or higher in the rating." Shouldn't that number be 1600 instead?

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

    I think this is a translation error. My understanding (from the original announcement of the trusted participant system) is that you must never have had a rating above 1900. In other words, if your rating is above 1900 at one point but then falls below 1600, Div. 3 rounds will be rated for you, but you will not appear in the official standings.

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

Experts to lower rankings in Div.3 be like:

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

After playing div2,I feel that div3 and div4 are still suitable for me

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

Tends to Pupil:)

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

hoping to solve at least 4 problems

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

In first line of blog "You will be offered 6-8 problems" .Later "You will be given 7 problems and 2 hours and 15 minutes to solve them ".So, 7 problems will be there ?.

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

It's fun that the round will be rated for me.

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

    tbh I don't see it as fun because you may become cm today by spamming div-3 , I think div-3 should be unrated for participants if they are >=1600 during participation even if they registered for div-3 when <1600

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

      But I won't be in this contest because my mom doesn't let me stay up all night.

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

        come on bro stay up , don't be a mommy's kid

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

        Why do you have to stay up all night? Look at tourist. Maybe he just need to wake up and spend about just only half an hour to ac this contest (equal to the time i understood problem E). Maybe u can follow that way :D.

        J4F

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

hope to be specialist in this contest

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

I am at the lowest confidence in my life.

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

Good Luck everyone

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

I will solve atleast 5 problems.

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

so she knows what awaits her. emmmmmmhahahahaha~

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

Thank you Vladosiya very much. This is the best Div.3 contest I've ever written.

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

Why I an rated ??????

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

Readforces

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

    my guy only read A and decided to conclude the entire contest was readforces

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

      It is still readforces because half the time I'm trying to decipher what the problems are saying, the statements can definitely be phrased better which a lot of people have mentioned also

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

        readforces isnt unclear wording, its when u got paragraphs upon paragraphs for a problem statement

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

any hints to G?

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

Yes/NoForces

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

D: Let difference d[0]=a[0], d[i]=a[i]-a[i-1] when i>0. If the missing prefix sum is n*(n+1)/2, then {d[i]} will be a permutation of [1, n] missing one element. Therefore, for this case we need to check in {d[i]} are pairwise distinct and inside range [1, n]. Otherwise, we will have a[n-1]=n*(n+1)/2, and n-2 elements of {d[i]} will be inside [1, n] and distinct, the last element will be the sum of 2 missing elements. So for this case we need to check if {d[i]} contains n-2 different numbers inside [1, n].

E: First for potions with infinite supply we can just set their cost to 0. Then, if potion i can be obtained mixing {j[1], j[2], ...}, we add a directed edge (j[t] --> i) for each j[t]. Since no potion can be obtained by mixing itself, these edges will from a DAG (directed acyclic graph), and we can run dp on the topological order of the DAG: Let dp[i]=sum(cost[j]) where edge (j --> i) exists, and cost[i]=min(cost[i], dp[i]).

F: If a[i], a[j] and x have only 1 bit, then if a[i]==0, a[j]==0, we can set x=1 then (a[i]^x)&(a[j]^x)=1, if a[i]==1, a[j]==1, we can set x=0 then (a[i]^x)&(a[j]^x)=1, if a[i]!=a[j], no matter how we set x, (a[i]^x)&(a[j]^x)=0. So we need to find (i, j) such that a[i]==a[j]. For general cases, we need to minimize (a[i]^a[j]) so that sum(t: 0<=t<k, the t-th bits of a[i] and a[j] are same)(1<<t) = (1<<k)-1-(a[i]^a[j]) is maximized. This can be processed using a trie, or sort a[i] and find the minimal a[i]^a[i+1].

G: For a single query (a, b, e), the maximum height of nodes on the path cannot exceed h[a]+e, which means, we can pass an edge (u, v) if max(h[u], h[v])<=h[a]+e. Therefore, we can sort queries by h[a]+e and sort edges by max(h[u], h[v]), then solving queries using dsu.

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

    F can be solved by property of xors:

    min(x^y, y^z) < x^z , for all non-negative integers x, y, z (x < y < z)

    so we can sort a, and find min xor of all a[i] ^ a[i + 1]

    sort(all(a));
    for(int i = 0;i < n - 1;i++){
        if((a[i + 1].fi ^ a[i].fi) < mn){
          mn = (a[i + 1].fi ^ a[i].fi);
          ans = mn | ((a[i+1].fi ^ ((1 << k) - 1)) & (a[i].fi ^ ((1 << k) - 1)));
          I = a[i+1].se;
          J = a[i].se;
        }
    }
    
    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Is there any intuitive proof of this property of xor?

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

        yes, you can read it here

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

        Find first bit so that: -it is in some of the numbers -it is not in all of them Then it's either in $$$y$$$ and $$$z$$$ or only in $$$z$$$ (because $$$x < y < z$$$). In both cases it can be seen that this bit is in $$$x \oplus z$$$ but not in $$$min(x \oplus y, y \oplus z)$$$. Later bits won't matter

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

      Why ans can be calculate by ans = mn | ((a[i+1].fi ^ ((1 << k) — 1)) & (a[i].fi ^ ((1 << k) — 1))); ?

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

        actually it is just: ans = (a[i+1].fi ^ ((1 << k) — 1)) & (a[i].fi ^ ((1 << k) — 1));

        at first we want to maximize some (a[i] ^ x) & (a[j] ^ x), now suppose we want to use some Kth bit up to k, then you can see that Kth bit have to be in both of a[i] and a[j], or doesn't appear in both of them,

        proof

        from above it is easy to see that it is efficient to minimize xor

        so we don't care about cases where a[i] has some bit and a[j] hasn't or reversed.

        there left two cases:

        |1. both a[i] and a[j] have some Kth bit

        to get this bit we shouldn't use it in our x, (1 ^ 0) & (1 ^ 0) == 1

        |2. both a[i] and a[j] have not some Kth bit

        to get this bit we have to use it in our x, (0 ^ 1) & (0 ^ 1) == 1

        since we can use all bits up to k, our x should contain all bits up to k, where a[i] and a[j] haven't them.

        |1. (a[i+1].fi ^ ((1 << k) — 1) taking all zeros from a[i] up to kth bit

        |2. (a[i].fi ^ ((1 << k) — 1) taking all zeros from a[j] up to kth bit

        |3. (a[i+1].fi ^ ((1 << k) — 1)) & (a[i].fi ^ ((1 << k) — 1)) combining zeros, where a[i]'s Kth bit = 0 and a[j]'s Kth bit == 0

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

    How do you thing is it possible to solve G if queries are online?

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

      Using persistent DSU

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

      Maybe we need to use some persistent data structures.

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

      For each edge $$$(u,v)$$$, let the cost of the edge be $$$\max(h[u],h[v])$$$. Then for query $$$(u,v)$$$ where $$$u\neq v$$$, the minimum of the maximum height of the nodes on the path is equal to the minimum of the maximum cost of the edges on the path. So we can build MST and use binary lifting to find the answer.

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

        I did try to write the binary lifting solution for G (feeling dumb after finding out doing it offline is much easier). I get a WA on test 4. I'm not sure whether my implementation is wrong or there indeed exists a counter-case that one of the best path doesn't lies on the MST.

        215605164

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

          Maybe my online solution can help you 215601542.

          I write the Kruskal's algorithm and build a tree to solve it.

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

      Build a kruskal reconstruction tree(or dsu tree) and find lca of the 2 nodes in each query

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

    minimizing xor of two elements can be done easier: sort the array, answer will always be the xor of two consecutive elements.

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

    F can be solved by max prefix for the binary presentation, there's maximum two unique numbers with the same max prefix. once we identify the max prefix, we can use a map to collect the ones that have the same max prefix, or we can just sort and compare adjacent elements.

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

Bad statement for most problems :(

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

Yes-NoForces!!

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

i feel language was bit difficult.

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

Learning tries was after all worth it saving me today. Problem F felt really good to AC :)

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

    It can be solved using recursion without tries

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

      can you share your implementation

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

        [submission:https://mirror.codeforces.com/contest/1851/submission/215630074]

        The key idea is to find two numbers with miminum xor. Let's try to find to numbers with common $$$k-1$$$ th bit. Divide the array into two so that in two arrays $$$k-1$$$ th bit is common in all numbers. Solve recursively for $$$k-2$$$ th bit and so on. If you put ending conditions correctly, this will work

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

    You just have to find optimal 'x' for all the pairs of adjacent elements of the sorted array of 'a', whichever pair gives max (ai^x & aj^x) is the ans.

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

      whats the reasoning behind adjacent elements ?

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

        I have an intutive explanation, for a bit to be included in the maximum answer either its not set in the two chosen indices or set in both, exploiting this information note that we can greedily start by trying to get the kth bit set first, so the whole array is divided into two multisets, one which doesnt have this bit set and other one has all the elements with this bit set, how to achieve this? Just sort the array, all the numbers which have kth bit set will be together, this holds(try to visualize this, it will make sense), Now if I want the kth bit to be set in the maximum answer, the final answer is going to be any two adjacent ( Just note that all the numbers with kth bit set will be consecutive, then among those all with k-1th bit will be consecutive and so on, and also numbers with kth bit set the numbers with k-1th wont set will be together, since thats just the nature of sorting), so if you were to write a bruteforce divide and conquer the final set will be some two consecutive numbers. Sorry if its lengthy but its a bit intutive to explain by writing

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

It was hard for me to concentrate on reading those problems, I liked it tho

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

D was awful, imho

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

I think my F is hackable

Submitted just after the contest got over.

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

Overall looks like a decent div3 contest, I have enjoyed solving A-E.

  • A — might be a little bit too much text for a div3A problem, but nothing too extreme
  • B and C — both are fine problems imo
  • D — some case work, nothing too dramatic, but I still have no idea how to prove my solution (also randomly got 50 additional penalty because I trolled myself again)
  • E — a problem about my favorite topic, I can see how this statement can confuse some people, but I myself probably couldn't phrase the condition of a graph being a DAG better
»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve E ?

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

    reread the statement and you ll see that if you draw the graph of elements (needing each other) it will be a dag -> just do a simple dp on it. my submission: 215587840

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

I thought that G was about finding a path, so that $$$max - min \le e$$$. Btw, would there be a solution if this was asked?

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

Lets Go Pupil here I come..........

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

rank 834 can add 39 to become expert?

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

Nice problems but bad statments for most of them , thanks anyway!

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

What the hell

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

Can someone share their solution to B, C and D.

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

    B — sort odd values and even values while not swapping odd and even with eachother, then check if array is sorted. C — you need to find shortest prefix that there are at least $$$k$$$ occurences of $$$c_1$$$, and the shortest suffix that there are at least $$$k$$$ occurences of last color. If first and last are equal, you just need to check that there are $$$k$$$ tiles with color $$$c_1$$$, else you need to check that sum of lengths of the found prefix and suffix is less or equal to $$$n$$$ D — didn't attempt

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

      Sort the array and compare it with the original array if both elements at same position are odd/even then its YES if NO then NO

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

problem E is an easy version of one of the provincial team selection test for NOI of Ahhui, China 2014(AHOI2014) problem. See in here:https://www.luogu.com.cn/problem/P4042

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

a

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

D was frustrating.

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

can some one explain this sample case for problem E

    4 2
    1 1 5 4
    2 4
    3 2 4 3
    0
    2 2 4
    1 2

how is the answer 0 0 0 0 , here

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

    Notice that Nastya already has unlimited numbers of potions 2 and 4 so the answer for 2 and 4 is 0. Also, to get potion 3 you can use potion 2 and 4 so you don't need any coins for potion 3 and the same for potion 1 so the answer is 0 0 0 0. Hope this helps!

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

    potions 3 can be obtained by potions 2(costs 0) + 4(costs 0) = 0

    potions 1 can be obtained by potions 2(costs 0) + 3(costs 0) + 4(costs 0) = 0

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

In problem A, is there any specific reason why Vlad cannot talk to the person on the same steps of the escalator??

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

    Two people with heights a and b can have a conversation on the escalator if they are standing on different steps It is given in problem statement

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

      I know bro.... it just bothered me becoz it is not so realistic

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

        ohhh, XD

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

        There is one type of escalators that has very narrow steps, that each step can only hold 1 person. I think the author is referring to that type of escalators??? :)

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

        It might be realistic because in some cities it is a known rule that people stand on the right and walk/run on the left side of an escalator. So, two people standing and talking on the same step will bother people in a rush.

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

    Vlad has bad breath.

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

Hello, could someone please help me figure out why my code is giving a runtime error on E? I don't usually use python https://mirror.codeforces.com/contest/1851/submission/215620727

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

    Maybe it's the python recursion limit/deep recursion issue, I know very little about python but I've seen similar kinds of questions regarding recursion/dfs traversal of a tree popping up here on codeforces.

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

      That must be it! I will try with stack, thanks for the tip.

      EDIT: That was it, AC'd now. Thanks!

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

    By default python has 1000 as the maximum recursion depth. Theoretically you've got to change it via sys.setrecursionlimit(), let's say sys.setrecursionlimit(10**5) and then it works, but in practice it will most likely give you memory limit exceeded on codeforces. So you just have to rewrite it without using recursion sadly, just directly use stack.

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

      Interesting stuff! Glad I used python this time, got to learn :D

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

Lol I didn't even understand the statement of problem E. Eventually, i just did wat-task-told-me-to-do + my guess and intuition and AC-ed :D

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

if problem E, the statement "Moreover, no potion can be obtained from itself through one or more mixing processes." is removed, I guess we need a scc to solve it?

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

    No, because if there is a cycle, then you:

    a) have one of the potions in the cycle which is trivial or

    b) don't have any of the potions. In that case, you will eventually revisit a node. Since a revisit is only possible due to a cycle, you will realize that the node came via a cycle and then can just buy the cheapest potion in that cycle.

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

Time to switch to hackforces

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

Problem statement is very hard

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

Thank you for having blank lines after the answer after every test case in Problem G. It made understanding the sample answer easier.

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

    Could you share your approach for G?

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

      Let $$$H$$$ be your current height and $$$E$$$ your current energy. If we go $$$x$$$ units up, your height changes to $$$H + x$$$ and energy changes to $$$E - x$$$. On the other hand if we go $$$x$$$ units down, your height changes to $$$H - x$$$ and energy changes to $$$E + x$$$. In both cases, the sum of your height and energy stays constant (equal to $$$H + E$$$, the sum of your original height and energy).

      Consider some query where you start from mountain $$$a$$$ with $$$e$$$ energy. This means that anywhere you go, the sum of your height and energy will be $$$h_a + e$$$. In order for your energy to stay non-negative, your height must not go above $$$h_a + e$$$. This means that you can go to any mountain $$$u$$$ with height $$$h_u \le h_a + e$$$ and you cannot go to any other mountains.

      Now, we can solve the problem in the following way:

      Consider the mountains and roads as an undirected graph. We will keep a DSU to tell which nodes (mountains) are reachable from each other.

      Sort all nodes $$$u$$$ in increasing order of $$$h_u$$$ and sort all queries in increasing order of $$$h_a + e$$$.

      When handling a query, we need to add all nodes $$$u$$$ with $$$h_u \le h_a + e$$$ and edges between them into the DSU. We can iterate over all nodes satisfying the above which have not yet been considered and add all edges going from those nodes to nodes with lower height to the DSU. After that, the answer to the query is YES iff nodes $$$a$$$ and $$$b$$$ are in the same component.

      Doing the above for all queries using a two-pointer approach is $$$O(n\cdot\alpha(n))$$$.

      Total time complexity: $$$O(n\log n)$$$ due to sorting.

      (slow) implementation: 215567991

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

Hope to become newbie after this contest

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

I couldn't debug G in time.Loved all the problems.

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

My thiscode gives correct output on my compiler and also on online compilers but somehow this is giving wrong answer on the Codeforces judge , what's the reason , please look into it.

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

    Your binary search could return -1 as index of array which is an undefined-behaviour.

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

I have doubt in problem statement of problem E.It is not mentioned whether cycle will exists or not.

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

    “It is guaranteed that no potion can be obtained from itself through one or more mixing processes.“

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

    "It is guaranteed that no potion can be obtained from itself through one or more mixing processes."

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

In F there is no need to know Trie , my solution is just greedy + binary search

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

Can anyone please explain the statement of problem e i still can't get it

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

    There are $$$n$$$ potions, each has its own cost. Each of the potions can either be bought or obtained by mixing some of the other potions. You have an unlimited number of $$$k$$$ potions which means you can use them for free. For each potion determine the minimal cost you should spend in order to obtain it.

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

i took this contest while in an airport lol

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

can someone help me understand why am I getting runtime error for this code (problem C round 888 div3):

#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k,w,flag1=0,flag2=0;
        cin>>n>>k;
        int l=k;
        vector<int> v;
        for(int i=0;i<n;i++)
        {
            int m;
            cin>>m;
            v.push_back(m);
        }
        int cnt=0;
        if(k==n && n==1)
        {
            cout<<"Yes"<<endl;
        }
        else if(v[0]==v[n-1])
        {
            for(int i=0;i<n;i++)
            {
                if(v[i]==v[0])
                {
                    cnt++;
                }
            }
            if(cnt>=k)
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
        }
        else
        {
            for(int i=n-1;i>=0;i--)
            {
                if(v[i]==v[n-1])
                {
                    k--;
                }
                if(k==0)
                {
                    w=i;
                    flag1=1;
                    break;
                }
            }
            for(int i=0;i<w;i++)
            {
                if(v[0]==v[i])
                {
                    l--;
                }
                if(l==0)
                {
                    flag2=1;
                    break;
                }
            }
            if(flag1==1 && flag2==1)
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
        }
        
    }
}
»
16 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Can E be solved using Dijkstra?

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

Why am I not in the standings?

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

    If you check the "unofficial" box, it shows me, but if you uncheck it, it doesn't.

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

      Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

      take part in at least five rated rounds (and solve at least one problem in each of them) do not have a point of 1900 or higher in the rating.

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

F is similar to 1721D.

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

waiting for editorial...

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

in D testcase 10:
prefix sum is: [13 21 36 42]
could not we assume initial array like this? [13, 8, 15, 6, 2]

[13, 8, 15, 6, 2] -prefix sum-> [13, 21, 36, 42, 44] and assume he lost [44]

what i am doing wrong?

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

    initial array is not a permutation. Your task is to find out if the given array can matches permutation. A permutation of n elements is an array of n numbers from 1 to n such that each number occurs exactly one times in it.

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

I was able to solve one problem, but still am unrated. Any reason for that?? (This was my first ever contest. Sorry if I'm being dumb)

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

    To qualify as a trusted participant of the third division, you must:

    take part in at least five rated rounds (and solve at least one problem in each of them)
    do not have a point of 1900 or higher in the rating.
    • »
      »
      »
      16 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Hey, one thing to clarify, does the triangle sign at the very right of the standings table mean the rating change?

      Another question, Will I get the ratings of my 5 contests added, or won't they be added? (After i become eligible for rating)

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

        It will be rated for you. Wait for the system tests to get over.

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

          but kgb said that I need to be qualified for Div 3, by participating in at least 5 rated contests and solving at least 1 problem.

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

            "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you."

            This is what's written immediately below in bold.

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

Boy was that a hard round. I could solve A and B in the first 40 minutes, and could only think of a DP solution for C :cry:

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

    Doesn't require DP though.

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

      I'm sure it doesn't; guess I've been practicing way too much DP (and not other things) haha

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

        Lol, initially, I too thought of a DP solution, seeing that it requires subsequence matching sort of problem. However, observing that it only requires checking of possibility of the pattern rather than optimization, I thought of the other solution.

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

Why the contest is begin shown unrated despite of being written "rated for less than 1600"?

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

seems that I have my first aked Div.3 contest :)

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

    I failed system test on problem D because of integer overflow, and missed the chance to solve all the problems during the contest :(

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

Who knows, has system testing already ended or not?

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

My solve E O(n) has Time Limit 14 bruh?!?!?!

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

Testing has finished.When will rating update ?

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

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

My solution for D fell on system tests because I used int instead of long long in one line where I forgot a_i <= 1e18 when I was writing it. This is really annoying, and I think that a test case like that should've been on main tests. But oh well, lesson learned, from now on I'm always using #define int long long

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

    So do I!

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

    Next message: "My solution got TLE on system tests, then I submitted it without #define int long long and got AC. I think that a test case like that should've been on main tests"

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

Reached Pupil after this contest that I'm happy

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

Hoorah! My rating became >1000 this round :D

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

This contest is quite good

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

Finally made it to Pupil after a year of hard-work 😊

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

https://mirror.codeforces.com/contest/1851/submission/216352004

wrong answer Jury has better answer (13) than participant (12) (test case 1)

Jury output: 1 3 14 My output: 1 3 12

(3⊕14)&(1⊕14)=(0011⊕1110)&(0001⊕1110)=1101&1111=1101=13

(3⊕12)&(1⊕12)=(0011⊕1100)&(0001⊕1100)=1111&1101=1101=13

What is wrong with 12 as 'x'?

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

Hello MikeMirzayanov,

Today I got a message from the system regarding the coincidence of my submission with my friend decltype_t submission.It is because of using common resource. In these codes we used the same templates for graph, topological sort, and for debugging. This is the proof for same. Graph template Topological sort template Debug template. However, the main logic is different.

We(Me and decltype_t) hail from same college and follow the same resources for practicing. We also have a combined repository. You can see the same here. I agree that it's my mistake that I didn't give the credit to the author for using his/her template. You can also check our previous graph or tree based question solutions where we have been using the same templates.

Thank you for providing this excellent platform.

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

my solution got skipped just because logic looks like others but i worked it after one wrong submission and just optimized it several times so not my fault it looks like others solutions

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

Attention!

Your solution 215580877 for the problem 1851E significantly coincides with solutions Milind_Sharma/215580877, fredreicc_/215618955. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

This is ridiculous, having same logic does not mean copied code, all of my submissions are now skipped. I have never copied a single code in any of my past contest. This is clearly a false positive.

I fail to see how my code is similar to the other user, also I submitted around 1 hour earlier.

Please take a look at the codes yourself and decide 215580877 and 215618955.

MikeMirzayanov Vladosiya

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

    MikeMirzayanov Vladosiya I have too been plagarised in this contest unnecessarily. I have even solved F problem that too within first 30 min. please check my code its not at all similar with others. I dont understand why I got plag. I had simple dfs call so that i can calculate the answer minimum just by topo sort. PLease see my code and give my ratings back. Its clearly wrong to plag someone who works hard. Kindly look into it and help me out.

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

'MikeMirzayanov Vladosiya Your solution 215615024 for the problem 1851E significantly coincides with solutions steve58/215601188 ...This is something not expected from codeforces the solutions by this guy and me is completely different I have used a simple graph topo sort which is having very common template of dfs call let me show you my code:

Here after taking the cost and making changes in its value depending upon free resources I had topological sorting in my code.I have used a simple dfs function which goes and checks its neighbours ahead then finally in ans array i stored the final minimum value of the cost and after topo sort value. My code is way different from one I am plagarized with . Please look in it and give my ratings back.


#include<bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() #define ll long long #define ld long double #define fuk return #define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());} #define pb push_back #define tr(it,a) for(auto it=a.begin();it!=a.end();it++) #define fo(i,n) for(int i=0;i<n;i++) #define fop(i,x,n) for(int i=x;i<=n;i++) #define forv(i,l,n) for(int i=l;i>=n;i--) #define nl <<endl; typedef pair<ll,ll> pl; typedef vector<ll> vl; typedef vector<bool> vb; typedef vector<ld> vd; typedef vector<string> vs; #define inp(v, n) for(int i=0; i<n; ++i) cin >> v[i]; #define opt(v) for(auto x: v) cout << x << ' '; cout nl const ll mod = 1000000007; const ll N = 2e5+10; #define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); ll bin_exp(ll a, ll b=mod-2, ll mod=mod){ ll ans = 1; while (b){ if(b % 2) ans = (ans * a) % mod; a = (a * a) % mod; b /= 2; } return ans%mod; } vl ans; ll n,k; vl c; vector <vector <ll> > v; void dfs(ll node){ if(ans[node]!=1e18) return; ll q=c[node]; ll tot=1e17; for(auto p:v[node]){ dfs(p); if(tot==1e17)tot=ans[p]; else tot+=ans[p]; } ans[node]=min(tot,q); return; } void solve(){ // fo(i,N) ans[i]=1e17; v.clear(); // fo(i,N) c[i]=1e17; cin>>n>>k; v.resize(n+1); c.resize(n+1); ans.resize(n+1); fo(i,n) ans[i]=1e18; ll p[k]; ll cost[N]; fo(i,n){ cin>>c[i]; cost[i]=c[i]; } fo(i,k){ cin>>p[i]; c[p[i]-1]=0; // ans[p[i]-1]=0; } fo(i,n){ ll f; cin>>f; ll k=0; fo(j,f){ ll p; cin>>p; p--; v[i].push_back(p); } } // fo(i,n){ // ll k=0; // ll f=0; // for(auto q:v[i]){ // f=1; // k+=cost[q]; // } // if(f) // cost[i]=min(cost[i],k); // } fo(i,n){ dfs(i); } fo(i,n){ cout<<ans[i]<<" "; } cout nl } signed main(){ IOS ll t; cin >> t; while(t--) solve(); return 0; }
»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello, MikeMirzayanov Today, I've received a message from noreply@codeforces.com that my code for the problems A and B are similar to the codes of the user kishorenanda. I really don't know this person and even where is he (or she) from. The codes are really short, so they could be similar to the codes of any other person who had just the same idea. But now all the solutions that I've sent to the system are erased from my official sendings. Rewatch my solutions, please. My solution for A: 215511238 My solution for B: 215514366