### Superty's blog

By Superty, history, 4 years ago, Author: crvineeth97
Testers: deepanshugarg, nir123

Author's code

Author: RohanRTiwari
Tester: Superty

Author's code

Author: aman_shahi2
Tester: mprocks

Author's code

Author: RohanRTiwari
Testers: codelegend, Superty

Author's code

Author: born2rule
Testers: devanshg27, FundamentalEq

Author's code

There was an unexpected solution that involved bitset that runs in complexity O(N2 / 32). Have a look at Syloviaely 's code: 34364964

Author: RohanRTiwari
Testers: born2rule, devanshg27, additya1998, virus_1010, nir123

Author's code

Author: FundamentalEq
Tester: born2rule

Author's code

Author: Superty
Tester: codelegend

Author's code  458, Comments (122)
 » Afaik subset sum convolution takes O(2n * n2) time , so shouldn't the complexity for G be 217 * 172? Anyways since 317 is pretty small here , we can just use that.
•  » » I don't know a way to do this using 2n·n2 even though I was acquainted with this problem, however I was aware of 2n·n3 solution. Can you elaborate on that?
•  » » » For problem, in my code, function "subset_pow_convol" is O(Nlog(N)2  +  Nlog(N)2logK) (it theoretically can reduce to O(Nlog(N)2  +  Nlog(N)log(log(N))logK)). Here, we take K = 2.
•  » » » I googled the algorithm and the first link gives 2nn2 algorithm: Fourier Meets Mobius: Fast Subset Convolution. Do you inverse n2 products separately before adding them up?
•  » » » » Thank, that's indeed tricky to compute n forward transformations, multiply them and add accordingly and compute one backward transformation instead of using convolutions as blackboxes.
•  » » » » » All the above links seem overly complicated to me so i will just describe my approach which doesn't involve any fourier transforms. To calculate A*B , calculate FA[i][j] = A[j] if bitcount(j) = i else 0 , similarly calculate FB , now do sum over subset dp over this to have FA[i][j] = sum of FA[i][k] where k is subset of j bitcount(k) = i , do the same on FB , now calculate FC[i][j] = FA[j] * FB[i][j] + FA[j] * FB[i-1][j] + ... FA[i][j] * FB[j] , now FC[i][j] not only consists of relevant product from A and B but there is some overlapping , but the overlapping must have been counted in proper subsets of j hence we can do inverse sum over subsets dp to subtract them. Codevoid mult(int a[] , int b[]){ for(int i = 0 ; i <= n ; ++i){ moba[popcnt[i]][i] = a[i]; mobb[popcnt[i]][i] = b[i]; }  SOS DP for(int i = 0 ; i < LN ; ++i){ for(int j = 0 ; j < LN ; ++j){ for(int k = 0 ; k <= n ; ++k){ if((k >> j) & 1){ moba[i][k] += moba[i][k ^ (1 << j)]; mobb[i][k] += mobb[i][k ^ (1 << j)]; } } } }   for(int i = 0 ; i <= n ; ++i){ for(int j = 0 ; j < LN ; ++j){ int res = 0; for(int k = 0 ; k <= j ; ++k){ res += moba[k][i] * mobb[j - k][i]; } mobc[j][i] = res; } }  Inverse SOS DPfor(int i = 0 ; i < LN ; ++i){ for(int j = 0 ; j < LN ; ++j){ for(int k = 0 ; k <= n ; ++k){ if((k >> j) & 1){ mobc[i][k] -= mobc[i][k ^ (1 << j)]; } } } }   for(int i = 0 ; i <= n ; ++i){ result[i] = mobc[popcnt[i]][i]; } } 
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   That's exactly how I imagined this :). But it's good to have it clearly written here, so that maybe useful for others as well.
 » Can anyone explain the solution for C in brief. What does the precomputated DP array actually store ???
