PROXYC - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Saurabh Yadav

Tester: Radoslav Dimitrov

Editorialist: Teja Vardhan Reddy

DIFFICULTY:

Cakewalk

PREREQUISITES:

Implementation

PROBLEM:

Given a string s made of A and P characters. You can change A into P only if atleast one of the two characters just before it and one of the two characters just after has a P written initially. Now, we want s to have atleast 75% P. What is the minimum number of changes needed to achieve it. (Also we cannot change among first two and last two positions).

EXPLANATION

We will iterate on all A characters which are not among first two and last two positions. And check number of those that can be changed to P. For checking if an A can be changed to P, we iterate over each of the two adjacent characters (two on either side) and see if atleast one of them on each side is P. Lets say x can be changed to P.

Now, lets calculate minimum number needed to be changed to meet the 75% requirement (lets say y). y will be equal to ceil(0.75*n) or (75*n+99)/100 (incase you want to avoid decimals). you can see that the second formula is exactly same as ceil(0.75*n).

Now if y \leq x. we output y otherwise -1.

TIME COMPLEXITY

For checking each A, it takes constant time.

Since, total O(n) positions can be checked. Time complexity is O(n).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
int main()
{
    int t,i,proxy,temp;
    string str;
    double percentage,n,countP;
    cin>>t;
    while(t--)
    {
        cin>>n>>str;
        proxy=0;temp=0;
        countP=count(str.begin(), str.end(), 'P');  
        percentage=((countP)/(n))*100;
        if(percentage>=75)                         
            cout<<proxy<<endl;
        else
        {
            for(i=2;i<n-2;i++)
            {
                if((str[i-1]=='P'||str[i-2]=='P')&&(str[i+2]=='P'||str[i+1]=='P')&&str[i]=='A') 
                {
                    countP++;
                    proxy++;                                 
                    percentage=((countP)/(n))*100;      
                    if(percentage>=75)
                    {
                        temp=1;
                        cout<<proxy<<endl;
                        break;
                    }
                }
            }
            if(temp==0)       
                cout<<-1<<endl;
        }
 
 
    }
    return 0;
}   
Tester's Solution
import sys
 
def read_line():
    return sys.stdin.readline()[:-1]
 
def read_int():
    return int(sys.stdin.readline())
 
def read_int_line():
    return [int(v) for v in sys.stdin.readline().split()]
 
############
# Solution #
 
T = read_int()
for _test in range(T):
    N = read_int()
    S = read_line()
 
    ans = 0
    cnt = 0
    for c in S:
        if c == 'P':
            cnt += 1
 
    for i in range(2, N - 2, 1):
        if cnt < (3 * N / 4) and S[i] == 'A' and (S[i - 1] == 'P' or S[i - 2] == 'P') and (S[i + 1] == 'P' or S[i + 2] == 'P'):
            ans += 1
            cnt += 1
 
    if cnt < (3 * N / 4):
        ans = -1
 
    print(ans)
Editorialist's Solution
 //teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int d;
        cin>>d;
        string s;
        cin>>s;
        int i,cnt=0,gg=0;
        int sz=s.length();
        rep(i,sz){
            if(s[i]=='P')
                cnt++;
        }
        int j,val,good=0;
        val=(75*sz+99)/100;
        f(i,2,sz-2){
            if(cnt>=val)
                break;
            if(s[i]=='P')
                continue;
            good=0;
            f(j,-2,0){
                if(s[i+j]=='P'){
                    
                    good=1;
                    break;
                }
            }
            if(good==0)
                continue;
            good=0;
            rep(j,3){
                if(s[i+j]=='P'){
 
                    good=1;
                    break;
                }
            }
           // cout<<i<<endl;
            if(good){
                cnt++;
                gg++;
            }
            
        }
        if(cnt<val)
            gg=-1;
        cout<<gg<<endl;
    }
    return 0;   
}

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2 Likes

#include <bits/stdc++.h>
using namespace std;

