"Can you answer this queries" problem from SPOJ?

arpit728 · April 24, 2018, 8:39am

I was solving GSS1 - Can you answer these queries I problem from SPOJ, but I have one query in statement Max { a[i]+a[i+1]+…+a[j] ; x ≤ i ≤ j ≤ y }, does this mean we have to find max sum subarray with in the given range.

Please explain approach to solve this problems in details.

arpit728 · April 24, 2018, 8:39am

@vikram91 @rs_710 @purendra_ @hemanth_1 @shraeyas @vidyut_1 @aryanc403 @meooow @alexthelemon @vijju123 @ram_24 @harrypotter0 @pankaj_chopra guys please help.

gagan86nagpal · April 24, 2018, 9:16am

Yes, it means to find the max sum subarray within given range.

Approach: Range queries, So, Segment tree should be the first DS that comes to mind. What should a node hold in segment tree such that we will not miss any corner cases? Think about the possible cases which can generate answers. Cleary, optimal subarray could be like [l,i] or could be [i,R] or [i,j], where l<=i <=j<=R.

[l, i] may suggest some sort of prefix.

[i, R] suggest some suffix

Also, in segment tree building process depends on just child nodes. So, how can you cover all cases ?? Think in this manner.

arpit728 · April 27, 2018, 11:17pm

@gagan86nagpal

Can you please tell me in more details.

gagan86nagpal · April 30, 2018, 9:04am

github.com

gagan86nagpal/SPOJ-200/blob/master/GSS 1 clean/main.cpp

#include <iostream>

using namespace std;

#define inf 16000000
int a[50002];
struct block
{
    int sum;
    int pref;
    int post;
    int ans;
};
block segtree[200008];
void build(int node ,int l ,int r)
{
    if(l==r)
    {
        segtree[node]= {a[l],a[l],a[l],a[l]};
        return;

This file has been truncated. show original

Check out my implementation and feel free to ask anything

vivek_1998299 · May 1, 2018, 3:35pm

Create a segment tree,node representing [i,j] lets call node p ,contains max subarray sum(Ap),max prefix sum(Pp),max suffix sum(Sp),totalSum(Tp)

Lets say node p in seg has child q(left child),r

So Ap=max(Aq,Ar,Sq+Pp)

Pp=max(Pq,Tq+Pr)

Sp=max(Sr,Tr+Sq)

Tp=Tq+Tr

Using this construct seg

vivek_1998299 · May 1, 2018, 3:40pm

And yeah,learn to upvote some1 if u think they solved ur doubts,people like me would help as we like to help,bt some people help to get some karma,and i really have never seen u upvote some1,so better do if they solve ur doubts,else people wont help u again

arpit728 · May 1, 2018, 6:09pm

@vivek_1998299

People were less active in answering my doubts, I think this was the reason. Thank you so much vivek for helping me and opening my eyes as well.
Thank you so much

Can you please look into this, I am getting TLE.

arpit728 · May 1, 2018, 8:46pm

@vivek_19982995

Can you please explain in more details.

vivek_1998299 · May 1, 2018, 9:10pm

Check this out,i dont think i can explain better than them.

arpit728 · May 3, 2018, 10:54pm

@vivek_1998299
I solved using approach described there, but I am getting TLE. I have spent too much time on it. Please help.

https://pastebin.com/jyuhAm22

Thanks in advance