•  » » dp[k] stores the number of steps it takes k to reduce to 1. For instance, dp = 0 and dp = 3.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   what about the ncr array?? can you explain me the whole solution. i am not geting it at all.-
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   Sure. I won't be able to do it completely in depth, but I can try my best. The dp array can be calculated like this: set dp = 0. for(int i = 2; i <= 1000; i++) dp[i] = 1 + dp[__builtin_popcount(i)]; __builtin_popcount(i) just gives the number of 1 bits in incr is also sort of a dp array. It stands for the mathematical combination function. C(n, r) = n! / ((n — r)! * r!). There is a special property that C(n, r) = C(n — 1, r) + C(n — 1, r — 1), called Pascal's identity. So, you can set ncr[i] = 1 and ncr[i][i] = 1 for all values of i up to 1000. Then, you can iterate through and set ncr[i][j] = ncr[i — 1][j] + ncr[i — 1][j — 1]. (Also, this n is not the n from the problem) If you don't know what the combination function does, it tells you the number of ways to choose a subset of r elements from a total of n. Note that 0 <= r <= n. https://en.wikipedia.org/wiki/Combination might also helpOf course, all this while, you are doing calculation mod 1000000007.The reason we are choosing to have dp be size 1000 is because the value of n that we are given in the problem has at most 1000 1 bits. So, what we can do is iterate through the dp array. Whenevery dp[i] == k — 1, we can calculate the number of numbers <= n that have i one bits. In other words, we want the number of numbers no larger than n that reduce to i in one operation.The method to calculate this number is described in the editorial.
•  » » » » » thnx a lot. understood most of the part now. :-)
•  » » » » » Thanx. I really did not know about Pascal's identity. Thanx a lot.
•  » » » » » Hello , thanks for your explanation . could you please explain the solve function in more details http://codeforces.com/contest/914/submission/34369389Thanks
•  » » » » » » Okay, here I go trying to explain the solve function. First of all, what does it do? solve(numSet, currBit) gives the number of numbers <= n such that1) all the bits up to but not including the currBit-th bit (0 — indexing) in n match up2) there are exactly numSet one bits from the currBit-th bit onwards (inclusive).So this is what each line does:if(numset < 0) return 0;Obviously, you cannot achieve a negative number of one bits, so the answer in this case is 0.if(currBit == n.size()) return ((numset == 0) ? 1 : 0);If you hae gone through every single bit, you either return 1 if you need exactly 0 more one bits, or 0 otherwise since there is no more room for more one bits.ll res = 0; if(n[currBit] == '1') res += C(n.size() — currBit — 1, numset);Notice here that C(A, B) is the one described in my earlier post. It tells you the number of ways to choose B things from a total of A. Here, we say, if the current bit of n is a one bit, we can set our bit to 0 and then from here on out, the bits can be anything we want. So, out of the remainin n.size() — currBit — 1 bits, we can choose any subset of them with size numSet to be our one bits.res += solve(numset — ((n[currBit] == '1') ? 1 : 0), currBit + 1);Here, we set out current bit to whatever the current bit of n is, and then recursively solve the problem.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   If we have gone through every single bit then why do we have to return 1 if numset==0 ? Also why is res=(res-1+mod)%mod when k==1?
 » I'm completely lost on Problem C. Could anyone explain it in layman's terms? I'm not very familiar with binary in general.
 » could someone please explain what is "subset convolution"?
•  » » 4 years ago, # ^ | ← Rev. 3 →   First of all, I have just learnt about those, so please correct me if I said something wrong.If you are asking just about subset convolution, you can find definition and good algorithm for it in this book (page 125 in the book — page 133 in the pdf): https://link.springer.com/content/pdf/10.1007%2F978-3-642-16533-7.pdf UPD: I think this is better resource: http://home.iitk.ac.in/~gsahil/cs498a/report.pdf I will give a simple idea with an easy but slow algorithm for it: You have a Set U of n elements, and you have 2 functions f(x) and g(x) which takes subset of U as an input, and you want to produce third function: (f*g)(S) = sum (f(X)*g(Y)) for all X,Y such that X and Y are subsets of S and they are disjoint and their union is Simagine that subset is represented as mask of n bits: so 101 represents subset S = {first element of U, third element of U} so (f*g)(101) = f(101) * g(000) + f(100) * g(001) + f(001) * g(100) + f(000) * g(101)An easy algorithm for it is to iterate over all masks (S), then iterate over its submasks (X), if you have S and X, you can easily get Y, this run in complexity O(3^n)Code: for(int i= (1<= 0; i--) { for(int j = i ; j > 0 ; j = (j-1) &i) ret[i] += f[j] * g[i^j]; ret[i] += f * g[i]; } in problem G: if you considered n=17 and f(x) = g(x) = count(x), running convolution on those functions will get what is stated in the tutorial.------------------------- I will share other useful links about convolutions (not subset convolution): This tutorial explains XOR convolution using transformation: https://apps.topcoder.com/wiki/display/tc/SRM+518XOR, OR and AND transformations can also be done using karatsuba-like approach in nlogn (where n is number of elements), For XOR convolution nlogn karatsuba-like approach, see rng_58 post: https://apps.topcoder.com/forums/?module=Thread&threadID=720792&start=0For AND convolution nlogn karatsuba-like approach, see triveni solution: http://codeforces.com/contest/914/submission/34392096OR convolution nlogn karatsuba-like approach is similar to AND one.Hope this help :)
•  » » » Thank you very much!
 » Hey, I don't understand why my solution for problem D gets TLE. I think the time limit was really tight, but it shouldn't give TLE: http://codeforces.com/contest/914/submission/34387847