int countpres(string str,int len,int countpre){
for(int i=0;i<len;i++){
if(str[i]==β€˜P’)
countpre++;
}
return countpre;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–){
double len,countpre=0,goodfriend=0;
string str;
cin>>len;
cin.ignore(numeric_limits::max(),’\n’);
getline(cin,str);
string proxy=str;
for(int i=2;i<len-2;i++){
if(str[i]==β€˜A’){
if((str[i-1]==β€˜P’||str[i-2]==β€˜P’) && (str[i+1]==β€˜P’||str[i+2]==β€˜P’)){
proxy[i]=β€˜P’;
goodfriend++;
}
}
}
//cout<<proxy<<’\n’;
double res=countpres(proxy,len,countpre);
//cout<<res<<’\n’;
setprecision(2);
double om=res/len;
//cout<<om<<’\n’;
if(om >= 0.75)
cout<<goodfriend<<’\n’;
else
cout<<"-1"<<’\n’;
}
return 0;
}
Please let me know where I’m wrong

I know its a more roundabout approach.But the code works for all testcases I have generated.However it gives WA on uploading.

import math
import sys
import decimal
decimal.getcontext().prec = 2
T = int(input()) # No. of testcases

def proxydays(s, S):
β€œβ€"
Input: The attendance string and its size
Output: Required no. of days to get 75% attendance
β€œβ€"
act = float(S.count(β€˜P’))/float(s)

if (act < 0.75):
    req = math.ceil((decimal.Decimal(0.75)-decimal.Decimal(act))*s)
    return(req)
else:
    return(0)

def proxymaker(s, A):
β€œβ€"
Input: Att. string, its size, required no. of days
Output: No. of possible proxies
β€œβ€"
p_days = 0
for i in range(2, s-2):
con1 = False
con2 = False
con3 = False
if (A[i] == β€˜A’):
con1 = True
if (A[i-1] == β€˜P’) or (A[i-2] == β€˜P’):
con2 = True
if (A[i+1] == β€˜P’) or (A[i+2] == β€˜P’):
con3 = True
if (con1 and (con2 and con3)):
p_days += 1

return(p_days)

while T:
s = int(input())
S = input()

req_days = proxydays(s, S)
proxy_days = proxymaker(s, S)

if (req_days > 0):
    if (proxy_days >= req_days):
        print(req_days)
    else:
        print("-1")
else:
    print("0")

T -= 1

Can we see failed testcases in codechef? The contest page mentioned it, but I am not able to find any such option.

Try this test case

1
10
APPPPPPPPP

Your code should fail there if I am not wrong

Hint: There is a major bug in Line 28. Focus on that. If you debug it, your code will get accepted most probably. If you can’t find the bug, read the problem statements slowly and carefully there is a catch there, which you are not applying in your code.

1 Like

The output must be zero.My code gives zero.I did try with other accepted solutions, it gives the same output.However I realized the bug is due to inherent nature of floats in python.
Trying this testcase:
1
43
APPAPAAAPPAAPAAAPPAAAPPPAPPPAAPPPPAPAAPAAPA

I get the output 11 but all accepted solutions get it as 12.That is because of the division I carry out in the

def proxydays(s, S):
β€œβ€"
Input: The attendance string and its size
Output: Required no. of days to get 75% attendance
β€œβ€"
act = float(S.count(β€˜P’))/float(s)

if (act < 0.75):
    req = math.ceil((decimal.Decimal(0.75)-decimal.Decimal(act))*s)
    return(req)
else:
    return(0)

The floating point division gives an exact 11but the real value is 11.25.On some other testcases the exact answer of division is 8 but python gives it 8.01 with a precision of 3.The issue should not matter but while using ceiling function it gives wrong answers.
This link tells more.

I still could not find the catch you were referring to because the code worked.Can you please elaborate a bit if possible?

Could anyone help me with this code ? All the test cases are working fine and yet it’s not getting accepted.

