What's wrong with my approach for CHGORAM?

help
1

Even my Brute Force approach was not working. This is what I thought - Let’s take every triplet i, j, k by naively iterating over all the possible triplets i, j, k. Next we determine if all the 3 nodes in the triplet are connected to each other(that is, if every node in the triplet is reachable from every other node). This can be easily done by taking the sum graph[i][j], graph[j][k] and graph[i][k] and finding if it equals to 2, here graph[i][j] is the Adjacency Matrix representation of the graph, where gaph[i][j] is set to 1 if nodes i and j are adjacent or 0 otherwise.
Next, if all the nodes are reachable from one another then we find which among the three is the parent of the rest, by parent I mean the node which is adjacent to both the other two nodes. Let’s say for example, j is our parent node here and i and k are other nodes of this triplet and reachable from one another(via j). So, finally we check if either i, j, k or k, j, i follows the order specified in Ramsay’s Restaurant Sequence and if it does we increment the answer by 1.
I tried my code on sample cases made by me and I was getting the expected result but WA on submission. Here is my submission- CodeChef: Practical coding for everyone

So, can anyone please-

  1. Explain me what’s wrong with my approach?
  2. The optimal approach with a step-step explanation.
2

By “adjacent”, do you mean “directly connected by an edge i.e. a path of length 1”? If so, this is not what the question asks for - it asks for triples (a1, a2, a3) where a2 lies on the shortest path between a1 and a3, which can be of any length (as long as it fits in the graph, of course!)

I haven’t finished writing the step-by-step documentation yet (the comment inside “main” just kind of “fizzles out” at the moment), but the code in my solution might give you some hints:

https://www.codechef.com/viewsolution/25921024

Hopefully I’ll finish writing it up completely in the next few hours.

1 Like
3

Yes, by adjacent I indeed meant directly connected by a path length equals to 1. Thank you. Would look at your solution. Waiting for the official editorials.

1 Like
4

Ok, I’ve simplified the approach somewhat, but I’m still finding it murderously hard to come up with a good description of the high-level approach.

Here’s a rough and un-proof-read version:

https://www.codechef.com/viewsolution/25925347

If interested people could have a read of that and let me know which bits are unclear (or flat-out wrong ;)) that would be appreciated :slight_smile:

@jhon113

2 Likes