crackme321's blog

UVA — 13002 — Just Some Permutation 5
By crackme321, history, 8 years ago, In English

Can anyone please tell me the process how to solve this problem .

link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4890

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

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You can optimize the n^2 * 2^n dp by grouping integers together. Lets say n = 28. Instead of keeping a mask of 28 bits, observe that you can group powers of 2 together and keep a count of how many of this group you used instead of a mask. There are 4 powers of 2 less than 28, so this already reduces your state from 2^28 to 2^24(for the other 24 numbers) * 5(used power of 2 = {0, 1, 2, 3, 4} ). You can group other numbers similarly. For example powers of 3, powers of 5, multiples of 6, etc which reduces the number of states significantly all together.

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

    I haven't understood the grouping technique , will you give me some more explanation?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 10   Vote: I like it +9 Vote: I do not like it

      You can group integers which have the same set of prime factors together. Consider the numbers 10(2 * 5), 20(2^2 * 5) and 100(2^2 * 5^2). According to the problem, a valid sequence is such that the gcd of adjacent elements is always 1. Since 10, 20 and 100 have the same set of prime factors, this means that you can exchange their positions arbitrarily in any valid sequence.

      Say you have placed the following numbers in the sequence so far:

      3, 5, 21, 10, 17, 20

      Also consider this sequence:

      100, 17, 3, 5, 21, 10

      In the 2^n * n^2 dp, you have a mask representing which numbers are used so far and what is the last number in the sequence. Now although the mask is different for these two sequences since one contains 100, where as the other contains 20, the number of ways to complete these two sequences is still the same.

      Why so? Because both of them contains exactly the same number of elements from every group and the last number comes from the same group. It does not matter whether there is 100 or 20 since both of them are from the same group. In the 2^n * n^2 solution, all numbers belong to different groups and so there are n groups. For each group we have a count(0 or 1) to indicate how many items we picked from this group so far. Now you have fewer number of groups (although possibly more numbers in some groups) which will reduce the number of states.

      For n = 6, initially you have 6 groups {1} {2} {3} {4} {5} {6}, so you have 2^6 = 64 possible options for mask. If you group the numbers in such a way so that all numbers from a group can be exchanged in any order, for example {1, 5} {2, 4} {3} {6}, now you have 3 * 3 * 2 * 2 = 36 possible options instead of 64.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I cant understand how to implement the grouping part in this problem. Will you send me the source code for this problem ?

        → Reply