newbie_forever_at_cp's blog

solution for problem 440 C
By newbie_forever_at_cp, history, 7 years ago, In English

hi every one. im having a doubt in codeforces problem 440 C. here is the link http://codeforces.me/problemset/problem/440/C. My approach was

A number x can be represented by having the number with only ones which is less than the given number. for eg if number is 40 one approach is taking 11.

Another is having the number with only ones which is greater than the given number. i.e. 111 for 40 then take absolute difference between the number and the given number i.e abs(11 – 40) = 29 and abs(111 – 40) which is 71.

Now call the function again for the new n. in this case fun(29) and fun(49).

Now added with the number of ones take the min of these two i.e min(fun(29) + 2, fun(71) + 3). that is the answer. Also if we can represent the number with the ones alone. for eg 11 then return 2 just. i.e without computing min(fun(11-11) + 2, fun(111- 11) + 3);

But i got wrong answer in test 14. the input is 81924761239462. and the expected output is 321. And my output is 395. Can you please tell me what is wrong.

here is the link: http://ide.geeksforgeeks.org/kRLASR. THanks in advance

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

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

I didn't understand this part:

if(m[n] == -1)
        return inf;

Can you explain?

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

    for eg, if n is 112 then it calls fun(abs(111 — 112), abs(1111 — 112)). here 1111 — 112 is 999. now for again 999 it calls fun(abs(111 — 999)) and fun(1111 — 999). 1111 — 999 is 112. so it goes on a non terminating loop. SO in order to terminate this, if i ve already seen 112 then stop and return bcoz it is not going to give the optimal solution as it adds extra 8 1s (1111 — 112 and 1111 — 999). and comes to same state. so in order to stop, i checked the condition whether it has been seen previously.

    → Reply