JahonaliX's blog

An interesting problem that I couldn't solve
By JahonaliX, history, 6 hours ago, In English

Hi everyone.

Please help me to solve this problem.

You are given a binary string s which is permutation of 0000000000000001111111111111111 (15 0s and 16 1s), you should find x such that s is lexiographic xth permutation of 0000000000000001111111111111111.

  • Vote: I like it
  • +25
  • Vote: I do not like it

»
6 hours ago, # |
  Vote: I like it +16 Vote: I do not like it

Very easy problem since 1798 in CHINA

→ Reply
»
5 hours ago, # |
  Vote: I like it +14 Vote: I do not like it

We can compute the total number of permutation for x zeros and y ones by (x+y)! / (x! * y!). Let f(x,y) be (x+y)! / (x! * y!).

c0=15,c1=16 ans=0

Iterate on index i from 0 , If s[i] is '1' then there will be some number of permutation which are smaller than the current permutation , at this index, so we have to add the number of such permutations. for s[i] = '0' then we don't have any element smaller than 0 so the permutation can't be smaller at this index.

If s[i] == '1' then the permutation to be smaller at this index we need to place zero at this index, if c0==0 then just continue else when we place zero then any permutation of the remaining elements will be smaller so add f(c0-1,c1) to ans.

subtract one from c0 or c1 according to s[i], if s[i]=='0' then from c0 else from c1.

→ Reply
  • »
    »
    5 hours ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Thank you.

    I have an another question when we are given x how to find s.

    → Reply
    • »
      »
      »
      5 hours ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I think that can be solve in a similar way.

      At each index we can try to put '1' if the permutation smaller than current exceeds x we are forced to put 0 else we put 1,at the end we will the desired permutation.

      → Reply
      • »
        »
        »
        »
        5 hours ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        Can you please give code for both.

        → Reply
        • »
          »
          »
          »
          »
          5 hours ago, # ^ |
          ← Rev. 3   Vote: I like it +11 Vote: I do not like it
          Updated Code
          → Reply
          • »
            »
            »
            »
            »
            »
            4 hours ago, # ^ |
            ← Rev. 7   Vote: I like it +13 Vote: I do not like it

            Thank you, but get_perm is working wrong (always returns 31 1s).

            UPD: worked, it was overflow.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              48 minutes ago, # ^ |
                Vote: I like it +2 Vote: I do not like it

              yeah you are right we might have to use int128(__int128 in G++ 20) or use some other way around.

              → Reply
          • »
            »
            »
            »
            »
            »
            39 minutes ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            $$$31*30*....*17 \ge 10^{20}$$$

            To avoid overflows it's better to divide simultaneously. 

            int mut = 1;
for (int k = 1; k <= y; k++) {
   mut *= p - k + 1;
   mut /= k;
}

            Why does this work? We first compute $$$C(p, 1)$$$, which in the next iteration will become $$$C(p, 2)$$$, and so on. Thus, dividing will not be a problem.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              31 minute(s) ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Thanks for suggesting the change, but you forgot to use long long.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                29 minutes ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                Nice catch. It could possibly overflow during multiplication.

                Solution:

                #define int long long
                → Reply