I was solving https://community.topcoder.com/stat?c=problem_statement&pm=12692&rd=15698.
Editorial : apps.topcoder.com/wiki/display/tc/SRM+586
I could follow the editorial till the section on "Transitivity". I don't understand how using Floyd's algorithm ensures that all constraints are satisified and what exactly is Transitive Closure. I looked up the term in graph theory though I don't see how it applies in this scenario.
Any help regarding the above matter would be appreciated.
Do you know about google? wiki
As I've mentioned I've already looked it up though I don't get how does it apply in case of the given problem
Then I don't understand what you don't understand. Look at section "Transitivity":
When there are more than 2 nations, then we should also worry about constraints that can be inferred from the initial ones.
There is a relationship between three nations based on the pair-wise differences. For three nations i, j and k: Mik is the minimum allowed difference between k and i, Mkj is the minimum allowed difference between j and k. If j and i were too far apart, then it wouldn't be possible to fulfill the conditions Mik and Mkj, so we need the distance between j and i to be at most (Mik+Mkj). This updates the constraint Mij:
Mij=max(Mij,Mik+Mkj)
Correct me if I'm wrong. From Hikari9's comment and your reply I get the following
When we update the constraints we look at only three nations. We don't consider more nations, i.e. we don't do something like Mij = max(Mij,Mia+Mab+Mbc+Mcj);
Application of Floyds algorithm ensures that constraints involving more than 3 countries also hold
Transitivity means that if u, v are connected and v, w are connected, then u, w are also connected. Floyd's transitive closure is an O(n^3) algorithm that transforms an adjacency matrix into a connection matrix. Meaning, all transitivites are already "closed" with adj[u][v] true if they are connected rather than merely just sharing an edge.
I haven't read the problem statement yet but I can explain what a transitive closure is.
Given the graph G(V, E), the transitive closure Gt of G is a graph Gt(V, Et) where there is an edge
iff there is a path from u to v in G.