#include<stdio.h>

void main() {
int t;
scanf("%d",&t);
while (t = t - 1)
{
int d,proxy = 0,flag = -1;
double att,pre=0.0;
scanf("%d",&d);
char str[1000];
scanf("%s",str);
for(int i = 0; i < d; i++)
if(str[i] == β€˜P’)
pre++;
att = (pre/d)*100;
if(att < 75)
{

        for(int i = 2;i < d-2; i++)
        {
            if((str[i] == 'A') && (str[i-2] == 'P'|| str[i-1]== 'P') && (str[i+1] == 'P'||str[i+2] == 'P'))
                {
                           proxy++;
                           att = ((pre + proxy)/d)*100;
                           if(att >= 75)
                           {
                               flag = 1;
                               printf("%d\n",proxy);
                               break;
                           }
                           else
                                flag = 0;
                }
    }
   }
   else
        printf("0\n");
   if (flag == 0)
        printf("-1\n");
   
}

}

The part where you set flag = 1, its ((float) p/n>=0.75) in place of ((float) p/n>0.75).

Thanks for pointing that out but its still not getting submitted. Although its running fine with some custom inputs.

Need help with below code.
What I am missing

#include <bits/stdc++.h>
using namespace std;

using namespace std;

int NumberPorxy(string attendance, int totalDays) {

int presentDays = count(attendance.begin(), attendance.end(), 'P');
int requiredDays =(int) ceil(totalDays * 0.75);

if (presentDays >= requiredDays) {
	return 0;
}
else{
	return (requiredDays - presentDays);
}	

}

bool CheckProxy(string attendance, int targetProxy) {

int numberProxy = 0;

for (int i = 2;i < (attendance.length() - 2);i++) {
	if (attendance[i] == 'A' &&
		((attendance[i-2] == 'P' || attendance[i-1] == 'P') &&
	     (attendance[i+2] == 'P' || attendance[i+1] == 'P'))) {
			numberProxy++;
			if(numberProxy == targetProxy){
			    return true;
			}
	}
}

return false;
}

int main() {

int testCase,totalDays,proxyDays;
string attString;

cin >> testCase;	

for (int i = 0;i < testCase;i++) {

	cin >> totalDays >> attString;

	proxyDays = NumberPorxy(attString, totalDays);
	if (proxyDays > 0) {
	
		if (CheckProxy(attString, proxyDays)) {
			cout << proxyDays << endl;
		}
		else {
			cout << -1 << endl;
		}
	}
	else {
		cout << proxyDays<<endl;
	}

}

}

#include
using namespace std;

int main() {
float t,d,x=0,b=0;
char a[1000];
cin>>t;
for(int i=0; i<t; i++)
{
cin>>d;
cin>>a;
for(int k=0;k<d;k++)
{
if(a[k]==β€˜P’)
b++;
}
for (int j=2; j<d-2; j++)
{
if(((b+x)/d)<0.75)
{
if(a[j]==β€˜A’||a[j]==β€˜a’)
{
if((a[j-2]==β€˜P’||a[j-1]==β€˜P’)&&(a[j+1]==β€˜P’||a[j+2]==β€˜P’))
x++;
}
}
}
if(((b+x)/d)>=0.75)
cout<<x<<endl;
else
cout<<"-1"<<endl;
x=0;
b=0;
}
return 0;
}

getting wrong answer for this solution
# cook your dish here

t = int(input())
while t :
d = int(input())
s = list(str(input()))
count = 0
countP = s.count(β€˜P’)

flag = 1
percentage = ((countP)/(d))*100;

if percentage >=75 :
print(count)
break

else:
for i in range(2,len(s)-2):
if (s[i] == β€˜A’) and ((s[i-2] == β€˜P’ or s[i-2] == β€˜p’) and (s[i+2] == β€˜P’ or s[i+2] == β€˜P’)):
countP =countP +1
count = count+1
percentage = ((countP)/d)*100

      if percentage >=75 :
        print(count)
        flag = 0 
        break
   
  elif not flag:
    print(-1)
    break

