STRQ - editorial

What would the approach to solve the given problem had the number of characters be 26?

I tried to use segment tree approach but got TLE :confused:

http://www.codechef.com/viewsolution/6204146
why my this solution was giving WA in contest ?? :frowning:
i checked it for nearly 400 test cases :frowning:

Some one please tell me what’s wrong with my approach.

I took a 2d array and stored the location ( indices ) of each character in the string. Then i took the input of queries and made a binary search and found out the least index at which the character is present in the given range. Then i counted the no. of possibilities. First subtask is accepted but the second and third are resulting in a TLE. Someone please help me in my approach.

http://www.codechef.com/viewsolution/6261829

Thanks in advance

Simply because it’s too much to do for every query. Every query needs to be answered in O(1).

Hello frendz ,

Hope you like this problem.

May be some of you are annoyed due to the strict time limit for this problem but it was intentionally set to forbid the solutions based on data structures or any other slower solutions.

Here is link to my solution for this problem link

4 Likes

my solution gives SIGSEGV for the last sub-task .Please help me in understanding what the problem is.
http://www.codechef.com/viewsolution/6306768

Hey, I got AC in the first 2 subtasks and tle in the 3rd.

(here’s the link : CodeChef: Practical coding for everyone )

Then I switched to scanf instead of cin and ended up getting SIGSEGV for all 3 sub tasks.

(here’s the link for the modified code : CodeChef: Practical coding for everyone )

Been at it since long now. Any help would be appreciated.

Thanks

please add proper category tags to problems of feb15.
It is very helpful for beginners like us.

whats wrong with my code for this question

http://www.codechef.com/viewsolution/6314036

LABOUR! Totally waste of time…!! Not expected from an author like you

please check my sol it is giving correct answer for given test cases but on server it is giving WA…
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
string P;
ll q;
char a,b;
ll *c,*h,*e,*f,*ch,*ce,*cf,*hc,*he,*hf,*ec,*eh,*ef,*fc,*fh,*fe,l,r;

