Tutorial is loading...

Solution By: Bingheng Jiang (NOIRP)

PS: The characters in problem 894A is Diamond and Bort from *Land of the Lustrous*.

Tutorial is loading...

Solution By: ZeRui Cheng (Marco.L.Tsien)

Tutorial is loading...

Solution By: Bingheng Jiang (NOIRP)

Tutorial is loading...

Solution By: Bingheng Jiang (NOIRP)

Tutorial is loading...

Solution By: Yiming Feng (whfym)

Hope you had fun in this contest and got high rating!

See you next time!

Thanks for light speed editorial and system test :)

Our pleasure :)

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

Hope you had fun with this contest and get high rating! See you next time!

Thanks for the contest!

What is this -> \t{1}?? Mathematical Processing error or anything else?

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

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

Hats off to codeforces! Really showed the class today. Whether it be the Amazing tricky Questions or the bullet like speed of system test! Everything was just amazing today.

Can you sort of give me a proof or an intuitive example why the lowest element must always divide all the elements in the set?

UPD I mean i understand why the answer will always be what it is whenever the smallest element divides all but i guess what i'm really asking is how to come up with such a solution. My bad I guess I need to improve my skills a lot.

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/)

Yes this surely helps :). Thank You very much. Like a lot of the participants today I too had misunderstood the question.

However I had thought some parts of what you are trying to explain over here. (Ex- All the elements must be in the set). But the thing is i dont know if I'd be able to solve it or not during the contest. Guess one never knows whether he/she would be able to solve a particular question or not without participating.

Thanks a lot though! :)

I'm sorry, but I still don't understand something: why the gcd of all numbers in the set must divide all the others gcd's? I think that there's something that may be obvious, but i'm not seeing it :(

thanks in advance!

Let's call the gcd of all numbers (sequence [0,n-1] of the answer) x, ok? We know x divides all the numbers in the answer, because it's the gcd of all numbers in the answer.

Now, choose any pair of indexes i and j. x divides all numbers in [i,j], so the gcd of the sequence [i,j] must be a multiple of x.

it helped a lot! I really need to study it more, but the explanation answer things that wasn't that clear for me, thanks!

It helped me a lot, too. Thanks :)

nice explanation good!!!

Suppose the smallest number( let's call it

P) in gcd setSdivides every other numbers inS.That means the problem has a solution. now,Case 1:Then we know that gcd( a[i] , a[j] ) = a[i] / a[j] ( belongs

S).so every elements ofScan be in the answer setA.Case 2:now no matter how you chose your range it always includes

P, if you put n-1Ps alternatively in between n numbers.Combining the two cases above produce the correct answer.

Even editorial strongly disagrees with this clarification I got in-contest... Hope it doesn't happen again...

http://codeforces.com/blog/entry/55858#comment-396071

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.

It's exactly the same method.

The contest was fun..... Thanks for such a great contest!!!!!

Is there a solution for D that works for arbitrary trees instead of (almost) complete binary trees?

Edit: Solved.

In problem B, why If k equals to -1 and the parity of n and m differ, the answer is obviously 0?

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

Thanks

Thanks for interesting and very interesting contest!!!

Sorry, what does mean [] in 2[(n - 1) * (m - 1)]?

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

plz someone explane about "C" . I couldn't understand what I do

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

here What is "S"??

S contains all of GCD?????

yes, it contains all gcd for all subarrays

For 894B — Ralph And His Magic Field: if we have case with non 0 answer, why is it that for all possible (n-1) lines and (m-1) columns filled area the uniquely determined solution will not have conflict in [n][m] cell (bottom right)? Why can't it happens that for our right column number of -1 (elements [1][m] to [n-1][m]) will differ in parity from number of -1 in bottom row (elements [n][1] to [n][m-1])?

!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

in

problem B, why"if k equals to -1 and the parity of n and m differ, the answer is obviously 0"?If

nis even andk= - 1, then the product of all the elements in the grid is the product of all the rows, which is .If

mis odd andk= - 1, then the product of all the elements in the grid is the product of all the columns, which is .So