•  » » It should get TLE, this is n log^3 n, because gcd is a log factor. Put the bsearch into the tree and it will remove a log factor
 » In H, I think tree[i][j] can be calculated in O(n3) if you enumerate the size of subtree of the child which has the minimum index during the transition.BTW, such a weak sample input makes me confused. I think it will be much better if you add a larger sample or give a more detailed explanation about the modification Ember could do (I think this process is a little bit complex and is somehow hard for me to understand well).
•  » » Yes, I think you're right. Nice.I wasn't sure how to improve the sample case without giving away the game. Yes, we should've given a more detailed explanation.
 » 4 years ago, # | ← Rev. 2 →   I see many Div2D solutions having complexity O(q*logn*logn) failed. My solution also had same complexity and is wrong!Code This part is wrong!g1=query1(1,1,n,mid+1,r); if(g1%x==0) return go(mid+1,r); //note it should be go(l,mid); g2=query1(1,1,n,l,mid); if(g2%x==0) return go(l,mid); //it should be go(mid+1,r); return false;  Example Looks like I was too lucky yesterday night! :)
 » 4 years ago, # | ← Rev. 2 →   I had the same solution for C . Missed the k = 1 Case :( . I did it using simple meimoization and not using binomial coefficients http://codeforces.com/contest/914/submission/34399092
•  » » Why at yesterday's contest problem C if k==0 the answer is one ?
•  » » » For k == 0 there is only one number which will be always less than or equal to any given n . That number is 1
•  » » » » i couldn't understand the problem is how many numbers less than or equal to n after k operations will be reduced to one right ?
•  » » » » » Yes. But you have to find minimum operations. If n == 1 then minimum operations would be 0 coz it's already 1 .But for any other number at least 1 operation would be required.So for k==0 there is only one number
•  » » » » » » thanks alot i got it :)
•  » » Not only did I fail the k==1 case, but I also unsuccessfully hacked solutions cause I thought their k==1 case was bugged :)
 » Can someone explain what the mask[u] is in E? Are we taking the path from the centroid to u? Does it matter if the paths of u and v intersect or does the solution only consider when u and v are in different parts?
•  » » 4 years ago, # ^ | ← Rev. 3 →   mask[u] has cnt[j]%2 at jth bit in binary representation of mask[u], considering characters from root to u. Now when we root the tree at centroid, we consider the paths from root to subtree of u and from subtree of u to vertices in other parts when we calculate answer for u. We do this for each centroid.
 » 4 years ago, # | ← Rev. 2 →   1030757 30757 33046 41744 39918 39914 41744 39914 33046 33046how the ans for this will be Conan .. plzz expalain
