spontaneously's blog

Washing Dishes hackerrank problemhttp://
By spontaneously, history, 10 years ago, In English

Problem Can anyone help me with this problem I think its a greedy problem but I'm not able to find out a correct approach.

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

Comments Comments (6)
| Write comment?
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +23 Vote: I do not like it
  • If you don't wash any dish, then your final score will be . Let's call that x.
  • Now, suppose you wash some dishes. Each dish i that you wash will contribute with pi to the answer instead of  - di, so for all the dishes that you wash, you must add pi + di to x.
  • Naturally, we want to take the elements with biggest pi + di, so we sort the dishes in non-increasing order of pi + di and then our answer will be .-
→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +5 Vote: I do not like it

    But why do you sort the pi PLUS di array and not a pi minus di array?

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +3 Vote: I do not like it

      because when we have subtracted di for not washing a dish, we need to add di back to make it 0 if we wash the dish and also add the pi value.

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

        I know that we have to readd the pi value in order to nulify the subtraction effect. BUT wouldn't it be more logic to sort pi — di, to find which dish is more efficiently to wash and not have big losses?

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

In this problem we are affected by a total amount of (p[i]+d[i]) so lets create another variable x =p[i]+d[i] and now sort the structure first with respect to x and if x is equal then with respect to p[i]. This would be an optimal approach because we'll be taking the values that would affect our total payment to a maximum extent. My code :https://ideone.com/dvm2ah

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

in the name of allah, most mrcifull

consider this test case:

2 1

1000 9

999 1

if we sort in non-increasing order of pi — di we will chose second one for washing and we will have 9 — 999 money

but if we sort in non-increasing order of pi + di we will chose first one and we will have 1000 — 1 money

i wanna say thank you spontaneously for this blog.

→ Reply