JahonaliX's blog

An interesting problem that I couldn't solve
By JahonaliX, history, 3 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
  • +20
  • Vote: I do not like it

»
3 hours ago, # |
  Vote: I like it +13 Vote: I do not like it

Very easy problem since 1798 in CHINA

→ Reply
»
2 hours ago, # |
  Vote: I like it +5 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
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Thank you.

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

    → Reply
    • »
      »
      »
      2 hours ago, # ^ |
        Vote: I like it +1 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
      • »
        »
        »
        »
        2 hours ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Can you please give code for both.

        → Reply
        • »
          »
          »
          »
          »
          109 minutes ago, # ^ |
            Vote: I like it +4 Vote: I do not like it
          Code
          → Reply
          • »
            »
            »
            »
            »
            »
            62 minutes ago, # ^ |
            ← Rev. 7   Vote: I like it +7 Vote: I do not like it

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

            UPD: worked, it was overflow.

            → Reply