### BledDest's blog

By BledDest, history, 22 months 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

 » 22 months ago, # |   0 Can someone prove/find a countercase for my solution for D? 41174052
 » 22 months 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!
•  » » 22 months 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"?
•  » » » 22 months 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.
•  » » » » 22 months 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.
•  » » 22 months 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.
 » 22 months ago, # |   0 In problem D... Why if xor of a1 a2 ...an != to xor of b1 b2 ...bm the answer is no??
•  » » 22 months ago, # ^ |   +16 Because is xor of all elements in matrix, and is xor of all elements in matrix. So they must be equal.
 » 22 months ago, # |   +1 Could someone explain to me the logic behind exercise — C? I can't seem to understand it,even after reading the editorial.
•  » » 22 months 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.
•  » » » 22 months ago, # ^ |   0 Thanks for the help, but one more thing, what values does Sum123,Sum321,Sum111 contain ?
•  » » » » 22 months ago, # ^ |   0 For that see Editorial.
•  » » » » » 22 months ago, # ^ |   0 Ok, thanks for the tips :-))
•  » » » » » » 22 months 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.
 » 22 months ago, # |   -23 Problem D can be solved with Gaussian Elimination. This way the solution is more straightforward.
•  » » 22 months ago, # ^ |   0 can you elaborate?
•  » » » 22 months 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.
 » 22 months 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 ??
 » 22 months ago, # |   0 Can someone please explain how to implement problem C ?Thanks.
 » 22 months 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
•  » » 22 months ago, # ^ |   +2 That's called an incomplete testset, not bugged. Just a missed possibility for the hack.
•  » » » 22 months ago, # ^ |   0 Sorry for my poor English,⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄So will the test data be updated?or still incomplete ?
•  » » » » 22 months ago, # ^ |   0 It has been added. Previous submissions are not retested, obviously, but this test will present for the further ones.
 » 22 months ago, # |   0 Can someone explain me how sum111 is handling the growth of the mushrooms in Problem C.
•  » » 22 months 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).
•  » » » 22 months ago, # ^ |   0 can you plz explain solution of C in detail, can't understand tutorial
 » 22 months 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 .
•  » » 22 months ago, # ^ |   0 Since a1 ^ a2 ^...^ an = b1 ^ b2 ^...^ bm, so, of course, a1 ^ b2 ^...^ bm = b1 ^ a2 ^...^ an.
 » 22 months ago, # | ← Rev. 3 →   +6 There are two announcements and two tutorials link in problems page.PikMike
 » 22 months 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?
•  » » 22 months 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).
•  » » 22 months 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 d1 x + w(x, y) + dn y = d1 n or d1 y + w(x, y) + dn x = d1 n, 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.
 » 22 months 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 !!!!
•  » » 22 months 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
•  » » 22 months ago, # ^ |   0 It was mentioned in the other thread that reading integers as doubles with cin slows down solution greatly.
 » 22 months 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)
 » 22 months 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.
 » 22 months 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
•  » » 22 months 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.
•  » » 22 months 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)]
•  » » » 22 months 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..
 » 22 months ago, # |   0 Can someone explain the statement for(int i = 0, j = 0; j < n; ++j, i ^= 1) in problem1016C
•  » » 22 months ago, # ^ |   0 it is equivalent to int i=0,j=0; while(j
•  » » » 22 months ago, # ^ |   0 Thank you :)
 » 22 months 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 ?
•  » » 22 months 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
•  » » » 22 months 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.
 » 22 months ago, # |   0 I am not able to understand the logic for the question "SEGMENT OCCURRENCES". Can someone explain its logic??
 » 22 months 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
•  » » 22 months ago, # ^ |   0 basically it is the same solution
•  » » » 21 month(s) ago, # ^ |   0 I misunderstood the solution at first. My reply looks stupid now...
•  » » » 21 month(s) ago, # ^ |   0 Could you please provide any proof or explain the problem why such arrangement will provide a correct answer ?
•  » » » » 21 month(s) ago, # ^ |   0 it is written in editorial
 » 21 month(s) 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].
•  » » 21 month(s) 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
•  » » » 21 month(s) 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 :)
•  » » » » 21 month(s) ago, # ^ |   0 Glad it helped :). Keep coding!
 » 15 months ago, # | ← Rev. 3 →   0 Problem B: solved