Bazoka13's blog

By Bazoka13, 4 weeks ago, In English

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 May/25/2024 17:35 (Moscow time). 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:

  • Vote: I like it
  • +604
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +37 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +79 Vote: I do not like it

Wasn't it supposed to be CodeTon Round 9?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    They probably don't have money. From Last round didn't come money

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

As a tester, jhdonghj112 is so handsome.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

Omg errorgorn Coordination !

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

I hope he played Dota 2

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

jhdonghj need better camera!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I think its hp's fault, they should equip a better camera on laptop lol

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Not only hp, general problem for every single laptop on earth

»
4 weeks ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

60 TESTERS, is that a codeforces record?

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

geometry dash?

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

As a tester, wish you enjoy the contest.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Acknowledge the hard work of the organizers and contributors.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

A GIANT TESTER ARMY...

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

So many testers 😮

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck all the participants.

»
4 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hope i can solve A or B :D

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

As a tester I highly recommend you writing this round!

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

This round is clashing with leetcode biweekly Dominater069

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Luck good¡¡¡

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited for the 6000 rating problem

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Mochaforces

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

My answer for the no-prize quiz is
»
4 weeks ago, # |
Rev. 5   Vote: I like it +11 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      Codeforces policy allows you to use code written before the contest.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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)$$$.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve F?

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve E ?? :(

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    How to solve E without TLE you mean?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it
          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
          
          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ohh right, black child means i only need to update parent thanks.

            • »
              »
              »
              »
              »
              »
              »
              9 days ago, # ^ |
                Vote: I like it +12 Vote: I do not like it
              Spoiler
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is problem D DP on Tree?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yes (is mentioned in the question)

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But it is only mentioned for initial nodes.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            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)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Let a stop at f and b stop at g, then b follows a.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That's what I did but it didn't work maybe there is something wrong with my implementation I will wait and see the tutorial.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      if dist is odd ..

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

first time solved E i am literally shivering :)

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve it ?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

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

      Correct answer: Yes

      Your answer: No

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same, which got me TLE on pretest 13

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    you only have to care about black nodes which have no black child

»
4 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

G made me lose the little mental sanity I had.

»
4 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

One of my worst contest

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    hint
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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)$$$.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

378QAQ is this the name of elon musk kid?

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

IMO, F << E

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

For the first time I hacked someones soln

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -13 Vote: I do not like it

    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
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

C is quite similar to 1349B - Orac and Medians

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Nice contest

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, kinda similar what I have I guess..

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone with D's Approach???

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

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 :(

»
4 weeks ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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

262542481

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

[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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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