_Chaitanya1999's blog

Interesting problem
By _Chaitanya1999, history, 3 months ago, In English

I recently encountered a problem which states : There is an array A which contains n integers. In one operation we can swap Ai with one of its neighbours i.e., swap(Ai,Ai+1) or swap(Ai,Ai-1) provided any element in the array can be swapped atmax once. After doing some optimal number of operations, we have to find the max value of summation of i*Ai for i = 1 to n.

For ex — A : [2,1,4,3] n = 4

Ans : 30 Swap elements at index 1,2 and elements at 3,4 that gives us the final array as [1,2,3,4]. The sum is 1*1 + 2*2 + 3*3 + 4*4 = 1+4+9+16 = 30

Can someone help me with the ideas to solve this problem ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any link of this problem?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if i swap Ai with Ai+1 does that mean i cant swap Ai+2 with Ai+1 ?

since Ai+1 swapped.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i haven't given it alot of thought but i think the idea of merge sort might work for this problem(ofc not the usual merge sort you will have to change somethings in it)

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, as it was noticed in comment, you can swap each element only once

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints??

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what about just swaping to the right the biggest $$$a_i$$$ you didn't swap so far? Any countercase?

→ Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can solve using dp.

$$$\text{dp}[i]$$$ denotes max value for prefix upto $$$i$$$. Transitions are simple, if you swap you get $$$\text{dp}[i - 2] + (i - 1)\cdot\text{a}[i] + i\cdot\text{a}[i - 1]$$$, if you don't swap you get $$$\text{dp}[i - 1] + i\cdot\text{a}[i]$$$.

$$$\text{dp}[i]$$$ is the maximum of these two values. Answer is $$$\text{dp}[n]$$$. Note that I've 1-indexed everything for brevity.

→ Reply