Gss1

[manish_malik]

Hi,
I'm trying the problem spoj.pl/problems/GSS1/
and getting error SIGSEGV.
My code is
[color=#8040BF]

#include<stdio.h>
void initialize(int ,int ,int );
int query(int ,int ,int ,int ,int );
int max(int ,int ,int );
int M[50100],A[50010],N;
int main()
{ int i,m,p,q;
  scanf("%d",&N);
  for(i=1;i<=N;i++)
   scanf("%d",&A[i]);
  scanf("%d",&m);
  initialize(1,1,N);
  while(m--)
  { scanf("%d%d",&p,&q);
    printf("%d\n",query(1,1,N,p,q));
  }
  return 0;
}
void initialize(int node, int b, int e)
  {   if (b == e)
          M[node] = A[b];
      else
       {  initialize(2 * node, b, (b + e) / 2);
          initialize(2 * node + 1, (b + e) / 2 + 1, e);
          M[node]=max(M[2*node],M[2*node+1],M[2*node]+M[2*node+1]);
      }
  } 
int query(int node, int b, int e, int i, int j)
  {   int p1, p2;
      if (i > e || j < b)
          return -1;
      if (b >= i && e <= j)
          return M[node];
      p1 = query(2 * node, b, (b + e) / 2,i, j);
      p2 = query(2 * node + 1, (b + e) / 2 + 1, e, i, j);
      if (p1 == -1)
          return M[node] = p2;
      if (p2 == -1)
          return M[node] = p1;
      if (A[p1] <= A[p2])
          return M[node] = p1;
      return M[node] = p2;
  }
int max(int x,int y,int z)
{ if(x>y)
   { if(x>z) 
       return x;
     else
       return z;
   }
  else    
   { if(y>z)
       return y;
     else
       return z;      
   }
}

[/color]

Can somebody please tell me the reason behind this error.
As far as I think, it should be because of the size of the M array, but I'm not quite able to calculate the right size for it.

Thanks in advance.

[leppyr64]

Calculate the maximum depth for a node using a brute force algorithm. After that you should know how big you need M to be.

[manish_malik]

So, is my algo correct?
n the error is coming because of M?
Actually i read about segment trees and not quite sure if this is the right way to use them

[leppyr64]

I'm not certain if your algorithm is correct. I was just answering your question about how to calculate re number of nodes in a segment tree.

Example segment tree, range 1 to 6.

parent->children
Null->[1,6]
[1,6]->[1,3],[4,6]
[1,3]->[1,2],[3,3]
[1,2]->[1,1],[2,2]
[4,6]->[4,5],[6,6]
[4,5]->[4,4],[5,5]

You don't need to store the information about the range (start and end) in the node because you are calculating it as you traverse down from the node.

A simpler problem to cut your teeth on is LITE.

[scofield23]

Can u please help me find the bug in the code...getting WA

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
vector<int> tree;
vector<int> number;
int merge(int n1,int n2)
{
    if(n1>n2) return n1;
    else return n2;
}
void build_tree(int node,int begin,int end){
     if(begin==end){
                    tree[node]=number[begin];
                    return ;
     }
     build_tree(2*node,begin,(begin+end)/2);
     build_tree(2*node+1,(begin+end)/2+1,end);
     tree[node]=merge(tree[2*node],tree[2*node+1]);
}
int query(int node,int begin,int end,int i,int j){
    if(i>end || j<begin){return -99999;}
    if(begin>=i && end<=j){return tree[node];}
    int p1=query(2*node,begin,(begin+end)/2,i,j);
    int p2=query(2*node+1,(begin+end)/2+1,end,i,j);
    if(p1==-99999){return p2;}
    if(p2==-99999){return p1;}
    if(p1>=p2){return p1;}
    else{return p2;}
}
int main()
{
    int n,x,q1,q2;
    scanf("%d",&n);
    if(n==0) return 0;
    for(int i=0;i<n;i++){    scanf("%d",&x); number.push_back(x);}
    int gh=(int)(log10(n)/log10(2))+1;
int sz=pow(2.0,gh+1);
vector<int> make_size(sz,-999999 );
tree=make_size;
make_size.clear();

build_tree(1,0,n-1);
int p;
scanf("%d",&p);
for(int i=0;i<p;i++){
        scanf("%d",&q1);
        scanf("%d",&q2);
        int ans=query(1,0,n-1,q1-1,q2-1);
        printf("%d\n",ans);
}
return 0;
}

[leppyr64]

Your code doesn't answer the problem in the problem statement. Read it carefully.

3 
-1 2 3
1
1 3

[scofield23]

can u be a bit more specific...
aren't we supposed to find max(i,j) element through segment tree...?? where is the flaw??

[leppyr64]

No. i and j can be anything between x,y.

Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.

[scofield23]

thnks.. I got it ....!! we are supposed to find max sum in the range (i,j) in logn time...!!
Just in case query 1 3 for the above case u mentioned results in answer=5 .. correct me if I am wrong...!!

[leppyr64]

Correct.

[logic_king]

hi,

i attempted the problem GSS!

i have the solved the problem using segment trees.....i have the checked my solution for the most of the cases but i am getting WA.......plz tell any case where my code fails !!.....please point out the bug if any in the code

#include<stdio.h>
//                                SEGEMENT TREE
// this program will make a segment tree of a given array and then perform the queries on it as asked in the question fo any range
//starting with the function to ionitialise the segement tree
//                        INTIALIZATION
void initialize(int node, int b, int e, int M[], int A[])
{
   if (b == e)
       M[node] = A[b];
   else
  {
//compute the values in the left and right subtrees
       initialize(2 * node, b, (b + e) / 2, M, A);
       initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A);
//search for the minimum value in the first and
//second half of the interval
       if (M[2 * node] >= M[2 * node + 1])
            M[node] = M[2 * node];
       else
            M[node] = M[2 * node + 1];
   }
}
//function for doing query on the segement tree
//                            QUERY
int query(int node, int b, int e, int M[], int A[], int i, int j)
{
    int p1, p2;
//if the current interval doesn't intersect
//the query interval return -1
    if (i > e || j < b)
        return -1;
//if the current interval is included in
//the query interval return M[node]
    if (b >= i && e <= j)
        return M[node];
//compute the minimum position in the
//left and right part of the interval
    p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);
    p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);
