@pragrame ur editorials are awesome… In MAY13 cook-off where almost all problems were of dynamic programming and bitwise operators the explanation given by you were superb. Keep posting us these editorials… :)
1 Like
@pragrame the question was awesome…but most of the people(including me ) got WA at the time 0.00 so please post that test case…so that it will be very useful.
please can ny body suggest how to optimize the code . i m getting TLE
//Data Structure includes
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<string>
#include<ctime>
//Other Includes
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
using namespace std;
#define s(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define sf(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define p(n) printf("%d\n",n)
#define pl(n) printf("%lld\n",n)
#define maX(a,b) ((a)>(b)?(a):(b))
#define miN(a,b) ((a)<(b)?(a):(b))
#define abS(x) ((x)<0?-(x):(x))
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define mp make_pair
#define FF first
#define SS second
#define pb push_back
#define SZ(v) ((int)(v.size()))
#define all(x) x.begin(),x.end()
#define INF (int)1e9
#define LINF (long long)1e18
#define EPS 1e-9
#define MOD ((1 << 30)-1))
#define MSZ 80
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<float,float> PFF;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
int countchar[10001][26];
int check(int left,int right)
{
int max=0;
FOR(j,0,26)
{
if(left==0)
{
if(countchar[right][j]>max)
max=countchar[right][j];
}
else
{
if(countchar[right][j]-countchar[left-1][j]>max)
max=countchar[right][j]-countchar[left-1][j];
}
}
return max;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen ("input.txt", "r", stdin);
//freopen ("output.txt", "w", stdout);
#endif
int t;
s(t);
while(t--)
{
char a[10005];
int b[10005];
ss(a);
int length=strlen(a);
int k=0;
FOR(i,0,length)
{
if(a[i]=='#')
{
b[k++]=i; //count pos of hash
}
}
FOR(i,0,length)
{
FOR(j,0,26)
{
countchar[i][j]=0;
}
}
FOR(i,0,length)
{
if(a[i]!='#')
{
FOR(j,i,length)
countchar[j][a[i]-'a']++; //count char count till index i
}
}
int max=0;
FOR(i,0,k-2)
{
if(i==0 && b[0]==0)
continue;
int p1=check(0,b[i]-1); //returmn count of char having max frequency
int p2=check(b[i]+1,b[i+1]-1);
int p3=check(b[i+1]+1,b[i+2]);
int p4=check(b[i+2]+1,length-1);
if(p1==0 || p2==0 || p3==0 || p4==0)
continue;
if(p1+p2+p3+p4>max)
max=p1+p2+p3+p4;
}
if(max==0)
p(max);
else
p(max+3);
}
return 0;
}
Hi,
Apologies for opening an old thread but i really liked the question and have been trying to get this one. My code is constantly getting WA for this question. I have tried the examples given along with some testcases mentioned in the comments, but their answer is coming fine.
http://www.codechef.com/viewsolution/3799371
Can someone please take a look and give any inputs he may want to share? It would be really helpful for me.
Thanks
The setter’s and tester’s solution links seem to be broken.
4 Likes
@admin why not you show at which case the answer is wrong or exceeding time limit or other case … after the contest is over…
I think this should not have any problem and I believe it will be good for a programmer like me having little bit error many times…and had to think everything in a new way…
1 Like
The sub-sequence that you are talking about (eg. a#b#c#d ) is the W string. Whereas a#b#c#d#e is just a string that contains W strings in it. Which does not make it a W string.
It would not only become really nice, but also really hard 
Who knows, maybe it’ll appear in future as a challenge question!
4 Likes
Thanks Its great to have this feedback. I personally am a fan of @anton_lunyov, who has mastered setting, testing, and editorial-writing.
@nihalpi1, solution links do tend to be broken at the initial point of uploading Editorials. The general aim is to roll out the Editorial as soon as possible after the contest. The Setter and Tester links will work in a day or two.
Actually ,when I read the problem statement for the first time, i do skipped that condition and coded the whole logic but then saw that it was not working for the third case.Wasted about 3 hours :’(
Adding to @unlimited700 's answer . In Hackerrank , the feature is available , showing for which test case , the solution fails.
You are calculating same thing again and again. What you are doing is going through the entire string again and again h number of times where h is the number of “#” so that makes your algo O(hn) where n is length of string in worst cast n = 10000, h=10000 so clearly your code won’t run in the specified time limit. What you could have done is you could have stored the character frequency in each possible range when you were reading the input in O(n). And then calculate the frequency in each possible range in O(26). Here’s my solution :- CodeChef: Practical coding for everyone
1 Like
Third sample case was put there to drive home the condition. If it weren’t there, I expect we’d’ve got a LOT of “Why is my code giving WA” comments during the contest
1 Like
that means for test case a#b#c#d#e, answer would be 7(I’m still confused)
@devuy11 Had the same problem, I even misread it twice, when it appeared to be a lot simpler. Really need to focus more on constraints next time.
@pragrame It sure is harder to find, but my code, which I think would be correct without the constraint, still is pretty short(even shorter than what I submitted with the constraint) and very doable for most of the people who solved this problem by theirselfs I guess.
Yes, why don’t you copy someone’s AC solution and check for some self-generated tests to avoid your confusion.
@unlimited700, @tutulive - Is showing testcases for practice problems helpful or not is highly debatable. Without test cases you are forced to think of boundary conditions/cases which probably you won’t if you see them. It will prove helpful in the long run specially if you practice on SPOJ.
1 Like