EOEO - Editorial

PROBLEM LINK:

Contest Link

Author: Sahil Chimnani
Tester: Felipe Mota
Editorialist: Rajarshi Basu

DIFFICULTY:

Easy

PREREQUISITES:

Implementation, logic, simple math

PROBLEM:

We have two players who have values JS and TS. We keep dividing them by 2. If at any point one is even and the other is odd, the player corresponding to the even value wins. If both are even, we continue dividing by 2. If both are odd, it’s a tie.
Given player 2’s value, TS \leq 10^{18} find number of JS \leq TS for player 1, such that player 1 wins.

QUICK EXPLANATION:

Let i be the greatest integer such that 2^i | TS.
ANS = \left \lfloor{\frac{x}{2^{i+1}}}\right \rfloor

EXPLANATION:

Subtask 1

For each testcase, iterate over all JS \leq TS and simulate the process.

Subtask 2

Observation 1

Any number x can be written as x = 2^{k}*y where 2^k is the highest power of 2 dividing x.

Implication?

y must be odd


Observation 2

if 2^k is the highest power of 2 that divides TS then 2^{k+1} must be the minimum power of 2 that divides JS, else player 2 won’t win.

Just to be clear ...

It does not imply that if JS = 2^{k+1}*y then y is odd. y can be a multiple of 2 as well.


Full Solution

Find 2^k such that k is the highest power of 2 which divides TS. Divide TS by 2^{k+1} and take the floor. Let that be z. z is the number of possible values of JS.
Relating to the above expressions, we can say that JS = 2^{k+1}*y, and the value of y can be 1,2,3 \dots z such that 2^{k+1}*(z+1) > TS. This is the precise z that we are getting, hence the answer is z. (Since all values from 1 \dots z are possible, hence there are exactly z values.)

Time Complexity

Since we have to find the maximum 2^i, our time complexity is O(log(TS)) per test case.

QUICK REMINDERS:

long long int is good for your health.

SOLUTIONS:

Setter's Code
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define db long double
#define pb push_back
#define all(a)                      a.begin(), a.end()
#define mod 1000000007
#define out cout<<
#define in cin>>
#define w(param) out #param<<" is : "<<param<<"\n"
#define fi first
#define sec second
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vdb vector<db>
#define vbool vector<bool>
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define pll pair<long long,long long>
#define plll pair<long long,pair<long long,long long>>
#define maxn 100005
#define invv(v,from,to) for(int i=from;i<=to;i++) \
						in v[i];
#define inv(v) for(int i=0;i<v.size();i++) \
				in v[i];
#define printv(v) out #v<<" is :\n"; \
			for(int i=0;i<v.size();i++) \
				out " "<<v[i];\
				nl;
#define printvv(v,from,to) out #v<<" is :\n"; \
			for(int i=from;i<=to;i++) \
				out " "<<v[i];\
				nl;
#define inmax INT_MAX
#define llmax LONG_LONG_MAX
#define nl out "\n"
#define nll out "\n\n"
#define pdd pair<double,double>
using namespace std;
 
ll g(ll p){
	while(p%2 == 0){
		p /= 2;
	}
	p /= 2;
	return p;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll q;
	in q;
	
	while(q--){
		ll ts;
		in ts;
		out g(ts) << "\n";
	}
	
	nl;
	return 0;
}
Tester's Code
q = int(raw_input())
while q > 0:
    ts = int(raw_input())
    while ts % 2 == 0:
        ts /= 2
    print ts / 2
    q -= 1 

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

3 Likes

I am unable to find my mistake can someone help me
https://www.codechef.com/viewsolution/33707795
https://www.codechef.com/viewsolution/34366710
These are the two solutions I submitted I got partially correct in both of them

1 Like

Video Explanation>>>

1 Like

your Subtask 2 is getting WA, i suppose?

:+1: :+1:

n / ((n & -n) << 1) //n: tom's strength

:grin:

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

int main() {
    int t;
    cin >> t;
    while(t--){
        long long n;
        cin >> n;
        while(n%2==0){
            n/=2;
        }
        cout << n/2  << '\n';
    }
}
5 Likes

https://codingallinone.blogspot.com/

check this solution, this solution has unique implementation and thinking you definitely going to learn something

June long challenge editorial beginner friendly video explanation with animation and code

