BledDest's blog

Educational Codeforces Round 48 — Editorial
By BledDest, history, 6 years ago, translation, In English

1016A - Death Note

Tutorial
Solution (Vovuh)

1016B - Segment Occurrences

Tutorial
Solution (PikMike)

1016C - Vasya And The Mushrooms

Tutorial
Solution (Ajosteen)

1016D - Vasya And The Matrix

Tutorial
Solution (Ajosteen)

1016E - Rest In The Shades

Tutorial
Solution (adedalic)

1016F - Road Projects

Tutorial
The first solution (PikMike)
The second solution (BledDest)

1016G - Appropriate Team

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +41
  • Vote: I do not like it

Comments Comments (52)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone prove/find a countercase for my solution for D? 41174052

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I upsolved D in the same manner. Will try to explain the logic behind it [Since the editorial simply left it to the reader to find its proof]

Let r,c be the dimensions of the matrix, row[1..r] be the row wise xor value array, col[1..c] be the column-wise xor value array.

Temporarily, forget a[1][1]. Fill a[1][2] with col[2], a[1][3] with col[3] and so on.. So everything except col[1] is satisfied right now. (We are filling the first row, except the first element, with values from col array)

Similarly, fill a[2][1] with row[2], a[2][3] with row[3] and so on.. Everything except row[1] is satisfied right now (We are filling the first column, except the first element, with values from row array)

Now we have a[1][1] left. Based on the values we filled right now, the current xor value of the first row in our matrix is col[2]^col[3]^..col[c]. This value, can also be represented as C^col[1], where C = total xor of the col array (col[1]^col[2]^..col[c]).. We know that the xor value of elements in first row should be row[1]. Hence, if a[1][1] is equal to C^col[1]^row[1], our answer satisfies all the stipulated properties.

What if we had done it the other way round? Lets check that out. Based on the values we filled right now, the current xor value of the first column in our matrix is row[2]^row[3]^..row[r]. This value, can also be represented as R^row[1], where R = total xor of the row array (row[1]^row[2]^..row[r]).. We know that the xor value of elements in first column should be col[1]. Hence, if a[1][1] is equal to R^row[1]^col[1], our answer satisfies all the stipulated properties.

If we had chosen either of the above options, it would still be the same value. Its because R=C!

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    How can we be sure this always identifies an impossible case? E.g what if using some other strategy you can make a matrix when this method returns "NO"?

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

      The initial check, about R not being equal to C (refer my first comment for notations), is enough for the impossible condition.

      R will have each element represented once, while C will have each elemented represented once. Xor-ing these two values should give zero.

      Hence, checking for this condition and then proceeding with this algorithm of filling the first row and first column alone, and leaving the other elements as zero is a good enough solution.

      Forgive me if I misunderstood your question.

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

        What if there is some case where you can fill some of the 0's such that an input you deemed "impossible" is possible. My question is how can you prove this case does not exist, because of course it works when there is a valid matrix, but how can we be sure it always identifies impossible case.

        I waited for this to be explained in editorial, and I'm a bit disappointed they didn't even mention it.

        → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You haven't given the proof rather you have explained the obvious thing. If you know the thing what @burdy said then please share otherwise the above thing of yours is just like some irrevelant stuff which I think everybody knows already :xD.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D... Why if xor of a1 a2 ...an != to xor of b1 b2 ...bm the answer is no??

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Because is xor of all elements in matrix, and is xor of all elements in matrix. So they must be equal.

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Could someone explain to me the logic behind exercise — C? I can't seem to understand it,even after reading the editorial.

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

    Let first you have to move in a zigzag pattern then go right to end and then left where you stop zigzag pattern.(it's cover all case) Key point is if you start moving in straight line you can't allow to move in zigzag pattern again only one 'U' turn at end.(think why?)

    So you can stop zigzag pattern at 1,2,3,...,N-1.For each value where you stop zigzag pattern (1<=i<=N-1) . You can find total weight of the collected mushrooms in O(1) by help of sum123, sum321 and sum111.

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

      Thanks for the help, but one more thing, what values does Sum123,Sum321,Sum111 contain ?

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

        For that see Editorial.

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

          Ok, thanks for the tips :-))

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

            that 3 arrays is like suffix sum array. ex: a[1,2,3,4] ss[10,9,7,4] at 1<='i'<=n we save sum of i to n;

            but in this case we make suffix weight.

            → Reply
