### whfym's blog

By whfym, history, 5 years ago,

Solution By: Bingheng Jiang (NOIRP)

PS: The characters in problem 894A is Diamond and Bort from Land of the Lustrous.

Solution By: ZeRui Cheng (Marco_L_T)

Solution By: Bingheng Jiang (NOIRP)

Solution By: Bingheng Jiang (NOIRP)

Solution By: Yiming Feng (whfym)

Hope you had fun in this contest and got high rating!

See you next time!

• +172

 » 5 years ago, # |   +64 Thanks for light speed editorial and system test :)
•  » » 5 years ago, # ^ |   +32 Our pleasure :)
•  » » 5 years ago, # ^ |   +13 Maybe it is because there are not many submissions to test? Therefore, the system test is very fast?
 » 5 years ago, # |   +36 Hope you had fun with this contest and get high rating! See you next time!
•  » » 5 years ago, # ^ |   0 Thanks for the contest!
•  » » 4 years ago, # ^ |   0 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
•  » » » 4 years ago, # ^ |   0 You can look up a DP solution in contest status.
•  » » » » 4 years ago, # ^ |   0 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?
•  » » » » » 4 years ago, # ^ |   0 But it is not hard to solve this problem in O(n) XD
•  » » » » » » 4 years ago, # ^ |   0 Haha! Mr. Purple, understand that you are talking to a grey guy. xDThanks a lot for posting the O(n) code and the contest. :D
•  » » » » » 4 years ago, # ^ |   0
•  » » » » » » 19 months ago, # ^ |   0 This is a clever solution. Would you mind writing an editorial on how you arrived at this solution (using prefix sums)? I am computing variations of prefix sums with pencil & paper but cannot imagine how I could come up with this during the competition.
•  » » » » » » » 18 months ago, # ^ |   0 How is it a DP problem?
• »
»
»
»
»
22 months ago, # ^ |
0

# include <bits/stdc++.h>

using namespace std;

int main() { string s; cin>>s; int n=s.size(); int dp[n]; for(int i=0;i<n;i++) dp[i]=0; int count=0; for(int i=0;i<n;i++) { if(s[i]=='Q') count++; else if(s[i]=='A') dp[i]=count; } count=0; for(int i=n-1;i>=0;i--) { if(s[i]=='Q') count++; else if(s[i]=='A') dp[i]*=count; } int sol=0; for(int i=0;i<n;i++) sol+=dp[i]; cout<<sol; return 0; }

•  » » » » » » 19 months ago, # ^ |   0 I don't think this is a DP solution. I couldn't find how your solution solves the problem via subproblems for instance- could you elaborate?IMO this looks more like a prefix sum/ scan solution, one that is much easier to follow than OP's I might add!
 » 5 years ago, # |   0 What is this -> \t{1}?? Mathematical Processing error or anything else?
•  » » 5 years ago, # ^ |   0 emmm... it means 1 the \t{} maybe a processing error?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 Sorry it's my mistake. And I have fixed it now.
 » 5 years ago, # | ← Rev. 2 →   +34 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.
 » 5 years ago, # | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +5 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/)
•  » » » 5 years ago, # ^ |   +3 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! :)
•  » » » 5 years ago, # ^ |   0 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!
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » » » 5 years ago, # ^ |   0 it helped a lot! I really need to study it more, but the explanation answer things that wasn't that clear for me, thanks!
•  » » » » » 5 years ago, # ^ |   0 It helped me a lot, too. Thanks :)
•  » » » » » 5 years ago, # ^ |   0 why it should be a multiple of x ?
•  » » » » » 2 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 nice explanation good!!!
•  » » 5 years ago, # ^ |   0 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 != jnow 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.
 » 5 years ago, # |   +21 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
•  » » 5 years ago, # ^ |   +5 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   -16 Btw, Sharon,Your submission for A and this is too similar.
•  » » » 5 years ago, # ^ |   +22 It's exactly the same method.
 » 5 years ago, # |   +1 The contest was fun..... Thanks for such a great contest!!!!!
 » 5 years ago, # | ← Rev. 2 →   +5 Is there a solution for D that works for arbitrary trees instead of (almost) complete binary trees?Edit: Solved.
 » 5 years ago, # |   0 In problem B, why If k equals to -1 and the parity of n and m differ, the answer is obviously 0?
•  » » 5 years ago, # ^ |   +17 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
•  » » » 5 years ago, # ^ |   0 Thanks
 » 5 years ago, # |   0 Thanks for interesting and very interesting contest!!!
 » 5 years ago, # |   0 Sorry, what does mean [] in 2[(n - 1) * (m - 1)]?
