WA in GSS1 spoj (9th test case)

segment-tree
spoj
tree

#1

Wa in GSS1 spoj

Getting WA on 9th test case

link to question : http://www.spoj.com/problems/GSS1/

Answer : http://ideone.com/zcPCr3


#2

The code fails here-

Input
10 
-200 -3 -4 -200 6 2 4 -200 5 6 
1 
5 10
Your Output
11
Expected Output
12 (6+2+4)

This bug is because of -

(max(query(seg,low,mid,qlow,qhigh,(2*pos)+1,arr),query(seg,mid+1,high,qlow,qhigh,(2*pos)+2,arr)));

The nodes here are such that-
(Format- NodeName- LeftBest,RightBest,OverallBest,TotalSum)

NodeA(on left side of tree) = 6,6,6,6 (Node from element in range [5,5] - 1 based indexing.)
Node B(on right side of tree) = 6,-183,11,-183 (Node made from element in range [6,10]- 1 based indexing)

You will have to find ans by-

ans= Maximum of (Best sum of node a, best sum of node b, sum of BestRight of A+sum of BestLeft of B)
(A new maximum can be formed when combining the nodes- not necessary that only the best sums of child nodes are sources of best sums of parent nodes)


#3

@vijju123 Please find my mistake, I wrote the getMaxSum function as you mentioned above

#define ll long long
using namespace std;
struct node
{
	ll sum;
	ll maxPrefixSum;
	ll maxSuffixSum;
	ll maxSum;
};
node segarr[4*50010];
ll arr[50010];

void constructST(ll arr[],node segarr[],ll l,ll r,ll pos)
{
	if(l==r)
	{
		segarr[pos].sum=arr[l];
		segarr[pos].maxPrefixSum=arr[l];
		segarr[pos].maxSuffixSum=arr[l];
		segarr[pos].maxSum=arr[l];
	}
	else
	{
		ll mid=(l+r)/2;
		constructST(arr,segarr,l,mid,2*pos+1);
		constructST(arr,segarr,mid+1,r,2*pos+2);
		segarr[pos].sum=segarr[2*pos+1].sum+segarr[2*pos+2].sum;
		segarr[pos].maxPrefixSum=max(segarr[2*pos+1].maxPrefixSum,
										segarr[2*pos+1].sum+segarr[2*pos+2].maxPrefixSum);
		segarr[pos].maxSuffixSum=max(segarr[2*pos+2].maxSuffixSum,
										segarr[2*pos+2].sum+segarr[2*pos+1].maxSuffixSum);
		segarr[pos].maxSum=max(segarr[2*pos+1].maxSuffixSum+segarr[2*pos+2].maxPrefixSum,
										max(segarr[2*pos+1].maxSum,segarr[2*pos+2].maxSum));
	}
}

ll getMaxSum(node segarr[],ll l,ll r,ll qs,ll qe,ll pos)
{
	if(qs>r || qe< l)
    	return -16000;
	if(qs<=l && qe >= r)
	return segarr[pos].maxSum;
	ll mid=(l+r)/2;
	ll a=getMaxSum(segarr,l,mid,qs,qe,2*pos+1);
	ll b=getMaxSum(segarr,mid+1,r,qs,qe,2*pos+2);
	return max(max(a,b),a+b);	
}

