vontman's blog

Any hint for this math problem ?
By vontman, history, 9 years ago, In English

The problem : Identify the Number Any help will be much appreciated .

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

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

maybe it can be solved using dp with printing the path but i didnt try to solve it.

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

    Can you be more specific ? , like what are the overlapping sub-problems here !

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

First of all, I have to say that I didn't solve the problem. However, I think the following approach works well. Let DP[pos][rem] be the maximum number with reminder rem (when it's divided by Q) that we can obtain considering the digits from 0 to the position pos. Clearly, the answer will be DP[N.size()-1][R] , and is not difficult to realize that DP[pos][rem] = max( DP[pos-1][rem] , DP[pos-1][newrem]*10 + N[pos] ) , where newrem = (rem — N[pos] ) * inv(10,modQ) , here there are some tricky cases. If newrem doesn't exist , if newrem takes more than one value because 10 and Q have some common factor(observe that if this is the case, there are at most 10 possible values for newrem) and I think that's it. I hope this help.

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

    This approach makes sense ,but how can I take the max number with reminder rem when I can't store the number !?

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

Let's define DP[ind][rem] where ind is the index of the character in the string n and rem is the current remainder when divided by Q. DP[ind][rem] contains a pair of the maximum length for this subproblem and the leftmost digit.

Now we can calculate DP[ind][rem] from DP[ind + 1][rem] and DP[ind + 1][rem * 10 + N[ind] % Q]. If one of them has a larger length than the other, then it's optimal to choose the one with the maximum length. If both lengths are equal, then the optimal is to choose the one with the larger leftmost number. If both have the same lengths and leftmost digit, It'll be optimal to choose the current index rather than a next one (because the current index can cover more than a later one).

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

    Isn't it possible when both subproblems have the same lengths and leftmost digit but the past one was larger and the current index didn't cover any more digits ?

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

      No. Imagine that there are two indices x, y where x < y where you can get the same length and leftmost digit from both. Now the second left most digit in the x subproblem can be chosen from x + 1 to n where in the y subproblem it can be chosen from y + 1 to n only, as x < y then it's guaranteed to reach the answer from x.

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

The whole problem actually states.You are given N digits.Choose a subset of them so that the number formed gives R as rest and is maximul possible.

This can be solved by DP. dp[i][j]=maximum number formed using from first i digits and it gives rest j.

With digit i you can move from 0 to Q-1 and add digit i at the end :)

→ Reply