Hello everyone. It would be nice if anyone helps me with the solution to this problem — Integer Expression
Problem Source : TCS Codevita 2018
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hello everyone. It would be nice if anyone helps me with the solution to this problem — Integer Expression
Problem Source : TCS Codevita 2018
Name |
---|
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 })
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.
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.
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
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).
Thanks a lot :)
But don't you think that this approach would time out as n<=10000 ?
It won't. N <= 10000 permits a O(n^2) solution.
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.
But I think it will be tough to get through with languages like Python or JAVA(not sure for JAVA though)
Don't use them. But Java I think should pass 1s on CF too. Python of course no, but PyPy can.