Hello,my code with ID 30677920 for MAXBTY is showig wrong ,can anyone help me find where I am
going wrong?
@tmwilliamlin Write down this kind of editorial for mysara question as well of march cookoff 2020 please
Can We use Fenwick trees for this problem?
I have some doubts in Update —>
U x v: Chef reevaluates the beauty of the letter from the x-th fan. The new value of Bx becomes v.
according to this statement: after U 1 1 result for query Q 2 4 must be 5
we have to replace current value of given array with v, right? in Fenwick tree at index x value will be updated as:
update(int *binaryIndexedTree,int value,int index,int n) //here x=index and v=value and value is passed as value=v-arr[x]; { while(index<=n) { binaryIndexedTree[index]+=value;
index+=index&(-index); }
I tried solving this with Binary Indexed Tree. If someone has solved this using BIT then please let me know.
This question is quite similar to this problem. If one carefully notes
problem link:GSS1 spoj
Tutorial link:- A classical segment tree problem
Classical segment tree for maximum sum in a range.
My code for which I solved the MAXBTY problem:-
https://www.codechef.com/viewsolution/30686539
Core Idea is to use x=maximum suffix subarray sum in range 1 to x-1
and y=maximum prefix subarray sum in range y+1 to n and
z=sum of subarray x to y
by using these three values
output max(z,x+z,y+z,x+y+z) as answer.
For obtaining this value use segment tree nodes.
CodeChef: Practical coding for everyone Hey can anyone tell me what I am doing wrong. My approach is same as given in editorial maintaining two segment trees for positive and negative prefix sums . It really means a lot if anyone can help. Thanks for your time.
https://www.codechef.com/viewsolution/30687934
Can anyone help me with it?
My logic is same as tester’s soltution the only difference is 0based and 1 based index
https://www.codechef.com/viewsolution/30687418
Can someone tell me what is wrong with this solution?
I’m unable to figure it out.
can we do this question with help of binary indexed tree ( used in LAZER of March 2020 long challenge) instead of segment tree?
link of LAZER : https://www.codechef.com/MARCH20B/problems/LAZER
Definitely you can if you preserve prefix suffix and sum in a range as per above shared article by me.
In-fact The second question of div1 of previous cook off can also be done the same way. This cook offs and previous cook offs second question were almost similar quickly check both the questions.
LIne 106 :-node y1=query(1,0,n-1,0,l-2);
Querying range 1 to x-1 and getting a node.
Line 107: - node y2=query(1,0,n-1,r,n-1);
Querying range y+1 to n and getting a node
in each node y , y1 and y2 we have maximum prefix subarray sum , maximum suffix subarray sum , total sum of subarray
thus now we got all the things for all the three ranges that is 1 to x-1 x to y and y+1 to n
now
x=maximum suffix subarray sum in range 1 to x-1 obtain this from node y1
and y=maximum prefix subarray sum in range y+1 to n and obtain this from node y2
z=sum of subarray x to y and obtain this from node y
by using these three values
output max(z,x+z,y+z,x+y+z) as answer.
i tried that way,my query working fine but update is not,shall we discuss more on BIT for this problem?
I tried the logic of editor’s solution and implemented it in Python. Can anybody tell me why am I getting TLE for my solution.
Link to my solution
//Can anyone tell me what is wrong in this solution?
def make_list(A,N,L,R):
s=0
r=0
L.append(A[0])
R.append(A[N-1])
for i in range(1,N):
if L[i-1]>0:
L.append(A[i]+L[i-1])
else:
L.append(A[i])
if R[0]>0:
R.insert(0,A[N-1-i]+R[0])
else:
R.insert(0,A[N-1-i])
T=int(input())
for t in range(T):
L=[]
R=[]
N,Q=map(int,input().split())
A=[int(x) for x in input().split()]
make_list(A,N,L,R)
for q in range(Q):
v,x,y=input().split()
if v==‘Q’:
x,y=int(x),int(y)
s=0
for i in range(x,y-1):
s=s+A[i]
s=s+L[x-1]+R[y-1]
print(s)
elif v==‘U’:
x,y=int(x),int(y)
A[x-1]=y
L=[]
R=[]
make_list(A,N,L,R)
there is very small and easy implementation
https://www.codechef.com/viewsolution/30709921
could somebody help me !!! i am getting wrong ans.
You are not updating the tree according to its lazy values when you perform querymin().
In Setter’s Solution,
in queryMin function why is it that we have to return 0, if the STnode’s range is not inside the query interval of (i,j) ?
if we return 0 , then wouldn’t the returned zero affect the further actual querying ?
That is, if size of array is 5 and we call queryMin for (4,5) interval… the queryMin call for (1,3) returns 0 and if the minimum value returned by queryMin for (4,5) interval is +ve ; then the final answer will be given as 0 as the minimum value.
I checked that this code returns 0 instead of the actual positive value which was supposed to come.
So, shouldn’t the value returned for out of range condition be changed to infinity?
But that’s what i did(exactly same as that of setter’s solution except for what i return) , getting some wrong answer for the sample test cases itself.
correct me if I’m wrong.