Need help in "Is this Jee" and "Conservative Graph" in International Coding Marathon

I tried going through codes of some Codechefers but couldn’t understand. Help me in the logic.
CodeChef: Practical coding for everyone - Is this Jee
CodeChef: Practical coding for everyone - Conservative Graphs

1 Like

Diffrentiate it by hand then Set min to 0 and max to pi/2. Do binary search, if slope is negative, go ahead, if slope is positive go behind. Then compute the value for f(x)

5 Likes

Got it Thanks

For conservative graph, first notice that distances must be additive, i.e, dist a to b + dist b to c = dist a to c. Hence, it is sufficient to store the distance with respect to one node per fully connected graph.dfs and check for every found node whether it has the same distance in this path or if it is not found then update the distance

2 Likes

got it!

1 Like

I didn’t get it, most of the people have use ternary search, can you explain ?

What if there are multiple points in the domain having slope=0 and the point having slope 0 can be a maxima,Also binary search may get TLEd if the point at which slope is zero is irrational

The slope is \frac{(2x+b)sin(x) -(ax^2 +bx+c)cos(x)}{sin^2 (x)}. Since it given b and c are positive, there may only exist one root within 0 to \pi/2; It is not true as we binary search only a 100 times per test case, which will not tle. 100 times will theoretically give an accuracy to 10^{-30}. The point having slope 0 is not a maxima as c is positive.

3 Likes

First notice that the graph may not be fully connected. It can be seen that it is sufficient to prove it for each fully connected subgraph. Knowing this, we first find a point we haven’t checked yet. We use this point as our reference point and iterate from there. Since the distance from each path should be equal, we can conclude that dist[a][b] +dist[b][c]=dist[a][c]. where dist[i][j] denotes the distance to go from i to j;
so to calculate any distance dist[b][c], we can simply do dist[a][c]-dist[a][b]. Now we start a search from a (our reference point). we check if we have already seen it. If we have not already seen it, then we initialise the distance, else we recheck if the distance from this path is equal. If it is not, then it is false, if it is we go on, until we have checked every node and edge. The method can be seen to be valid using recursion.
Here’s my uncommented solution
https://www.codechef.com/viewsolution/29703751

1 Like

Here’s my solution for “Is This JEE” question, instead of taking the derivative, I have used binary search and calculated f(mid - 0.000001), f(mid + 0.000001) to see which one is moving towards the maximum.

Here’s my simple solution
https://www.codechef.com/viewsolution/29705402

1 Like

But the function is not monotonic, why did it work ?

Thats just an obfuscated way of calculating the slope, you just check whether a slight increase increases or decreases the function

It has only a single minima in any graph in the given constraints. Otherwise it wouldnt work.

2 Likes

I wonder if it’s basically checking that for every cycle in the graph (taking edges in only one direction), whether the net sum is zero or not.

That is a valid method, but it would be difficult to find and iterate over all cycles.

Hi, I got your approach , even implemented it and got and AC too . but still I am not able to get that how are we ensuring that all the possible paths between any 2 nodes have been checked , I mean we are just performing a dfs and if we encounter a same vertex again then we compare it with the previous value distance value for it and return true or false accordingly .It would be great if you can please explain of how are we encsuring its correctness ?
COMMENTED CODE : CodeChef: Practical coding for everyone

Let’s start with one node. Is it conservative? yes. Now what does it mean to add a point. We must ensure that any paths through the new node also have the same distance. Now as a given fact, let’s assume the graph aside from it is conservative. So we must verify that any path passing through it is also gives the same distance. So we check every pair of ways possible through this node, since we are searching from every node in our previous graph, and checking that distance is equal, and then we are checking that every node reachable from the new node still has the same distance when we search from it. The order may not be retained, but we are checking all of these conditions, so the approach is correct.

1 Like

Oh , nice I got it now thanks bro