PSHOT - Editorial

akashbhalotia · February 24, 2020, 11:49am

PROBLEM LINK:

Practice
Contest

Author: Jatin Nagpal
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

A penalty shoot-out between two teams, A and B, taking N shots each, alternating in between shots, in which the result of each shot is known. A goes first. Find the earliest shot, after which the result of the shoot-out can be determined, irrespective of the results of the remaining shots.

HINTS:

Not the full solution. Just some hints to help you if you are stuck at some point. As soon as you encounter a hint that you had not thought of, go back to solving the problem.

Hint 1:

There can be three possible results:

A is the winner, or
B is the winner, or
It’s a draw.

Is it possible to determine a drawn state before all the 2*N shots have been taken?

Hint 2:

If A has scored, say, 5 goals after a particular number of shots, and B has scored 2 goals after the same number of shots, and both have, say, 2 shots remaining, is it still possible for B to catch up to and defeat A?

QUICK EXPLANATION:

show

The result of the shoot-out can be known as soon as one of the teams has a score which is greater than - the score of the other team + the number of shots remaining for the other team. If all turns are over without a clear winner, it will be a draw. We can only know be sure of a draw after all 2N shots have been taken.

EXPLANATION

show

Consider the following states in the shoot-out, where:

X is the number of goals scored by A till now,
Y is the number of goals scored by B till now,
LeftA is the number of shots still left for A to take, and
LeftB is the number of shots still left for B to take.
N is the total number of shots to be taken, per team.

State 1:
X > (Y+LeftB)

State 2:
Y > (X+LeftA)

State 3:
X \leq (Y+LeftB) and Y \le (X+LeftA) and total number of shots taken <2*N

State 4:
(LeftA=LeftB=0)

Let’s consider the above states one by one.

In state 1, as X > (Y+LeftB), this implies that X>Y, so A is clearly ahead of B right now. But is it still possible for B to catch up to A and beat it? In the best case scenario for B, A shall miss all their remaining shots, and B shall score in all of them. But since B has only LeftB shots remaining, the maximum score it can achieve is (Y+LeftB), which is < X. Thus, it is not possible to defeat A if such a state is reached.

In state 2, as Y > (X+LeftA), this implies that Y>X, so B is clearly ahead of A right now. But is it still possible for A to catch up to B and beat it? In the best case scenario for A, B shall miss all their remaining shots, and A shall score in all of them. But since A has only LeftA shots remaining, the maximum score it can achieve is (X+LeftA), which is < Y. Thus, it is not possible to defeat B if such a state is reached.

In state 3, irrespective of whether X<Y or Y<X or X=Y, the teams have enough shots left to catch up to or defeat the other team. Thus, we need to wait for the results of more shots, before we can determine who’s going to win the shoot-out.

In state 4, the teams have no more shots left. Thus, we’ll be able to determine the result of the shoot-out, based on their current scores. If, right now, X>Y, then A is the winner, if Y>X, then B is the winner, and if X=Y, then it’s a draw. In every case, we can be sure of the result now, as no more shots are left.

Thus, if the result of the shoot-out is one of the teams winning, it can be known as soon as one of the teams has a score which is greater than : the score of the other team + the number of shots remaining for the other team. This is because the other team won’t be able to catch up with the former team even if it manages to score in all its remaining turns and the former team misses in all its remaining turns.

While, if the result of the shoot-out is a draw, it can only be known after all the 2*N shots have been taken. This is because in a draw, the scores are equal. This implies that if A scored in it’s N^{th} shot, and the score of B was equal to the score of A before A's final shot, we’ll only be sure of the result after B's final shot, i.e., whether it will be able to equalise the score or not. On the other hand, if A misses its final shot, B still has a chance to win the game, if it scores in its final shot.

Thus, to solve the problem:

Iterate through the shots one by one, maintaining X, Y, LeftA and LeftB,
If after any shot, X > (Y+LeftB) or Y > (X+LeftA), we now know that one of the teams can no longer be defeated, irrespective of the results of the remaining shots. Thus, the result of the shoot-out can be known after this shot.
If we couldn’t predict the result even after 2*N-1 shots, we can be sure of it after the 2*N^{th} shot, as no more shots are remaining for either of the teams. Thus, whatever is the score after the 2*N^{th} shot, will be the final result.

SOLUTIONS:

Setter

