Hi,

I am trying to solve this problem from AtCoder: F — Make 10 Again, using the following approach. (I have read the editorial and it makes sense to me, but it is a different dp approach).

the answer == the number of valid dice roll states / the total number of dice roll states

For a valid state, it means there is some way to get a sum of a target sum.

Let dp[i][j] be the number of valid states from A[1, i] with sum j

My main logic is as follows. Clearly this is wrong. But I am not sure why it is incorrect.

Is it because the assumption of valid ways / total ways is incorrect? (since A[i] can be different values) or if this is right, my dp state transition is incorrect.

            long[][] dp = new long[n + 1][11];
            dp[0][0] = 1;
            for(int i = 1; i <= n; i++) {
                dp[i][0] = 1;
                for(int j = 1; j <= 10; j++) {
                    //a[i] does not contribute to the sum j, so a[i]'s actual roll does not matter
                    dp[i][j] = dp[i - 1][j] * a[i] % mod;
                    //a[i] contributes to the sum j, a[i]'s actual roll must be <= j
                    for(int v = 1; v <= min(a[i], j); v++) {
                        dp[i][j] = addWithMod(dp[i][j], dp[i - 1][j - v], mod);
                    }
                }
            }
            long total = 1;
            for(int i = 1; i <= n; i++) {
                total = multiplyWithMod(total, a[i], mod);
            }
            long ans = dp[n][10] * modInv(total, mod) % mod;
            out.println(ans);

Any help is appreciated!

This is a problem from LeetCode from the latest biweekly contest.

You are given a 0-indexed m x n binary matrix grid.

Let us call a non-empty subset of rows good if the sum of each column of the subset is at most half of the length of the subset.

More formally, if the length of the chosen subset of rows is k, then the sum of each column should be at most floor(k / 2).

Return an integer array that contains row indices of a good subset sorted in ascending order.

If there are multiple good subsets, you can return any of them. If there are no good subsets, return an empty array.

A subset of rows of the matrix grid is any matrix that can be obtained by deleting some (possibly none or all) rows from grid.

Constraints:

m == grid.length; n == grid[i].length; 1 <= m <= 10^4; 1 <= n <= 5; grid[i][j] is either 0 or 1.

Instead of finding any subset, I misread the problem to be : Find the maximum number of rows that can be selected to form a subset that meet the above condition.

I could not solve this harder version. I wonder if this version can be solved given the constraints. Any help / insight on this is appreciated.

I am trying to solve 1818D - Fish Graph with the following idea.

1. For each node V whose degree is >= 4, do BFS starting from V to find the shortest cycle that includes V.
2. If such a cycle exists, get all the nodes in this cycle, then check if we can add 2 more extra edges from V to other 2 nodes that are not in this cycle.

My submission (with some comments) is : 204063133. However I am getting WA on test case 2: wrong answer edge (4, 8) was used twice (test case 137).

I am sure my logic is incorrect somewhere but couldn't figure it out. Any help is appreciated.

Hi,

I have tried the following to solve this problem 833A - The Meaningless Game with the following approach.

1. preprocessing: get all the prime numbers from 2 to the floor(square root of 10^9).
2. for the input a and b, get their prime factorizations using the prime number list.
3. do the following check:

(a). check if both a and b's prime factorizations contain the same set of prime numbers, i.e, there is no prime number that only exists in one of the factorization but not the other.

(b). if passing the above check, then for each prime number P that appears in the factorization, do the following check:

A few notes: Say P appears v1 times in a's factorization and v2 times in b's factorization.

Of all the times P appear in a round, assume the 1st player(Slastyona) wins c1 times and the 2nd player(her dog) wins c2 times, we then have:

c1 * 2 + c2 = v1

c1 + c2 * 2 = v2

from the above two equations, we have c2 = (v2 * 2 — v1) / 3, c1 = v2 — (v2 * 2 — v1) / 3 * 2. So we check if v2 * 2 — v1 >= 0 and is divisible by 3, we also check if c1 >= 0. If these conditions are all true, the check for the prime number P passes otherwise it fails.

Intuition:

1. The reason that I chose to use prime factorization is that each round if we are given a composite number k, we can convert it to a product of only prime numbers and use multiple rounds to get the same result. For example, if k is 6, then k^2 = 36, we can have 1 round of k = 2 and another round of k = 3 to get the same result.

2. The max prime number we need to consider is upper bounded by the square root of 10^9 since if there is prime factor that is bigger than this upper bound, then the winner of that round will multiply a number that is bigger than 10^9.

However, the above approach is incorrect and it fails on test case 4. Unfortunately I can not see the input that gives the wrong output. My submission link is 140311042

I think my approach is not correct but could not figure out why it is wrong, can some one help to provide some insights on why this gives the wrong answer?

Thanks!

Hi,

I am trying to solve this problem from atcoder : B — LRUD Game. After reading the editorial and this https://codeforces.net/blog/entry/66849#comment-510066, I still do not understand the solution and have the following 2 questions:

1. why we need to process all moves by both players backwards?
2. When processing backwards, other than the last move by the 2nd player, we need to first do updates based on the 2nd player's moves, then the 1st player's moves. Doing it the opposite yields a wrong answer.

Can some one help me understand the above 2 key ideas?

This is my AC submission after reading other people's submission: submission link.

Thanks!