•  » » Sorted input: 30757 30757 33046 33046 33046 39914 39914 39918 41744 41744 Conan takes 39918Agasa takes 41744Conan takes 41744
•  » » » he must choose LARGEST CARD in order to delete max no of cards so he can ensure its winning .But why u choose 2 largest card why not 41744 IN turn of conan .. by ur case he is not PLAYING OPTIMALLY expalin me i'm confused
•  » » » » The editorial explains it better than I could. If you have any doubt you can ask.
•  » » » » It is not optimal to remove as many cards as possible.It is optimal to play in such a way that you win. This winning strategy is explained in the editorial.
•  » » » » » what a great editorial mate :)
•  » » » » » I have two questions regarding the PROBLEM — C1-- Since the number of set bits in numbers smaller than2^1000 is less than 1000, any number smaller than 2^1000 would reduce to a number less than 1000 in one step. Can u give me a valid proof for this using an example 2-- How do u assume that the min no of steps req to convert a no in to 1 is equal to the order of that no and what role order signifies here.
•  » » » » » » A number less than 21000 has at most 1000 digits in binary, so it can have at most 1000 digits set to 1. We are defining order here.
•  » » » » » » » Can u tell me the order building logic behind it .and what DP array contains
•  » » » » » » » » Try to solve Collatz Problem, you'll get the insight of what you're asking.
 » 4 years ago, # | ← Rev. 2 →   In C We can iterate through all possible i and compute the answer using binomial coefficients.How?
•  » » Check the code for clarification. For a given i (as defined in the statement) the number of possibilities for indices i + 1 to n to have k ones is n - i choose k.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   I had understood that but can't understand the logic behind it...Can you please explain?
•  » » » » Got it.
 » Can somebody tell me what's wrong with my code for Problem C. I can't figure it out. My Solution
 » Can someone explain why this code fragment is used? if(i == 0 && k == 1) ans = (ans+MOD-1)%MOD
 » in Problem C, why do we use Binomial co-efficients? and what is the logic of this line?Every number x < n satisfies the property that, for some i (1 ≤ i < k), the first i - 1 digits of x are the same as that of n, the ith digit of n is 1, and the i-th digit of x is 0. We can iterate through all possible i and compute the answer using binomial coefficients, that can be computed in O(l) where l is the length of binary representation of n.Please explain
 » One more alternate solution for problem F : Define x = 25 For any query string of length > x directly do KMP otherwise we will use hashing to match. For each length 1<=l <= x we can keep hash array say hash[.i..] which will contain hash of substring starting from each index, i, and of length l. Note that this will take O(n) for each l. To update, we need to update the hash arrays for each l and each update takes O(l). So, overall it can be done in O(x^2) per update. To query in a range, we also need to decompose the hash array into sqrt(n) buckets for each l. Also for each bucket keep a hashmap so that it is O(1) to find how many matches occur in a bucket. Note that there is lot of optimization needed to get it through. Here is my submission 34404651, if anyone is interested. Note that unordered map won't work, I had to implement simple hash table. Also many dirty optimizations like, unsigned short int etcetera.
•  » » Note that there is lot of optimization needed to get it through. Don't do KMP, just naive substring comparison Don't do SQRT-decomposition, just naive loop that will count hashes And redefine x = 12, so hashes will fit into int64, and it will be deterministic solution. http://codeforces.com/contest/914/submission/34377829
•  » » » 4 years ago, # ^ | ← Rev. 2 →   Looks like O(n3 / 32). Does it pass only because of weak tests?
•  » » » » It's O(N2). Let K=lengh of queries, each query is O(NK) for K>12, and O(N) otherwise, and we have N/K queries
•  » » » » » You right.
 » Can someone tell, what is wrong in my iterative segment tree solution of D 34410510
 » I have one doubt in problem C. Question is asking about numbers which can be reduced to 1 in minimum k steps. then shouldn't we have to compute for all dp[i]>=k-1 ? Here we are calculating for the numbers that will be reduced to 1 in exactly k steps. Correct me if I am wrong or have misunderstood something. Thanks.
•  » » From what I can understand from your comment, I think you are a bit confused between the terms "minimum" and "at least". Please note that after reaching 1, the added number of operations that you will do will be redundant and thus won't fit into the category of "minimum". Thus we will be picking elements from the dp[] which are exactly equal to k-1 and not such that dp[i]>=k-1. I hope this helps.
•  » » » Thanks.I understood now.
 » can anyone explain problem c in simple layman's term. unable to understand second test
