Mythic07's blog

By Mythic07, history, 5 months ago, In English

In a recent Online assessment, i got this beautiful problem.

We are given a connected undirected graph. We have to find the number of triplets i, j and k (i != j != k) such that: on removing vertex j from the graph, vertex i and k becomes unreachable from each other.

1 <= n <= 1e5 (vertices) 1 <= m <= 1e5 (edgee)

We're supposed to utilize the concept of articulation points and 2-vertex-connected components. But couldn't deduce any proper solution.

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

By Mythic07, history, 12 months ago, In English

I'm searching for a problem which goes like this...

Given a graph with n vertices and m edges, all the vertices has some value associated with them. We as Player 1, makes the first move and removes exactly one vertex from the graph. The opponent as Player 2, makes a move and select any one component of their choice from the available ones. Then, we make our 2nd move and select any one component from the remaining ones (it is possible that there is nothing left for us). The score of any player is defined as the sum of values of vertices in their component.

Our goal is to maximize our own score, considering that the opponent plays OPTIMALLY.

Someone mentioned that they have seen this problem either on CF or LC, but I'm unable to find it. I have a solution that passed all the cases that i could think of but I want to be sure that this is the correct and optimal one.

Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it