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

×

WA in GSS1 spoj (9th test case)

Wa in GSS1 spoj

Getting WA on 9th test case

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

Answer : http://ideone.com/zcPCr3

asked 21 Jun '17, 20:30

chunky_2808's gravatar image

3★chunky_2808
1649
accept rate: 4%

edited 22 Jun '17, 12:58


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)

link

answered 22 Jun '17, 14:13

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

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

(23 Jun '17, 17:30) chunky_28083★
1

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.

(23 Jun '17, 23:30) vijju123 ♦♦5★

@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,2pos+1); constructST(arr,segarr,mid+1,r,2pos+2); segarr[pos].sum=segarr[2pos+1].sum+segarr[2pos+2].sum; segarr[pos].maxPrefixSum=max(segarr[2pos+1].maxPrefixSum, segarr[2pos+1].sum+segarr[2pos+2].maxPrefixSum); segarr[pos].maxSuffixSum=max(segarr[2pos+2].maxSuffixSum, segarr[2pos+2].sum+segarr[2pos+1].maxSuffixSum); segarr[pos].maxSum=max(segarr[2pos+1].maxSuffixSum+segarr[2pos+2].maxPrefixSum, max(segarr[2pos+1].maxSum,segarr[2pos+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,2pos+1); ll b=getMaxSum(segarr,mid+1,r,qs,qe,2pos+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[i]); 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\n",ans); } return 0; }

link

answered 06 Nov '17, 19:15

ramini's gravatar image

2★ramini
615
accept rate: 8%

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

(06 Nov '17, 23:37) vijju123 ♦♦5★

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.

(06 Nov '17, 23:49) ramini2★

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)

(07 Nov '17, 00:03) vijju123 ♦♦5★

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

(07 Nov '17, 00:10) ramini2★

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. :)

(07 Nov '17, 00:12) vijju123 ♦♦5★

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

(07 Nov '17, 00:43) ramini2★
showing 5 of 6 show all

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?

link

answered 07 Nov '17, 01:17

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

@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?

link

answered 07 Nov '17, 12:40

ramini's gravatar image

2★ramini
615
accept rate: 8%

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)

(07 Nov '17, 12:48) vijju123 ♦♦5★

Sure bro. Thanks!

(07 Nov '17, 12:55) ramini2★

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[i]);
        }
        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;
}
link

answered 08 Dec '17, 22:28

codash's gravatar image

3★codash
0
accept rate: 0%

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

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

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

(08 Dec '17, 23:00) vijju123 ♦♦5★

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

(09 Dec '17, 10:19) codash3★
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:

×1,755
×1,136
×708

question asked: 21 Jun '17, 20:30

question was seen: 1,361 times

last updated: 09 Dec '17, 10:19