×

# VILTRIBE - Editorial

Author: Praveen Dhinwa
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov

CAKEWALK

None

# PROBLEM:

Given a string consisting of symbols ., A and B, count the number of symbols which are either A, or are . (dots) and next and previous non-dot symbols in the string are A. Also, calculate this count with respect to symbols B.

# QUICK EXPLANATION:

Consider the characters one-by-one, maintain last non-dot symbol $last$_$symbol$ and the number of dots $num$_$dots$ since the last character. Whenever the current symbol is non-dot and is the same as last, add the number of dots since the last symbol.

# EXPLANATION:

Consider one of the symbols to calculate the answer for, for example, A. Which symbols contribute to the answer? First, of course, all occurrences of A in the string give a $+1$. However, we are also interested in dots that are preceded and followed by A-s (when considering non-dot symbols). Let's consider a block of consecutive dots; clearly, they either all contribute $+1$ to answer if they are surrounded by A-s, or give nothing. When we iterate over the characters from left to right, we can maintain how many symbols are there in the current block of consecutive dots, and which symbol preceded it. We can actually find answers for A and B in a single pass. Whenever we meet a dot, we increment the counter of consecutive dots ($num$_$dots$). Whenever a non-dot symbol is met, we check whether the symbol that preceded block of dots is the same as current. If so, we add $num$_$dots$ to the answer. We also reset the counter in this case.

The solution works in $O(|s|)$ time (we only consider each character once) and requires $O(1)$ additional memory (apart from the $O(|s|)$ memory to store the input string) because we only use the constant amount of variables.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.
Editorialist's solution can be found here.

# RELATED PROBLEMS:

This question is marked "community wiki".

4★melfice
811637
accept rate: 0%

19.6k349497539

# include<string.h>

int main()

{

int count,counta,countb,i,t;

char str[100000],lastc='0';

scanf("%d",&t);
while(t)
{
counta=countb=count=0;
scanf("%s",str);
for(i=0 ; i<strlen(str) ; i++)
{
if(str[i]=='.')
{
count++;
if(lastc=='0')
lastc=str[i];
}
if(str[i]=='A')
{
counta=counta+1;
if(lastc==str[i] || lastc=='0')
{
counta=counta+count;
}
lastc=str[i];
count=0;
}
if(str[i]=='B')
{
countb=countb+1;
if(lastc==str[i] || lastc=='0')
{
countb=countb+count;
}
lastc=str[i];
count=0;
}
}
printf("%d   %d\n",counta,countb);
--t;
}


return 0;

can you tell where my program is failing?

This program giving correct answers but after submission it showing the wrong answer

11
accept rate: 0%

 0 #include using namespace std; int work(char x, string s){ int a=0, first[4]={0,0,0,0}; for (int i = 0; i < s.length(); i++) { if(s[i] == x){ first[a]=i; a+=1; } } int diff = first[a-1]-first[0]; if(a>0) return diff+1; else return a; } int main() { int t; std::cin >> t; while(t--){ string s; std::cin >> s; cout<< work('A',s)<< " "; cout<< work('B',s)<< " "; std::cout << endl; } return 0; }  This program giving correct answers but after submission it showing the wrong answer answered 05 Jan, 10:05 1 accept rate: 0%

# include<stdio.h>

void main() { char a[100001]; long int i,c,k,l,m,j,t,n; scanf("%ld\n",&t); while(t--) { c=0; k=0; n=0; for (i=0;;i++) { scanf("%c",&a[i]); if(a[i]=='\n') break; n++; } for (i=0;i<n;i++) { if(a[i]=='A') c++; if(a[i]=='B') k++; if(a[i]=='.') {j=i-1; l=0; for(m=i;;m++) { if(a[m]!='.') break; l++; } if(a[j]=='A'&&a[m]=='A') c=c+l; if(a[j]=='B'&&a[m]=='B') k=k+l; i=m-1;} } printf("\n%ld %ld",c,k); } }

0
accept rate: 0%

 0 I tried the below code and I was able to get the correct answer. BUT, it did not get submitted and mentioned as wrong answer. Please help here. testCaseCount = eval(input()) dict = {} dict['A'] = 0 dict['B'] = 0 emptyCount = 0 previous = "" str = [] str1 = "" if(testCaseCount <= 20): for val1 in range(0,testCaseCount): str1 = input() if(len(str1) <= 1000): str.append(str1) for newVal in str: dict['A'] = 0 dict['B'] = 0 emptyCount = 0 for val in newVal: if(val == 'A'): if(previous == 'A'): dict['A'] = dict['A'] + emptyCount dict['A'] = dict['A'] + 1 previous = 'A' emptyCount = 0 if(val == 'B'): if(previous == 'B'): dict['B'] = dict['B'] + emptyCount dict['B'] = dict['B'] + 1 previous = 'B' emptyCount = 0 if(val == '.'): if(previous == 'A'): emptyCount = emptyCount + 1 if(previous == 'B'): emptyCount = emptyCount + 1 print(dict['A'] ,dict['B'])  answered 09 Mar, 12:12 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,125
×1,554
×301
×2

question asked: 11 Nov '17, 20:47

question was seen: 1,788 times

last updated: 09 Mar, 12:12