int main()
{
	ll n;
	scanf("%lld",&n);
	for(ll i=0;i< n;i++)
	scanf("%lld",&arr*);
	constructST(arr,segarr,0,n-1,0);
	ll m;
	scanf("%lld",&m);
	while(m--)
	{
		ll a,b;
		scanf("%lld%lld",&a,&b);
		a--;b--;
		ll ans=getMaxSum(segarr,0,n-1,a,b,0);
		printf("%lld
",ans);
	}
	return 0;
}

#4

Ok, so you want the reasoning behind it?

Firstly, I assume that you know why MaxSum of Left Node+ MaxSum Of Right node is wrong.

Now, say our nodes have information about sub-arrays-
L={-20,10,10} (index say, 0 to 2) and R={10,10,-20} (index say, 3 to 5). Now our parent node stores by combining results of L and R. So parent node stores result for {-20,10,10,10,10,-20}.

Ofc, the answer for query is 10+10+10+10=40. But look at values.

For L, Sum=0, Maxsum=20, PrefixSum=0, Suffixsum=20.
For R,Sum=0,Maxsum=20,PrefixSum=20,SuffixSum=0;

Now when we combine segments L and R, we get collective segment {-20,10,10,10,10,-20}. Focus on how this segment {10,10,10,10} got formed. Isnt it the “Best Suffix sum of node L + Best Prefix Sum of Node R”?

If you argue for Maxsum of L + Max sum of R, then an easy counter example is {10,10,-200,-200,10,10}. Maxsum of L + Maxsum of R gives 20+20=40, but its not possible because positions must be contiguous.

But when we add suffix and prefix sum, then its obvious that the positions are contiguous, for we calculated those 2 that way!

Still any doubt that why its Best Suffix Sum of L + Best Prefix Sum of R?


#5

@vijju123 Cleared Bro. Thanks a lot for taking the time and clearing my doubt.Will you recommend me any other good problems on Segment Trees?


#6

Hey @vijju123 , I am also stuck on the same question. I have implemented the same thing that you have described in previous answers still I am getting WA. Could you please help!
Code:

#include<bits/stdc++.h>
using namespace std;
long long MAX = 4000001;
vector <long long> tree, lazy, arr;
map <pair<int, int>, long long> dp;
map <pair<int, int>, long long> ::iterator it;
class Node
{
public:
  long long presum , postsum, maxsum, totalsum, left, right;
  Node *cleft, *cright;
  Node()
  {
    presum = -15008;
    postsum = -15008;
    maxsum = -15008;
    totalsum = -15008;
    cleft = NULL;
    cright = NULL;
  }
  void merge()
  {
    presum = max(cleft -> presum, cleft -> totalsum + cright -> presum);
    postsum = max(cleft -> postsum + cright -> totalsum, cright -> postsum);
    totalsum = cleft -> totalsum + cright -> totalsum;
    maxsum = max(max(cleft -> maxsum, cright -> maxsum), cleft -> postsum + cright -> presum);
  }
};

void build(Node* node, long long start, long long end)
{
  if(start == end)
  {
    node -> totalsum = arr[start];
    node -> maxsum = arr[start];
    node -> postsum = arr[start];
    node -> presum = arr[start];
    node -> left = node -> right = start;
  }
  else
  {
    node -> cleft = new Node;
    node -> cright = new Node;
    node -> left = start;
    node -> right = end;
    long long mid = (start + end)/2;
    build(node -> cleft, start, mid);
    build(node -> cright, mid + 1, end);
    node -> merge();
  }
}



Node* queryRange(Node* node, long long start, long long end, long long l, long long r)
{
    Node* a1;
    a1 = new Node;
    if(start > end || start > r || end < l)
        { 
          return a1;   }      
    if(start >= l && end <= r)             
        return node;
    long long mid = start +(end - start) / 2;
    a1->cleft = (queryRange(node -> cleft, start, mid, l, r));         
    a1->cright = (queryRange(node -> cright , mid + 1, end, l, r)); 
    a1 -> merge();
    return a1;
}

int main()
{
    long long n, query;
    Node *root = new Node;
    Node *ans;
    
        scanf("%lld", &n);

        arr.resize(n, 0);
        for(int i = 0; i < n; i++)
        {
          scanf("%lld", &arr*);
        }
        build(root, 0, n - 1);
        cin >> query;
        int p, q;
        while(query--)
        {
          scanf("%d %d", &p, &q);
          if(dp.find(make_pair(p, q)) == dp.end())
          {
            dp[make_pair(p, q)] = queryRange(root, 0, n - 1, p - 1, q - 1) -> maxsum ;
            
          }
          printf("%lld", dp[make_pair(p, q)]);
        }
        arr.clear();
    
    return 0;
}

#7

GOt my mistake !!
Took me 3 days to solve it !!
thanks!!


#8

Give "SPOJ ‘Frequent’ " a try as well. If you solved this Q with correct concept (and not an ad-hoc solution), you will find that Q using 80% same algorithm. If thats done easily, you can be assured of your concepts regarding relation b/w child and parent nodes in seg. tree.


#9

Look at your getMAxsum function. Now look at qs,qe , and l and r. You interchanged roles of qe,qs,l and r. Look here-

getMaxSum(segarr,l,mid,qs,qe,2*pos+1); and then the condition if(qs>r || qe< l) and function definition ll getMaxSum(node segarr[],ll l,ll r,ll qs,ll qe,ll pos)

I think you interchanged positions of qs,qe ,l and r in function definition


#10

No, I haven’t. qs->query starting, qe->query ending, l and r are initially set to 0 and n-1. I didn’t change the order.


#11

Okay, I got confused by the names XD.

From analysis of your code over outputs, I think you are doing it as “Max of-
MaxSum of left node, MaxSum of right node, Maxsum of LeftNode+Maxsum of Right Node”

But this is wrong. Eg- for this case-

10 -200 -3 -4 -200 6 2 4 -200 5 6 1 5 10

It considers max sum of left node, 6, then max sum of right node, 11, and their sum 17. Your code gives 17 as output here, but its not possible as theres a -200 in between.

Correct expression is (Best sum of node a, best sum of node b, sum of Best**Right** of A+sum of Best**Left** of B)


#12

Can you give me the expression that I should include in my code?


#13

You need to do some tweaking in order to get the sum of Best**Right** of A+sum of Best**Left** of B . Think for a while, if it doesnt strike after some time then ping me again. :slight_smile:


#14

Not getting bro. Please explain why should we take max(leftMax,rightMax,sum of leftMaxSuffix+rightMaxPrefix)


#15

I think K-Frequency was a nice problem. It uses same concept, and is good to make sure that you got the concept idea.

Then go for PRMQ from long contest (It appeared in one of long contest held b/w April-June- cant remember exact deets atm)


#16

Sure bro. Thanks!


#17

I cannot have a look right now dear, in middle of exams till 14th :frowning:

printf("%lld", dp[make_pair(p, q)]);

BTW, Are you sure that you are printing answer of each query on a new line??


#18

ok…just have a look at it when you are free.
And regarding that newline , removed fast io code, so changed it to printf and scanf.
P.S.: Also tried submitting the above code…getting tle XD