ncannot be even ifmis odd. Similarly,mcannot be even whennis odd. Somandnmust have the same parity whenk= - 1.I still don't get it at all! Not all numbers have to be -1.

suppose k=-1,the product of all n*m elements can be (-1)^(n) = (-1)^(m), so if n is even , the left result is 1, so m must be even as n, so as to get 1 in result; when n is odd , the left result is -1, so m must be odd too. In total, n must have the same parity as m, when k == -1. when k ==1, you can derive the conclusion in similary supposition

Still don't understand ((

now understand. the product of the columns must be equal to the product of the lines. but 1 != -1 so its impossible.

or number of -1's will differ (link comment)

In problem 894B, how will you find

2^((m-1)*(n-1))? I mean the expression(m-1)*(n-1)can even be greater than a64-bit integer.By Fermat's Little Theorem, 2

^{(109 + 6)}≡ 2^{0}(mod (10^{9}+ 7)). So you can findaandbless than (10^{9}+ 7) withm- 1 ≡a(mod 10^{9}+ 6),n- 1 ≡b(mod 10^{9}+ 6) and use Fast Exponentiation to find 2^{ab}.Hi ntfoim, in your submission why do you add up INF-1 to m and n?

In the case when

N=INF- 1, (Nmod(INF- 1)) - 1 = - 1, which can screw everything up in the exponentiation (because my fast exponentiation doesn't support negative numbers). Adding INF-1 after taking mod was just my way of fixing this issue.We know that:

2

^{(m - 1) * (n - 1)}= (2^{m - 1})^{n - 1}So first you can solve

x: = 2^{m - 1}mod 1e9 + 7Then the answer is

x^{n - 1}mod 1e9 + 7you could also use __int128

Can someone give a more detail explanation of

D's solution?Is there a DP solution for QAQ?

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.Thank you, I will try to understand it!

the way you got rid of one dimension is fab. thanks for the solution sir! i didn't expect an O(n) solution for this one.

it's my opinion, for problem D, time limit is not enough, it's my ac solution after contest http://codeforces.com/contest/894/submission/32482217, it's my my TLE solution during contest http://codeforces.com/contest/894/submission/32473208, both are (n + m) * log2(n) * log2(n), but only one difference is scanf, printf, instead of cin, cout, WHY?

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()`

: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.

For problem D, Why is it O(n(log(n))^2) for using std::sort? I thought that std::sort was implemented as introsort, which is O(n(log(n)))?

Also, would std::stable_sort be better for this problem since it (given enough space) defaults to mergesort.

`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.Thanks for the clarification

in problem D how do we take into account the nodes not in its subtree?

For each query we go up to the root. So, we change

vfromato 1 (excluding) witha=a/ 2. Then for eachvwe take its parentpandp's other childu(if it exists). We could easily takepinto account and then take allu's subtree using precalculated data. Note that each vertex belongs to its subtree in this solution.I wonder in D why my (n*log2(2000000)+m*log2(2000000)*log2(1000000)) is getting tle. http://codeforces.com/contest/894/submission/32482922 I have made a test case where n=1000000,m=100000,it runs successfully.I am using persistent segment tree. I think at least 10^8 operations can be done within 1 second on compiler,so my codes complexity is enough for 2.5 second.If anyone has a explanation where is my mistake,it will be helpful

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) *Ccould easily TLE.Thank u so much

Still I am a bit confuse,how Should I calculate the complexity when there is a segment tree involved .To get TLE the constant factor must be at least 4.

Dunno. You could just try to test some trivial task (e.g. RMQ) with segment tree and watch for how big the constant is compared to some faster (e.g. fenwick tree).

Perosnally I assume that for most tasks (

n_{max}≥ 100000) segment tree is slow enough to TLE if there is something likeCould you please explain this line a bit more in

problem D?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 mostlog(N) nodes.Well, the solution of the B problem makes me feel kinda stupid. Well, thanks for the editorial anyway!

Could you please prove both "obvious" parts of div2B? Why there is no sulution when parity is different and why all the cells exist if we set first (n — 1) * (m — 1) as we wish? There may be problems with the one which is in right-bottom corner.

I don't understand solution for

