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

Автор Bazoka13, 6 месяцев назад, По-английски

Hello, Codeforces! Or, as we like to say in Servalish (created by Serval): High-low, Cold-for-seize!

We are glad to invite you to participate in Codeforces Round 947 (Div. 1 + Div. 2), which will start on 25.05.2024 17:35 (Московское время). The round is a combined round and will be rated for everyone.

The problems are prepared by Atomic-Jellyfish, Nerovix, SanweiTreap, Serval, Toxel, jhdonghj112 and me. You will be given 9 problems to solve in 3 hours. Scoring distribution will be announced later.

We would like to thank everyone that makes this round possible:

We recommend you to read the statements of all problems. Good luck & Have fun! (=・ω・=)

A no-prize quiz

UPD: Scoring distribution: 250-500-1000-1500-2000-2500-3000-4500-6000

UPD2: Editorial is available now.

UPD3: Thank you for your participation in this round! Congratulations to the winners:

  1. tourist
  2. Golovanov399
  3. maspy
  4. hos.lyric
  5. Um_nik

And the first solves on each problem:

UPD4: Chinese editorial is available now.

Photo of reviewer and some authors:

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

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

About the quiz: First of all, not genshin impact.

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

Plea vet, cold-for-seize! Water she wall Serval days. Wall shall Servalish. Good Luck & Have Fun!

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

    Translation: Hi (maybe Russian), Codeforces! I'm Serval (Japanese) and I speak Servalish (Chinese). Good Luck & Have Fun! (English, obviously)

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

Wasn't it supposed to be CodeTon Round 9?

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

As a tester, jhdonghj112 is so handsome.

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

Omg errorgorn Coordination !

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

I hope he played Dota 2

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

jhdonghj need better camera!

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

As a tester,I sincerely hope that all the participants would enjoy the magnificent problems while competing in this round~

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

60 TESTERS, is that a codeforces record?

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

geometry dash?

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

As a tester, wish you enjoy the contest.

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

Acknowledge the hard work of the organizers and contributors.

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

It's gonna be a math round isn't it?

I'm gonna be really disappointed if Jellyfish didn't play getting over it with bennett foddy this time around.

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

A GIANT TESTER ARMY...

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

So many testers 😮

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

How come it is div1 + div2 when it seems like the sponsor (codeton) has backed out?

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

Can't trust the unrated testing fsfdgdg smashing 3000+ questions while being unrated ;_; .

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

    Bruh I'm his classmate

    Actually he's in NOI2024 Sichuan Provincial Team. He just has no time to take part in CF rounds cuz he usually lives in school

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

Best of luck all the participants.

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

Did anyone recieve their prize from the last CodeTON Round? (Round 8)

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

Tester count in this contest are more than entire Vatican City population.

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

CF is lagging a lot , is anyone facing the same issue ?

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

hope i can solve A or B :D

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

As a tester I highly recommend you writing this round!

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

my div1+2 history isn't good, hope to change it today

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

This round is clashing with leetcode biweekly Dominater069

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

Luck good¡¡¡

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

Excited for the 6000 rating problem

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

Gellyfish looks just like the man in the famous painting The Son of Man by Magritt.

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

Mochaforces

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

Is everyone waiting to be evaluated? Or CF now only assessing the questions in this contest right now.

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

"Jellyfish usually got ideas from games, so what game did Jellyfish play this time?"

My answer for the no-prize quiz is
»
6 месяцев назад, # |
Rev. 5   Проголосовать: нравится +11 Проголосовать: не нравится
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится -21 Проголосовать: не нравится

    Ohh boy and here I was thinking why many of the solutions for task C looked very familiar with each other. Even some experts have cheated from the GFG code. Hope that they will be severely punished when the system testings are being done to find copied codes. I would like to draw the attention of the moderators to make sure that the solution codes for problem C are checked against this particular code to prevent any mass cheating

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

