MYSERVE - Editorial

editorial
,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: jeevanjyot
Tester: Harris Leung
Editorialist: hrishik85

DIFFICULTY:

691

PREREQUISITES:

None

PROBLEM:

Alice and Bob are playing a game where every player makes 2 serves with Alice making the initial 2 serves, followed by Bob and so on. On each serve - either Alice or Bob score a point. Given their current scores - P and Q, we have to determine who is currently serving.

EXPLANATION:

Hint 1

Note that on each serve - necessarily Alice or Bob have to score a point. There is no draw / tie. What does this tell us about their scores?

Hint 2

If we write down a sequence of the first 20 serves - can it help us identify the logic for solving this problem?

Hint 3

On each serve - Alice or Bob have to score a point.

Hint 3a

What is the sum of the points scored by Alice and Bob?

Hint 3b

Since each serve was equivalent to a point → it is necessarily true that the total points scored so far are equal to the total serves which have happened so far.
Can you try to solve the problem based on this?

Hint 4

Let’s write down the example of the first 20 serves.

Hint 4a

In the list below, A stands for Alice and B for Bob.
Serves by - [A A B B A A B B A A B B A A B B A A B B]
Total points scored- [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
What do we observe?

Hint 4b

Independent of who scores the points - the serve sequence will always run as per the above. So the total points scored can help us identify who is currently serving. How do we do that?

Hint 5

So now, given P and Q, we know that the number of serves finished is P + Q. Now how do we figure out who the next person to serve is?

Hint 5a

Let’s call the two consecutive serves by the same player as their turn. So in the first turn, Alice serves twice. Then in the next turn, Bob serves twice, etc.

Hint 5b

Can we find out how many turns have been completed?

Hint 5c

That’s right. If there have been S serves, there have been floor(S/2) turns.

Hint 5d

Since turns alternate between Alice and Bob, we just need to look at whether floor(S/2) is even or odd.

Hint 6

Full Solution:

Hint 6a

First we calculate total points score as (P + Q)

Hint 6b

We observe that each person has 2 serves → so the current turn serving is (P + Q) / 2

Hint 6c

Since Alice goes first and Bob goes second, If (P + Q) / 2 is even → then Alice is serving and if (P + Q) / 2 is odd → Bob is serving

TIME COMPLEXITY:

Time complexity is O(1).

SOLUTION:

Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+5;
int n;
ll a[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;
	while(t--){
		int a,b;cin >> a >> b;
		int x=(a+b)%4/2;
		if(x==0) cout << "Alice\n";
		else cout << "Bob\n";
	}
}
Editorialist's Solution 
t=int(input())
for _ in range(t):
    p,q=map(int,input().split())
    total=p+q
    total=total//2
    if total%2==0:
        print("Alice")
    else:
        print("Bob")