•  » » 4 years ago, # ^ | ← Rev. 3 →   The number of steps to reduce a number x is entirely determined by the number of 1 in its binary representation. Let f be the function f(x) = number of 1 in its representationCompute in table d recursively the number of steps required to reach 1 from every number from [1,1000]. d[i]=d[f(i)]Then go through this table, for each of the values i so that d[i] is equal to k, you need to add the number Z(n,i) of numbers not greater than n that have i 1 in their representation. As a special case, you'll have to remove 1 from this number if k==1, because of the fact that 1 becomes 1 in 0 steps. let p be the number of digits of the binary representation of n.You already know that there are C(p,i) ways to make a number lower than 2^p with i 1. C is the combination function. You'll need these values for p<=1000 you can compute these recursively.Let Y(n,p,i) be the number of number greater than n, but with no more than p in its binary representation that have i 1 in their representation. Thus Z(n,i)=C(p,i)-Y(n,p,i)Thus if you compute Y(n,p,i), you win !You can compute Y(n,p,i) recursively on p. by using the digits of the representation of n.If the first digit of n is 1, Y(n,p,i)=Y(n',p-1,i-1) where n' is n with the first digit removed. That is because no number starting with 0 is greater than n.If the first digit of n is 0, Y(n,p,i)=C(p-1,i-1)+Y(n',p-1,i) This is because all numbers starting with 1 will be greater than n (there are C(p-1,i-1) cause the first one is already placed and you got p-1 slots remaining for i-1 "1" digits).You can also stop as soon as the second argument becomes lower than the third argument, cause in that case Y is worth zero.Then you can output the sum of Z(n,i) (or as stated above Z(n,1)-1 if k==1)
•  » » » Are you sure it is k instead of i in Y(n,p,i)=C(p-1,k-1)+Y(n',p,i) ?
•  » » » » Thanks you were correct, I tried to fix my mistakes.
•  » » » » » 4 years ago, # ^ | ← Rev. 4 →   Thanks for fixing but please replace all the remaining k's below this line"If the first digit of n is 0, Y(n,p,i)=C(p-1,i-1)+Y(n',p-1,i) This is because all numbers starting with 1 will be greater than n"in your post with i so that it is clear for others who will read the post.
•  » » » can you take a example small one other than given test cases and 'k' , i ,mean a binary of 'n' and 'k'. and solve it according the statement you have above written.it would be easy to grasp your logic.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   OK :110001 3I create recursively a value of the number of steps taken to reach 1 depending on the number of "1" bit in the initial binary representation. I find that all the numbers that have 3,5 or 6 "1" initially will work, i.e. give 3 steps to reach 0. I will go through these cases : doing 6 Computing Y(110001,6,6) Computing Y(10001,5,5) Computing Y(0001,4,4) added 1. because C(3,3)=1 Computing Y(001,3,4) added 0. because C(2,3)=0 Computing Y(01,2,4) added 0. because C(1,3)=0 Computing Y(1,1,4) adding C(6,6)- Y(110001,6,6) = 1 - 1 doing 5 Computing Y(110001,6,5) Computing Y(10001,5,4) Computing Y(0001,4,3) added 3. because C(3,2)=3 Computing Y(001,3,3) added 1. because C(2,2)=1 Computing Y(01,2,3) added 0. because C(1,2)=0 Computing Y(1,1,3) adding C(6,5)- Y(110001,6,5) = 6 - 4 doing 3 Computing Y(110001,6,3) Computing Y(10001,5,2) Computing Y(0001,4,1) added 1. because C(3,0)=1 Computing Y(001,3,1) added 1. because C(2,0)=1 Computing Y(01,2,1) added 1. because C(1,0)=1 Computing Y(1,1,1) adding C(6,3)- Y(110001,6,3) = 20 - 3 19 The logic : it's easier to remove numbers too big rather than to count all numbers below a certain threshold cause it enables a closed form formula (the combinations). if your threshold starts with a 0, you disqualify all numbers that start with a 1 and have the correct number of 1 (they are all higher than your threshold, and you got a closed formula), Then you need to disqualify all numbers above your threshold, that start with the same number as your threshold. For this, you recurse (removing the first number of your threshold, and decreasing the number of required "1" in your representation by 1 if your threshold first digit was "1".
•  » » » » » Thanks a lot
•  » » 4 years ago, # ^ | ← Rev. 2 →   The initial approach to the question revolves around thinking that the maximum number of ones that can come in the binary representation of a number n<2^1000 will be 1000. Thus, just in one step, from a large number, you will have reduced second level number less than or equal to 1000. Also, now you will be left with k-1 operations as you used one before. You can precompute the number of steps required for all i from 1 to 1000 to be reduced to 1 in an array, say arr[]. For all i's, if arr[i]==k-1, that means you have to place i number of 1's in a string of size l(size of given number's string in binary representation) such that the number formed doesn't exceed the given number n. This can easily be done by one simple "for" loop. You permute these using nCr function which one must mind to precompute for 1<=n<=1000 and 1<=r<=1000, otherwise will give TLE. Also mind special cases like n=1 and k=1.
•  » » » In the function cntperm , why are you doing temp--?? I am not able to understand this part!
•  » » » » In the function cntperm(), temps hold the number of 1's that I have to place after index i. So, say for string 10011001, if temp=2, the first iteration(i=0) calculates the number of ways that exist which have a '0' at index i=0 and two 1's after i=0. The answer will be 7C2. By placing 0 at index i=0 and 2 1's only after that ensures that all the permutations produced are less than the given number. Now, I place '1' at i=0 and move forward in the next iteration i.e i=1. So the remaining number of 1's that I will be working with will be 1 less than the previous count that is temp-1. That's why I am doing temp--. Also, if I have used all the ones (when temp becomes 0), I am left with no more permutations except that I fill all the remaining places after that by only zeros. So, I increase the count by one for one final time and exit the loop.
•  » » » » » Thank you. Your explanation clears a lot of things for me. :)
•  » » » » » Great explanation. Thanks for taking time and explaining!
 » can somebody please tell me what is wrong with my solution for C code
 » 4 years ago, # | ← Rev. 2 →   Solution to D is wrong.Consider Following test case.44 4 7 411 1 4 2The problem statement states that He considers the guess to be almost correct if he can change at most one element in the segment such that the gcd of the segment is x after making the changeThe answer should be NO, because if we change 7, gcd of segment become 4, else gcd of segment is 1. In no case we can make gcd of range 2. I didn't even implement, because of this.Shouldnt the problem state that gcd of segment shall be divisible by x for your solution to be correct???EDIT: got my mistake... Sorry
