Please help me to solve this question.
https://www.codechef.com/DI17R107/problems/CHEFSOCD
What contest is this? And why are all problems unsolved? 
It was a past contest used for recruitment into Directi.
No submissions in any of problems?
I think its a “mirror” of original one. I remember I saw this contest back before as well and that time there were submissions. It has got to be a mirror/replica of original one I guess.
1 Like
I am not completely confident that this is a correct solution, and I have no way to verify since the problem is not available for practice, so everyone is welcome to try and break it or correct it.
It’s not specifically mentioned in the statement, but I suppose the imperfect cake is heavier/lighter than the perfect cakes which all weigh the same. For convenience assume all > comparisons have been converted to < comparisons by swapping the elements of both sides.
Let S_{L_i} be the set of cakes to the left of the < sign in the i^{th} comparison, and S_{G_i} be the set of cakes on the opposite side of that sign. If the comparison is = instead, the cakes on both sides belong to the set of perfect cakes S_P. Now let S_L be the intersection of all S_{L_i}, and similarly S_G be the intersection of all S_{G_i}. The imperfect cake can be in either of these two sets. Any cake that lies on the left side of one < comparison and to the right of another must also be perfect, so add all such cakes to S_P. Now remove all cakes from S_L that belong to S_P, and likewise for S_G.
Simply put, now S_L is the set of cakes that occur to the left of every < comparison and never to the right, barring the cakes we already know to be perfect, and it’s similar for S_G. If exactly one cake remains in either S_L or S_G, then that cake is imperfect. If both S_L and S_G are empty, then look at the cakes not present in any comparison. If there is exactly one such cake, that is once again the imperfect one. In all other scenarios, there is insufficient information to determine the imperfect cake.
1 Like
It boils down to mst (kruskals algoritm)…
1 Like
@dishant_18 think of all the OK roads as existing edges and the broken roads as edges that may be added. The aim is to make the whole graph connected. Bunch each connected component into a single vertex. Now consider all broken roads that connect different components. The answer is the minimum spanning tree constructed from these edges and the modified vertices.
@beginner_1111 yes, Kruskal’s algorithm is one way to solve the MST. There are other algorithms too.
2 Likes