Codeforces Round #565 (Div. 3) Editorial

Codeforces Round #565 (Div. 3) Editorial

3 years ago, # | Problem E was little tricky, learned a lot. Thanks a lot for great contest!!

3 years ago, # ^ | can u explain problem E? I haven't understood the tutorial. thanks in advance!!

• 3 years ago, # ^ | Maintain a adjacency list, and then arrange the vertices by number of other vertices it is connected to(v[current_vertex].size) in a multiset or priority_queue (descending order). Pop to the priority_queue and mark the vertex as visited and push it in ans_vector. Iterate all the vertices to which it is connected as also mark them true but dont put these vertices in ans. (Because you need to maintain different colour). Do this until all vertices are visited. Ex: For a tree with 3 vertices and 2 edge: 1-2 and 2-3. Vertex 2 will have max size(2), push it in ans_vector and also mark 1,2 and 3 as true. Now you have an answer vector. If the size if less than equal n/2 print it otherwise print those which not not in ans_vector . This is because the set of vertices which are in ans_vector and which aren't both satisfies the condition of given problem (expect for size one) My submission: https://codeforces.com/contest/1176/submission/55381513 Though i was not able to do it in contest.

  • 3 years ago, # ^ | thanks!!

  • 3 years ago, # ^ | If someone is trying this approach, try this case. You will understand why pure greedy approach won't work. 1 9 8 1 3 2 3 3 4 4 5 4 6 9 7 4 9 9 8 Thats why we have to use either the found set or compliment of it.

    • 3 years ago, # ^ | Thanks for your testcase. I thought greedy was possible but I was wrong.

    • 2 years ago, # ^ | Thanks a lot for this test case. I was thinking greedy will work

      • 23 months ago, # ^ | ← Rev. 2 →   0 What do you exactly mean by greedy here, I just ran a dfs on the graph starting with coloring 1 with 0, its uncolored neighbors with 1 and so on, got ac link , then printing each all colored 0 or1 based on their size Am i missing something,

        • 19 months ago, # ^ | I meant to say that I was thinking greedy will work, but actually it won't work. And by greedy, I mean select the edge with maximum number of edges.

        • 12 months ago, # ^ | hey, I tried the same method as yours but the time taken by your code is much less than mine. I even modified my code to match yours but still, it's much slower can you help me to figure out why it's much slower than yours

  • 2 years ago, # ^ | please explain the condition when the ans.size() > n/2 if i understood it correctly you want the answer to be all the other remaining vertices. Why is it so?

    • 2 years ago, # ^ | This is because the vertices not present in ans vector will also satisfy the given problem statement. Consider coloring the vector in answer vector by color 1 and rest by color 2. Now reverse the colors. You can better understand by drawing some examples.

      • 2 years ago, # ^ | thanks for help.

      • 2 years ago, # ^ | please tell why i am getting a TLE on test 2, when i am using a priority queue. PS: the solution is not correct but i just want to know why TLE,it should give a WA

  • 21 month(s) ago, # ^ | Can you elaborate this If the size if less than equal n/2 print it otherwise print those which not not in ans_vector . with a test case. Since we are sorting in descending order why there is a need to do so?

  • 16 months ago, # ^ | For the future readers. Here it's not necessary to select nodes with highest priority based on their cardinality since we don't have to optimize the number of selected nodes. Here is my solution. my java solution

• 3 years ago, # ^ | Alternately, you can try the approach given in tutorial. Use BFS. Since BFS transverses the graph layer-wise, you can 'color' the alternate layers with color 0 and 1. Ex:For a tree with 3 vertices and 2 edge: 1-2 and 2-3. Color vertices 1 and 3 with color 0 and 2 with color 1. You would get two answers, the vertices those on even layers and the other on odd. Print the one with minimum size. This is a more cool approach :)

  • 3 years ago, # ^ | thanks for the explanation.very clear