•  » » I think you could change the third element in the array to be 2, and the gcd will become 2, so it don't need to state that gcd of segment shall be divisible by x.
•  » » » I already got my mistake (even edited my comment above).Thanks for reply.
 » Can someone tell me why this solution34419524 got accepted for problem A(Perfect Squares) since sqrt of negative numbers gives 'nan'.
•  » » Because any operation with NaN gives a NaN and NaN is unequal to itself. floor(NaN) is NaN, ceil(NaN) is NaN, NaN != NaN, and hence floor(NaN) != ceil(NaN), so the program thinks “this (negative) number is not a square”, which is correct.
 » Can someone please elaborate the solution of problem E ? It's almost impossible to understand it from the given editorial ?
•  » » 4 years ago, # ^ | ← Rev. 3 →   First root the given tree on its centroid. Now for each node u, masku has at jth bit in binary representation of masku, considering count of characters from root to u. We can say that a path from u to v is palindromic if has at most 1 set bit. Now let partv be defined as subtree of vertex v such that v is children of the centroid. Now we consider all paths that include centroid. For each node u, valid paths are the paths ending in part other than partu, and starting from any node in subtree of u including itself and satisfying the above property. Valid masks for a node u are: mask[u] and . Let otheru be the sum of all valid masks from other parts for u. So for u, otheru will be such that v lies in its subtree (including itself) . Hence add it to the answer. For root (centroid), answer will be summation of cnt1[mask[u]]·cnt2[maskx] for all u, such that cnt1 is count of masks in part of u, and cnt2 is count of masks in other parts and maskx are valid masks of u.Now solve recursively for each of the parts.
•  » » » Can you please explain the role of dfs1() & dfs2() function?
•  » » » » dfs1() calculates the mask for each vertex. dfs2() calculates the answer for each vertex. dp[u] is the the number of paths starting from subtree of u and ending in any other part.
•  » » » » » cnt and cnt[1<
•  » » » » » » Paths which go from one part to another are counted twice. And we add paths from u to root once when we solve for each vertex u. To make their count twice, we add paths from root to u again. Now we add dp[r]/2 to the ans.
•  » » » 3 years ago, # ^ | ← Rev. 4 →   Can you please elaborate how we get the paths from nodes that we've already removed as centroids? I read the explanation twice but couldn't understand how that's resolved. ThanksEDIT: nvm, it is very simple, just add the aggregated values to the nodes when you dfs.EDIT 2: oops still 6 hours of queue that I forgot about
 » Problem E editorial is not clear. Please, somebody explain it better.
•  » » This might be helpful.
 » anyone could explainthe proof for D problem ?
•  » » 4 years ago, # ^ | ← Rev. 4 →   First Consider that GCD of the complete range is X .That means each element in the range should have X as their factor .Now consider the original problem.If say one number is such that it is not a multiple of X that is it doesn't contain X in its factors. If there was no GCD involved and the test cases were such that an O(N*Q) passes then we could easily count the number of elements not a multiple of X. If count is <=1 then answer is YES else No.Why ? Because I know all elements except this one element doesn't have X in them so I can simple replace that single number with X and thus GCD of range is X.We can only replace by X and not by any other factor of X. Why ? Say numbers are A,B,C,D A=4X,B=5X,C=2X,D=say 1 Now if D is changed to X the GCD is X right ?Now We just have to optimize this using above logic in segment tree.You have to check the nodes and keep a track of the node where GCD is not a multiple of X .If it isn't we have to find all those elements which are not a factor of X.Example :- say a parent node has two children nodes having info as gcd of {A,B} and {D,E} say A,B & D are factor of X and E isn't then,when we reach D,E we need to further check E and D and determine the count of the number not divisible by X. if cnt<=1 ans is YES (i.e we will replace this E by X) else answer is NO.
 » Can somebody please explain me the computations being done in the ncr matrix? I understand what is being done there but not how. Thanks!
•  » » You can compute using the identity .
•  » » » if(i == 0 && k == 1) { ans = (ans+MOD-1)%MOD; } why ans need to substract 1 for k==1?
•  » » » » Basically this chunk of code do when k = 1.You can obviously see that answer will be n - 1.If it is not used then after the first iteration the ans will be updated by (n - 1). and after second iteration it will be n (only for the case k = 1) which is not possible.So for handling this an extra one is deducted from result.
 »  long long nones = 0, ans = 0; for(int i = 0; i < n.size(); i++) { if(n[i] == '0') { continue; } for(int j = max(nones, 1LL); j < 1000; j++) { if(dp[j] == k-1) { ans = (ans + ncr[n.size()-i-1][j-nones])%MOD; if(i == 0 && k == 1) { ans = (ans+MOD-1)%MOD; } } } nones++; } I am not able to understand what this code segment of the 3rd question doing.Can anyone help me?
•  » » 4 years ago, # ^ | ← Rev. 2 →   As the solution says, we can bruteforce all the possible prefixes. So I refers to which bit we are up to, since the first difference should be x[i]=1,y[i]=0 (otherwise it clashes with the constraint)Say we have used “nones” 1s, we are going to pick the left 1s we can pick to insert into the suffix. The number of such thing can be calculated by binomial coefficients.
 » Would anyone like to explain the solution to F which is created Syloviaely? appreciate it :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   I am gonna give it a try.Notice that in bitset x[i] the positions on the original string that have character 'a'+i are set to 1. For example if the original string is "hahati" we will have 2nd and 4th bit of x set and X will have 1st and 3rd bit set to 1 and so on. I think you can easily figure out how the update operation was done.Now for query, at the beginning all bits of ans are set. Now let's see what happens at the very first iteration in the for loop of 1 to len. An AND operation was done with the bitset of corresponding character with 1 right shift. What will it do? It will kepp the 0th bit of ans set and all other bits with same relative distance as in the characters bitset. For example if our query string is "ha", our first character is 'h' so an AND operation with X<<1 will keep 0th and 2nd bit of ans set to 1 and all other reset to 0. Second character is 'a', a right shift with 2 for X will keep 0th and 2nd bit set and after AND with ans 0th and 2nd bit of ans is set. We do this for all characters in the string and if even a single character doesn't match along the way corresponding bit will be reset to 0. For example if we had "hat" as our query on the third iteration for character 't' 0th bit will be reset to 0 but the 2nd one won't.This way ans will store all the positions where a query string starts as substring in the original string. But we don't need all the positions, only the positions between l to r-len+1. That's what was done in the last line.Here is the solution in question if someone was wondering.
•  » » » get it, ty :)
•  » » » » can you please explain the query part with an example. I never used bitset so, having difficulty in understanding this. Thanks!
 » can anyone please help me with my code for F : solution It is giving MLE. I used suffix tree and it requires O(n) space and so my complexity will be around O(n*28). I am unable to figure out the reason please help me.
 » Please someone explain the editorial of Problem E
