whfym's blog

By whfym, history, 4 weeks ago, In English,
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!

 
 
 
 
  • Vote: I like it  
  • +172
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it +64 Vote: I do not like it

Thanks for light speed editorial and system test :)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Our pleasure :)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +34 Vote: I do not like it

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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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! :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It helped me a lot, too. Thanks :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nice explanation good!!!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose the smallest number( let's call it P ) in gcd set S divides every other numbers in S.That means the problem has a solution. now,

    Case 1:

    when i == j .

    Then we know that gcd( a[i] , a[j] ) = a[i] / a[j] ( belongs S ).so every elements of S can be in the answer set A.

    Case 2:

    when i != j

    now no matter how you chose your range it always includes P, if you put n-1 Ps alternatively in between n numbers.

    Combining the two cases above produce the correct answer.

»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -16 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for interesting and very interesting contest!!!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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])?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    !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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +21 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I still don't get it at all! Not all numbers have to be -1.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Still don't understand ((

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 a 64-bit integer.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi ntfoim, in your submission why do you add up INF-1 to m and n?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    We know that:

    2(m - 1) * (n - 1) = (2m - 1)n - 1

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

    Then the answer is xn - 1 mod 1e9 + 7

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you could also use __int128

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone give a more detail explanation of D's solution?

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there a DP solution for QAQ?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, I will try to understand it!

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the clarification

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Should I calculate the complexity when there is a segment tree involved

        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 (nmax ≥ 100000) segment tree is slow enough to TLE if there is something like

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it
" To answer each query, we can iterate on the highest vertex on the tour and do binary search on the sorted array to get the answer. "

Could you please explain this line a bit more in problem D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Well, the solution of the B problem makes me feel kinda stupid. Well, thanks for the editorial anyway!

»
4 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand solution for 894B at 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 n and m should be the same if k = -1. Why it couldn't be some combination of 1s and -1s when the number of -1s in 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 proper n, m rectangle. In particular, what if parity of -1s in 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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +16 Vote: I do not like it

    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

    kn = km.

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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 11   Vote: I like it 0 Vote: I do not like it

      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:

      xxxxx0
      xxxxx1
      xxxxx0
      xxxxx1
      xxxxx1
      01010y
      

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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 c

          d e f

          g h i

          Then to extend this square, we are forced to put certain number 1 or -1 so that for example, a * b * c * x == k.

          Obviously, for a any given a, b, c there is only one choice of x to make a * b * c * x == k.

          Now, it's not clear to me that in a new extended square:

          a b c x

          d e f y

          g h i z

          f g h r

          There would be x * y * z * r != f * g * h * r in case parity of -1s in x, y, z, r and f, g, h, r is different.

          When we put x, y, z and f, g, h in one forced choice to satisfy existing numbers (for example: a * b * c * x == k). There is no guarantee that this case wouldn't happen.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
            Rev. 3   Vote: I like it +4 Vote: I do not like it

            Fix the upper 3-by-3 matrix. Then

            a3i = ka2ia1ia0i, 
            ai3 = kai2ai1ai0.

            This implies that

            a30·a31·a32 = a03·a13·a23

            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

            km = kn

            which is true. Now we can just select the value of

            a33

            which works.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it +13 Vote: I do not like it

              Big thanks Benq!!!

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

              a * b * c * x = k

              to:

              a * b * c * k = x

              (in case when a, b, c, x, k are numbers either -1 or 1)

              In my head, I couldn't do that swap since I operated them as general integers instead of doing special case when only integers 1 and -1.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 11   Vote: I like it 0 Vote: I do not like it

In problem C this 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 the gcd(a[i], a[j]) for every pair in the sequence! this variation (present in the contest is a bit easier!)

can someone help me find a solution to this variation I thought the problem was? NOIRP

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      You just sayrepeat 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:)

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Excellent!

          Now you have solved my confusion!

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

          Thx:)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

  • if k is -1 and parity is different, the answer is 0
  • if either n or m is 1 then the answer is 1
  • otherwise, we can calculate the number of unique boards using 2 ^ [(n-1) * (m-1)] since the nth row and mth column will be determined by the rest of the board

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by whfym (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B what is parity ? and what is the proof behind the solution in editorial ?

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

piece of shit

»
4 weeks ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot for a detailed explanation.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain problem C as well?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thank you for writing good editorial for this problem!

      Observe that a == product of first row

      To me it was very big surprise. In fact, I suffered 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 would overlook this.

      Since numbers are only 1 and -1 we can change the following equation:

      x1 * x2 * x3 * a == k

      To:

      x1 * x2 * x3 * k == a

      I checked this observation on concrete numbers in all cases, it works:

      k == -1, odd number of -1s in x1, x2, x3:

      1 -1 1 1 = -1, after swapping a and k equality still holds 1 -1 1 -1 = 1.

      For all others cases it's the same.

      I have to remember this nice property!

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks, glad I could be of help.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        1 * 1 == 1
        1 * (-1) == -1
        (-1) * 1 == -1
        (-1) * (-1) == 1
        
        Haven't you seen this operation before?
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain me problem 894C

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain E ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why always in queue?

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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