•  » » 5 years ago, # ^ |   0 oh, got it. It means 2^((n — 1) * (m — 1))
 » 5 years ago, # |   +1 plz someone explane about "C" . I couldn't understand what I do
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » 5 years ago, # ^ |   0 here What is "S"??S contains all of GCD?????
•  » » » » 5 years ago, # ^ |   0 yes, it contains all gcd for all subarrays
 » 5 years ago, # |   +16 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])?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 !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
•  » » 5 years ago, # ^ |   0 Sorry, my previous post was not a valid proof. I think this one is, thoughIn 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 areaLet'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
 » 5 years ago, # |   0 in problem B, why "if k equals to -1 and the parity of n and m differ, the answer is obviously 0"?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +21 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.
•  » » » 5 years ago, # ^ |   0 I still don't get it at all! Not all numbers have to be -1.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » 5 years ago, # ^ |   0 Still don't understand ((
•  » » » » 5 years ago, # ^ |   0 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)
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +11 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.
•  » » » 5 years ago, # ^ |   0 Hi ntfoim, in your submission why do you add up INF-1 to m and n?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +1 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.
•  » » 5 years ago, # ^ |   +21 We know that:2(m - 1) * (n - 1) = (2m - 1)n - 1So first you can solve x:  = 2m - 1 mod 1e9 + 7 Then the answer is xn - 1 mod 1e9 + 7
•  » » 5 years ago, # ^ |   0 you could also use __int128
 » 5 years ago, # |   +1 Can someone give a more detail explanation of D's solution?
 » 5 years ago, # |   +1 Is there a DP solution for QAQ?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » 5 years ago, # ^ |   0 Thank you, I will try to understand it!
•  » » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   +5 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?
•  » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 years ago, # ^ |   0 Thanks for the clarification
 » 5 years ago, # |   0 in problem D how do we take into account the nodes not in its subtree?
•  » » 5 years ago, # ^ |   +6 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.
 » 5 years ago, # |   +3 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
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 Thank u so muchStill 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.
•  » » » » 5 years ago, # ^ |   0 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
 » 5 years ago, # | ← Rev. 2 →   +1 " 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?
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   +8 Well, the solution of the B problem makes me feel kinda stupid. Well, thanks for the editorial anyway!
 » 5 years ago, # | ← Rev. 2 →   +7 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.
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +16 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.
•  » » » 5 years ago, # ^ | ← Rev. 11 →   0 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.
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   0 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 cd e fg h iThen 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 xd e f yg h i zf g h rThere 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.
•  » » » » » » 5 years ago, # ^ | ← Rev. 3 →   +4 Fix the upper 3-by-3 matrix. Then a3i = ka2ia1ia0i,  ai3 = kai2ai1ai0.This implies that a30·a31·a32 = a03·a13·a23because 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 = knwhich is true. Now we can just select the value of a33which works.
•  » » » » » » » 5 years ago, # ^ |   +13 Big thanks Benq!!!To me it was a very big surprise that, you can swap from:a * b * c * x = kto: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.
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » 2 years ago, # ^ |   0 Thanks a lot, Benq amazing explanation.
•  » » 5 years ago, # ^ |   +1 " 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)
 » 5 years ago, # | ← Rev. 11 →   0 In problem C this test -> 3 1 15 25The author's solution produces -> 5 1 1 15 1 25so 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
•  » » 5 years ago, # ^ |   0 5 is the number of solution
 » 5 years ago, # |   0 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
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   +3 I’am sorry but it seems that you didn’t solve my confusionYou 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:)
•  » » » » 5 years ago, # ^ |   +1 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.
•  » » » » » 5 years ago, # ^ |   0 Excellent!Now you have solved my confusion!The case for k=-1 could be a little different though.Thx:)
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   0 Your logic is correct, but you have to take modulo by 10^9 + 7.
•  » » » 5 years ago, # ^ |   0 whups, what a silly mistake, thanks!
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   +21 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.
 » 5 years ago, # |   0 For 894D,can someone please explain how to get the sorted array of each vertax?Will we use dfs?
 » 5 years ago, # |   0 Auto comment: topic has been updated by whfym (previous revision, new revision, compare).
 » 5 years ago, # |   0 In problem B what is parity ? and what is the proof behind the solution in editorial ?
 » 5 years ago, # |   +5 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?
•  » » 5 years ago, # ^ |   +3 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.
 » 5 years ago, # |   -13 piece of shit
 » 5 years ago, # | ← Rev. 6 →   0 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 12From the above result, 2 will be gcd of all sub-arrays, and 4, 6, 12 are not gcd of any sub-array.
•  » » 5 years ago, # ^ |   0 Sorry got it, I thought i must be different than j.
»
5 years ago, # |
Rev. 2   0

894A - QAQ

# Solved

 » 5 years ago, # |   +4 May I ask for a more specific tutorial on question B? Too many "obvious" in the tutorial provided and I cannot get the point.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +13 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:xxxaxxxbxxxcdef?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