//return the position where the overall
//minimum is
    if (p1 == -1)
        return /*M[node] =*/ p2;
    if (p2 == -1)
        return /*M[node] =*/ p1;
    if (p1 >= p2)
        return /*M[node] =*/ p1;
    return /*M[node] =*/ p2;
}
int A[50000]={0},M[100000]={-1};
int main()
{
    int n,i,j,tc;
    scanf("%d",&n);//now number of elements in the array is known
    for(i=0;i<n;i++)
        scanf("%d",&A[i]);
    //initialize your segement tree now
   initialize(1,0,n-1,M,A);
/*    for(i=0;i<2*n;i++)
            printf("%d  ",M[i]);
       printf("\n");
    */
    //perform the queries here
   scanf("%d",&tc);
    while(tc--)
    {
        scanf("%d%d",&i,&j);
        //perform the query for each interval
       printf("%d\n",query(1,0,n-1,M,A,i-1,j-1));
        //print the maximun value here
    }
return 0;
}

[logic_king]

anyone...plz help me out !!

[flopcoder_sof]

In your initialize finction you have assumed that the maximum subarray sum obtained from combination of two nodes is max(leftmax,rightmax).This is not true.The maximum subaray might stretch across both the intervals.You're nodes must have the following members.
1.MaxSum(M[] in your case)
2.MaxSuffixSum
3.MaxPrefixSum
4.Sum of all elements

[logic_king]

you got it wrong....i am creating the tree for finding thee maximum value....not maximum sum !!

[logic_king]

sry...i misread the problem...thanx for pointing it out

[chownikhil_sof]

Hello Everyone,

I have been trying out this problem with very little success. I got rid of TLE but am unable to get rid of WA.

my logic :

I maintain two variables curr_sum and max_sum (both are initialized to 0). I start from the xth number and keep adding every number to curr_sum. Meanwhile i will be checking for two conditions.
1 . If curr_sum is greater than max_sum, then max_sum = curr_sum
2 . if curr_sum is < 0 then curr_sum = 0
In case if all the numbers are negative in the given range, then i will print the largest negative number in the sequence.

Here's my code.

