AUG20 RGY what's your approach?

What’s your approach for Chef Thanos Wants Perfect Balance (RGY) problem in august long challenge as I don’t think they are going to provide official editorial and many people like me are waiting for it.

I did not have any absolute correct approach. I used some heuristics and optimizations.

  1. First of all I removed all linear chains of nodes which are having degree <= 2.
  2. While finding an even cycle I visited a node either when it has been visited lesser than three times or passing through that node had given me even cycle earlier.
  3. In order to find a new even cycle I started my dfs from the nodes which were connected to nodes of earlier found even length cycles. That gives a high probability that I will find another cycle near that area.
  4. Some more heuristics like that and I got 100 points.

I am eagerly waiting for the editorial and other’s solutions to learn about expected approach.

5 Likes

If we remove all even cycles from a graph, the resulting graph(s) must be a cactus, which has less than 1.5n edges. I could not however come up with a way to remove all the cycles.

1 Like

My approach -
First run a dfs and remove atmax n edges to make degree of all nodes even
since all degrees are even there exists https://mathworld.wolfram.com/EulerianCycle.html in the graph for each connected component.
We wont remove any edge from connected components with even no of edges.
For odd no of edges in a connected component I removed smallest cycle with odd length (can be simply found by looking at adjacent occurrences a node) from eulerian tour.
You will also remove atmax n edges in this step.

This way you can solve it by painting atmax 2n edges yellow.
This is enough for first 2 subtasks and with random shuffling of adjacency list and trying until no of yellow edges are more than 1.5n using just one while loop. I managed to get 100 points.

2 Likes

My approach:

  • Generate any spanning forest T, denote E’ = { edges not in T }, path(u, v) = { edges in path from u to v in T};
  • If there is a vertex u and two edges e1 = (u, v1), e2 = (u, v2) in E’:
    • If u, vi are not connected in T (I=1,2), insert (u, vi) into T;
    • Else, consider these 3 cycles: C1 = {e1} ∪ path(u, v1), C2 = {e2} ∪ path(u, v2), C3 = {e1, e2} ∪ path(v1, v2), at least one of them Ci has even length, color Ci using red and green alternatively and remove all edges in Ci;
      Repeat until each vertex has degree at most 1 in E’;
  • Color all edges in T ∪ E’ yellow, clearly |T| ≤ n-1, 2|E’| = Σ deg_{E’} (v) ≤ n, so |T ∪ E’| ≤ 3n/2 - 1.
    This approach needs to maintain the forest T, but I’m too lazy to implement an LCT, so I use brute force to maintain T, O(nm) time. Luckily the data is so weak that I passed this problem.
3 Likes

My approach:

  1. mark the degree of all nodes as even and odd.
  2. for each node X which has an odd degree find the closest node Y that has degree odd and remove all the edges from node X to Y. (color these removed edges as yellow)
  3. Repeat step 2 until all odd degrees are gone.
  4. Now find the Euler circuit of each connected component.
  5. If the # of edges in the Euler circuit is even. Color Red and Green alternatively.
  6. If the number of edges in the circuit is odd (let’s say n ) then there is exactly one fundamental cycle with odd size. let’s say we have Euler circuit as euler[]. then for any two valid indices, i < j. if euler[i] == euler[j] then there is a cycle from i to j of size (j-i) and remaining circuit will be of size n - (j-i). One of them must be even. Take the even one out and color it RED and GREEN. keep repeating with the odd size until you are left with just one single cycle of odd length.
1 Like

Your approach is similar to mine. :sunglasses:

1 Like