MotaSanyal's blog

By MotaSanyal, history, 5 years ago, In English

Hello everyone. It would be nice if anyone helps me with the solution to this problem — Integer Expression

Problem Source : TCS Codevita 2018

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Looks like simple O(n^2) dp. dp[num][2]:

dp[num][0] — minimum length for expression evaluated as num with '+' operation on the top
dp[num][1] — minimum length for expression evaluated as num with '*' operation on the top

Expressions with one number interpretated as expression with both '+' and '*' on the top. With that all transitions are trivial. (Example: dp[11] = { 2, 2 }, dp[14] = { 8, 12 })

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

    Can u please explain what do you mean by 'top'?. Also how do you get dp[11] and dp[14]? Sorry, if I am asking a trivial question but I am new to dp.

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

      I mean that '+' is last operator for execute.

      dp[11] you can build expression '11'
      dp[14] you can build expression '(11 + 1 + 1 + 1) * 1' that is shortest expression with '*' at the top. and '11 + 1 + 1 + 1' is the shortest expression with '+' at the top.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Thanks for the solution, but I still have the following doubts : 1. Can you please explain the reccurence relation that you have used in your solution? 2. How come the time complexity turned out to be O(n^2) ? @balalaika

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      dp[1] = { 1, 1 }
      dp[11] = { 2, 2 }
      dp[111] = { 3, 3 }
      dp[1111] = { 4, 4 }

      Let's say you need get answer for num = 123. How 123 can be get? 121 + 2, 3 * 41, 51 + 72 and so on. In order to calc dp[123][0] you need to iterate over all possible terms. Let's say that 123 = l + r. Both l and r < 123. So you can reccursively calculate dp[l] and dp[r].

      You calculated them and you need to construct the shortest expression. Neither of terms need to be wrapped in brackets, so dp[123][0] = min(dp[l][0], dp[l][1]) + 1 + min(dp[r][0], dp[r][1]).

      Analogically you can calculate dp[123][1]. But factors can be wrapped in brackets (this adds 2 to answer). For example, 123 = 3 * 41. 3 = 1 + 1 + 1. You can't tell that 123 = 1 + 1 + 1 * 41. But you can tell 123 = (1 + 1 + 1) * 41. That because (1 + 1 + 1) has '+' on the top. With such reasoning you can calculate transitions.

      For each n there is iterating over O(n) possible terms and O(sqrt(n)) possible factors. So the whole complexity is O(n^2).

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

        Thanks a lot :)

        But don't you think that this approach would time out as n<=10000 ?

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

          It won't. N <= 10000 permits a O(n^2) solution.

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

            Why permits? There would at max 1e+8 arithmetic operations. CF would do that less than 0.1s. Of course it depends on how tough TL and how slow testing machins are but I'm sure O(n^2) would be enough.

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

              But I think it will be tough to get through with languages like Python or JAVA(not sure for JAVA though)

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

                Don't use them. But Java I think should pass 1s on CF too. Python of course no, but PyPy can.