»
6 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Problem D can be solved with Gaussian Elimination. This way the solution is more straightforward.

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

    can you elaborate?

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

      Since a[i], b[i] <= 10E9, for each number in the table, there are at most 30 bits, and each bit is independent from others. I mean, the k-th bit of c[i][j] has nothing to do with (k + 1)-th bit, etc.

      Consider k-th bits of all c[i][j]. Let denote that b[k][i][j] = 1/0.

      Now you can see that we have a system of n + m linear equations such that:

      (b[k][1][1] + b[k][1][2] + ... b[k][1][m]) % 2 = k-th bit of a1

      ...

      (b[k][n][1] + b[k][n][2] + ... b[k][n][m]) % 2 = k-th bit of a[n]

      (b[k][1][1] + b[k][2][1] + ... b[k][n][1]) % 2 = k-th bit of b[1]

      ...

      (b[k][1][m] + b[k][2][m] + ... b[k][n][m]) % 2 = k-th bit of b[m]

      This way, it makes sense that a solution of this system of equations is also a solution for all k-th bits of c[i][j]. In order to find a solution, use Gaussian Elimination. Since there are 30 bits, do this 30 times :)

      Here is my AC code 41183870

      In my code, in order to implement easily, I assume that every equation has n + m variables. However, if the variable is unnecessary for the equation (for instance, b[k][2][1] is unnecessary for (*)), let the coefficient 0, otherwise 1.

      In addition, since the eliminating process is the same for all bits, I list all bits at once and do the eliminating process once only.

      → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

In problem C what if we were not allowed to fill 0 as an entry i.e. if 1<=c<=2*10^9 ??

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain how to implement problem C ?

Thanks.

→ Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

There's a bug in test data in Problem F:

There is an Accepted Submission: 41232049

The test data:

4 1
1 2 1
2 3 1
1 4 100
1

correct answer should be : 100(link the vertex 1 and 3)

but its answer is: 3

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    That's called an incomplete testset, not bugged. Just a missed possibility for the hack.

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

      Sorry for my poor English,⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

      So will the test data be updated?or still incomplete ?

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

        It has been added. Previous submissions are not retested, obviously, but this test will present for the further ones.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me how sum111 is handling the growth of the mushrooms in Problem C.

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

    sum111[i] is the total speed of mushroom growth in the cells on segment [i .. n].

    So, for example, if we start collecting mushrooms on segment [i .. n] in time moment 2i — 2, then we add to the answer the value of sum123[i] + sum111[i] * (2i — 2).

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone, please correct me if I am wrong but can the top left element be also set as b1 ^ a2 ^ a3 ^ ... ^ an in problem D .

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

    Since a1 ^ a2 ^...^ an = b1 ^ b2 ^...^ bm, so, of course, a1 ^ b2 ^...^ bm = b1 ^ a2 ^...^ an.

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

There are two announcements and two tutorials link in problems page.

awoo

→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

It's interesting that the second solution for F works even without the restriction that the input graph is a tree. Have you used the same technique before for other problems?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    That's really interesting, I didn't even see that.

    In fact, it will be better if I address this question to vovuh because he actually proposed this idea in problem F (and I just implemented the solution and handled the fact that the edges we add are bidirectional).

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Wow! Such an interesting fact. Well, I haven't used this idea earlier (I suppose). I came up with it while I thought about a shortest paths graph condition (for the edge (x, y) it is true that this edge is in the shortest paths graph iff d1x + w(x, y) + dny = d1n or d1y + w(x, y) + dnx = d1n, it is well known equation). And I decided that it also can be true for the general case, but I haven't thought about it.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is Binary Search giving me TLE in Proble 1016E — Rest In The Shades ?

http://codeforces.net/contest/1016/submission/41256720

I think there's no better solution than O(log n) per query.

