AOC02-Editorial

editorial
,
1

PROBLEM LINK:

Problem link

Author: hareesh29

DIFFICULTY:

EASY

PREREQUISITES:

Binary search

PROBLEM:

GIven a string of length n. where the first k elements are “R” and the next n-k elements are “B”. we have to print Alice wins if(k>n-k) else print Bob wins

EXPLANATION:

This is a classic binary search problem. The idea is to find the value of k using a modified binary search.

pseudo code of modified binary search binary search

while(s[first]=="R" and s[last]=="B"):
        mid=(first+last)//2
        if(s[mid]=="R"):
             f=mid+1
        elif(s[mid]=="B"):
          l=mid-1
        
if(s[first]=="B"):
    nr=first
    nb=n-first
elif(s[last]=="R"):
    nr=last+1
    nb=n-nr

Explanation:

Initially first=0 and last=n-1 and mid=(first+last)/2. Here logic is to find value of mid such that s[mid] is R and s[mid+1] =B or s[mid] is B and s[mid-1] is R.In the first case k=mid+1 and in the second case k=mid.now we have to just compare k and n-k.if k is greater than n-k then Alice wins else Bob wins .

TIME COMPLEXITY

O(log(n))

SOLUTIONS:

Setter's Solution 
for _ in range(int(input())):
    n=int(input())
    s=input()
    f=0
    l=n-1
    while(s[f]=="R" and s[l]=="B"):
        mid=(f+l)//2
        if(s[mid]=="R"):
          f=mid+1
        elif(s[mid]=="B"):
          l=mid-1
        
    if(s[f]=="B"):
        nr=f
        nb=n-f
    elif(s[l]=="R"):
        nr=l+1
        nb=n-nr
    if(nr>nb):
        print("Alice wins")
    else:
       print("Bob wins")
2

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
string s;
int n,i,m,flag=0;
cin>>n;
cin>>s;
//cout<<s<<endl;
if(n%2!=0)
{
if(s[n/2]==‘B’)
{
cout<<“Bob wins”<<endl;

        }else
        {
            cout<<"Alice wins"<<endl;
        }
    }else
    {
        if((s[n/2]!=s[(n/2)-1] )|| (s[n/2]=='B'))
        {
            cout<<"Bob wins"<<endl;}
        else
            {
                cout<<"Alice wins"<<endl;
            }
        }
    
   
}
return 0;

}

time complexity is O(1) still showing time limit exceeded why?

4

I wrote a slightly shortened version and was able to submit it successfully. I’m not sure what the error is with your code though.

1 Like
5

https://www.codechef.com/viewsolution/39191826
O(1) solution

1 Like