whfym's blog

By whfym, history, 7 years 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_T)

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +64 Vote: I do not like it

Thanks for light speed editorial and system test :)

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

    Our pleasure :)

  • »
    »
    7 years 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?

»
7 years 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!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can look up a DP solution in contest status.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I opened about 40-45 solutions, all of them are brute-force (including mine) and including people in red color. Looks very less number of people have written the DP solution.

        I understand that it's pointless when the bound is <= 100, but this (or similar) question might come up as C-D with higher bounds. If not the whole code, is it possible to get only the psuedocode, please?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years 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.

»
7 years 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.

»
7 years 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.

  • »
    »
    7 years 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.

  • »
    »
    7 years 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/)

    • »
      »
      »
      7 years 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! :)

    • »
      »
      »
      7 years 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!

      • »
        »
        »
        »
        7 years 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.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It helped me a lot, too. Thanks :)

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          so the gcd of the sequence [i,j] must be a multiple of x.

          Wait, that isn't obvious. If x divides A and y also divides A, then it is not true that x divides y.

          Actually the proof of the statement EdsonSousa was asking for is this: X divides all numbers in in [i,j]. OK. Now, the gcd of [i,j], lets say k, must be greater or equal to x, since if not, x is a better candidate for gcd than k. Now k>=x. Assume now that x does not divide k. This implies that there are some prime factors in x that are not in k (again by contradiction). Since these prime factors divide all the elements of the array, they also divide each element of [i,j]. This implies that multiplying k with these prime factors still makes it a common divisor, and now a multiple of x too.

          Hence k is a multiple of x.

»
7 years 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.net/blog/entry/55858#comment-396071

  • »
    »
    7 years 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.

  • »
    »
    7 years 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.

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 years 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.

»
7 years 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?

  • »
    »
    7 years 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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    7 years 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

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

  • »
    »
    7 years 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

  • »
    »
    7 years 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

»
7 years 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"?

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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.

      • »
        »
        »
        »
        7 years 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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Still don't understand ((

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

»
7 years 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.

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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?

      • »
        »
        »
        »
        7 years 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.

  • »
    »
    7 years 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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you could also use __int128

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there a DP solution for QAQ?

  • »
    »
    7 years 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.

»
7 years 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.net/contest/894/submission/32482217, it's my my TLE solution during contest http://codeforces.net/contest/894/submission/32473208, both are (n + m) * log2(n) * log2(n), but only one difference is scanf, printf, instead of cin, cout, WHY?

  • »
    »
    7 years 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.

  • »
    »
    7 years 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.

»
7 years 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.

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the clarification

»
7 years 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?

  • »
    »
    7 years 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.

»
7 years 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.net/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

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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.

      • »
        »
        »
        »
        7 years 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

»
7 years 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?

  • »
    »
    7 years 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.

»
7 years 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!

»
7 years 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.

»
7 years 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.

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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.

      • »
        »
        »
        »
        7 years 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.

        • »
          »
          »
          »
          »
          7 years 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.

          • »
            »
            »
            »
            »
            »
            7 years 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.

            • »
              »
              »
              »
              »
              »
              »
              7 years 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.

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

              I know I'm late but thanks for this, this is amazing.

              In fact, I found another problem on Xor on grid which uses the same idea. I immediately got solution to that problem after I read your comment. I couldn't resist thanking.

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

              Thanks a lot, Benq amazing explanation.

  • »
    »
    7 years 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)

»
7 years 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

»
7 years 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

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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:)

      • »
        »
        »
        »
        7 years 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.

        • »
          »
          »
          »
          »
          7 years 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:)

»
7 years 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.

  • »
    »
    7 years 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.

»
7 years 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.

  • »
    »
    7 years 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.

»
7 years 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).

»
7 years 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 ?

»
7 years 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?

  • »
    »
    7 years 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.

»
7 years ago, # |
  Vote: I like it -13 Vote: I do not like it

piece of shit

»
7 years 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.

»
7 years 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.

  • »
    »
    7 years 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

    • »
      »
      »
      7 years 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.

    • »
      »
      »
      7 years 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!

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks, glad I could be of help.

      • »
        »
        »
        »
        7 years 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?
»
7 years 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?

  • »
    »
    7 years 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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why always in queue?

»
7 years 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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow!

  • »
    »
    7 years 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!

  • »
    »
    7 years 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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me find the bug in this:
http://codeforces.net/contest/894/submission/32906228
its code for problem E. I did: 1) SCC 2) DAG construction 3) DP

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

IN problem C If Input 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Participant's output 10 15 14 13 12 11 10 9 8 7 6 Jury's answer 29 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 Checker comment wrong answer Integer 2 appears in the set, but not produced by the sequence.

I am not able to find why It is giving wrong answer gcd(14,12) = 2 then why it is saying that we can't produce 2 by sequence. Can anyone help me??

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C, My Solution: http://codeforces.net/contest/894/submission/33303911

My Solutions is printing every element Twice because GCD(9,9) = 9.

I am not able to find why It is giving the wrong answer on test 15.

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

    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.