Thanks Xellos for the hint for C: Chamo and Mocha's Array

I have added hints and thought process for this problem on CF Step

Here's my code for reference.

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

lesson learned from today's contest: never wasting time on ChatGPT.

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

Stuck on F for 2h, please tell me there's something elegant and it's not some bitset crap

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

    Suppose $$$v[0] = \lbrace 0 \rbrace$$$, so that it is of length $$$2^n$$$.

    Solve recursively, on a given $$$v$$$ of length $$$2^m$$$:

    • If $$$m = 0$$$, then it is solveable only if $$$0 \in v[0]$$$.

    • If $$$m - 1 \in S$$$, then you can reduce to a new vector $$$u$$$ such that $$$u[i] = v[i] \cap (v[i + 2^{m-1}] - 1)$$$.

    • Else, reduce to $$$u[i] = v[i] \cap v[i + 2^{m-1}]$$$.

    Then solve recursively for both $$$u$$$'s (both of length $$$2^{m-1}$$$), while carrying your decision. While this may seem naive, the time complexity is $$$O(n2^n)$$$.

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

      Okay that is fully my bad — I had this but did not calculate the complexity correctly. Thanks.

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

    u can try merging the constraints as u fix one bit at a time, eg if you fix the 0th bit to be on, then u can combine all x with x+1 (since both of them share all other bits so the other bits must satisfy both their constraints), thus at each level, the array shrinks by 2, while the number of calls double by 2, so in the end the complexity is n2^n

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

How to solve F?

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

How to solve E ?? :(

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

    How to solve E without TLE you mean?

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

      Solving usually does mean without TLE. I don't think a solution which gives TLE is considered "solving".

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

    My logic: You only need two things no of connected components if we only consider the black nodes in the tree .We only need to check further if the components is 1.

    Now to know if the conn comp is a chain you only need to see if the distance between the 2 farthest nodes in the conn comp is equal to the number of black nodes in the tree, in a chain these two farthest nodes are leafs i.e. nodes connected to only 1 black node.

    To maintain both conn comp and leafs, you only need the number of black neighbours of a node. Now i did this using segment tree on bfs ordering, since changing the colour of a node only affects its children and parent. My sol is $O(q log^2(n)) but there might be a better way.

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

      root the tree end points of the chain are the black nodes which have no black child so chain is possible if the count of such nodes are <= 2 if count is 1 chain is possible if count is 2 let l be the lca(u, v) chain is possible if total no. of black nodes is equal to dist[u] - dist[l] + dist[v] - dist[l] + 1

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

        But how are you finding the leafs? My approach was qlog^2 due to the leafs

        • »
          »
          »
          »
          »
          6 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          apply dfs make parent and cnt array, cnt array stores no. of black child for each node so if the black node have 0 black child it can be end point so store all these nodes in a set. now in each query you can update the set in logn and cnt array in o(1) time by some case work
          
»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can't figure out how to optimize by O(qlog^2) sol to pass in E, Someone help Submission, The main time is due to the call of query_r2 func

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

is problem D DP on Tree?

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

    A little bit of DP, but the main idea is adhoc anyway

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

    No, you use DFS to calculate the distance from node A to node B — they should walk towards each other, and will first meet each other at some node C. After that they "travel together", and the number of steps is equal to the number of edges times two, minus the (distance from meeting point C to some furthest node D). Because it's best to "end" the trip in that node from which you don't have to return — so you make this ending node D the farthest one.

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

      When both of them travel together does the node color directly go from white to blue?

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

        Yes (is mentioned in the question)

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

          But it is only mentioned for initial nodes.

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

            the order they move is in the description; first P_A moves (and marks the vertex red), then P_B moves (and marks the vertex blue)

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

      What if it's a-> f -> g -> b they will meet on g or f I know it's impossible too meet in one of them but what is the solution in that case?

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

      if dist is odd ..

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

first time solved E i am literally shivering :)

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