Delicious cake (CONTAIN) : https://youtu.be/tXD2yEVA0pM
Tom and jerry (EOEO) : https://youtu.be/ZWI5n0Ogir0
Even matrix (EVENM) : https://youtu.be/KA8WoO7jCg8

yes

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

int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
    long long int a;
    cin>>a;
    if(a%2==1)
    {
        cout<<(a-1)/2<<"\n";
    }
    else
    {
        long long int ans =a;
        long long int x=0;
        while(a%2==0)
        {
            x++;
            a=a/2;
        }
        long long int y = pow(2,x+1);
        cout<<(int)ans/y<<"\n";
    }
    
}

}

whats wrong with my code seems like i have done it like editorial during contest time only subtask 1 passed subtask 2 failed… please explain someone

Hi!
After reading your solution I got to know that I misunderstood the question, however even after reading the question now once again I still can’t seem to find why my understanding is wrong. Please guide me where I went wrong with respect to the question statement.

Here’s my pseudo code:

  • START

  • Input test case, and for each test case repeat the following process:

  • Input TS

  • If TS is odd, answer is TS//2

  • If TS is even, JS can have all the even values from 2 to TS, for each combination of TS and JS do the following:

      - Divide both TS and JS by 2 till one of them becomes odd, 
      - If TS becomes odd first then increment a counter (ctr ++) 
      - If JS becomes odd first then do nothing.
    
  • Print ctr

  • END

Thanks in advance!

so stupid of me. i did typecasted to int , didnt have to do any typecasting
it should have been long long

One line code

1 Like

This Question Gave me AC in the first attempt, i was surprised chef and ice cream was kept before this question

1 Like

I know I am doing a stupid mistake or something but I am unable to find it so can someone help me.

I am only getting a partial.

t = int(input())

for i in range (0 , t):
ts = int(input())
temp = ts
count = 0
while ts % 2 != 1:
ts = ts / 2
count = count + 1
m = 2 ** (count + 1)
print(int(temp/m))

please format your code from now on
Also, read the question carefully…divide TS by 2 till it is odd and JS can have all values such that JS divided by same number (2**n) will be even

copy pasted from vscode it looks formatted there used preformatted text here several times in edit didnt work… how to format it correctly?
UPD: done formatting

I figured it and did it like this, look like a noob’s solution but go correct answer :slight_smile:
Let,
N = number of JS choices leading Jerry to win,

Start
TS = 20
JS = 2 4 6 8 10 12 14 16 18 20 - excluding odd nums leading to loss

proceed to next turn with above JS
divide TS by 2 and all Possible JS choices by 2

TS/2 = 10
JS/2 = 1 2 3 4 5 6 7 8 9 10
Valid JS = 2 4 6 8 10 - excluding odd nums leading to loss(N=N/2)

proceed to next turn with above JS
divide TS by 2 and all Possible JS choices by 2
TS/2 = 5
JS/2 = 1 2 3 4 5
Winning entries = 2 4 (from choices 6 and 8) (N = (N-1)/2)
// for last turn we do (N-1)/2 instead of N/2 due to inclusion of TS as upper bound in choice of JS

Code:-

count =(found by counting trailing 0’s in TS’s binary rep)
ie How many times I have to divide this number to get an odd num so jerry wins with an even num on that turn

long possibleJSChoices =(TS)/2;//all even nums between 1 and TS so that game proceeds
long N = possibleJSChoices
for(int i = 0 ; i < count;i++)
{
if(i==count-1)
N = (N-1)/2;
else
N = (N)/2;
}
System.out.println(""+N);

1 Like

I had an approach on similar lines.

  1. Dividing TS till an odd number is reached and counting the number of divisions (count).
  2. In order for JS to win, the smallest such number will have to be divided the same number of times till even. (Resulting in TS being odd and JS being even, so JS wins - first such occurrence)
  3. Smallest such number will therefore be 2^(count +1)
    Winning numbers will be a list of multiples of this smallest number and less than TS.
#include <iostream>
#include <cmath>
using namespace std;

int main() 
{ 
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    long long int T, TS, result, ts, count, divisor, i;
    cin >> T; 
    for (i = 0;i<T;i++){
        cin >> TS;
        if (TS % 2 != 0){
            result = TS/2;
            cout << result<<'\n';
        }
        else{
            ts = TS;
            count = 0;
            while (ts % 2 == 0){
                ts = ts/2;
                count ++;
            }
            count++;
            divisor = pow(2,count);
            result = TS/divisor;
            cout << result<<'\n';
        }
    }
}