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

×

WSTRING - Editorial

Problem Link:

Practice
Contest

Difficulty:

Easy

Pre-requisites:

Dynamic Programming

Problem:

A W-String is defined as a string consisting of lower-case alphabets, and exactly 3 "#"s that divide the string into 4 non-empty contiguous parts, where each part consists of the same alphabet. Given a string S, find the length of the longest W-String that is a subsequence of S, with the added constraint that the three chosen #-positions in W, are consecutive #-positions in S.

Explanation:

Let us suppose that we choose our three #-positions as P1, P2 and P3. After fixing P1, P2, P3, we greedily choose the most frequent character from [0, P1-1], [P1+1, P2-1], [P2+1, P3-1], [P3+1, N-1]. We further should disregard cases when any one of the above yields an "empty" string.

Let cnt[i][k] = Number of times character k occurs in S[0...i]. Then, given P1, P2, P3, we just need to calculate
max(cnt[P1][k] : 1<=k<=26) (greedy choice of character in [0, P1-1]
+ 1 (# character)
+ max(cnt[P2][k] - cnt[P1][k] : 1<=k<=26) (greedy choice of character in [P1+1, P2-1]
+ 1 (# character)
+ max(cnt[P3][k] - cnt[P2][k] : 1<=k<=26) (greedy choice of character in [P2+1, P3-1]
+ 1 (# character)
+ max(cnt[N-1][k] - cnt[P1][k] : 1<=k<=26) (greedy choice of character in [P3+1, N-1],
for all potential W-Strings (that is, they have all "greedy choice of character" values > 0).

Precomputing values of cnt[i][k] will take time O(N * 26). Further, we can iterate over all consecutive P1,P2,P3 in O(N) time, and each will lead to a calculation of 26 time. Thus overall complexity will be O(N * 26 * T). This can be sped up by a constant factor by precomputing MaxLeft(i) and MaxRight(i) which will find the maximum frequency of a single letter to the left or to the right of position i respectively.

Setter's Solution:

Can be found here

Tester's Solution:

Can be found here

This question is marked "community wiki".

asked 17 Jun '13, 15:33

pragrame's gravatar image

6★pragrame ♦♦
983568379
accept rate: 14%

edited 19 Jun '13, 13:56

admin's gravatar image

0★admin ♦♦
19.8k350498541

3

The setter's and tester's solution links seem to be broken.

(17 Jun '13, 16:16) nihalpi16★
1

@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...

(17 Jun '13, 18:44) unlimited7002★

@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.

(18 Jun '13, 01:38) pragrame ♦♦6★

Adding to @unlimited700 's answer . In Hackerrank , the feature is available , showing for which test case , the solution fails.

(18 Jun '13, 16:27) tutulive3★
1

@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.

(21 Jun '13, 20:29) Shubham283★

For people who are asking why there code was wrong, you have the working codes now. Write code for creating random and heavy test cases and compare the output of your code and working code. It will be very easy to find error in this way rather than asking other people to read your complete code and point out the error.

link

answered 17 Jun '13, 21:48

shashwat001's gravatar image

4★shashwat001
5241610
accept rate: 17%

The Problem Could be made really very nice if you just remove this condition " there must not be any '#' symbols between the positions of the first and the second '#' symbol he chooses, nor between the second and the third ", otherwise the problem is simply a piece of cake.

link

answered 17 Jun '13, 22:13

devuy11's gravatar image

4★devuy11 ♦♦
56273842
accept rate: 0%

4

It would not only become really nice, but also really hard :P Who knows, maybe it'll appear in future as a challenge question!

(18 Jun '13, 01:33) pragrame ♦♦6★

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 :'(

(18 Jun '13, 14:35) devuy11 ♦♦4★
1

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 :)

(19 Jun '13, 01:27) pragrame ♦♦6★

@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.

(20 Jun '13, 03:08) samjay5★

@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.. :):)

link

answered 17 Jun '13, 23:57

parikshit979's gravatar image

3★parikshit979
74127
accept rate: 0%

Thanks :) Its great to have this feedback. I personally am a fan of @anton_lunyov, who has mastered setting, testing, and editorial-writing.

(18 Jun '13, 01:36) pragrame ♦♦6★

plz tell me where i can reduce steps to reduce my time complexity,...

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

link

answered 17 Jun '13, 15:42

tablet007's gravatar image

3★tablet007
11
accept rate: 0%

1

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 :- http://www.codechef.com/viewsolution/2235754

(18 Jun '13, 19:00) v_akshay4★

please tell why am i getting wrong answer..

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

link

answered 17 Jun '13, 16:04

baby_doll's gravatar image

2★baby_doll
1112
accept rate: 0%

Plz explain me why a#b#c#d#e is not a w-string.. it is clear that a#b#c#d is a sub-sequence of a#b#c#d#e and a#b#c#d is a w-string. This shows that a#b#c#d#e is a w-string.. Plz tell the violated condition..

link

answered 17 Jun '13, 16:58

satya8081's gravatar image

2★satya8081
11
accept rate: 0%

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.

(17 Jun '13, 21:29) bhambya2★

@satya8081 >> This was the most common misconception during the contest. a#b#c#d#e is NOT a W string, but a#b#c#d is a W string. The string given by Ryuk need not be a W string, your task was to find out the length of the maximum subsequence of the given string S, such that it is a W string. Please don't get confused. Read the conditions for a string to be a W string, once again, carefully.

link

answered 17 Jun '13, 17:46

bugkiller's gravatar image

3★bugkiller
8.7k194898
accept rate: 9%

that means for test case a#b#c#d#e, answer would be 7(I'm still confused)

(20 Jun '13, 01:24) satya80812★

Yes, why don't you copy someone's AC solution and check for some self-generated tests to avoid your confusion.

(20 Jun '13, 15:46) bugkiller3★

@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.

link

answered 18 Jun '13, 12:41

aravind159's gravatar image

2★aravind159
464
accept rate: 0%

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;
}
link

answered 19 Jun '13, 01:06

abhi231594's gravatar image

4★abhi231594
17651317
accept rate: 11%

edited 19 Jun '13, 01:08

Hey, instead of posting your entire code here you can simply give the link to your solution here.

(21 Jun '13, 20:57) admin ♦♦0★

http://www.codechef.com/viewsolution/2281355 can anyone tell why i am gettin WA :(

link

answered 20 Jun '13, 07:37

iit2011006's gravatar image

2★iit2011006
1
accept rate: 0%

Someone please help me out in figuring why I got WA for this: http://ideone.com/7y3jvr

link

answered 21 Jun '13, 22:34

r20rock's gravatar image

2★r20rock
01
accept rate: 0%

@r20rock the output for this test case

1 uuu#####yyy#yyy#yyy#########uuu

must be 15 whereas your code returns 0. Read the problem statement more carefully.

(21 Jun '13, 23:05) aichemzee4★

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

link

answered 28 Apr '14, 23:51

anantkaushik89's gravatar image

4★anantkaushik89
1116
accept rate: 0%

edited 28 Apr '14, 23:51

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:

×15,852
×3,820
×2,212
×37
×10

question asked: 17 Jun '13, 15:33

question was seen: 5,264 times

last updated: 28 Apr '14, 23:51