**Problem Link:**

https://www.codechef.com/CDSO2016/problems/TRAL
**Difficulty:**

Medium
**Problem :**

There are two cities namely Truthtown and Liarville on the distant isle of Googlia. People living in Truthtown always tell the truth and people living in Liarville always lie. While exploring the isle you can run across a group of N inhabitants, and you want to figure out which city each one came from.
To make life simpler, you begin by numbering these people 1 through N. You then question each person, and record their M statements in the short-hand described below.

Short-hand Meaning

i T j Person #i says, “Person #j is from Truthtown.”

i L j Person #i says, “Person #j is from Liarville.”

i S j k Person #i says, “Persons #j and #k are from the same city.”

i D j k Person #i says, “Persons #j and #k are from different cities.”

Your task is to deduce which city each person came from. It is guaranteed that there will always be at least one solution.

For example, suppose you were given the following statements:

1 D 2 3, 1 D 2 4, 1 D 3 4, and 2 L 1.

Then, you could reason as follows:

• There are only two cities, so persons #2, #3, and #4 could not all have come from different cities.

• Therefore, at least one of person #1’s claims must have been a lie.

• Therefore, person #1 is from Liartown, and all of his claims must have been lies.

• Therefore, persons #2, #3, and #4 must all be from the same city.

• Person #2’s claim is true, so he must be from Truthtown.

• Therefore, persons #3 and #4 are also from Truthtown.

**Explanation:**

A good first step for this problem is to sit down and figure out exactly what scenarios can lead to

each statement being made. For example, if you see 1 T 2, then one option is that both person

#1 and person #2 are truth-tellers. There is one other option though, which is that both people

are liars.

So let’s just write everything down. In the table below, the first three columns correspond to the

scenario where persons #i, #j, and #k are truth-tellers or liars as shown. The remaining columns

indicate whether the given statement could have been made:

#i #j #k i T j i L j i S j k i D j k

L L L Yes No No Yes

L L T Yes No Yes No

L T L No Yes Yes No

L T T No Yes No Yes

T L L No Yes Yes No

T L T No Yes No Yes

T T L Yes No No Yes

T T T Yes No Yes No

So what does this table tell us? Let’s look at i S j k. As the table shows, this statement is

equivalent to saying exactly 1 or 3 (i.e., an odd number) of persons #i, #j, and #k are truth-

tellers.

If you are familiar with modular arithmetic, this is when inspiration might hit. Let’s make variables

x_{t} for each person t where x_{t} = 1 if the person is a truth-teller, and 0 otherwise. Then the

statements can be summarized as follows:

i T j iff x_{i} + x_{j} is even.

i L j iff x_{i} + x_{j} is odd.

i S j k iff x_{i} + x_{j} + x_{k} is odd.

i D j k iff x_{i} + x_{j} + x_{k} is even.

At this point, you should see that each statement corresponds to a linear equation, and we need

to solve them. That’s not a task you normally see on a programming contest, but hopefully you

remember how to deal with systems of linear equations from math class. We only have

evenness/oddness information here, rather than the exact value of each sum, but actually that

works just fine. (In fact, the theory and methods of linear algebra apply to any field. The case of

even and odd numbers corresponds to the simplest finite field, called F_{2} .)

So here’s how you would go about solving the system of equations (based on Gaussian

elimination). The only change we have to make is that we have to constantly treat all even

numbers as being the same as 0, and all odd numbers as being the same as 1. Here’s a fairly

detailed description of what to do (although you may need to refresh your memory on Gaussian

elimination to understand why it works!):

First write the system of equations in matrix form. Each row corresponds to one equation

and has N + 1 entries. For the first N entries, a value of 1 indicates that the

corresponding x i appears in the equation, and a value of 0 indicates that it does not. The

final entry is 1 if the sum must be odd, and 0 otherwise.

Put the matrix into row-echelon form.

o If the entire left-most column is empty, ignore it and recurse on the remaining columns.

o Otherwise, swap rows if necessary so that the top-left entry is a 1.

o Add the top row to any other rows whose left-most entry is a 1. After adding, reduce the resulting row modulo 2 (i.e., replace all even numbers with 0 and replace all odd numbers with 1).

o The left-most column should have a 1 in the top row and a 0 everywhere else, which means the left-most column and top-most row are done. Recurse on the rest of the matrix.

Gaussian elimination guarantees that the system of equations corresponding to this

matrix is equivalent to what we started with, but now simpler.

Put the matrix into reduced row-echelon form.

o Find the bottom-most non-zero row and let i be the index of its first non-zero value.

o Add this row to any higher rows (and reduce modulo 2 - see above) that are also non-zero in entry #i.

o Repeat for all higher rows.

Again, Gaussian elimination guarantees that the system of equations corresponds to this matrix is equivalent to what we started with.

We are now done! If a row gives an equation with only one variable, then we can just read off whether the corresponding person is a truth-teller or a liar. Otherwise, the people in that row can be either truth-tellers or liars, and you can’t deduce which.