Invitation to InfInITy 2k19

infinity%20poster%20png
Greetings from IIIT Pune,

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.

Setters - @abhi2402, @codingso101, @tchalla, @darshancool25

Contest Link - https://www.codechef.com/INFY2019
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.

6 Likes

Registrations can now be done on the InfInITy 2k19 Contest Page.

Contest Link - https://www.codechef.com/INFY2019

1 Like

please upload the editorials also for last 4 questions .
thanks in advance !!

1 Like

please upload the editorials also for last 4 questions .
thanks in advance !!

1 Like

Solution Outlines of the last 4 problems will be provided tomorrow, and if you have any doubts, feel free to ask them on this thread.

1 Like

Here is Solution Outline to

Not Today!

  1. Make bipartite graph with n nodes on one side, and a node for
    every possible answer on the other side
  2. Connect each pair of numbers to their 3 possible answers
  3. Find a maximum matching, if this is of size n we have a solution.

A Faceless Mission

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:

  1. Simple(not loops) edges are not adjacent.
    Then graph will have four vertices with odd degree so Euler path won’t exist.(Try out!)
  2. Simple edges that are adjacent.
    Graph will have exactly two vertices with odd degree so Euler path exists.
  3. 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.

4 Likes

What about these two problems ?
TORTURE, TREE OF HAPPINESS