kingofnumbers's blog

spoj COOLNUMS
By kingofnumbers, 12 years ago, In English

I need help to solved this intersting problem link .

thank you in advance.

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

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

if you now know how to solve it then please help .

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

    not sure at all but this might work:

    First, let's work on finding the # of cool numbers <= X, for a given X (then we can get the answer by computing that for B and A-1).

    For a fixed X, we can get the # of cool numbers with a dp[digit][sum1][sum2][alreadyless_bit]

    digit will be the position of the digit we're trying, We will go from most significative to least. sum1 and sum2 are the sums of the two sets. alreadyless_bit tells if we are already strictly less than X, if so, the new digit can be any digit, otherwise, it has to be between 0 and the respective X's digit.

    This counts the cool numbers but it might count each one many times, I don't know if you can avoid that hehe

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

Did you solve this problem later.. ? If yes can you share your idea?

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

Can someone help in this question

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

I might be wrong, but how about...

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

    I couldn't think of any solution. I know above idea proposed by lmn0x4F seems to be good but couldn't find a way to for overcounting issue.

    Can you provide some hint?

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

      I viciously precomputed answers for blocks of size 200000 and then solved naively for the remainders. You might want to have a fast naive solver (i.e., $$$O(d)$$$ instead of $$$O(d^2)$$$ knapsack). Keep in mind the 50K source size limit.

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

        Thanks a lot for sharing your approach

        → Reply