problem-B is toxic, thought too much for that simple thing.

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

    How to solve it ?

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

      If a number $$$small$$$ divides $$$b$$$, then it is true that $$$b$$$ should be bigger than or equal to $$$small$$$.

      Think about the minimum element of the array. If you don't select it as the candidate, no element would be able to divide it. Hence, one candidate is locked. I'll leave out the analysis for the second candidate as an exercise.

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

      sort list. All items must be divisible by first item(F1) or the first item not not divisible by F1.

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

      You need to make a simple observation:

      In order for some $$$a_k$$$ to be divisible by some $$$a_i$$$ , $$$a_k \geq a_i$$$, so we need to choose the smallest element to be our $$$a_i$$$.

      We then mark every multiple of $$$a_i$$$ as visited, this can be done in plenty of ways.

      You will have a new array of visited and unvisited elements, you choose the minimum of the unvisited elements, let's call it $$$m$$$. Loop through the array, skip the visited elements, if one unvisited element is not multiple of $$$m$$$, the answer is No.

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

      You need to find 2 minimal elements in the array such that:

      First element is always the minimum of the array(because if it's not minimum and other number is chosen, the minimum won't be divisible by a bigger number)

      Second element is always the minimum element in the array that is not divisible by the first minimum.

      For example array: 4 2 15 5 6

      First you find minimum — 2 in this case, after that second minimum is 4, but it should not be chosen, because then we can not check on 15 correctly, 4 is divided by first min without remainder. So the second min is chosen to be 5 and then we are going to check if all the array elements divide by those two minimums we chose.

      TC: O(N)

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

    what was it?? I am still unable to find error in my code.262564497

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

      You just assumed that after sorting the array the first and the second element are the required i and j. Assume the case as Array=[2,4,5,6,10,15] where your code.But here the answer is yes with i=1 and j=3.

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

      Your code fails on the testcase, n = 3, 2 4 7

      Correct answer: Yes

      Your answer: No

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

In E I used CD with HLD to find out if all black vertices are connected. But I have no idea how to understand if all of them lie on a path

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

    Same, which got me TLE on pretest 13

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

    after rooting the tree end points of the chain are the black nodes which dont have any black childs so you have keep track of all black nodes which have no black child

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

    Connectivity can actually be checked in a much simpler way: The black nodes are connected iff there is exactly one black node that doesn't have a black parent.

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

      Thanks. My mistake was thinking about all degrees instead of parents only

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

To solve $$$E$$$ I am thinking if any way I can maintain number of black nodes having adjacent black nodes of size 2 and number of black nodes having adjacent black nodes of size 1 , am I thinking in the right direction?

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

G made me lose the little mental sanity I had.

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

One of my worst contest

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

For E, I was thinking of maintaining the degrees of all black vertices . If it is of the form {1, 1, 2, 2.....2}, then it forms a path, considering the corner case for #black vertices=0, 1, 2 . Am I thinking in right direction?

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

    Would be difficult to maintain. A single query can change up to N values (all neighbors).

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

    I had the same idea during contest and managed to get $$$O(n\sqrt{n}log(n))$$$, complexity but it was to slow. You can maintain big/small vertices and recalculate "black-degree" for every vertex every $$$\sqrt{q}$$$ operations

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

