VILTRIBE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

CAKEWALK

PREREQUISITES:

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:

2

#include<stdio.h>

#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

3

#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

4

#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);
}
}

5

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'])