Insti Summer of Code
43 views
Skip to first unread message
Shantanu Thakoor
May 13, 2015, 1:58:54 PM5/13/15
to wncc-...@googlegroups.com
Hey everyone!
This summer, inspired by the prolific Lit Summer Blogs and quizzes, WnCC has decided to start a new initiative, that we call the Insti Summer of Code!
The idea is simple: to get the community of competitive coders in the institute discussing more on a common online forum, we'll get things started by posting a question as often as we can.
To keep things light and low-effort, solutions should be in the form of an algorithm explanation, and not source code (although coding the whole solution would be encouraged as an exercise, of course).
We'll post these questions a few times a week, and you'll have until the next day midnight to submit answers. After that, we'll release the winners along with their solution, and everyone can discuss it online.
Sound good? For more details, and the questions themselves, check out
https://wnccprocon.wordpress.com/2015/05/13/insti-summer-of-code/
Happy coding! :)
This summer, inspired by the prolific Lit Summer Blogs and quizzes, WnCC has decided to start a new initiative, that we call the Insti Summer of Code!
The idea is simple: to get the community of competitive coders in the institute discussing more on a common online forum, we'll get things started by posting a question as often as we can.
To keep things light and low-effort, solutions should be in the form of an algorithm explanation, and not source code (although coding the whole solution would be encouraged as an exercise, of course).
We'll post these questions a few times a week, and you'll have until the next day midnight to submit answers. After that, we'll release the winners along with their solution, and everyone can discuss it online.
Sound good? For more details, and the questions themselves, check out
https://wnccprocon.wordpress.com/2015/05/13/insti-summer-of-code/
Happy coding! :)
Shantanu Thakoor
May 14, 2015, 1:16:47 PM5/14/15
to wncc-...@googlegroups.com, shanu....@gmail.com
Hey,
We're closing the first question now.
The second question will be posted by midnight.
Venkateswarao was the first to comment with the correct answer; congrats!
For those who couldn't solve it, here's the solution:
We model this question as a graph. People are nodes, and "knowing" is a directed edge from A -> B is A knows B.
Now, Friendship is defined as A knowing B, or being friends with someone who knows B.
With a little intuition, you can easily see this as there being a path from A to B of directed edges, in the graph.
True friends are such that A and B are both friends of each other; which means that there is a path from A to B and from B to A.
In graph theory, a strongly connected component (SCC) is a set of nodes in a directed graph such that there exists a path from every node to every other node in the SCC.
So in this question, a "Group" of friends is simply a SCC in the corresponding graph.
In the end, the question reduces to finding the number of SCC's in a given graph.
This can be solved using multiple DFS's through the graph.
Consult Tarjan's algorithm for a simple efficient implementation.
Overall, the entire algorithm will run in O(V+E) time, which is O(people + "knowing relationships")
However, since the input is given as an adjacency matrix, merely reading in the input takes O(V^2) time.
Hence the solution runs in O(V^2).
Congratulations to everyone who solved it, and those who couldn't hopefully found a nice intro to a popular graph algorithm :)
Tomorrow's question will be significantly tougher, so be on the lookout for a challenge!
Happy Coding!
Shantanu Thakoor,
Manager, WnCC
We're closing the first question now.
The second question will be posted by midnight.
Venkateswarao was the first to comment with the correct answer; congrats!
For those who couldn't solve it, here's the solution:
We model this question as a graph. People are nodes, and "knowing" is a directed edge from A -> B is A knows B.
Now, Friendship is defined as A knowing B, or being friends with someone who knows B.
With a little intuition, you can easily see this as there being a path from A to B of directed edges, in the graph.
True friends are such that A and B are both friends of each other; which means that there is a path from A to B and from B to A.
In graph theory, a strongly connected component (SCC) is a set of nodes in a directed graph such that there exists a path from every node to every other node in the SCC.
So in this question, a "Group" of friends is simply a SCC in the corresponding graph.
In the end, the question reduces to finding the number of SCC's in a given graph.
This can be solved using multiple DFS's through the graph.
Consult Tarjan's algorithm for a simple efficient implementation.
Overall, the entire algorithm will run in O(V+E) time, which is O(people + "knowing relationships")
However, since the input is given as an adjacency matrix, merely reading in the input takes O(V^2) time.
Hence the solution runs in O(V^2).
Congratulations to everyone who solved it, and those who couldn't hopefully found a nice intro to a popular graph algorithm :)
Tomorrow's question will be significantly tougher, so be on the lookout for a challenge!
Happy Coding!
Shantanu Thakoor,
Manager, WnCC
Reply all
Reply to author
Forward
0 new messages