COMAPR06 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Devesh Jagwani

Editorialist: Devesh Jagwani

DIFFICULTY:

MEDIUM

PREREQUISITES:

2-SAT, Graphs

PROBLEM:

The aim is to find whether all the given ‘m’ number of games between two persons can be made ‘interesting’ where a game is ‘interesting’ if atleast one of the persons is ‘smart’. The persons can be a player out of ‘n’ competitors or his/her friend, where each player/competitor has exactly one friend, thus total of ‘2*n’ persons. It is also given that if we assume a player to be ‘smart’, than his/her friend should be ‘dull’ and the same reverse behaviour holds for a dull player also.

EXPLANATION:

This is the standard version of the 2-SAT problem where we have ‘m’ number of clauses, where each clause is an ‘OR’ operation between two boolean terms. These ‘m’ clauses are connected by ‘ANDs’. There are ‘n’ number of variables. A term in the ‘OR’ operation can be a variable or its negation.

We have to make the CNF (Conjunction of clauses) true by assigning some values to the variables. In other words, we have to assign some values, i.e. ‘smart’ or ‘dull’ (‘true’ or ‘false’) to the players such that all the ‘m’ games become ‘interesting’. It can easily be observed that the friend of a player is its negation.

Now, we will interpret the clauses as follows:

  1. For a game between ‘a’ and ‘b’, if any or both of the values is/are greater than ‘n’, then that value is considered to be the negation, since the friend of the ‘ith’ player is ‘(i+n)th’ player. E.g. Let ‘n’ = 10, for a game played between ‘1’ and ‘12’, we consider the game is played between ‘1’ and ‘~2’, since person ‘12’ is the friend of player ‘2’.

  2. From all the above clauses, we will form the implication graph. Then, by running the 2-SAT algorithm on the implication graph, we can determine whether there is a possible assignment of values to the boolean variables, such that the CNF is true (or all the ‘m’ games can be made ‘interesting’).

The time complexity for the algorithm is O(V + E), where V = 2n (number of vertices) and E = 2m (number of edges).

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.