int main()
{
//freopen(“input.txt”,“r”,stdin);
cin>>P;
ll len=P.length();
c=(ll*)malloc(sizeof(ll)(len+1));
h=(ll
)malloc(sizeof(ll)(len+1));
e=(ll
)malloc(sizeof(ll)(len+1));
f=(ll
)malloc(sizeof(ll)*(len+1));
c[0]=h[0]=e[0]=f[0]=0;

ch=(ll*)malloc(sizeof(ll)*(len));
ce=(ll*)malloc(sizeof(ll)*(len));
cf=(ll*)malloc(sizeof(ll)*(len));

hc=(ll*)malloc(sizeof(ll)*(len));
he=(ll*)malloc(sizeof(ll)*(len));
hf=(ll*)malloc(sizeof(ll)*(len));

ec=(ll*)malloc(sizeof(ll)*(len));
eh=(ll*)malloc(sizeof(ll)*(len));
ef=(ll*)malloc(sizeof(ll)*(len));

fc=(ll*)malloc(sizeof(ll)*(len));
fh=(ll*)malloc(sizeof(ll)*(len));
fe=(ll*)malloc(sizeof(ll)*(len));


for(int loop=0;loop<len;loop++)
{
    if(P[loop]=='c')
    {
        c[loop+1]=c[loop]+1;
        h[loop+1]=h[loop];
        e[loop+1]=e[loop];
        f[loop+1]=f[loop];

    }

    else if(P[loop]=='h')
    {
        c[loop+1]=c[loop];
        h[loop+1]=h[loop]+1;
        e[loop+1]=e[loop];
        f[loop+1]=f[loop];

    }
   else if(P[loop]=='e')
    {
        c[loop+1]=c[loop];
        h[loop+1]=h[loop];
        e[loop+1]=e[loop]+1;
        f[loop+1]=f[loop];

    }
    else if(P[loop]=='f')
    {
        c[loop+1]=c[loop];
        h[loop+1]=h[loop];
        e[loop+1]=e[loop];
        f[loop+1]=f[loop]+1;

    }

}

/*for(int check=0;check<=len;check++)
{
    cout<<"C:"<<c[check];
}
cout<<"\n";
for(int check=0;check<=len;check++)
{
    cout<<"H:"<<h[check];
}
cout<<"\n";
for(int check=0;check<=len;check++)
{
    cout<<"E:"<<e[check];
}
cout<<"\n";
for(int check=0;check<=len;check++)
{
    cout<<"F:"<<f[check];
}
cout<<"\n";*/

ch[0]=ce[0]=cf[0]=hc[0]=he[0]=hf[0]=ec[0]=eh[0]=ef[0]=fh[0]=fe[0]=fc[0]=0;
for(int loop=1;loop<len;loop++)
{
ch[loop]=(h[loop+1]-h[loop])*c[loop]+ch[loop-1];
ce[loop]=(e[loop+1]-e[loop])*c[loop]+ce[loop-1];
cf[loop]=(f[loop+1]-f[loop])*c[loop]+cf[loop-1];

        hc[loop]=(c[loop+1]-c[loop])*h[loop]+hc[loop-1];
        he[loop]=(e[loop+1]-e[loop])*h[loop]+he[loop-1];
        hf[loop]=(f[loop+1]-f[loop])*h[loop]+hf[loop-1];

        ec[loop]=(c[loop+1]-c[loop])*e[loop]+ec[loop-1];
        eh[loop]=(h[loop+1]-h[loop])*e[loop]+eh[loop-1];
        ef[loop]=(f[loop+1]-f[loop])*e[loop]+ef[loop-1];

        fc[loop]=(c[loop+1]-c[loop])*f[loop]+fc[loop-1];
        fh[loop]=(h[loop+1]-h[loop])*f[loop]+fh[loop-1];
        fe[loop]=(e[loop+1]-e[loop])*f[loop]+fe[loop-1];

}

/* for(int check=0;check<len;check++)
{
cout<<“CH: “<<ch[check];
}
cout<<”\n”;
for(int check=0;check<len;check++)
{
cout<<“CE: “<<ce[check];
}
cout<<”\n”;
for(int check=0;check<len;check++)
{
cout<<“CF: “<<cf[check];
}
cout<<”\n”;*/
//cout<<"val "<<ec[5]<<endl;
cin>>q;
while(q–)
{
cin>>a>>b;
cin>>l>>r;
if(P[l]==P[r] || l==r)
cout<<“0”<<endl;
else
{
if(a==‘c’&&b==‘f’)
cout<<cf[r-1]-(f[r]*c[l-1])<<endl;

        else if(a=='c'&&b=='e')
        cout<<ce[r-1]-(e[r]*c[l-1])<<endl;

        else if(a=='c'&&b=='h')
        cout<<ch[r-1]-(h[r]*c[l-1])<<endl;

        else if(a=='h'&&b=='c')
        cout<<hc[r-1]-(c[r]*h[l-1])<<endl;

        else if(a=='h'&&b=='e')
        cout<<he[r-1]-(e[r]*h[l-1])<<endl;

        else if(a=='h'&&b=='f')
        cout<<hf[r-1]-(f[r]*h[l-1])<<endl;

        else if(a=='e'&&b=='c')
        cout<<ec[r-1]-(c[r]*e[l-1])<<endl;

        else if(a=='e'&&b=='h')
        cout<<eh[r-1]-(h[r]*e[l-1])<<endl;

        else if(a=='e'&&b=='f')
        cout<<ef[r-1]-(f[r]*e[l-1])<<endl;

        else if(a=='f'&&b=='c')
        cout<<fc[r-1]-(c[r]*f[l-1])<<endl;

        else if(a=='f'&&b=='h')
        cout<<fh[r-1]-(h[r]*f[l-1])<<endl;

        else if(a=='f'&&b=='e')
        cout<<fe[r-1]-(e[r]*f[l-1])<<endl;
    }

}
free(c);free(h);free(e);free(f);free(ch);free(ce);free(cf);
free(hc);free(he);free(hf);free(ec);free(eh);free(ef);free(fc);free(fh);free(fe);

return 0;
}

getting WA for 3rd subtask…please help correct my code :confused:
http://www.codechef.com/viewsolution/7172102

This seems like a great long-challenge problem, and you gave fair warning with the “precalculation” tag.

The difficulty of getting the time down for full solution, gradually extending the precalc overhead, was just frustrating enough to make it interesting, with the benefit of seeing the restricted problem results move in the right direction. I ended up with a set of cumulative-pairs arrays calculated nicely in Python with:

# 1 where each character occurs 
mask = tuple( 
         tuple( int(f == v) for f in full) 
         for v in cx )
# cumulative count of each character
cacc = tuple( 
         tuple(accumulate(mask[v])) 
         for v in cx )
# cumulative number of ordered pairs per ch. pair
pairsacc = tuple(
             tuple(
               tuple(accumulate( map(mul, cacc[v], mask[w]) ))
               for w in cx )
             for v in cx )

and calculation per query as described in the editorial. (accumulate is imported from itertools and mul from operator).

Hey pulkit the problem with your code was that you were initializing the large array of the order of 10^6 inside the main(which is a stack memory) , you should have done it outside the main(in heap memory) this resulted in SIGSEV . Also there was an overflow error which I corrected. Your AC solution
CodeChef: Practical coding for everyone .

1 Like

Will you please elaborate?. If you mean as in this case we have only chef what if we have all 26 characters? than also I think we will move in the same direction. there will be 26*25 array.

Ya but in that case, the amount of memory usage will increase to 262510^6, which I think might give RE (SIGSEGV). Correct me if I am wrong. I just want to know is there a method which is more memory efficient with the similiar time complexity

1 Like

thanks a ton johri21.:slight_smile:

@shivama7 i haven’t read your solution completely but i guess the problem is that you have declared array c (size ~10^6) in main, make it global n check.

@johri21 my


[1] is giving TLE for the last subtask, can you advice me on how to optimize it


  [1]: http://www.codechef.com/viewsolution/6307244