•  » » This might be helpful.
 » 4 years ago, # | ← Rev. 2 →   In solution of problem H para.7: "where tree[i][any] is the number of trees of i vertices with any root degree from 1 to d. " Maybe I think there's a mistake: not d but d-1 ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   And could someone explain how to calculate the denominator of value c in module p which is not guaranteed a prime ? Thanks a lot.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   Yes, you're right. It should be d - 1. The editorial has been updated. Thanks!As for your second query, observe that and so •  » » » » Got it. Thank you very much.
 » Need help Problem D: Keep getting TLE, can't understand why, should be pretty fast. http://codeforces.com/contest/914/submission/34645114
 » In the editorial for problem C, For each x (x < 1000) such that x has order k - 1, we need to compute the number of numbers less than or equal to n that have k set bits.Don't you mean, For each x (x < 1000) such that x has order k - 1, we need to compute the number of numbers less than or equal to n that have x set bits.
•  » » Yes, you are right. Since we are using 1 step to go from n to x and now x must have order of k — 1.
 » In the author's solution to C, what does the following piece of code do if(i == 0 && k == 1) { ans = (ans+MOD-1)%MOD; } 
•  » » Yes, can someone please explain this, it is not quite clear whether the following case "10000..00" (zeroes = length(n) — 1) is being excluded (but why?) or something else is taken care by this statement?
 » 3 years ago, # | ← Rev. 2 →   in D i am getting Time limit exceeded in test case 8. Plz help me! this is my submission :- 35174367
 » int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tests=1; //freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); //cin>>tests; { string s; cin>>s; int k; cin>>k; int c1 = 0,c0=0; for(int i = 0;i
 » Help For Cint main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tests=1; //freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); //cin>>tests; { string s; cin>>s; int k; cin>>k; int c1 = 0,c0=0; for(int i = 0;i
 » in div2 c..whenever k==1 then an extra count will appear for value ==1...becoz 1 has count of ones ==1 ans dp[cnt]=dp=0(k-1).. if(i == 0 && k == 1) { ans = (ans+MOD-1)%MOD; } this code is only to avoid this condition..:)
 » Why the solution of G is not expected to be o(3**N)I wrote it and it passed in only 1800 ms...I didn't knew about subset sum convolution but it was great...
 » For 914C — Travelling Salesman and Special Numbers, one can simply use __builtin_popcount() to replace the ones() function in the editorial. Bye.
•  » » It should be __builtin_popcountll()!
 » I've been struggling with D for several hours now. Here is my submission: https://codeforces.com/contest/914/submission/91172586.I'm using the efficient segment tree from https://codeforces.com/blog/entry/18051 blog. The cnt function counts how many bad gcds there are, and should be O(log(n)) as you go down at most one branch of the binary tree. Cnt is called at most once every query, so the total complexity of each query should be log(n). However, I am getting TLE on test #8 and I have no idea why.Any help would be greatly appreciated. I have just learned segment trees and this is part of my practice for segment trees, so I may just be using it incorrectly. The code passes the first 7 test cases though, so I'm at a loss.
 » Sorry for bumping this, but isn't the time complexity for D O(q*n*log(n))?I got this complexity from the factor of q from the number of queries, the log n from decomposing the original range, and a factor of n to check if a node works if it is not a multiple of n. If this is true, won't the program TLE? Or is my complexity wrong?
 » In problem D, The size of the arrays in the solution code are much smaller than the task's requirement. When node is 5e5, will arrays' index overflow occur?