Editorial for Greedy Harshit problem from NCC2017?

editorial
1

Can someone please help me with this problem?


Here’s my approach, i was just selecting minimum of both the extremes and was multiplying it by k(starting from 1 upto array-length),but got WA.
Please help.
Thanks :slight_smile:
1 Like
2

How are you dealing with cases where both extremes are equal?

Eg-

1 10 3 2 1 3 10 1

How will your program run for this type of test cases?

1 Like
3

I think selecting any of them should not matter(in this case).
My code gives ans as 162.
Is there any other optimal answer?
It would be really good if someone comes up with the editorial.
I have seen other people’s solution as well. They have used dp to solve this problem.But i’m unable to understand their solution.

4

The correct ans is 163. Yes, even I was feeling that dp has to be used here. Lemme see if I can help in explanation.

1 Like
5

Alright,Waiting for it.I had a feeling for such corner cases but wasn’t getting it.Thanks :slight_smile:

6

A greedy solution, although intuitive, will not always give the best answer. Consider a case where A is [10, 10, 1, 11]. If you choose the minimum every time, you will get a total of 77. However if you sacrifice the largest value, 11, the $10$s will increase a lot by the time you reach them, granting a total of 83.

To find the best answer we can use dynamic programming. Let f(i, j) be the answer for the subarray A[i..j]. Naturally our required answer is f(0, n-1) for the whole array.
At any stage, for f(i, j), we can pick either A[i] or A[j], but both must be multiplied by some time factor x. This time factor can be easily obtained by the length of the subarray. So if we have length of [i..j]=3, then already n-3 turns have passed and each jar now has a value of (initial value$)\times (n-3+1)$.
Back to our choice, if we pick A[i]\times x, we will be left with A[i+1..j] for which we know the answer as f(i+1, j) :smiley:
And if we pick A[j] \times x, we will be left with A[i..j-1] and once again we can easily get f(i, j-1).
We will choose the maximum of the two since we want to maximize the sum we collect.
The base case is for i=j+1 as 0, because the game is over when the subarray is empty.

Here is my solution following this approach. The complexity is \mathcal{O}(n^2).
Hope this helps :slight_smile:

3 Likes
7

Thanks a lot. I got it.

8

No problem :slight_smile:

1 Like
9

Beautiful explanation @meooow! I swear, this problem was making me restless throughout the professor’s Math lecture today XD. I am fortunate to find the solution soon after the class :p.

BTW, can you share how you thought of the approach? Since I usually get overwhelmed by multiple possibilities while thinking “how to tackle the problem”, so I feel hearing how you reached the conclusion/derived the result would really help me!

10

This is one of the best intuitive problem of dp, I too applied greedy for the first time when I did a problem somewhat like this.

2 Likes
11

http://www.spoj.com/problems/TWENDS/ try this problem next, It is somewhat alike.

1 Like
12

@vijju123 https://www.quora.com/How-do-I-figure-out-how-to-iterate-over-the-parameters-and-write-bottom-up-solutions-to-dynamic-programming-related-problems/answer/Michal-Danilák?srid=OdyH look through this

13

Yeah,sure.

14

Thanks neil!!

1 Like
15

My code is here …


int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
dp[i][i]=(n)*a[i];
}
for(i=2;i<=n;i++)
{
for(j=1;j<=n-(i-1);j++)
{
ll k =j+i-1;
dp[j][k]=max(a[j]*(n-i+1)+dp[j+1][k],a[k]*(n-i+1)+dp[j][k-1]);
}
}
cout<<dp[1][n]<<endl;
}
return 0;
}
1 Like
16

Read this answer on quora, similar problem, beautifully explained.

1 Like