#include<stdio.h>
#include<math.h>
long getNum()
{
    long i=0, temp = 0, neg=0, num[5], j;
    char c;
    c = getchar();
    while(c!='\n' && c!=' ')
    {
                  if(c=='-') neg = 1;
                  else
                  {
                      num[i] = c-48;
                      i++;
                  }
                  c = getchar();
    }
    i--;
    j = i;
    i = 0;
    while(j>=0)
    {
               float x = pow(10, j);
               temp += x*num[i];
               i++; 
               j--;
    }
    if(neg==1) temp = temp*(-1);
    return temp;
}
int main()
{
    long a[50000], count, m, temp = 0;
    count = getNum();
    while(count)
    {
                a[temp] = getNum();
                temp++;
                count--;
    }
    m = getNum();
    while(m)
    {
            long x, y, i;
            x = getNum();
            y = getNum();
            long curr_sum = 0, max_sum = 0, max_neg = -32000, neg_count = 0, count = 0;
            for(i=x-1;i<y;i++)
            {
                             if((curr_sum+a[i])>0)
                             {
                                                  curr_sum += a[i];
                                                  if(curr_sum>max_sum) max_sum = curr_sum;
                             }
                             else
                             {
                                 curr_sum = 0;
                             }
                             if(a[i]<0) 
                             {
                                        if(a[i]>max_neg) max_neg = a[i];
                                        neg_count++;
                             }
                             count++;
            }
            if(count==neg_count) printf("%d\n", max_neg);
            else printf("%d\n", max_sum);
            m--;
    }
    return 0;
}

[fitcat]

I think your getNum() may be implemented incorrectly. Try redirect a input file to your program and you will know what I mean.
Your program can't pass the first test case (there are several of them in this problem). This may be caused by the incorrect getNum().
I replaced it by my own fast read function and got TLE at the 9th test case.
Regarding your algo, it is O(M * (y - x)). In the worst case, it is O(M * N). You will definitely get TLE. You need an algo O(M * log N) to get AC.
Read the posts about this topic. Hint: segment tree.

[chownikhil_sof]

Thanks a lot for your reply

[chownikhil_sof]

I implemented segment trees but still getting TLE. It would be very helpful if you could suggest where i am going wrong

#include<stdio.h>
#include<math.h>
long a[50000];
long max = 0, pre = 1, suf = 2, full = 3;
long maximum(a, b, c)
{
     if(a>=b)
     {
             if(a>=c) return a;
             else return c;
     }
     else
     {
         if(b>=c) return b;
         else return c;
     }
}
long* MaxSubArray(long x, long y)
{
     if(x==y)
     {
             long ret[4] = {a[x], a[x], a[x], a[x]};
             return ret;
     }
     else
     {
         long* left;
         long* right;
         long leftTemp[4], rightTemp[4];
         left = MaxSubArray(x, (x) + (y-x)/2);
         leftTemp[max] = left[max];
         leftTemp[pre] = left[pre];
         leftTemp[suf] = left[suf];
         leftTemp[full] = left[full];
         right = MaxSubArray((x) + ((y-x)/2) + 1, y);
         rightTemp[max] = right[max];
         rightTemp[pre] = right[pre];
         rightTemp[suf] = right[suf];
         rightTemp[full] = right[full];
         long ret[4];
         ret[pre] = maximum(leftTemp[pre], leftTemp[full]+rightTemp[pre], leftTemp[full]+rightTemp[full]);
         ret[suf] = maximum(rightTemp[suf], leftTemp[suf]+rightTemp[full], leftTemp[full]+rightTemp[full]);
         ret[full] = leftTemp[full]+rightTemp[full];
         ret[max] = maximum(leftTemp[max], rightTemp[max], leftTemp[suf]+rightTemp[pre]);
         return ret;
     }
}
long read()
{
     char c = getchar();
     int num[5], i = 0, j = 0, neg = 0;
     long temp = 0;
     while(c==' ' || c=='\n') c = getchar();
     while(c!=' ' && c!='\n')
     {
                if(c=='-') neg = 1;
                else 
                {
                     num[i] = c - 48;
                     i++;
                }
                c = getchar();
     }
     i--;
     j = i;
     while(j>=0)
     {
                float x = pow(10, j);
                temp += num[i-j]*x;
                j--;
     }
     if(neg==1) temp = temp*(-1);
     return temp;
}
int main()
{
    long count, m, temp = 0;
    count = read();
    while(count)
    {
                a[temp] = read();
                temp++;
                count--;
    }
    m = read();
    while(m)
    {
            long x, y;
            long *i;
            x = read();
            y = read();
            i = MaxSubArray(x-1, y-1);
            printf("%ld\n", i[0]);
            m--;
    }
    getch();
    return 0;
}

[fitcat]

If you are new to segment tree, try to solve the easy one LITE first.