TRAL - Editorial

[apurvsinghgaut]

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₂ .)

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.