We invite all the coding enthusiasts around here to show off your coding skills and solve challenging problems in the biggest coding event of Indian Institute of Information Technology, Pune , InfInITy 2k19. Get ready for 3hrs of problem solving and win great prizes.
Contest Link - Contest Page | CodeChef Date - 20th October, 2019 Contest Timing - 18:00 - 21:00 IST Contest duration - 3 hrs
Prizes - For Global Winners 1st - INR 5000 2nd - INR 3000 3rd - INR 2000
To be eligible for prizes, you have to be registered for the contest. You can register on the App.
Winners from IIIT Pune will get special prizes apart from the global winners.
For all previous questions and setter solutions please download the app here.
For more information, also visit the Infinity Website.
An Euler path is a path that uses every edge of a graph exactly once.
Let’s decide which edges are you going to visit once. All the other edges we can split into two. Then Wonderful Path in old graph is equivalent to an Euler Path in new graph.
Widely known that Euler path exists in graph when and only when there are 0 or 2 vertexes with odd degree. Consider following cases of mutual placement of edges that will be visited once:
Simple(not loops) edges are not adjacent.
Then graph will have four vertices with odd degree so Euler path won’t exist.(Try out!)
Simple edges that are adjacent.
Graph will have exactly two vertices with odd degree so Euler path exists.
One of the edge is loop.
Graph hasn’t any vertex with the odd degree(if another chosen edge is a loop too) or has two of them(if another chosen edge is simple).
Afterward you just need to apply combinatorics and count the number of Wonderful Paths.
Also, we need to check the graph to be connected by edges. If the graph is not connected then the answer is 0. We can do it using algorithms of DFS or BFS.
