Any approach for question swapping

help
1

can someone provide the solution of swapping question

2 Likes
2

Use this dp approach:-

rl=dp[i-2]+ a[i-1].i + a[i].(i+1);
lr=dp[i-2]+ a[i].i + a[i-1].(i+1);
pf=dp[i-1]+ a[i].(i+1);

     ll m=max1(rl,lr,pf);
     
     dp[i]=m;
3 Likes
3

Did see you participating in lunchtime ?

4

sir can u explain little bit more??
Thanks…

5

Yes, sir sure…I’ll explain few minutes…

1 Like
6

Standard DP problem - bottom up approach. For each element at index i you can either skip swapping it or swap it with it’s adjacent element i + 1.
The answer is thus maximum of the two, i.e. dp[i] = max(dp[i+1], dp[i+2])
with the base case- dp[n-1] = arr[n-1].

7

Recursive solution: CodeChef: Practical coding for everyone
Might be easier to understand…

4 Likes
9

Such an elegant solution @hetp111 :grinning:

1 Like
10

Works fine even without lr

11

Can u explain ur method pls…@thesmartguy

12

What I did wasn’t provocatively a DP solution but rather very intuitive.

1.>First find the sum of the array with sum+=a[i]*(i+1).

2.>second make an array with the difference of elements of a like b[i]=a[i]-a[i+1];

3.>now you have an array with the prefix difference… to maximise the sum, you have to take all
positive difference and in such a way that no two difference are adjacent
for example lets say a[]={5,3,2,4,1} so our difference array will be {2,1,-2,3}. So now we will have
to take the maximum possible subsequence such that its sum is maximum from the diff
array… so it’ll be 2+3; so we have our val=5 , and so i’ll update it accordingly like:
maxm=max(sum,sum+val); => sum=38 and val =5 so ans=43.

4.>So now, How to take maximum sum subsequence such that no two elements of that are
adjacent? Well it’s a pretty conventional approach , You can either maintain an array dp[] and
take maximum including and excluding the element or just traverse through the array
calculating the same…

Here’s my submission if you want to take a look: [CodeChef: Practical coding for everyone]

4 Likes
13

lol PKMKB :joy: sahi hain

1 Like
14

can some one explain easy dp solution for this problem more elaborately.

15

Anyways nice approach :slight_smile:

1 Like
16

@hetp111 very nice solution

1 Like
17

here say you have 3 elements you have 2 choices 1) swap a1 and a2 ; 2)swap a2 and a3
so using dp solve for first 3 elements and then recursively call the function.

https://www.codechef.com/viewsolution/25456156

here initially calculate (i)*a[i] for the input array and in every swap you basically gain the difference of the 2 elements being swapped , g[i] stores then gain for the last n elements add the gain for the whole array to sum(i*a[i]) and you get the answer.

18

This is a classic case of “Bottoms Up”.

  1. Imagine a test case with just one element. For this the optimal approach is “No SWAP”. The final answer is the same as input. This will be DP[0].

  2. Now, imagine two inputs. Consider the following two values:

    • The second input multiplied by 2 + first multiplied by 1 = x
    • The first input multiplied by 2 + second multiplied by 1 = y

if x is larger than y, it means no swap was needed and final answer is 2A2 + 1A1. Or else now the output will be 2A1+1A2. This will be DP[1].

  1. Now lets analyze the third case, with three elements. Here - we have two “possibilities”. We could swap 3rd input and 2nd input; or we need not. If have to swap 3rd input and 2nd input, then we cannot swap 2nd and 1st input. That is the cost we pay. But DP[1] took into account the benefit of swapping 1st and 2nd element! Thus DP[1] is, so to say, "corrupted. DP[0] talked about the best case before 1st and 2nd element were swapped.

So we have to compare DP[0]+swap_benefit vs DP[1]+no_swap_of_3_2. Whichever is better becomes our DP[2]. Here swap_benefit means benefit of swapping (3,2) over (2,1).

Generalizing, for DP[k] - we need to analyze:
DP[k] = MAX(DP[k-2]+swap, DP[k-1]+no_swap).

https://www.codechef.com/viewsolution/25464905

2 Likes
19

Hey @tanha_barati even i too did the same thing, Once i got the difference array, i traversed on it and on getting a positive number i stored it, and on getting a negative or a zero value, i took my stored vector and found the highest sum giving subsequence in it, and added it to the the answer.

I choose the highest sum giving subsequence in the following manner.
suppose we have v = {2,3,4,5,6};
as we have only positive numbers we only have two choices, summing up the odd indexed values and summing the even indexed values and then find their maximum, that will be the maximum sum.

But i got WA for my this approach, i have tried my code with numerous test cases and it seems to be giving same anwer as the other correct ones, please tell me what is wrong with my this approach.

solution link

20 
    dp[0]=0;
    dp[1]=a[1];
    
    for(int i=2;i<=n;i++)
    {
        dp[i] = max(a[i]*i + dp[i-1], dp[i-2] + a[i]*(i-1) + a[i-1]*i);
    }
    return dp[n];

Solution Approach: Think Dynamically as statement said in the problem::

  1. Keep element at its own place i.e, result till previous index + a[i] * i;
  2. Swap the recent two element. ie. result till i-2 index + a[i] * (i-1) + a[i-1] * (i);

Store the maximum of the two.

7 Likes
21

this is nice dude :slight_smile:
Thanks a lot!
@anon55659401
you too!

1 Like