You are not logged in. Please login at www.codechef.com to post your questions!

×

DELISH - Editorial

21
9

Problem Link:

Practice
Contest

Difficulty:

Simple

Pre-requisites:

Dynamic Programming

Problem:

Given an array D[1...N], find max(abs((D[i] + ... + D[j]) - (D[k] + ... D[l])) : 1<= i <= j < k <= l <= N).

Explanation:

Let us look at the final solution, and work backwards. Let the final solution be due to some i0, j0, k0, l0. We now have two cases:

Case 1: D[k0] + ... + D[l0] <= D[i0] + ... + D[j0].
In this case, we get that among all possible choices of l, D[k0] + ... + D[l] is MINIMUM for l = l0. Else, we could choose such l, and this would give us a larger absolute difference. We also get, that among all 1 <= i <= j <= k0-1, D[i] + ... + D[j] is MAXIMUM.

Case 2: D[k0] + ... + D[l0] > D[i0 + ... + D[j0].
In this case, among all possible choices of l, we choose l0 to give the MAXIMUM value of the sum, and we choose i0, j0 to give the MINIMUM possible sum.

Hence, it would be useful precomputing values that answer "what is the [minimum|maximum] value I can get if I [start|end] at position i?"

Solution 1

The above setting motivates the following few definitions:
HardLeftMin(i) = Minimum value of the sum of a contiguous subarray whose rightmost point = i.
HardLeftMax(i) = Maximum value of the sum of a contiguous subarray whose rightmost point = i.
SoftLeftMin(i) = Minimum value of the sum of a contiguous subarray whose rightmost point <= i.
SoftLeftMax(i) = Maximum value of the sum of a contiguous subarray whose rightmost point <= i.
HardRightMin(i) = Minimum value of the sum of a contiguous subarray whose leftmost point = i.
HardRightMax(i) = Maximum value of the sum of a contiguous subarray whose rightmost point = i.

Recurrences for the above are easy to find:
HardLeftMin(i) = min(D[i], D[i] + HardLeftMin(i-1)) : either you select position i-1 as well in your subarray and take the best from there, or you don't even take position i-1.
HardLeftMax(i) = max(D[i], D[i] + HardLeftMax(i-1)) : similarly.
HardRightMin(i) = min(D[i], D[i] + HardRightMin(i+1)) : similarly.
HardRightMax(i) = max(D[i], D[i] + HardRightMax(i+1)) : similarly.
SoftLeftMin(i) = min(HardLeftMin(i), SoftLeftMin(i-1)) : either your minimum ends at points i, or it ends at some point <= i-1.
SoftLeftMax(i) = max(HardLeftMax(i), SoftLeftMax(i-1)) : similarly.

Note that, using the above recurrences, we can calculate all the arrays in O(N) time using dynamic programming.

Finally, our case (1) will be covered by SoftLeftMax(j0) - HardRightMin(j0+1), and case (2) will be covered by HardRightMax(j0+1) - SoftLeftMin(j0).
Iterate over all values of j0, and take the maximum, as your answer. This again takes O(N) time to run.

Solution 2

This solution cleverly disposes of SoftLeftMin, SoftLeftMax() functions and works relying on the following claim.

Claim: Without loss of generality, k0 - j0 = 1. That is, we can consider our optimal phases as being consecutive.

Let us say that OPT returned i, j, k, l, with k-j > 1. Now, consider sum S = D[j+1] + D[j+2] + ... + D[k-1]. If S >= 0, then it can be added to the larger of the two segments [i...j], [k...l]. If S <= 0, then the segment can be added to the smaller of the two segments [i...j], [k...l]. In both cases, it gives us a Delish value atleast as good as the Optimal. Hence, wlog, the two segments we choose are consecutive.

Thus, finally, we iterate over j, and consider abs(LeftMax(j) - RightMin(j+1)) and abs(RightMax(j+1) - LeftMin(j)) as candidates. This approach was used by the Setter.

Setter's Solution:

Can be found here

Tester's Solution:

Can be found here

This question is marked "community wiki".

asked 18 Jun '13, 00:19

pragrame's gravatar image

6★pragrame ♦♦
963568379
accept rate: 14%

edited 19 Jun '13, 13:57

admin's gravatar image

0★admin ♦♦
15.9k347484508


12

Can anyone explain me this solution of karlheinz_jung???? I have tried my best to understand it, but unfortunately I can't.

Those who solved this question help me in figuring a case where my solution went wrong.

link

answered 18 Jun '13, 02:03

devanshug's gravatar image

4★devanshug
2.7k111927
accept rate: 13%

edited 18 Jun '13, 02:46

really.. that annoying.. coding right.. it's better to understand someother code(esp. above tutorial) than that purely written code..

(18 Jun '13, 02:13) shashank_jain2★
1

haha.... I knew it bro.... I was jst thinking, in what world karlheinz would be, when he wrote the code.... I mean how a person can write such a code.... I think he himself cant xplain that....

(18 Jun '13, 02:41) devanshug4★
1

dafaq is this code !!!whre's a main() ??

(18 Jun '13, 11:29) spandanpathak2★

@spandanpathak, It has a main.. but nothing else is understandable. Probably we first need to replace all those variable to simple ones and the format it to understand where the functions start and end.. :P

(18 Jun '13, 12:00) ajit_a2★
1

That code gives me urges that he must have done something which he is hiding behind that dirty code :)

(18 Jun '13, 12:09) shashank_jain2★

@shashank_jain: I always prefer akash4983's code for this purpose . least use of templates , least use of all the big constructs and more of a simple oriented approach devoid of problems associated with using abs , fabs , mods etc.

(18 Jun '13, 13:03) kavishrox3★
1

The code seems to be the output of a decompiler or obfuscator. Some reasons which come to my mind are either he would have done it to optimise the code (eg, compile with gcc -O3 and then decompile) or maybe he cheated from someone else so to make the code look different obfuscated it.

(18 Jun '13, 15:37) n2n_5★
1

I guess he used some translation tool (between programming languages) or other. After doing below conversion(and formatting a little), the code will be fine. Though the basic idea is the same as mine, his implementation is simpler. I fun to work out this puzzle :-) (i_d6->readingBuff),(i_d8->readInt), (i_d12,i_d13,i_d14,i_d15: non-use), (i_d9->sign),(i_d10->value),(i_d11->ch), (i_d7->curChPtr),(i_d18->testCase), (i_d19->i),(i_d20->N),(i_d22->D),(i_d21->maxV), (i_d23->sumMaxL),(i_d24->sumMaxR),(i_d25->sumMinL),(i_d26->sumMinR), (i_d27->pLL),(i_d28->endD),("\45\154\154\144\n"->"%lld\n")

(22 Jun '13, 18:24) gengengen5★
showing 5 of 8 show all

So, finally, after reading the editorials several times and after searching for some AC solutions, I finally got AC with my solution in C++:

/* Problem DELISH @Codechef JUN13 Long Contest
 * 
 * Main idea is to use DP approach to solve problem in linear time.
 * We need to maintain 4 vectors that will store:
 * - Max value of delish starting from left
 * - Max value of delish starting from right
 * - Min value of delish starting from left
 * - Min value of delish starting from right
 * 
 * Now, since the value of a partial sum is always either >= 0 or <=0
 * it is safe to assume that the optimal indexes i,j,k and l
 * which form the intervals to substract are in fact contigous.
 * This is because either we add a value to one of them and increase it
 * , or we add it to the other one which also increases it, towards the
 * first interval. This yields, wlog, the optimal answer. */
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long int LL;
#define put(x)  printf("%lld\n",x)

vector<LL> max_sum_left(int N, vector<LL> arr)
{
    vector<LL> res(N);
    for(int i = 0; i < N; i++)
    {
        res[i] = 0;
    }
    res[0] = arr[0];
    LL currMax = arr[0];
    for(int i = 1; i < N; i++)
    {
        currMax = max(arr[i],arr[i]+currMax);
        res[i] = max(res[i-1], currMax);
    }
    return res;
}

vector<LL> min_sum_left(int N, vector<LL> arr)
{
    vector<LL> res(N);
    for(int i = 0; i < N; i++)
    {
        res[i] = 0;
    }
    res[0] = arr[0];
    LL currMin = arr[0];
    for(int i = 1; i < N; i++)
    {
        currMin = min(arr[i],arr[i]+currMin);
        res[i] = min(res[i-1], currMin);
    }
    return res;
}

vector<LL> max_sum_right(int N, vector<LL> arr)
{
    vector<LL> res(N);
    for(int i = 0; i < N; i++)
    {
        res[i] = 0;
    }
    res[N-1] = arr[N-1];
    LL currMax = arr[N-1];
    for(int i = N-2; i >= 0; i--)
    {
        currMax = max(arr[i],arr[i]+currMax);
        res[i] = max(res[i+1], currMax);
    }
    return res;
}

vector<LL> min_sum_right(int N, vector<LL> arr)
{
    vector<LL> res(N);
    for(int i = 0; i < N; i++)
    {
        res[i] = 0;
    }
    res[N-1] = arr[N-1];
    LL currMin = arr[N-1];
    for(int i = N-2; i >= 0; i--)
    {
        currMin = min(arr[i],arr[i]+currMin);
        res[i] = min(res[i+1], currMin);
    }
    return res;
}

LL compute(int N, vector<LL> arr)
{
    LL maxDiffAbs = arr[0]-arr[1];
    vector<LL> leftMax = max_sum_left(N,arr);
    vector<LL> leftMin = min_sum_left(N,arr);
    vector<LL> rightMax = max_sum_right(N,arr);
    vector<LL> rightMin = min_sum_right(N,arr);

    LL diff;
    for(int i = 0; i < N-1; i++)
    {
        diff = leftMax[i]-rightMin[i+1];
        if(diff >= maxDiffAbs)
            maxDiffAbs = diff;

        diff = rightMax[i+1]-leftMin[i];
        if(diff >= maxDiffAbs)
            maxDiffAbs = diff;
    }
    return maxDiffAbs;
}

int main()
{
    int t,dim;
    scanf("%d",&t);
    for(int i = 0; i < t; i++)
    {
        scanf("%d",&dim);
        vector<LL> arr;
        for(int j = 0; j < dim; j++)
        {
            LL elem;
            scanf("%lld",&elem);
            arr.push_back(elem);
        }
        LL ans = compute(dim,arr);
        put(ans);
    }

    return 0;
}

Thanks for this enlightening editorial @pragrame, which allowed me to write what I believe to be a clean solution for this problem!

Keep the good work up :D

I hope I can also devote some of my time to understand the problem W-string a bit better and hopefully code a solution for it as soon as my time allows me to do so!

I hope I can really improve something with this good contest :D

Also, @xpertcoder, Thanks for your words! As you probably noticed, those problems are easy ones and those are the concepts which I can say that I feel most comfortable with, so, as you can see I still have a loong way to go :)

Best regards,

Bruno

link

answered 18 Jun '13, 15:47

kuruma's gravatar image

2★kuruma
17.4k72143208
accept rate: 8%

4

Nice work, I've also seen some of your tutorials and one time you even explained a problem to me. You have really nice logic, I think if you don't give up you'll become a really strong competitor and be able to fight for the first spots. Also, I've seen you complain a lot about math basis but you shouldn't let it stop you from solving problems. If you do that you'll just be wasting your talent, we should turn our weaknesses into our greatest strengths. In no way I'm saying this to only encourage you, I say this because it's true.

(18 Jun '13, 15:57) junior944★

Thanks @junior94, I hope that if I stick around this community my knowledge can grow much, much more and I can grow as a coder and as a person as well :D Everyone's words are a great motivating factor and hopefully things will go better on next month or at least as good as they went on this one :)

(18 Jun '13, 16:03) kuruma2★

Your solution is very neat but with an observation you could dove done it a lot cleaner. Think about reversing the array after finding the frist min and max.

(18 Jun '13, 18:40) ervin903★

Maybe then it's possible to use only 2 arrays instead of four?

(18 Jun '13, 19:18) kuruma2★

I was aiming to the fact that you could've used the first two methods for the other calculations aswell,

(19 Jun '13, 00:57) ervin903★

As contests pass by... and as I see I keep struggling to solve only 3 maybe 4 problems over 10 days... The more convinced I get that I might be too dumb for doing Algorithms at the minimum acceptable competitive level... After reading editorial I believe I understood the underlying idea behind DP a bit better (Truth is, I say this, but, as I never, or rarely get the chance to practice properly, I always end up only reading the editorial and not coding anything with my own comments etc, etc, which is what I think is needed to gain more skill).

Nontheless, I found it absolutely hillarious that my code almost had the same designations as the Solution 2 described in editorial... However, I got stuck with the code EXACTLY like this for all the contest, after solving 3 problems in the 1st day of contest...

I can't express how frustrated I feel with myself right now at this moment... I feel like FUCKTHISSHIT

I really hope I can improve something... If I can't, this is just... very demotivating... :(

link

answered 18 Jun '13, 02:28

kuruma's gravatar image

2★kuruma
17.4k72143208
accept rate: 8%

same story...... here :-/

(18 Jun '13, 02:32) avastpulkit3★
4

think it this way.... Compare your present knowledge with the knowledge you had when you started competitive coding..... we all know that it must be way better than at that time.... Now you are a part of a dedicated community whose members are not only working for themselves but are working for each other.... At least you are better than your mates who dont even knw a bit about competitive programming.... At least we try our best to solve these tuff problems and become part of a big competitions... Cheerup bro these conditions will reoccur.... all what we need is unstoppable efforts... ;)

(18 Jun '13, 03:03) devanshug4★
1

Well, @devanshug, you're right and it is indeed a lot better now than it was before... I even got to write some Simple problems as a setter and I actually think I managed to write good tutorials here on forums... But sometimes I feel that this is all I got.. Maybe it's the lack of time that makes me think this way, but it's still very frustrating and demotivating... I think I will try to work as hard as university allows me, in order to get a little bit better though :) Thanks for your words

(18 Jun '13, 03:10) kuruma2★
2

@kuruma, Being relatively new to competitive programming and algorithms besides the constraints due to university, i feel the same as i have not been able to solve more than 3 problems but each time we get stuck we learn something new(be it the simplest of things) but that is what should drive us as these little things go a long way in enhancing our programming skills. Bit by Bit, Bytes of knowledge can be acquired, learnt and applied to improve our speed and efficiency in solving more problems. And considering that you are a lot better than before, its an achievement in itself. Chin up!

(18 Jun '13, 11:30) scep24★
2

It's natural to feel this way maybe you were trying too hard...but as @devanshug said compare your knowledge now with what you have when you started...Key is to keep practicing...and C'mon you are the one who wrote questions like FCBARCA and CLBMSTRS which I loved to solve...these are way too creative..simple series questions hidden behind very creatively created stories...AWESOME MAN AWESOME!!! Happy Coding:-)

(18 Jun '13, 13:29) xpertcoder4★

Can anyone pls tell where i am going wrong in this solution.. sol_1

I used the same approach.. and got ACed when i did this : sol_2

Thank you in advance !! :)

link

answered 18 Jun '13, 15:08

anick_gemini's gravatar image

3★anick_gemini
1.1k61215
accept rate: 0%

edited 18 Jun '13, 15:14

@pragrame - shouldn't we also include abs(LeftMax(j)-RightMax(j+1)) and abs(LeftMin(j)-RightMin(j+1)) as well because we are considering abs value ? If LeftMin(j)=-2 and RightMax(j+1)=4 and RightMin(j+1)=-10, then the max. abs value among these is abs(LeftMin(j)-RightMin(j+1)) which is not checked! I apologise if I am missing some point ! Thanks !

link

answered 18 Jun '13, 00:39

rohangarg's gravatar image

5★rohangarg
111
accept rate: 0%

2

Not really. In your example, you say LeftMin(j) - RightMin(j+1) is larger. But note that LeftMin(j) <= LeftMax(j). So your case will be considered (and potentially bettered) in the check for LeftMax(j) - RightMin(j+1). You can check that the same will happen with comparing other pairs - wherever you compare difference of "max with max" or "min with min".

(18 Jun '13, 01:30) pragrame ♦♦6★

I made 2 functions using Kadane's algorithm for max and min. Function max gave me i,j,sum1. Function min gave me k,l,sum2. I took four cases. 1)max(0,arr.length-2) and min(j+1,arr.length-1) result1=Math.abs(sum1-sum2). 2)min(0,arr.length-2) and max(l+1,arr.length-1) result2=Math.abs(sum1-sum2). 3)max(1,arr.length-1) and min(0,i-1) result3=Math.abs(sum1-sum2). 4)min(1,arr.length-1) and max(0,k-1) result4=Math.abs(sum1-sum2). I took maximum of all four results.I satisfied all given cases as well as cases in comments still I got WA always any help or case where it fails please :( :(.....

link

answered 18 Jun '13, 16:48

sid4art's gravatar image

2★sid4art
11
accept rate: 0%

Cannot figure out what's wrong...Please Help.. http://www.codechef.com/viewsolution/2279041

link

answered 18 Jun '13, 21:46

shubham2892's gravatar image

2★shubham2892
1
accept rate: 0%

@sid4art i did the same thing and got WA! http://www.codechef.com/viewsolution/2276586

Can someone please point out what is wrong with this approach?

link

answered 19 Jun '13, 14:26

nilakshdas's gravatar image

2★nilakshdas
1
accept rate: 0%

http://www.codechef.com/viewsolution/2299047

Can anyone tell whats wrong in this code????

link

answered 27 Jun '13, 17:04

javacoding's gravatar image

1★javacoding
1
accept rate: 0%

By same reasoning , one can implement Kadane algorithm too.

link

answered 24 Jun '15, 23:24

empty_life's gravatar image

2★empty_life
355819
accept rate: 20%

Can anyone explain me the output for 5 10 3 1 2 9

The output according to setter's or tester's code is 12. How?

link

answered 14 Oct, 16:43

dsahapersonal's gravatar image

2★dsahapersonal
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×1,259
×780
×26
×13

question asked: 18 Jun '13, 00:19

question was seen: 12,089 times

last updated: 14 Oct, 16:43