894Bat all. I've read editorial many times, I've read comments. The explanation doesn't make sense to me at all.First, it's absolutely not obvious to me why parity of

nandmshould be the same ifk = -1. Why it couldn't be some combination of1sand-1swhen the number of-1sin each row and column is odd?Second, I absolutely don't understand why any random rectangle of size

(n — 1), (m — 1)can be extended to propern, mrectangle. In particular, what if parity of-1sin added row and column is different. I don't see why it shouldn't happen.P.S. With such cryptic explanation it could be the same not having editorial at all. 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.

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

k^{n}=k^{m}.You can use this to prove why the special case mentioned above does not work, while all other cases do.

Thanks, now I understand why answer is

`0`

when`k == -1 && n % 2 != m % 2`

.But it's still not clear to me why if you are extending some randomly generated rectangle (marked as

`x`

), it could not be the case when parity of`-1s`

in new extended row and new extended column is different, say something like this:So as I understand by extending row or column, you are forced to put certain digit. So in case when parity of

`-1s`

in added column or row is different then no matter what you put in`y`

you can't make them both equal correct parity.By a similar argument, the product of the incomplete last row (excluding the final element) must be equal to the product of the incomplete last column. This is not the case in your example.

I know it must be equal but since we have randomly generated square (let's assume we denote these numbers as letters

a..i):a b cd e fg h iThen to extend this square, we are forced to put certain number

1or-1so that for example,a * b * c * x == k.Obviously, for a any given

a, b, cthere is only one choice ofxto makea * b * c * x == k.Now, it's not clear to me that in a new extended square:

a b c xd e f yg h i zf g h rThere would be

x * y * z * r != f * g * h * rin case parity of-1sinx, y, z, randf, g, h, ris different.When we put

x, y, zandf, g, hin one forced choice to satisfy existing numbers (for example:a * b * c * x == k). There is no guarantee that this case wouldn't happen.Fix the upper 3-by-3 matrix. Then

a_{3i}=ka_{2i}a_{1i}a_{0i},a_{i3}=ka_{i2}a_{i1}a_{i0}.This implies that

a_{30}·a_{31}·a_{32}=a_{03}·a_{13}·a_{23}because when we substitute with the above two expressions, we cancel out all the variables of the upper 3-by-3 matrix and end up with

k^{m}=k^{n}which is true. Now we can just select the value of

a_{33}which works.

Big thanks

Benq!!!To me it was a very big surprise that, you can swap from:

a * b * c * x = kto:

a * b * c * k = x(in case when

a, b, c, x, kare numbers either-1or1)In my head, I couldn't do that swap since I operated them as general integers instead of doing special case when only integers

1and-1." 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)

In problem

Cthis test ->`3`

`1 15 25`

The author's solution produces ->

`5`

`1 1 15 1 25`

so if these numbers are valid how come

`gcd(15, 25) == 5`

isn't in the`gcd set {1, 15, 25}`

?UPD: I'm sorry I think I misunderstood the problem, I was thinking the input set was thefor every pair in the sequence! this variation (present in the contest is a bit easier!)gcd(a[i],a[j])can someone help me find a solution to this variation I thought the problem was? NOIRP

5 is the number of solution

For problem B:

It’s obvious that we could get an unique answer right.

But could anyone help me to understand the unique answer is always a valid answer.

For example I put 1 in all (n-1,m-1)entries and I got a valid answer,now I change some entries from 1 to -1 ,here why can we guarantee that we could get a valid answer rather than a conflict answer

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.

I’am sorry but it seems that you didn’t solve my confusion

You just say

`repeat the process for all rows and columns to make them valid`

.Here I understand right,but why can you guarantee we can put the (n,m) entry to satisfy both n-row and m-column after doing the above steps,could you please prove it,thx:)That's a good point I didn't consider that. Thinking about it for a bit I came up with the following argument.

Let's consider the case k=1 and two cases. First case we have an even number of -1s in the sub-matrix A[1...n-1][1...m-1]. With our construction each row product is 1 so the total product of the of the sub-matrix A[1...n-1][1...m] is 1. This means the column A[1...n-1][m] must also have an even number of -1s, since if it had an odd number of -1s the total product of the sub-matrix A[1...n-1][1...m] would be -1. With a similar argument we can show we will also have an even number -1s in the row A[n][1...m-1]. This means in this case we can set A[n][m] to 1 and the product of the n-row and m-column will be 1.

