Kotlin Coding Test, I don't want to become a liar

Problem Description

There are several residents in our village. Among these residents, some tell lies to express their opinions. Can we identify the liars among the information we have?

Problem Summary

The given N residents provide information about their neighbors. Each resident inputs who they consider their neighbors and what those neighbors said about them. We are trying to determine whether each resident is deceiving themselves. Ultimately, this problem is about figuring out whether the statements of the residents are consistent with each other.

Input Format

The first line contains the number of residents N. Then, for N lines, the index of each resident, the number of neighbors M that the resident thinks they have, and information about M neighbors is provided in a scattered manner. The neighbor’s information contains the index of that neighbor and whether the statement about that index is false or true.

Output Format

Based on whether each resident is a liar or not, the result is printed as YES or NO.

Example Input

Example Output

    NO
    NO
    YES

Problem Solving Process

To solve this problem, we follow the steps outlined below.

Step 1: Understand the Problem

To distinguish between truth and lies in the residents’ statements, we need to check the consistency between the statements of different residents based on what they said about their neighbors. For example, if a resident A claims that B is a neighbor, and B claims A is lying, we can conclude that A is indeed a liar.

Step 2: Design the Data Structure

To solve this problem, we can use an array or list to store and manage the information of the residents. A suitable method is to use the index of each resident (starting from 0) and a list to hold the information of their neighbors. Using a Pair class to compose resident information is also a good idea.

Step 3: Algorithm Design

After collecting information about the given residents, we will determine whether their statements are consistent with each other based on this information. We can design the following algorithm.

    1. Input the number of residents N.
    2. Initialize a list to store each resident's information.
    3. For each resident, input and store the information about their neighbors and statements.
    4. Check whether the neighbors' statements of each resident are consistent.
    5. If they are not consistent, determine that the resident is a liar.
    6. Print the results.

Step 4: Implement the Kotlin Code

Now we will implement the algorithm in Kotlin code. Below is the Kotlin code to solve the problem.


    data class Neighbor(val index: Int, val isLiar: Boolean)

    fun findLiar(N: Int, statements: List>): List {
        val result = MutableList(N) { "NO" }

        for (i in 0 until N) {
            val neighbors = statements[i]
            for (neighbor in neighbors) {
                val expectedTruth = !neighbor.isLiar
                if (expectedTruth && result[neighbor.index] == "YES") {
                    result[i] = "YES"
                    break
                } else if (!expectedTruth && result[neighbor.index] == "NO") {
                    result[i] = "YES"
                    break
                }
            }
        }
        return result
    }

    fun main() {
        val N = readLine()!!.toInt()
        val statements = mutableListOf>()

        for (i in 0 until N) {
            val input = readLine()!!.split(" ").map { it.toInt() }
            val M = input[1]
            val neighbors = mutableListOf()

            for (j in 0 until M) {
                val neighborIndex = input[2 + j * 2]
                val liar = input[3 + j * 2] == 1
                neighbors.add(Neighbor(neighborIndex, liar))
            }
            statements.add(neighbors)
        }

        val result = findLiar(N, statements)
        for (r in result) {
            println(r)
        }
    }

Step 5: Test and Validate

Once the code is completed, it should be validated through various test cases. It is necessary to verify the overall stability and reliability of the code through minimal input, maximal input, and various scenarios.

Conclusion

This problem taught us how to approach and solve algorithm problems in Kotlin. Analyzing the residents’ statements to distinguish between truth and lies greatly helps in developing logical thinking necessary for problem-solving. Additionally, learning how to approach complex problems through simple data structures and algorithm variations will be beneficial.

Now, you should carefully implement the algorithm to find the liars!

Kotlin Coding Test, I don’t want to become a liar