WA in DWW19H

Hi,
I’ve written the code correctly and also tested with the sample input, it showed me the correct result. But on submission, it showed me it is wrong.
Can someone explain to me what could be the reason?
here’s my code: https://www.codechef.com/viewsolution/28586237

U have forgotten a case:
If the first letter and last letter of the word in S then if it is concatenated N times then the no. of “SS”(extra) are N-1.
So total there are count(from ur solution)+N-1.

1 Like

Hey,
Consider the case
1
1
SSS
Th answer should be 2 but your code produces the output 0.

1 Like

that is really surprising though i’m working on rectifying the code thanks!

i will consider that, thanks!

   t=int(input())
while(t!=0):
    t=t-1
    n=int(input())
    a=input()
    count=0
    strx=""
    for i in range(n):
        strx+=a
        for i in range(0,len(a)-1):
            if(a[i]=='S'and a[i+1]=='S'):
                count+=1    
    print(count)
    count=0

try this i feel now it should work

This will give only 30 pts as your solution is O(an), which is at worst case O(10^10). Instead of looping through the concatenated string, try to find the answer for the string and account for the case where the last letter and first letter are S.

1 Like

This should give (no of times “SS” occurs in original string)*(n).
If last letter and first letter are “S”,
just add n-1 to the existing answer

1 Like

t=int(input())
while(t!=0):
t=t-1
n=int(input())
a=input()
count=0
strx=""
for i in range(n):
strx+=a
for i in range(0,len(a)-1):
if(a[i]=='S’and a[i+1]==‘S’):
count+=1
if(strx[0] and strx[len(strx)-1]):
count = count + n-1
print(count)

You can remove the first forloop( range(n)). And you dont need strx

Link to my AC submission: https://www.codechef.com/viewsolution/28585477

1 Like

Consider the test case_
SASS

2 Likes

Should it work if we multiply the occurrences (n) to the count of ‘SS’ in the original string?
Because I’ve tried doing that and it showed me WA.

it gave the result as 1
when n=1

Yes thats the approach but u have to consider the case when starting and ending of the string is S and S
Here’s the code :-
int n; cin>>n;
string s; cin>>s;
ll c=0;
for(int i=0;i<s.length()-1;i++)
{
if(s[i]==‘S’ && s[i+1]==‘S’)
{
c++;
}
}
ll pre=c*n;
if(s[0]==‘S’ && s[s.length()-1]==‘S’)
{
pre+=(n-1);
}
cout<<pre<<endl;
}

1 Like

legendary!

You should not use count because if the string is “SSS” the answer expected would be 2 but your answer gives 1. Instead check for every 2-length substring

1 Like

its the exact similar solution of dormordo’s except in C++
Thanks!

@dormordo has mentioned it correctly. Here’s the corresponding Python3 code:

for _ in range(int(input())):
    n = int(input())
    s = input()
    ans = 0
    for i in range(len(s) - 1):
        ans += (s[i] == s[i + 1] and s[i] == 'S')
    ans *= n
    ans += (n - 1) * (s[0] == s[-1] and s[-1] == 'S')
    print(ans)

Hope it helps!

1 Like

thank you so much!