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

×

VILTRIBE - Editorial

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:

This question is marked "community wiki".

asked 11 Nov '17, 20:47

melfice's gravatar image

4★melfice
811637
accept rate: 0%

edited 19 Nov '17, 11:23

admin's gravatar image

0★admin ♦♦
19.6k349497539


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

link

answered 05 Dec '17, 21:17

mohan_sai's gravatar image

1★mohan_sai
11
accept rate: 0%

#include <iostream>
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

link

answered 05 Jan, 10:05

shubh5003's gravatar image

0★shubh5003
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); } }

link

answered 06 Jan, 09:28

shivam1423's gravatar image

1★shivam1423
0
accept rate: 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'])
link

answered 09 Mar, 12:12

vipra2018's gravatar image

0★vipra2018
1
accept rate: 0%

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,125
×1,554
×301
×2

question asked: 11 Nov '17, 20:47

question was seen: 1,788 times

last updated: 09 Mar, 12:12