t-=1

Thanks for the Editorial

really ? python without indentation
why didn’t you give your submission link instead

1 Like

Why in the editorialist’s solution has he included <vector> and <set> etc again after including <bits/stdc++.h>?

Please help me with this.Below is my solution. Getting WA :frowning:
package com.company;

import java.util.;
import java.io.
;

public class Main {

public static void main(String[] args) {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    try {
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String s = br.readLine();
            int count = 0;
            int p=0;
            int ans=0;
            int m = (int) Math.ceil(n * 0.75);
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == 'P')
                    count++;
            }
            if(count<m) {
                for (int i = 2; i < n - 2; i++) {
                    if (s.charAt(i) == 'A') {
                        if (s.charAt(i - 1) == 'P' || s.charAt(i - 2) == 'P') {
                            if (s.charAt(i + 1) == 'P' || s.charAt(i + 2) == 'P')
                                p++;
                        }
                    }
                }

                if (p+count < m)
                    ans = -1;
                else
                    ans = m-count;
            }
            System.out.print(ans);
        }

    }
    catch(Exception e){}
}

}

I was trying to tell you the part in which you were marking all the days which are proxy also present. So that could lead to a major confusion as you needed Chef to be really present and not by proxy on either day[i - 2] or day[i - 1] and day[i + 1] or day[i + 2]. I guess I was pointing out the correct mistake because it seems that you have edited your code above. :slight_smile:

where is the problem…anyone please help me

#include<bits/stdc++.h>
using namespace std;
int main(){
int t,j;
cin>>t;
for(j=0;j<t;j++){
int i,c=0,k=0;
float m,d;
cin>>d;
string a;
cin>>a;
for(i=2;i<d-2;i++){
if(a[i]==β€˜A’&&((a[i+1]==β€˜P’||a[i+2]==β€˜P’)&&(a[i-1]==β€˜P’||a[i-2]==β€˜P’))){
c++;
}
}
for(i=0;i<d;i++){
if(a[i]==β€˜P’)k++;
}
m=(d*75)/100;

m=ceil(m);

if(m-k<=c&&c!=0){cout<<m-k<<endl;}
else if(m-k<=0){cout<<0<<endl;}
else{cout<<-1<<endl;}

}
}

Can u find what is wrong in this.this code passed the time limit also.
thanks in advance.
#include
using namespace std;

int main() {
int T;
cin>>T;
for(int i=0;i<T;i++)
{ int D;
cin>>D;
char S[1000];int ct,prox_avail;//ct is the total number of days he originally is present
ct=0;prox_avail=0;//no. of proxy we can make to the maximum
for(int d=0;d<D;d++)
{ cin>>S[d];
if(S[d]==β€˜P’)
ct++;}
for(int d=2;d<D-2;d++)
if((S[d]==β€˜A’)&&(S[d-1]==β€˜P’||S[d-2]==β€˜P’)&&(S[d+1]==β€˜P’||S[d+2]==β€˜P’))
prox_avail++;
int req;//req is the required number of days to be present for 75%
if(D%4==0)
req=D*(0.75);
else
req=((req*3)/4)+1;
if(req<prox_avail)
cout<<req;
else
cout<<"-1";
}
return 0;
}

your code is giving wrong answer on this test case:

1
1
P

Answer should be 0 but code gives -1. Attendance is already 100% so minimum proxy required is 0.

Check this test case

1
12
PPAPPPAPPPPP

Your answer is -1, but the correct answer is 0. To be honest, I think that there is an error in planning the code because a single line didn’t have the bug, but there were a cluster of them.

From the next time please give us the link of your solution. The other coders have a tough time scrolling up and down. It would be a great benefit for the Codechef community as a whole.

Try it out again with a cool head and you will surely get AC. :slight_smile: