kingofnumbers's blog

help with spoj problem
By kingofnumbers, 12 years ago, In English

Hi, I have no idea how to solve this problem. can anyone help me?

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

Comments Comments (5)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Every positive number can be represented as a form like this: 2^x * 3^y * z, where z is not divisible by 2 and 3.

Let's suppose that n = 2^x * 3^y * z. Then we cannot have 2n = 2^(x+1) * 3^y * z and 3n = 2^x * 3^(y+1) * z in set S.

Now, let's define a plane P[z]. For each number 2^x * 3^y * z, draw a point in P[z]. Then, the problem will be solvable :)

Sorry for the poor English.

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

    We can have 2n and 3n in set S if we didn't include n in set S.

    can you code your idea please to make me understand your idea very well.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Sorry for my mistake..

      Let's suppose that n = 2^x * 3^y * z. (where z is not divisible by 2 and 3) If we include n in set S, we cannot have 2n = 2^(x+1) * 3^y * z and 3n = 2^x * 3^(y+1) * z in set S.

      Let's define a plane P[z] where z is not divisible by 2 and 3. For each positive integer i = 2^x * 3^y * z (<= N), draw a point (x, y) at P[z].

      If we select the point (x, y) in P[z], then we cannot select the point (x+1, y) and (x, y+1) in P[z]. So the problem is: how many ways can we choose points such that the condition above is satisfied?

      The value of x and y are very small, so we can do this in DP.

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

        Good idea, but how to do this in DP effectively, notice that we have n/3 numbers less than n that not divisible by 2 and 3 and we have 500 test cases per input.

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

          You can use bitmasks.. It needs more complex solution than just bitmasking. Think about it :)

          → Reply