For the case where there are an odd number of -1s in the submatrix and k=1 the argument is similar but now A[1...n-1][m] and A[n][1...m-1] will have an odd number of 1s and we set A[n][m]=-1.

The same argument should work if k=-1 assuming there are valid solutions.

Excellent!

Now you have solved my confusion!

The case for k=-1 could be a little different though.

Thx:)

For Problem B:

I have read and understood the editorials and I am trying to implement the solution but am getting the wrong answer, can someone assist me. Here is my logic:

Is there something wrong with this logic? edge cases? I have been trying for a few hours now and I can't figure out whats wrong.

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

whups, what a silly mistake, thanks!

Why was the constraints for problem C this low? if it was for the checker it can be implemented in

O(nlog(n)). You can use the implementation for problem 475D - CGCDSSQ.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.

For 894D,can someone please explain how to get the sorted array of each vertax?Will we use dfs?

Auto comment: topic has been updated by whfym (previous revision, new revision, compare).In problem B what is parity ? and what is the proof behind the solution in editorial ?

For B, how can this code not be TLE? 32471265. Owner does fast exponentiation (binpow) on this way, to compute x^k :

If k is even, then binpow(x, k) = binpow(x, k/2) * binpow(x, k/2);

This way, the binpow function will be called k times (and not log(k)). As k can be large, it should TLE. On my computer it is veryy long. Why not on codeforces?? Is there an option i didn't know?

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.

piece of shit

So in 894C, it's valid to have a number in S which is not gcd of any sub array?

For example, with this sample test:

4

2 4 6 12

The output (from the above tutorial) will be:

2 2 4 2 6 2 12

From the above result, 2 will be gcd of all sub-arrays, and 4, 6, 12 are not gcd of any sub-array.

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

894A - QAQ

## Solved

May I ask for a more specific tutorial on question B? Too many "obvious" in the tutorial provided and I cannot get the point.

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 thatany 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

Thanks a lot for a detailed explanation.

Can you please explain problem C as well?

Nevermind, I got it. For subarray length 2 or greater, gcd will always be the min element, otherwise for length 1 the numbers are as it is present in set. Nice solution

Yes I completely understand now, thanks you. Actually I could understand the idea here but just could not find the proof. The critical fact here is

abc=cdf, and it is the key to prove that for any filling of the (n-1)*(m-1) matrix, we can always generate one and only one matrix of size n*m.Thank you for writing good editorial for this problem!

To me it was very big surprise. In fact, I

a lot till Benq explained it to me. I don't think I would find this observation even after a week of thinking because I wouldsufferedthis.overlookSince numbers are only

1and-1we can change the following equation:x1 * x2 * x3 * a == kTo:

x1 * x2 * x3 * k == aI checked this observation on concrete numbers in all cases, it works:

k == -1, odd number of-1sinx1, x2, x3:1 -1 1, after swapping1=-1aandkequality still holds1 -1 1.-1=1For all others cases it's the same.

I have to remember this nice property!

Thanks, glad I could be of help.

Haven't you seen this operation before?Very nice analogy!

can anyone explain me problem 894C

in problem #447 C

Are all the elements of the given set S gcd of some range (i,j) of the output (final sequence).

Please clarify the doubt.

A doubt in b's tutorial,providing random values from the set {-1,1} for n-1 rows and m-1 columns,we would have definite values for nth row and mth column entries.Now for a[n][m](value at index n,m)what if we need to have contrary values?

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.

can anyone please explain E ?

Why always in queue?

As regards D. It can be solved in O((n+m)logn). You don't have to do any sort — all the arrays are sorted, so you just merge them in linear time. Also you do not need any binary search — for each sorted query just progress the pointer in sorted distances array until distance is too big for that query.

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.

Can someone please help me find the bug in this:

http://codeforces.com/contest/894/submission/32906228

its code for problem E. I did: 1) SCC 2) DAG construction 3) DP