#include <bits/stdc++.h>
using namespace std;
int si(int a)
{
	if(a==0)
		return 0;
	if(a<0)
		return -1;
	return 1;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("input.doc","r",stdin);
	//freopen("output.doc","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		string s;
		cin>>n>>s;
		int a[2]={0,0};
		int b[2]={n,n};
		int ans=2*n;
		for(int i=0;i<2*n;i++)
		{
			int j=i%2;
			if(s[i]=='1')
			{
				a[j]++;
			}
			b[j]--;
			int sig[2]={si((a[0]+b[0])-(a[1]) ),si( (a[0])-(a[1]+b[1]) )};
			if(sig[0]==sig[1] && sig[0]!=0)
			{
				ans=i+1;
				break;
			}
		}
		cout<<ans<<'\n';
	}
}

Tester

//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#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)a; 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 int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
 
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	//t=1;
	while(t--){
		int n,a=0,b=0,i,rema,remb;
		string s;
		cin>>n;
		cin>>s;
		rema=n;
		remb=n;
		rep(i,s.length()){
			if(s[i]=='1'){
				if(i%2==0){
					a++;
				}
				else{
					b++;
				}
			}
			if(i%2==0){
				rema--;
			}
			else{
				remb--;
			}
			if(a>remb+b){
				cout<<i+1<<endl;
				break;
			}
			if(b>rema+a){
				cout<<i+1<<endl;
				break;
			}
			if(a==b&&remb==0){
				cout<<i+1<<endl;
				break;
			}
		}
 
	}
	return 0;
}

Editorialist

CodeChef: Practical coding for everyone

//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
	public static void main(String[] args) throws IOException
	{
	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

	    int i,N,scA,scB,leftA,leftB;

	    int T=Integer.parseInt(br.readLine().trim());
	    StringBuilder sb=new StringBuilder();

	    while(T-->0)
	    {
	        N=Integer.parseInt(br.readLine().trim());

	        String s[]=br.readLine().trim().split("");
	        int a[]=new int[2*N+1];
	        for(i=0;i<2*N;i++)
	            a[i+1]=Integer.parseInt(s[i]);

	        scA=scB=0; //scores of both the teams
	        leftA=leftB=N; //number of turns left per team

	        for(i=1;i<=2*N;i++) //turns
	        {
	            if(i%2==1)
	            {
	                scA+=a[i];
	                leftA--;
	            }
	            else
	            {
	                scB+=a[i];
	                leftB--;
	            }
	            
	            // Is it no longer possible to beat A?
	            // Is it no longer possible to beat B?
	            // Can no team win now (draw)?
	            if((scA>scB+leftB)||(scB>scA+leftA)||(scA==scB&&i==2*N))
	                break;
	        }
	        sb.append(i).append("\n");
	    }
	    System.out.println(sb);
	}
}

Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions

ritulanand · February 27, 2020, 6:13am

#include
#include
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t–){
int n;
cin>>n;
string s;
cin>>s;
int sa=0, sb=0, c=0;
for(int i=0;i<2n;i++){
if(i%2==0&&s[i]==‘1’){
sa++;
}
if(i%2!=0&&s[i]==‘1’){
sb++;
}
if(i%2!=0&&(sa-sb)>n-i/2-1){
cout<<i+1<<endl;
c++;
break;
}
else if(i%2!=0&&(sb-sa)>n-i/2-1){
cout<<i+1<<endl;
c++;
break;
}
}
if(c==0){
cout<<2n<<endl;
}
}
}
what is wrong in this code?

anon98533376 · March 25, 2020, 6:59pm

Hey,
Can anyone tell me why I am getting a Wrong Answer? Or maybe please tell me any possible corner test cases where my code maybe wrong.
Here is my code::CodeChef: Practical coding for everyone

sarthak_jain29 · May 5, 2020, 4:17am

cook your dish here

try:
t=int(input())
while t>0:
n=int(input())
s=input()
a=0
b=0
ra=n#remaining matches of a
rb=n#remaining matches of b
c=0
for x in range (0,len(s)):
if x%2==0:
if s[x]==‘1’:
a+=1
ra=ra-1;
if(a>b+rb):
print(2n-ra-rb-1)
c=1
break
else:
if s[x]==‘1’:
b+=1
rb=rb-1
if(b>a+ra):
print(2n-ra-rb-1)
c=1
break
if c==0:
print(len(s))
t=t-1
except:
g=0

        whats wrong in this???

