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

×

SPOJ - GSS1 - Can you answer these queries I

http://www.spoj.com/problems/GSS1/

Since this problem is set for segment trees, Kadane's algorithm failed. So I looked up segment trees and got the gist of it. I followed this for learning the basics:

https://codeextractor.wordpress.com/2016/07/11/playing-with-ranges-segment-tree/

After trying few times, I got my code working, but got a WA for final test caes, so I googled up the concept of maximum subarray and managed to get it working, but now my implementation times out, even with optimized IO (beyond scanf and printf, using one of those fancy templates available online)

I decided to remove everything, including vectors, and deal purely with arrays and scanf/printfs and I still get a time out. Either the time limit is really strict or the code doesn't work as I think it should and maybe gets stuck.

Here is my final implementation using arrays: http://ideone.com/MqeiLa

Thanks.

asked 20 Dec '16, 06:14

epsilonalpha's gravatar image

4★epsilonalpha
10516
accept rate: 25%


You have done a mistake in your code ,
in line no. 55 ,
in Data query(int l, int r, int s, int e, int node) function.
here it is,

make the above function as follows:

Data query(int l, int r, int s, int e, int node)
{
    Data d;
    if(s>r || e<l)
        return d;
    else if(s>=l && e<=r)  //use this instead of '(s>=e && e<=r)'
        return tree[node];

    int m = s+(e-s)/2;
    if(l>m)
        return query(l,r,m+1,e,2*node+1);
    else if(r<=m)
        return query(l,r,s,m,2*node);
    else
    {
        Data lQuery = query(l,r,s,m,2*node);
        Data rQuery = query(l,r,m+1,e,2*node+1);
        calc(node,d,lQuery,rQuery);
        return d;
    }
}

The AC solution of your code is here.

Here you have to check whether the current node is completely inside the range or not.
If it is completely inside the range, then return the node.

I have solved the same problem, you can see my solution on github.
Hope this is helpful. If you still don't get anything ,feel free to ask.

link

answered 20 Dec '16, 07:51

anooakv's gravatar image

4★anooakv
1002
accept rate: 57%

edited 20 Dec '16, 08:41

What a silly typo, I didn't even notice it... and here I was trying to optimize IO. Thank you so much, I'll take much better care next time.

link

answered 20 Dec '16, 18:13

epsilonalpha's gravatar image

4★epsilonalpha
10516
accept rate: 25%

can you please explain what actually we have to do i am not able to undesrtand?? stuck between max and all (what is the need)??

link

answered 01 Feb '18, 21:47

abhi007rider's gravatar image

2★abhi007rider
122
accept rate: 0%

can u plz tell me the approach in this question i m not able to understand what actuall quest wants!! @vijju123

linl-> http://www.spoj.com/problems/GSS1/

link

answered 01 Feb '18, 21:59

abhi007rider's gravatar image

2★abhi007rider
122
accept rate: 0%

edited 01 Feb '18, 22:00

1

Question asks for maximum sub range sum, just like you calculate maximum sub array sum (u can consider this as range from 0 to n-1). Here you have to answer maximum sum in range l to r.
here you can get a nice explanation.

(02 Feb '18, 22:52) siddharthp5384★

Sorry, saw this late. Refer to what siddharth said :)

(02 Feb '18, 22:59) vijju123 ♦♦5★
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,768
×1,137
×75
×68
×21

question asked: 20 Dec '16, 06:14

question was seen: 3,378 times

last updated: 02 Feb '18, 22:59