Please help !!!!

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

    try using scanf and printf the timlimit is to hard for this one i believe... i only got AC with scanf and printf too

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

    It was mentioned in the other thread that reading integers as doubles with cin slows down solution greatly.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The graph for problem F can be further restricted: its a path between 1 and n where every vertex on the path has at most one additional child wich is a leaf. (in every other case there would be 3 vertices connected by two edges which are not on the 1 to n path. Adding a third edge to this triangle would not change the shortest path as the added edge cant even lie on any simple path between 1 and n)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There's a typo in the tutorial for problem C. Instead of the ai s, we have ak s. I'm mentioning this because I initially got confused while reading the expressions in the tutorial.

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Someone can explain to me why we do exactly this pr[i + 1] = pr[i] + ok[i]; and this --l, r -= m - 1; in problem B? This is not clear to me

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the statement for(int i = 0, j = 0; j < n; ++j, i ^= 1) in problem1016C

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

    it is equivalent to 

    int i=0,j=0;
while(j<n)
{
   ...
   ++j;
   i=1-i;
}
    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C's editorial,

"Let's iterate on the number of columns Vasya will pass in a zigzag pattern and maintain the weight of mushrooms he will collect while doing so."

How exactly we know which zigzag path we have to take and upto where ?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Firstly, we can observe that there are exactly (n + 1) ways to go through the grid

    Ill express the coordinate using the format (row_num, col_num)
    The first scenario is to from (1,1) to (1,n) then to(2,n) then to (2, 1) (Sample Input 1)
    The second scenario is a zig-zag pattern (Sample Input 2)
    The rest is by combining the two.

    Any other scenario will block the previous cell and disconnects the grid

    Example:
    n = 3
    (1,1) -> (1,2) -> (2,2) -> (2,3) -> (1,3)

    Obviously, all path to (2,1) is blocked

    With the above conclusion, we can use Dynamic Programming to precompute the prefix sum and calculate the answer

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

      Many thanks! That helped clear the cloud of ignorance in my thinking pattern. "Any other scenario will block the previous cell and disconnects the grid" — this line hit me so hard, i realized where i was stuck.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Maybe there's an easier solution for D. The matrix could be

b[1] b[2] …… b[m-1] (a[1] xor b[1] xor b[2]……b[m-1])

0 0 …… 0 a[2]

0 0 …… 0 a[3]

....

0 0 …… 0 a[n]

Because (a[1] xor b[1] ...b[m-1]) xor a[2]...a[n] = b[m], so it is a possible solution

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

    basically it is the same solution

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

      Could you please provide any proof or explain the problem why such arrangement will provide a correct answer ?

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1016A - Death Note

[Problem:B] - Segment Occurrences

Can someone please explain to me why 'l' is decremented in the last for loop?

And also it would be much appreciated if you explain for any value x, what does pr[x] stand for? From the above code, I guess pr[x] represents the number of times string 't' appears in s[1, x+|m|-1].

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    First, see prefix sum : https://www.hackerrank.com/topics/prefix-sum

    And decrementing of l because the input is given 1 based while we work zero based in our arrays.

    Second, hope looking at it from the other side clears it up. So here's my approach. You'll find prefix sum of occurrences of string t in s but instead of marking the start positions of the string, you'll mark the end positions.

    For example, in the first test case looking for for in codeforces the prefix array will look like this

    c o d e f o r c e s

    0 0 0 0 0 0 1 1 1 1

    now pre[i] means number of occurrences of string t in string s in [0, i]. This is consistent with given r but we need to push l (m-1) positions. now you have pre[r] and pre[l+m-1]. To get what's in between them you substract pre[r] — pre[(l+m-1) — 1].

    Hopefully this clears it up also see my code 41592407 for further understanding

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I've gone through your solution thoroughly and understood how you actually stored number of occurrences of string t in prefix sum array using the end index, that way it makes the range clearer! Thanks a lot for your help Bekh :)

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

        Glad it helped :). Keep coding!

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There's no need to do prime factorization in problem G, it can be solved in true polynomial time. Just factor $$$Y$$$ relative to numbers $$$a_1, \ldots, a_n, X$$$. By relative factorization I mean, represent $$$Y = f_1^{b_1} \cdots f_k^{b_k}$$$, where $$$f_i$$$ are pairwise coprime and for each $$$r \in a \cup X$$$, $$$GCD(r, f_i)$$$ is either $$$1$$$ or $$$f_i$$$. This factorization can be easily found by starting with $$$[Y]$$$ and refining it with each element of $$$a \cup X$$$. Finally you can safely use this factorization instead of the true prime factorization of $$$Y$$$ in the same way as in the editorial.

Sample code: 82648734

→ Reply