How solve G? I know there is a bitset solution but I don't know how to optimise it

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

    I ended up with WA7 so I may be wrong, but I believe most of it is correct (and I probably have a bug):

    • If none of the strings contain asterisks, then it is easy.

    • If both contain asterisks, then check both prefixes and suffixes for equality, until you reach asterisks. If prefixes and suffixes were equal, then it should be "Yes".

    Assume now that $$$s$$$ has no asterisks, and $$$t$$$ has at least one. Remove equal prefixes and suffixes, so that $$$t$$$ begins and ends with asterisk. If all of $$$t$$$ is asterisks, answer is "Yes".

    Now, you need to take every substring of $$$t$$$ between a pair of asterisks, and match it to the first substring of $$$s$$$ that matches it, greedily.

    It's a classical algorithm to determine whether a string can be anothers' substring, when both may contain '-' symbols, using fft in $$$O(n \log n)$$$ where $$$n$$$ is the larger of those lengths.

    Now, to find the first position in which a substring of $$$t$$$, of length $$$m$$$, matches in $$$s$$$, starting from a given index $$$i$$$, you can do an exponential search:

    Check if the substring appears in the substring of $$$s$$$, starting at $$$i$$$ of length $$$m$$$. If it isn't found, increase to length $$$2m$$$, and so on until it is found.

    The total complexity should be $$$O(n \log^2 n)$$$.

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

      It's $$$O(n \log(n))$$$ because the moment you find something in string of length $$$2m$$$ you at least jumped ahead $$$m$$$ characters. And you did at most twice as big wildcard matching as the amount of characters you jumped ahead. So it's $$$O(n \log(n))$$$ amortized.

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

378QAQ is this the name of elon musk kid?

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

IMO, F << E

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

    I have the opposite opinion. In fact I found that D, F >> E.

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

      In E I was writing something like dynamic connectivity(dsu) offline. But in F very simple divide and conquer, standard idea for tasks with bits.

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

Thanks for the contest! I'm looking forward for Editorial. Problems were quite good!

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

For the first time I hacked someones soln

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

