PROBLEM LINK:
Div1
Div2
Practice
Setter- Meesha Chorniiee
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey
DIFFICULTY:
CAKEWALK/SIMPLE
PRE-REQUISITES:
Modulo Operator (%), Basic Maths of Addition, Logic
PROBLEM:
Let me denote knowledge by A and power by B. Now, as given in the question, we initially have A=1 and B=1. Tell if its possible for you to reach A=N AND B=M using following operations-
- Increase A by X
- Increase B by Y
- Increase A and B by 1. We can only do it once.
QUICK-EXPLANATION:
Key to AC- Modulo along with careful checking for corner case (N=1 or M=1) fetched AC in first try.
The problem clearly asks if you can find two integers k and l such that either (1+X*k=N \&\& 1+Y*l=M) OR (1+X*k=N-1 \&\& 1+Y*l=M-1). Move the 1 in LHS to RHS to get equations in form (X*k=N-1 \&\& Y*l=M-1) OR (X*k=N-2 \&\& Y*l=M-2). Lets consider one equation for example, say X*k=N-1. Clearly, LHS can move only in steps of X. This means, X*k can never be equal to N-1 (for all possible integers k) if N-1 is not a multiple of X, or in other words, if N-1 is not divisible by X. Similar analogy holds in other 3 equations.
EXPLANATION:
The problem is quite simple, hence we will have only a single section in editorial. We will discuss editorialist’s solution in those. I might sound over-explanative in the explanation below, and perhaps you may ask “Why is he now considering case only for Knowledge and not considering Power right now?” &etc. I want you, the reader, to patiently read it. I have tried to picture the thought process which should be on your mind when typically solving such easy problems, so please try to grasp it if possible. 
Editorialist’s Solution-
For sake of formality, lets discuss the first subtask’s solution first. We can brute force for task 1. The idea is, keep increasing Knowledge by X till its less than N, and keep increasing power by Y if its less than M. At last, check if Knowledge==N \&\& Power==M. If not, subtract X from Knowledge and Y from Power and check Knowledge==N-1 \&\& Power==M-1.
The above fails, or gets time limit exceeded, if number of steps for Knowledge and Power to reach N and M are large.
For the full solution, first ask yourself what exactly do we have to check?
Let me denote knowledge by A and power by B. Now, we initially start with A=1, B=1 and have to see if we can reach A=N, B=M. At each step, we can add X to A, Y to B, or use the special operation 1 to both A and B . The special operation can be done only once.
Think on the special operation. It increases A and B by 1. When will it exactly be useful to us? It can help us reach A=N and B=M if, and only if we can reach A=N-1 and B=M-1 first. If we reach there, then we can use this special operation to reach A=N and B=M (Recall that it will increase A and B both by 1).
Now the problem reduces to, checking if we can reach (A=N \&\& B=M) OR (A=N-1 \&\& B=M-1) by moving in steps of X (for A) and Y (for B). Lets talk about A for now, the exact same thing will be later applied to B.
We initially have A=1, we can increase it in steps of X in normal operations. Say, I apply the operation k times, then my A will be -
A=1+X*k
Forget about everything else now. Just see that we have A=1+X*k, and we have to reach an integer N. When will it be possible? We see that we need-
1+X*k=N
\implies X*k=N-1
Stop there. See the LHS, i.e. X*k. k must be an integer, as number of operations is a whole number. Hence, this means LHS will always be a multiple of X. Also, since k can be any whole number, we can see that, LHS can reach any multiple of X. But can we reach numbers which are not multiples of X? No! Because if we could, then it will contradict the fact that k is a whole number (and not a fraction r decimal).
This means, all we need to check is to see if N-1 is a multiple of X or not! If it is, we can reach it, if its not, then we cannot reach it. And since we used no special property (i.e. no property which was only available only to A and is not available to B), we can repeat the above steps and arrive at Y*l=M-1, where l is number of times operation is done. Then, using arguments above, we conclude we can reach M iff and only if M-1 is divisible by Y!
Now lets bring the special operation into the picture. So far, we know how to check if we can reach a given number N or M from A=1 and B=1. What change does the special operation bring? See above, it just has the effect of "If I can reach N-1 and M-1, I can then use special operation to reach N and M"
Hence, our conditions reduce to checking-
- Check if we can reach N for knowledge and M for Power. If yes, print “Chefirnemo” else below.
- Check if we can reach N-1 for knowledge and M-1 for Power. If yes, print “Chefirnemo” else below.
- Conclude that we cannot reach A=N for knowledge and B=M for power. Wail out loud, cry, bang your head on wall and sobbingly print “Pofik”
The main aim of this editorial was not to merely explain solution of the problem, but to plant the thought-process which should go on your mind, as these are the common techniques, methods and tricks which will ultimately help you ace out as a programmer.
On a side note, beware of the corner case N=1 or M=1. We can prove that special operation cannot be used if N=1 or M=1. (Proof in bonus section.)
SOLUTION
Setter
Tester
Click to view
/*
*
********************************************************************************************
* AUTHOR : Vijju123 *
* Language: C++14 *
* Purpose: - *
* IDE used: Codechef IDE. *
********************************************************************************************
*
Comments will be included in practice problems if it helps ^^
*/
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int mod=pow(10,9)+7;
int fastExpo(long long a,long long n, int mod)
{
a%=mod;
if(n==2)return a*a%mod;
if(n==1)return a;
if(n&1)return a*fastExpo(fastExpo(a,n>>1,mod),2,mod)%mod;
else return fastExpo(fastExpo(a,n>>1,mod),2,mod);
}
inline void add(vector<vector<int> > &a,vector<vector<int> > &b,int mod)
{
for(int i=0;i<a.size();i++)for(int j=0;j<a[0].size();j++)b[i][j]=(b[i][j]+a[i][j])%mod;
}
void multiply(vector<vector<int> > &a, vector<vector<int> > &b,int mod,vector<vector<int> > &temp)
{
assert(a[0].size()==b.size());
int i,j;
for(i=0;i<a.size();i++)
{
for(j=0;j<b[0].size();j++)
{
temp[i][j]=0;
for(int p=0;p<a[0].size();p++)
{
temp[i][j]=(temp[i][j]+1LL*a[i][p]*b[p][j])%mod;
}
}
}
}
void MatExpo(vector<vector<int> > &arr,int power,int mod)
{
int i,j,k;
vector<vector<int> >temp,temp2,temp3;
vector<int> init(arr[0].size());
for(i=0;i<arr.size();i++){temp.push_back(init);}
temp3=temp;
temp2=temp;
for(i=0;i<arr.size();i++)temp3[i][i]=1;
while(power>0)
{
if(power&1)
{
multiply(arr,temp3,mod,temp);
swap(temp3,temp);
}
multiply(arr,arr,mod,temp2);
swap(arr,temp2);
power>>=1;
}
swap(arr,temp3);
}
vector<int> primes;
int isComposite[1000001]={1,1};
void sieve()
{
int i,j;
for(i=2;i<=1000000;i++)
{
if(!isComposite[i])
{
primes.push_back(i);
isComposite[i]=i;
}
for(j=0;j<primes.size() and i*primes[j]<=1000000;j++)
{
isComposite[primes[j]*i]=i;
if(i%primes[j]==0)break;
}
}
}
int main() {
// your code goes here
#ifdef JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
srand(time(NULL));
int t;
cin>>t;
assert(1<=t and t<=1000);
while(t--)
{
int n,m,x,y;
cin>>n>>m>>x>>y;
assert(1<=n and n<=1000000000);
assert(1<=m and m<=1000000000);
assert(1<=x and x<=1000000000);
assert(1<=y and y<=1000000000);
n--;
m--;
if(n%x==0 and m%y==0)cout<<"Chefirnemo\n";
else if((n-1)%x==0 and (m-1)%y==0 and min(n,m)>0)cout<<"Chefirnemo\n";
else cout<<"Pofik\n";
}
return 0;
}
Time Complexity=O(1) per test case
Space Complexity=O(1) per test case
CHEF VIJJU’S CORNER 
1. Proof that we cannot apply special operation of ShareChat if N=1 or M=1.
Click to view
The operation will increase BOTH N and M by 1. Once a value is increased, then it cannot be decreased by our operations!! In other words, say N=1 and we use special operation, then N will become 2 and can never be made equal to 1!! Similar argument holds for M as well.
2. Solve the below 2 questions based on variants of - “Say, instead of special operation increasing A and B by 1, it did following-”
- Increase EITHER A OR B.
- Increase A and B by k instead of 1 (k can be negative)
- Is same as that in question, but can be use as many times as possible
3. Related Problems-
- GIVCANDY - This problem is at least 2 levels higher than our current problem. Make sure to read about Berzout’s Identity and GCD before attempting :).