•  » » » 5 years ago, # ^ |   0 Thanks a lot for a detailed explanation.
•  » » » 5 years ago, # ^ |   0 Can you please explain problem C as well?
•  » » » » 5 years ago, # ^ |   0 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
•  » » » 5 years ago, # ^ |   +4 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.
•  » » » 5 years ago, # ^ |   +8 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 == kTo:x1 * x2 * x3 * k == aI 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!
•  » » » » 5 years ago, # ^ |   0 Thanks, glad I could be of help.
•  » » » » 5 years ago, # ^ |   +1 1 * 1 == 1 1 * (-1) == -1 (-1) * 1 == -1 (-1) * (-1) == 1  Haven't you seen this operation before?0 xor 0 == 0 0 xor 1 == 1 1 xor 0 == 1 1 xor 1 == 0 
•  » » » » » 5 years ago, # ^ |   0 Very nice analogy!
 » 5 years ago, # |   0 can anyone explain me problem 894C
 » 5 years ago, # |   0 in problem #447 CAre all the elements of the given set S gcd of some range (i,j) of the output (final sequence).Please clarify the doubt.
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   0 can anyone please explain E ?
 » 5 years ago, # |   0 Why always in queue?
 » 5 years ago, # |   +5 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.
•  » » 5 years ago, # ^ |   0 Wow!
•  » » 5 years ago, # ^ |   +5 Yes,it can be solved in O((n+m)logn),thanks a lot for pointing it out!
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   0 Can someone please help me find the bug in this:http://codeforces.com/contest/894/submission/32906228its code for problem E. I did: 1) SCC 2) DAG construction 3) DP
 » 5 years ago, # |   0 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??
•  » » 5 years ago, # ^ |   0 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 :)
 » 5 years ago, # |   0 In Problem C, My Solution: http://codeforces.com/contest/894/submission/33303911My 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Please read the statement carefully.And this input may help you:32 12 18Your output: 2 2 12 12 18 18GCD(12,18)=6However 6 is not in the set.
•  » » » 4 years ago, # ^ |   0 Just to elaborate in this (because it took me a while to understand)The problem statement says that set S contains the GCD of every continuous subset of array a. Also the constraints are 1<=i<=j<=n. Hence for every i=j, we simply insert a[i]. So for the given input:32 12 18Our final answer will be 2 2 12 2 18 2. For subset i=j, we'll insert a[i] in S. And for every other subset, we'll insert 2.
»
19 months ago, # |
0

FOR Coder Looking For O(N)=====>>>>

/* BABA JAGAAAAAA */

# define l long

using namespace std; const int mod= 1e9+7; const int inf=1e9+3; /* vectorparent; vectorrank; int find(int x)

{ if(parent[x]==x) return x; return parent[x]= find(parent[x]); // path compression// O(log n)

}

void merge(int a, int b)
{
int x1= find(a);
int x2= find(b);

if(rank[x1]<rank[x2])
parent[x1]=x2;
else if(rank[x2]<rank[x1])  //(lon n)
parent[x2]=x1;          // union by rank//
else
{
parent[x1]=x2;
rank[x2]++;
}

}

*/ void solve() { string s; cin>>s; int n=s.size(); int pre[n],suff[n]; memset(pre,0,sizeof pre); memset(suff,0, sizeof suff); s[0]=='Q'?pre[0]=1:pre[0]=0;

for(int i=1; i<s.size(); i++)
{
if(s[i]=='Q')
pre[i]=1+(pre[i-1]);

else
pre[i]=pre[i-1];
}
s[n-1]=='Q'?suff[n-1]=1:suff[n-1]=0;

for(int i=n-2; i>=0; i--)
{
if(s[i]=='Q')
suff[i]=1+suff[i+1];
else
suff[i]=suff[i+1];
}

int count=0;
for(int i=1; i<s.size()-1;i++)
{
if(s[i]=='A')
{
if(pre[i] && suff[i])
count+=(pre[i]*suff[i]);
}
}

cout<<count;

} int main() { fast;
int t=1; //cin>>t; while(t--) { solve();
cout<<"\n";
} return 0;

}

 » 12 months ago, # |   0 I've been looking for easy problems for recursion basics and 894A is perfect. It's a good problem to identify base cases, do a bit of work on the way down, and collecting the results.https://codeforces.com/contest/894/submission/120031377 import java.util.Scanner; public class Cf894a { public static void main(String[] args) { Scanner input = new Scanner(System.in); String message = input.nextLine(); int res = solve(message, 0, ""); System.out.println(res); } private static int solve(String s, int position, String current) { if (current.equals("QAQ")) { return 1; } else if (position >= s.length() || current.length() > 3) { return 0; } else { int res = 0; for (int i = position; i < s.length(); i++) { if (s.charAt(i) == 'Q' || s.charAt(i) == 'A') { res += solve(s, i + 1, current + s.charAt(i)); } } return res; } } }