Solved problem E, but the contest ended just as I was about to submit it. I was so close to a huge positive delta! :(

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

    Can anyone please check if my solution for problem E is correct? I can't wait the system to finish and submit it.

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

How to solve D?

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

    Observation 1: The blue color chess piece needs to visit all the nodes once, after it reaches a node colored red. It needs exactly this, no more or less.

    Observation 2: The red and blue color piece meet most quickly if they move towards each other.

    Solution: Find the midpoint where they meet using DFS/BFS. From this point as the starting point, find the minimum cost to visit all nodes at least once, again using DFS/BFS.

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

      For calculating the minimum cost to visit all nodes at least once, you can show that this is equal to 2*(number of edges) - (distance to farthest vertex from starting point). (Why?)

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

      I was doing exactly this :( I found the mid point and tried doing DFS, two things I was stuck at when they are are at odd distance and in dfs i had overcounting when i had to stop just when dfs ended.

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

      Or find max path to any node from meeting point. In this case it will be one of the 2 endpoints of the diameter.

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

Last 2-3 problems might be kept for another round.

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

Nice contest

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

Is this approach intended for E:

-> Maintain the smallest depth (i.e highest) black node.

-> For every node, maintain a set of it's children which are black.

-> Now for the highest black node, if the count of it's black children is greater than 2, then the answer is NO.

-> Then for it's (<=2) children, we can find the deepest black nodes in their respective subtrees using subtree max queries, say U and V.

-> Now we just have to check if all nodes on the path b/w U and V are black, and dist(U,V) + 1 = total no. of black nodes.

-> Path sum queries with updates is a standard cses task

If this is indeed the intended approach, it's a garbage task

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

Had no time to submit D.

Logic I used was: if the distance from nodes is 1 they won't meet at the same point so return (n-1)*2

else I considered that optimal was for Pa and Pb first meet, then with DFS find the longest path to reach the ending point of the graph from meeting point (Because thought it was optimal not to "go up" from the ending point of the graph) int maxPath = CalculateMaxPath()

Considered that other edges are visited twice (going up also counts as a step) and calculated

(n-1)*2 — maxPath + minimumstepsNeededToMeet

What am I missing in logic?

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

    Here's what I did (passed all pretests):

    • Calculate the midpoint node between $$$a$$$ and $$$b$$$. Let this node be $$$m$$$. (In case the distance between $$$a$$$ and $$$b$$$ is odd, take the point further away from $$$b$$$).

    • If the distance between $$$a$$$ and $$$b$$$ is $$$d$$$, moving $$$B$$$ to $$$m$$$ takes $$$\lceil \frac{d}{2} \rceil$$$ steps.

    • Answer will be the above steps + minimum number of steps to reach every node from $$$m$$$.

    This worked but I'm not able to prove why it did. Just went with intuition.

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

      had exact same idea but couldn't solve in time

      maybe "minimum number of steps to reach every node from m" is what really matter

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

    This seems correct: (n-1)*2 — maxPath + minimumstepsNeededToMeet

    Why do you have an extra case? In case distance between nodes is 1, you still need to use the same formula. (minimumstepsNeededToMeet = 1 in this case, and you will have to still subtract maxPath)

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

Can anyone prove why checking subarrays of size 2 and 3 are enough for C?

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

    I guess because increasing the subarray length won't increase the median, we are not limited in minimum steps count so if we find maximum medians of subarray of length 3 we can eventually make the whole array consist of that median values only. suppose [3, 2, 2] subarray from some longer array. no matter if the first element is greater or less then other two equal elements, the median will be still "passed" to that third value too, that proves the fact that eventually the whole array can be filled with median values that we found in subarray length of 3.

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

    consider some segment containing a[i]. for a[i] to be median, there should be at least one element in this segment >= a[i]. lets prove that one is enough. consider, there are at least two of them. if they are on the same side from a[i], than if distance between them >= 1, the second one doesn't change anything. otherwise, use those two consequent elements as a new segment, with a bigger median. if those two elements are on different sides, just use on of the sides, it also won't change anything. So, you just have to check that there is an element >= a[i] in 2-proximity

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

Anyone with D's Approach???

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

    Go to middle point if odd then get at one edges distance.Then find the deepest node so that you do not have to return from the deepest nodes.Thn count -maximum+(n-1)*2.

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

Video Editorial for (A, B, C) YOUTUBE VIDEO LINK --Click Here

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

Can anyone explain me D, when point A and point B are not overlapping and say d distance apart and d is odd.

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

    Because wen d is odd then they will be separated by one edge .Think like this that red goes over all edges and at any times blue is one step behind as red finsihes blue will be one step behind.So one step more to complete.That is steps to be one edges away+ one step to cover the delay for the red

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

Some fun facts about this round:

  1. The original constraint of problem G was $$$5\times 10^5$$$ and 3s. However, I managed to squeeze a bitset solution inside the time limit during testing. That's why the constraint seems so insane in the current version.

  2. If you ever mistyped and corrected your mistake after testing the sample in problem D, it's also because of me. The original sample was (probably not intentionally) so weak that even if you didn't read from input correctly, you could still pass it. I got stuck here and wasted too much time on a stupid mistake during testing :(

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

solution of Problem $$$D$$$ is the greatest love story if distance between $$$a$$$ and $$$b$$$ is even and greatest simping story if distance between them is odd

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

Editorial for E is mind-blowing and elegant. Maybe we over-think it because it's an E not a B/C lol.

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

In fact, 2745518585 passed E 20 seconds before maspy, so the first solve on E is 2745518585.

262542481

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

    I don't know why people are downvoting this comment but this comment is actually true , the reason why maspy appears before the other guy in terms of judging time because when sorting based on judging time second parameter is ignored and sorted based on minute first then based on handle name , as both of them have same value in minute parameter then they were sorted based on handle names and it looks like any handle name starting with digit comes later after handle names starting with letters

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

[submission:262597281]As, you have stated that a submission coincides with some others, I don't know how significantly, it matched, because I used ChatGPT for this question, I admit this much, so this maybe the reason that it may have similarity, otherwise, I haven't copied anyone's else code

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

are the ratings rolled back , didnt get any notification but my 2 contest have not been counted what's the issue

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

Is it possible to solve Problem C using binary search? Because it appears like a max-min problem

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

How div1+div2 is different from div 1 and div 2 contests?