Our pleasure :)

Maybe it is because there are not many submissions to test? Therefore, the system test is very fast?

Hi! Problem A has an O(n^3) solution, where n is the size of the input string. I was working out the DP solution for the same, but I am getting wrong answers. It'll be a great help if you please post a DP solution as well, please?

Thanks a lot! :D

emmm... it means 1 the \t{} maybe a processing error?

Sorry it's my mistake. And I have fixed it now.

Use the GCD of all the numbers to divide all the elements in the set. Then GCD of the range which includes that GCD number will be GCD of all numbers.

The statement says that all the gcds are in the set, alright? So, the gcd of ALL the elements of the answer must be in the set.

Besides that, gcd(a, b) <= min(a, b), so the gcd of all of the elements of the answer must be the smallest number in the set, so every number must divide it.

(PS: I tried to explain my intuition on it, hope it helps! o/)

I'm sorry :( Maybe someone replied you in a hurry and made a mistake. You know there were a lot of questions at that time.

Btw, Sharon,Your submission for A and this is too similar.

suppose that n is even and m is odd. if an answer exists then we have even rows each with odd -1s (even -1 in total) and odd columns each with odd -1s (odd -1 in total) => contradiction

oh, got it. It means 2^((n — 1) * (m — 1))

if gcd of all set is not smallest element in set — answer is -1; else input: 4 2 4 6 12 output 2 4 2 6 2 12. U insert the smallest element between every two.

Hope i got all correctly

!Not true, see updated post!

Oh, nevermind, i think I got it. If k == 1, every -1 in row or column should be balanced out by odd number of -1s. So, that means that number of -1s in last row (without [n][m] element) should have same parity as number of -1s in last row (without [n][m] element). For k == 1, same can be said for number of 1 elements. And given that we know that n%2 == m%2, same can be said for number of -1s. Please correct me if I'm wrong

Sorry, my previous post was not a valid proof. I think this one is, though

In case of k == 1 if we have -1 in some cell in last row, let's say it's cell[n][x], for cells in that column x (cells from [1][x] to [m-1][x]) we we can say that there is odd number of -1, because their product should be -1.
If we have 1 in same cell, we can say that number of -1 is even for that column, because their product should be -1.
If we have -1 in some cell in last column, let's say it's cell [x][m], for cells in that row x (cells from [x][1] to [x][m-1]) we can say that there is odd number of -1, because their product should be -1.
If we have 1 in same cell, we can say that number of -1 is even for that column, because their product should be -1.

Let's say there is P -1 in (n-1)(m-1) filled area

Let's say we have x1 -1 elements in last column (without [n][m] element). Let's calculate parity of number of -1 in (n-1)x(m-1) filled area. Sum of -1 in all rows ending (ending meaning [i][m] element is -1) with 1 will be even (sum of whatever number of even numbers is even). Sum of -1 in all rows ending with -1 will depend on x1. For every such row there is odd number of -1. If a1 is even (sum of even number of odd numbers is even), if a1 is odd, sum is odd (sum of odd number of odd numbers is odd). So, we can say that x1= P (mod 2).
For last row (without [n][m] element), let's say we have x2 -1 elements. Using same logic as above, we'll discover that x2 = P(mod 2), giving us that x1 = x2(mod 2). (parity is same)
Therefore, we won't have any conflicts in [n][m] cell.

We'll apply almost similar logic to k == -1 case.

In case of k == -1, if we have -1 in some cell in last row, let's say it's cell[n][x], for cells in that column x (cells from [1][x] to [m-1][x]) we we can say that there is even number of -1, because their product should be -1.
If we have 1 in same cell, we can say that number of -1 is odd for that column, because their product should be -1.
If we have -1 in some cell in last column, let's say it's cell [x][m], for cells in that row x (cells from [x][1] to [x][m-1]) we can say that there is even number of -1, because their product should be -1.
If we have 1 in same cell, we can say that number of -1 is odd for that column, because their product should be -1.

We can do the same as we did before, but this time we'll prove that y1 = y2(mode 2), where y1 and y2 are number of 1 elements in last row / column (not number of -1 elements, as before).
B we already know that for k == -1 case, n = m (mod 2). Therefore, x1 =x2 (mode2), where x1 and x2 are number of -1 elements in last row/column (parity is same)
Therefore, we won't have any conflicts in [n][m] cell

If n is even and k =  - 1, then the product of all the elements in the grid is the product of all the rows, which is .

If m is odd and k =  - 1, then the product of all the elements in the grid is the product of all the columns, which is .

So n cannot be even if m is odd. Similarly, m cannot be even when n is odd. So m and n must have the same parity when k =  - 1.

By Fermat's Little Theorem, 2^{(109 + 6)} ≡ 2⁰ (mod (10⁹ + 7)). So you can find a and b less than (10⁹ + 7) with m - 1 ≡ a (mod 10⁹ + 6), n - 1 ≡ b (mod 10⁹ + 6) and use Fast Exponentiation to find 2^ab.

We know that:

2^{(m - 1) * (n - 1)} = (2^m - 1)^n - 1

So first you can solve x:  = 2^m - 1 mod 1e9 + 7

Then the answer is x^n - 1 mod 1e9 + 7

you could also use __int128

Yes, 32477025. Basically dp[i][j] is the number of subsequences of t[0..j] in s[0..i]. And to save memory you can get rid of one dimension.

It's common problem that iostream is not fast enough for reading 1000000 numbers. You could use the following lines in the beginning of your main():

