HMAPPY1 - EDITORIAL

any reviews for this approach
I consider connected components and then update them as per query and return max of sizes of connected component.

=> https://www.codechef.com/viewsolution/21573122

1 Like

https://www.codechef.com/viewsolution/21550313
did Without segment tree.
Much easier to understand and short program.

I used the same approach as @abhi2402 but it wasn’t able to pass the 15th sub-task. What could be the reason? Here’s my code : CodeChef: Practical coding for everyone

i have tried this with Segment Tree as per the editorial,
i have build the segment tree for 2*N , but i am stuck at query part, can’t figure out how to find the answer when the answer is the sum of suffix of left child and prefix of right child and not the max of both child;
someone guided me to return a node rather than the answer for each query, i tried it but can’t get the idea how to return the node.
Here’s my code : https://ideone.com/vG4Xo3

can anyone help me with this, and if possible can update the query function.

please someone help me find error in my code…thanks in advance

code link

without segment tree / set …
( like a few others in the posts above) my solution (simple to understand as well) CodeChef: Practical coding for everyone

It’s a little late but I think the solution to this problem is relatively simpler than described in the editorial. Ofcourse other approaches mentioned are also great.

I simply pre-calculated and hashed the sequences of 1’s and their sizes and beginning indexes. Sorted them so I get the largest sequences on one side.

Then I pre calculated the result for each N, by simply checking if the pointer is outside, inside or at the edge of the largest sequence, the second largest and so on…

The code is a little messy but the approach is very simple

https://www.codechef.com/viewsolution/21479865

1 Like

loved the editorial , was struggling a bit to fit segment tree in there .I know of the other approaches now but this is what I neeeded

https://www.codechef.com/viewsolution/21524883

Idea Behind: I made a new vector in a way that it contains number of consecutive 1’s and 0’s

1 1 1 0 0 0 0 1 1

the vector would be: 3 -3 2 (1’s by positive value and 0’s by negative sum)

i kept the maximum abs(maximum sum) till now and used Deque and BANG! Solved

I hope my solution will help you understand

1 Like

It can be done in O(N+Q) as well. My Soln.

2 Likes

Note that my competition answer didn’t implement the answer array, but it makes the code a bit tidier and there is a small timing advantage.

Segment tree is louv XD

@savaliya_vivek I tested your code locally and found that your method to find 1st Max ans 2nd Max is having bugs. Check out this Solution to find your error. rest is fine.

Even though you are using deque, whenever there is a query of ‘?’ type, your code takes O(N) time for getting the largest subsequence. For query of type ‘!’, your code does shifting in O(1) time as you are using deque, but if there are lots of query of type ‘?’ your code can take O(N*Q) time which easily exceeds the time limit. You can check my answer above for doing the problem in O(N+Q).

1 Like

Rotation was just there to explain it carefully.

Well, that’s the alternate Implementation.

@taran_1407 Yes, and I mentioned it here in case anyone reviewing my code wonders where it happens.

I think there’s a slight mistake. the vector should be 3 -4 2 as I guess. Nice solution.

Glad you found it useful

Please explain the time complexity of buiding the tree. I have read that time complexity of building a tree is O(n). Why are you multiplying with log(n). I don’t understand why I am getting TLE as I am using segment trees.

#include <bits/stdc++.h>
using namespace std;

#define speedup ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define N 200010
#define M 800040
int A[N],tree[M],p[M],s[M];
bool z[M]={0};

int max(int a,int b,int c){
if(a>=b && a>=c)
return a;
else if(b>=a && b>=c)
return b;
else if(c>=a && c>=b)
return c;
}

void buildtree(int node,int l,int r){

if(l==r){
    tree[node]=A[l];
    if(A[l])
        p[node]=s[node]=1;
    else{
        p[node]=s[node]=0;
        z[node]=1;
    }
    
    return;
}

int mid=(l+r)/2;
//mid>>1;
buildtree(2*node+1,l,mid);
buildtree(2*node+2,mid+1,r);
if(!z[2*node+1] && !z[2*node+2])
    tree[node]=p[node]=s[node]=p[2*node+1]+s[2*node+2];
else if(z[2*node+1] && !z[2*node+2]){
    p[node]=p[2*node+1];
    s[node]=s[2*node+1]+s[2*node+2];
    tree[node]=max(tree[2*node+1],tree[2*node+2],s[node]);
    z[node]=1;
}
else if(!z[2*node+1] && z[2*node+2]){
    s[node]=s[2*node+2];
    p[node]=p[2*node+1]+p[2*node+2];
    tree[node]=max(tree[2*node+1],tree[2*node+2],p[node]);
    z[node]=1;
}
else{
    p[node]=p[2*node+1];
    s[node]=s[2*node+2];
    tree[node]=max(tree[2*node+1],tree[2*node+2],p[node]+s[node]);
    z[node]=1;
}

}

int main() {
// your code goes here
speedup;
int n,k,q;
cin>>n>>k>>q;
for(int i=0;i<n;i++){
cin>>A[i];
A[i+n]=A[i];
}
string s;
cin>>s;
//buildtree(0,0,n-1);
int shift=0,f=1;
for(int i=0;i<s.length();i++){
if(s[i]==’?’){
if(f){
buildtree(0,n-shift,2*n-1-shift);
f=0;
}
if(tree[0]>k)
cout<<k<<endl;
else
cout<<tree[0]<<endl;
}
else{
f=1;
shift++;
shift=shift%n;
}
}
return 0;
}