ABC | Atcoder | Competitive Programming

C-False Hope-Atcoder ABC 319

Let us take on a — not — so easy problem

Introduction

Have you ever encountered a problem that combines logic, permutations, and a touch of probability? If not, you’re in for a treat. Today, we’re diving into the “False Hope” problem from AtCoder. This mind-boggling challenge is not just about finding solution but also understanding the intricacies of sequence and probability. I have given the problem link below and at the end the entire code in java , so make sure to first try it out yourself .

Problem link — False Hope Atcoder ABC 319 problem

Understanding the Problem

Imagine a 3x3 grid filled with numbers ranging from 1 to 9, with each number occupying a square. The goal is to determine the probability that a person, Takahashi, can look at this grid without experiencing disappointment. But what constitutes disappointment in this context?

Disappointment arises when Takahashi observes any line (row, column, or diagonal) where the first two squares have the same number, but the last square has a different number. For example, if squares A and B have the same number, but square C has a different number, that’s a disappointment.

Now, let’s get a clearer picture of the problem:

• The grid consists of numbers from 1 to 9.
• Disappointment conditions involve rows, columns, and diagonals.
• Sequence matters — the order in which squares are opened determines disappointment.
• Remember that in constraints it is given that no three consecutive cells( vertical, horizontal, or diagonal) have the same number.

Approach to Solving

To solve this puzzle, we adopt a two-step approach:

1. Counting Non-Disappointing Ways: Our primary objective is to count the number of ways Takahashi can view the grid without encountering disappointment. This involves generating different orders of opening squares and checking if each order leads to disappointment.
2. Generating Possible Orders: To count these ways, we must first generate all possible orders in which Takahashi can open the squares. This is where permutations come into play. Permutations allow us to explore different sequences of square openings.

Crux

1. Generate all possible orders of square openings.
2. For each order; check each row, column, and diagonal for disappointment
3. If no disappointment found, increment the count of non-disappointing ways.
4. Calculate the probability: Number of non-disappointing ways / Total number of ways

Why do permutations matter? They ensure that we consider every possible order of opening squares, which is crucial because disappointment depends not only on the numbers but also on the sequence in which squares are opened.

Conclusion

In this journey through the “False Hope” problem from AtCoder, we’ve delved into the heart of logic, permutations, and somewhat probability. We’ve learned that solving complex problems often requires meticulous attention to detail, especially when sequence and order play pivotal roles.

Before i present to you the entire code below, I encourage you to give this problem a try on your own again. Understanding the problem conditions and working through it step by step can be an incredibly rewarding experience.

In the end, it’s not just about finding solutions; it’s about appreciating the beauty of problem-solving and the elegance of mathematics. Thank you for joining me on this problem — solving adventure, and remember, disappointment can be defeated with the right sequence of events.

Closing Thoughts

If you have any questions, insights, or if there’s a particular problem you’d like me to explore in the future, please feel free to reach out. Happy problem-solving!

Java code

import java.util.Scanner;

public class FalseHope {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] cells = new int[9];

        // Read the input grid
        for (int i = 0; i < 9; i++) {
            cells[i] = scanner.nextInt();
        }

        // Define lines (vertical, horizontal, and diagonal)
        int[][] row = {
                {0, 1, 2}, // 1st row from the top
                {3, 4, 5}, // 2nd row from the top
                {6, 7, 8}, // 3rd row from the top
                {0, 3, 6}, // 1st column from the left
                {1, 4, 7}, // 2nd column from the left
                {2, 5, 8}, // 3rd column from the left
                {0, 4, 8}, // top-left to bottom-right diagonal
                {2, 4, 6}  // top-right to bottom-left diagonal
        };
        
        // first order/ way defined
        int[] order = new int[9];
        for (int i = 0; i < 9; i++) {
            order[i] = i;
        }

        int notDisappoint = 0, all = 0; // Counters for disappointing and total ways
        do {
            all++;
            boolean disappointFlag = false; // Determine if this order disappoints him
            for (int[] line : row) {
                int a = line[0];
                int b = line[1];
                int c = line[2];
                // It's disappointing if squares a and b are equal, and c is the last square to be opened within these three
                if (cells[a] == cells[b] && order[a] < order[c] && order[b] < order[c]) {
                    disappointFlag = true;
                }
                // Same applies for the two other pairs that can be the same digit
                else if (cells[a] == cells[c] && order[a] < order[b] && order[c] < order[b]) {
                    disappointFlag = true;
                } else if (cells[b] == cells[c] && order[b] < order[a] && order[c] < order[a]) {
                    disappointFlag = true;
                }
            }

            // If it is not disappointing, increment the count
            if (!disappointFlag) {
                notDisappoint++;
            }
        } while (nextPermutation(order)); // Try all ways to reveal it

        // Instruct to print 10 decimal places
        System.out.printf("%.10f\n", (double) notDisappoint / all);
    }

    // Function to find the next permutation
    static boolean nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
        return i >= 0;
    }

    // Function to swap two elements in an array
    static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // Function to reverse an array
    static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}