std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);

And it will become fast.

Author's solution is O(nlogn+mlog^2n) using merge sort.Your solution isn't the intended one,and that's why your solution can't fit in the time limit.

std::sort takes O(n log(n)) time. In the editorial they meant that the construction of the complete tree takes O(n log(n)^2) time.

For each query we go up to the root. So, we change v from a to 1 (excluding) with a = a / 2. Then for each v we take its parent p and p's other child u (if it exists). We could easily take p into account and then take all u's subtree using precalculated data. Note that each vertex belongs to its subtree in this solution.

The logarithm of segment tree usually has relatively big constant C (maybe because of many divisions and random array access). 1e5 * log(1e5) * log(2e5) * C could easily TLE.

The root of the complete binary tree is at 1. Each node has a level. The solution identifies tours by the smallest level node on them. For example 9->4->2->5->10->21 is identified by 2, and it's added to the solution, when going through node 2. The "highest" node, thus the smallest level one will be a node from the path of v, 1 (endpoints included), and because it's a complete binary tree, this path has at most log(N) nodes.

Observe that the product of all the numbers in the rectangle is equal to both the product of all the columns as well as the product of all the rows. This means that

You can use this to prove why the special case mentioned above does not work, while all other cases do.

" If amount of effort to understand solution from reading others submissions is the same as amount of effort to read editorial, then we don't need editorial."

well said (y)

5 is the number of solution

Let's assume our k=1 and look at a particular row. If the product of the first m-1 elements in this row is equal to 1 we set the mth element to 1 and the row is valid since the product of the m elements remains 1. If the product the first m-1 elements i equal to -1 we set the mth element to -1 and the row becomes valid since the product of the m elements becomes 1. We can repeat the process for all the rows and columns to make them valid. The same approach works if k=-1, although we have to handle the edge cases where m is odd and n is even and n is odd and m is even.

Your logic is correct, but you have to take modulo by 10^9 + 7.

The checker should be easy and readable so we reduced the constraints from 1e5 to 1000. And reducing it to 1000 will make some contestants come up with some other constructive ways to solve the problem. It's very ok for a Div.2 C.

I think it's because the compiler optimization sees that it's the same call and same result and must do some kind of auto-memoization. When I add a global counter variable and increment it each time we call the function, it takes ages, but it works instantly without this counter variable.

Sorry got it, I thought i must be different than j.

We can only use 1 and -1 because otherwise the product won't be 1 or -1.

First for the invalid case, it's because product of all row == product of all column == product of entire rectangle. So you can't have k = -1 with odd row and even column (and vice versa) because row product == 1 and column product == -1 which is different.

Now for the valid case, let's say we want to fill n*m rectangle. The formula given in editorial pow(2, [(n - 1) * (m - 1)]) can be rephrased as: The value of the last row and the last column is predetermined by the first (n-1) row and (m-1) column. Also, the formula implies that any arbitrary filling of the first (n-1) row and (m-1) column is always valid; We can always correct any wrong product with the last row and last column.

To see why any arbitrary filling is correct, consider the following 4x4 rectangle (it can easily be generalized to any other size), and k == 1. Suppose we have randomly filled 3x3 with 1 and -1:

xxxa

xxxb

xxxc

def?

Where x is the random filled value. a-f and ? is the value we will insert to correct the product of the 3x3 rectangle.

First, notice that the value a-f is already predetermined. For example, if the product of the first row (without "a") is -1, then "a" must be -1 because k == 1. "a" == 1 otherwise. The same goes for bcdef.

Now the part that may get confusing is, how do we fill the "?". If the sign of a*b*c != d*e*f, then obviously the rectangle is invalid. For example a*b*c = -1, and d*e*f = 1. Then we cannot correct both product with a single "?". Fortunately, we can prove that it is impossible for (a*b*c) to be different from (d*e*f).

Consider the 3x3 rectangle. Observe that a == product of first row, b == product of second row and c == product of third row. This means that a*b*c == product of all row(3*3) == product of 3*3 rectangle.

Similar thing with d,e,f. d == product of first column, e == product of second column, and f == product of third column. This means that d*e*f == product of all column(3*3) == product of 3*3 rectangle.

But since a*b*c == d*e*f == product of 3*3 rectangle, they must have the same sign, so the value of "?" is also predetermined!

You can use very similar logic to prove things for k = -1. Sorry if the proof is not mathematical enough, but I hope it's clear.

*Just noticed there are many users already explaining B above. If you have trouble understanding mine, you can try the others

You'll have contrary values on a[n][m] only if k=-1 and n%2 != m%2 (try on a simple example to see why), That's why in this case, answer is 0. In all other cases, the value on a[n][m] will be uniquely defined.

Wow!

Yes,it can be solved in O((n+m)logn),thanks a lot for pointing it out!

I also did not manage to edit my post yesterday (cf was quite slow) but memory is linear O(n+m) — you just compute the size of the subtree and fill that space with sorted distances. As regards queries, you remove them from children, merge them in ascending order and assign to parent. There is no need to duplicate or to keep old values in children.

Your output sequence can't produce 2. 10 15 14 13 12 11 10 9 8 7 6 You can't find a range of number which GCD = 2 in your sequence. Please read the statement carefully :)

Please read the statement carefully.

And this input may help you:

3

2 12 18

Your output: 2 2 12 12 18 18

GCD(12,18)=6

However 6 is not in the set.