Superty's blog

By Superty, history, 7 months ago, In English,
Tutorial is loading...

Author: crvineeth97
Testers: deepanshugarg, nir123

Author's code
Tutorial is loading...

Author: RohanRTiwari
Tester: Superty

Author's code
Tutorial is loading...

Author: aman_shahi2
Tester: mprocks

Author's code
Tutorial is loading...

Author: RohanRTiwari
Testers: codelegend, Superty

Author's code
Tutorial is loading...

Author: born2rule
Testers: devanshg27, FundamentalEq

Author's code
Tutorial is loading...

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
Tutorial is loading...

Author: FundamentalEq
Tester: born2rule

Author's code
Tutorial is loading...

Author: Superty
Tester: codelegend

Author's code
 
 
 
 
  • Vote: I like it  
  • +84
  • Vote: I do not like it  

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +49 Vote: I do not like it

          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[0][j] * FB[i][j] + FA[1][j] * FB[i-1][j] + ... FA[i][j] * FB[0][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.

          Code
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the solution for C in brief. What does the precomputated DP array actually store ???

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dp[k] stores the number of steps it takes k to reduce to 1. For instance, dp[1] = 0 and dp[13] = 3.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      what about the ncr array?? can you explain me the whole solution. i am not geting it at all.-

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it +11 Vote: I do not like it

        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[1] = 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 i

        ncr 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][0] = 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 help

        Of 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.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thnx a lot. understood most of the part now. :-)

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanx. I really did not know about Pascal's identity. Thanx a lot.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hello , thanks for your explanation . could you please explain the solve function in more details http://codeforces.com/contest/914/submission/34369389

          Thanks

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 that

            1) all the bits up to but not including the currBit-th bit (0 — indexing) in n match up

            2) 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.

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm completely lost on Problem C. Could anyone explain it in layman's terms? I'm not very familiar with binary in general.

»
7 months ago, # |
  Vote: I like it +42 Vote: I do not like it

could someone please explain what is "subset convolution"?

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    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 S

    imagine 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<<n) - 1; i >= 0; i--)
    {
        for(int j = i ; j > 0 ; j = (j-1) &i)
            ret[i] += f[j] * g[i^j];
        ret[i] += f[0] * 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+518

    XOR, 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=0

    For AND convolution nlogn karatsuba-like approach, see triveni solution:
    http://codeforces.com/contest/914/submission/34392096

    OR convolution nlogn karatsuba-like approach is similar to AND one.

    Hope this help :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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).

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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!
Example

Looks like I was too lucky yesterday night! :)

»
7 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why at yesterday's contest problem C if k==0 the answer is one ?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For k == 0 there is only one number which will be always less than or equal to any given n . That number is 1

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            thanks alot i got it :)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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 :)

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

10

30757 30757 33046 41744 39918 39914 41744 39914 33046 33046

how the ans for this will be Conan .. plzz expalain

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorted input: 30757 30757 33046 33046 33046 39914 39914 39918 41744 41744

    Conan takes 39918

    Agasa takes 41744

    Conan takes 41744

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The editorial explains it better than I could. If you have any doubt you can ask.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          what a great editorial mate :)

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I have two questions regarding the PROBLEM — C

          1-- Since the number of set bits in numbers smaller than
          2^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.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            1. A number less than 21000 has at most 1000 digits in binary, so it can have at most 1000 digits set to 1.

            2. We are defining order here.

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Can u tell me the order building logic behind it .and what DP array contains

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Try to solve Collatz Problem, you'll get the insight of what you're asking.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In C We can iterate through all possible i and compute the answer using binomial coefficients.How?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody tell me what's wrong with my code for Problem C. I can't figure it out. My Solution

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain why this code fragment is used? if(i == 0 && k == 1) ans = (ans+MOD-1)%MOD

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

      Looks like O(n3 / 32). Does it pass only because of weak tests?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell, what is wrong in my iterative segment tree solution of D 34410510

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain problem c in simple layman's term. unable to understand second test

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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 representation

    Compute 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)

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are you sure it is k instead of i in Y(n,p,i)=C(p-1,k-1)+Y(n',p,i) ?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks you were correct, I tried to fix my mistakes.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        OK :

        110001 3

        I 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".

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In the function cntperm , why are you doing temp--?? I am not able to understand this part!

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you. Your explanation clears a lot of things for me. :)

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Great explanation. Thanks for taking time and explaining!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody please tell me what is wrong with my solution for C code

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Solution to D is wrong.

Consider Following test case.

4

4 4 7 4

1

1 1 4 2

The 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 change

The 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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why this solution34419524 got accepted for problem A(Perfect Squares) since sqrt of negative numbers gives 'nan'.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Can someone please elaborate the solution of problem E ? It's almost impossible to understand it from the given editorial ?

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain the role of dfs1() & dfs2() function?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          cnt[0] and cnt[1<<i](for i=1:20) are added to dp[r] only once. where are these added twice? As we are making ans[r]=dp[r]/2, shouldn't those cnts be added twice?? Can you please describe the second position?

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      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. Thanks

      EDIT: 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

»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Problem E editorial is not clear. Please, somebody explain it better.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone could explainthe proof for D problem ?

  • »
    »
    7 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain me the computations being done in the ncr matrix? I understand what is being done there but not how. Thanks!

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can compute using the identity .

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      if(i == 0 && k == 1)
              {
                ans = (ans+MOD-1)%MOD;
              }
      

      why ans need to substract 1 for k==1?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it
 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?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Would anyone like to explain the solution to F which is created Syloviaely? appreciate it :)

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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[0] set and X[7] 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[7]<<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[0] 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      get it, ty :)

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you please explain the query part with an example. I never used bitset so, having difficulty in understanding this. Thanks!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone explain the editorial of Problem E

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    And could someone explain how to calculate the denominator of value c in module p which is not guaranteed a prime ? Thanks a lot.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, you're right. It should be d - 1. The editorial has been updated. Thanks!

      As for your second query, observe that

      and

      so

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Need help Problem D: Keep getting TLE, can't understand why, should be pretty fast. http://codeforces.com/contest/914/submission/34645114

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

in D i am getting Time limit exceeded in test case 8. Plz help me! this is my submission :- 35174367