anon8804934 · May 24, 2020, 6:45am

    `#include<bits/stdc++.h>
#define itr(i,start,end) for(int i = start;i<end;i++)
#define ll long long

using namespace std;

int main() {
	ll T;
	cin >> T;
	while (T--) {
		ll N;
		cin >> N;
		string score;
		cin >> score;

	ll totalA = 0, totalB = 0;
	ll need = 0;
	ll index = 0;
	bool winner = false;

	for (ll i = 0, j = 1; j < 2 * N; i += 2 , j += 2) {
		if (score[i] == '1')
			totalA++;
		if (score[j] == '1')
			totalB++;

		if (totalA > totalB) {
			need = totalA - totalB;
			if (need > N - ((j + 1) / 2)) {
				index = j + 1;
				winner = true;
				break;
			}
		}
		else if (totalB > totalA) {
			need = totalB - totalA;
			if (need > N - i + 1) {
				index = i + 1;
				winner = true;
				break;
			}
		}
	}

	if (winner) {
		cout << index << endl;
	}
	else {
		cout << 2 * N << endl;
	}
}
return 0; }

`

WHY IS THIS GIVING WA, IS MY LOGIC WRONG??

nishanth271199 · August 26, 2020, 5:03am

in 15th line you forgot to use * in between 2 and n

ssjgz · August 26, 2020, 5:10am

That’s just the forum software messing up their code, which is why everyone should format their code!

sanjayraj_36 · October 23, 2020, 5:21pm

#include <iostream>
using namespace std;

int main()
{
    int T, N;
    char scoreValue[100000];
    cin >> T;
    while (T--)
    {
        cin >> N;
        int inputPointer = 0;
        int shootChances = N;
        int teamAScore = 0, teamBScore = 0, isEqual = 0;
        cin >> scoreValue; // str inserted
        while (shootChances--)
        {
            int isTeamAAhead = 0, isresultDefined = 0;
            teamAScore += scoreValue[inputPointer++] == '1' ? 1 : 0;
            teamBScore += scoreValue[inputPointer++] == '1' ? 1 : 0;
            if (teamAScore == teamBScore)
            {
                isEqual = 1;
            }
            else
            {
                isEqual = 0;
                int diff = 0;
                (teamAScore > teamBScore) ? isTeamAAhead = 1 : isTeamAAhead = 0;
                if (isTeamAAhead)
                {
                    diff = teamAScore - teamBScore;
                }
                else
                {
                    diff = teamBScore - teamAScore;
                }
                if (shootChances < diff)
                {
                    cout << (N - shootChances) * 2 << "\n";
                    break;
                }
            }

            if (isEqual)
            {
                cout << (N - shootChances) * 2 << "\n";
            }
        }
    }
    return 0;
}

`> Blockquote`

Can anyone tell me why I am getting SIGSEGV while submitting ?

saikarthik000 · November 3, 2020, 8:10am

please let me know what I am missing

for t in range(int(input())):
    n=int(input())
    s=input()
    e1=0
    o1=0
    if s[0::2].count("1")==s[1::2].count("1"):
        print(len(s))
    else:
        for i in range(len(s)):
            if i%2==0 and int(s[i])==1:
                e1+=1
            elif i%2==1 and int(s[i])==1:
                o1+=1
            if i%2==0:
                k=0
            else:
                k=1
            #print(i,e1,o1,k,o1+(len(s)//2-(i+k)//2),"even",k)   
            if e1>o1+(len(s)//2-(i+k)//2):
                #print(e1,o1+(len(s)//2-(i+k)//2),"even",k)
                print(i+1)
                break
            elif o1>e1+(len(s)//2-(i+k)//2):
                #print("odd",k)
                print(i+1)
                break

ajai_qmar · May 13, 2021, 4:54pm

HINT : LOOK OUT FOR SPACES.

avnmht1025 · June 2, 2022, 6:33pm

This is my code and i am getting WA. I think there is something wrong with the way i am taking max and min but it seems fine for me… can anyone explain y i am getting this…

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

void Solve(){
    long long n;
    cin>>n;
    string s;
    cin>>s;
    int A=0;
    int B=0;
    for(int i=0;i<2*n;i++){
        if(i%2==0){
            if(s[i]-'0'){
                A++;
            }
        }
        else{
            if(s[i]-'0'){
                B++;
            }
            if((max(A,B)) > min(A,B)+(n-(i+1)/2)){
                cout<<i+1<<endl;
                return;
            }
        }
    }
    cout<<2*n<<endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
	int t;
	cin>>t;
	while(t--){
	    Solve();
	}
	return 0;
}