### BledDest's blog

By BledDest, history, 2 years ago, translation,

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

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

1016G - Appropriate Team

Tutorial

• +41

 » 2 years ago, # |   0 Can someone prove/find a countercase for my solution for D? 41174052
 » 2 years ago, # |   0 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!
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 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"?
•  » » » 2 years ago, # ^ |   0 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.
•  » » » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
 » 2 years ago, # |   0 In problem D... Why if xor of a1 a2 ...an != to xor of b1 b2 ...bm the answer is no??
•  » » 2 years ago, # ^ |   +16 Because is xor of all elements in matrix, and is xor of all elements in matrix. So they must be equal.
 » 2 years ago, # |   +1 Could someone explain to me the logic behind exercise — C? I can't seem to understand it,even after reading the editorial.
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   0 Thanks for the help, but one more thing, what values does Sum123,Sum321,Sum111 contain ?
•  » » » » 2 years ago, # ^ |   0 For that see Editorial.
•  » » » » » 2 years ago, # ^ |   0 Ok, thanks for the tips :-))
•  » » » » » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   -23 Problem D can be solved with Gaussian Elimination. This way the solution is more straightforward.
•  » » 2 years ago, # ^ |   0 can you elaborate?
•  » » » 2 years ago, # ^ |   0 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 41183870In 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.
 » 2 years ago, # |   -8 In problem C what if we were not allowed to fill 0 as an entry i.e. if 1<=c<=2*10^9 ??
 » 2 years ago, # |   0 Can someone please explain how to implement problem C ?Thanks.
 » 2 years ago, # | ← Rev. 5 →   0 There's a bug in test data in Problem F:There is an Accepted Submission: 41232049The 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
•  » » 2 years ago, # ^ |   +2 That's called an incomplete testset, not bugged. Just a missed possibility for the hack.
•  » » » 2 years ago, # ^ |   0 Sorry for my poor English,⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄So will the test data be updated?or still incomplete ?
•  » » » » 2 years ago, # ^ |   0 It has been added. Previous submissions are not retested, obviously, but this test will present for the further ones.
 » 2 years ago, # |   0 Can someone explain me how sum111 is handling the growth of the mushrooms in Problem C.
•  » » 2 years ago, # ^ |   0 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).
•  » » » 2 years ago, # ^ |   0 can you plz explain solution of C in detail, can't understand tutorial
 » 2 years ago, # |   0 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 .
•  » » 2 years ago, # ^ |   0 Since a1 ^ a2 ^...^ an = b1 ^ b2 ^...^ bm, so, of course, a1 ^ b2 ^...^ bm = b1 ^ a2 ^...^ an.
 » 2 years ago, # | ← Rev. 3 →   +6 There are two announcements and two tutorials link in problems page.PikMike
 » 2 years ago, # |   +14 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?
•  » » 2 years ago, # ^ |   +11 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).
•  » » 2 years ago, # ^ |   +3 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.
 » 2 years ago, # |   0 Why is Binary Search giving me TLE in Proble 1016E — Rest In The Shades ?http://codeforces.com/contest/1016/submission/41256720I think there's no better solution than O(log n) per query.Please help !!!!
•  » » 2 years ago, # ^ |   0 try using scanf and printf the timlimit is to hard for this one i believe... i only got AC with scanf and printf too
•  » » 2 years ago, # ^ |   0 It was mentioned in the other thread that reading integers as doubles with cin slows down solution greatly.
 » 2 years ago, # |   0 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)
 » 2 years ago, # |   0 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.
 » 2 years ago, # |   -8 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
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 i know its stupid, but why u cant just explain instead of "-8"?why ok[i] influences on pr[i+1] but not on pr[i]why we reduce r by (m-1), but l only by 1.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 The first one is prefix sums. https://www.hackerrank.com/topics/prefix-sumFor the second one: Since t is of length m, within the segment [l, r], the last position where it can start from is r-(m-1), So, we only count the occurences of t between [l, r-(m-1)]
•  » » » 2 years ago, # ^ |   0 Oh, thank u,i know what the prefix sum is, i was confused by 1-index array and i forget that we must reduce L by 1 for getting right segment, sorry for this stupid question..
 » 2 years ago, # |   0 Can someone explain the statement for(int i = 0, j = 0; j < n; ++j, i ^= 1) in problem1016C
•  » » 2 years ago, # ^ |   0 it is equivalent to int i=0,j=0; while(j
•  » » » 2 years ago, # ^ |   0 Thank you :)
 » 2 years ago, # |   0 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 ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   0 I am not able to understand the logic for the question "SEGMENT OCCURRENCES". Can someone explain its logic??
 » 2 years ago, # | ← Rev. 2 →   -8 Maybe there's an easier solution for D. The matrix could beb[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
•  » » 2 years ago, # ^ |   0 basically it is the same solution
•  » » » 2 years ago, # ^ |   0 I misunderstood the solution at first. My reply looks stupid now...
•  » » » 2 years ago, # ^ |   0 Could you please provide any proof or explain the problem why such arrangement will provide a correct answer ?
•  » » » » 2 years ago, # ^ |   0 it is written in editorial
 » 2 years ago, # |   0 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].
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 First, see prefix sum : https://www.hackerrank.com/topics/prefix-sumAnd 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 thisc o d e f o r c e s0 0 0 0 0 0 1 1 1 1now 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
•  » » » 2 years ago, # ^ |   +3 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 :)
•  » » » » 2 years ago, # ^ |   0 Glad it helped :). Keep coding!
 » 18 months ago, # | ← Rev. 3 →   0 Problem B: solved
 » 3 months ago, # |   0 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