You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFADV - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Misha Chorniy
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$ as long as its less than $N$, and keep increasing power by $Y$ as long as 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-

  1. Check if we can reach $N$ for knowledge and $M$ for Power. If yes, print "Chefirnemo" else below.
  2. Check if we can reach $N-1$ for knowledge and $M-1$ for Power. If yes, print "Chefirnemo" else below.
  3. 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.)

Try to frame the conditions in your coding language now. An implementation in C++ is given below for reference :).

View Content

SOLUTION

The respective codes are also pasted in tabs below in case the links do not work. This is for convenience of readers, so that they can copy paste it to whichever IDE or editor they are comfortable reading it in and immediately have access to the codes. :)

Setter

Tester

View Content

Editorialist

View Content

$Time$ $Complexity=O(1)$ per test case
$Space$ $Complexity=O(1)$ per test case

CHEF VIJJU'S CORNER :D

1. Proof that we cannot apply special operation of ShareChat if $N=1$ or $M=1$.

View Content

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. A LOT of you guys made a silly error which got you WA in both the subtasks. It is generally known that $(a-b)\%m=a\%m -b\%m$ if $b\le a$. And we can also write it as $(a-b)\%m=a\%m -b\%m=a\%m -b$ if $b<m$ and $b<a\%m$ . So lot of you guys did $(N-1)\% X ==0\implies N\% X==1$ and similarly for $M$ and $Y$. Ask yourself, is this step correct? Well, it is for $998$ out of $1000$ inputs, but at cases where $X=1$ and/or $Y=1$, this fails miserably, because that case $b \% m= 1 \% 1=0$!! Be very, very careful when doing such manipulations under modulo, and always check if they are allowed or not!

4. 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 :).

asked 07 Sep '18, 01:17

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 18 Sep '18, 12:35

admin's gravatar image

0★admin ♦♦
19.8k350498541


Which testcase did My answer failed

Note I have Reduce N and M by 1; This making mod opreation easier'

Thanks in advance:)

link

answered 18 Sep '18, 20:03

krishyadav007's gravatar image

2★krishyadav007
1047
accept rate: 2%

Just for fun, a Python implementation making use of True == 1 and False = 0:

res = ["Pofik", "Chefirnemo"]
for _ in range(int(input())):
    n,m,x,y  = map(int, input().split())

    if n==1 or m==1:
        print(res[(n%x == 1%x and m%y == 1%y)])
    else:
        print(res[   (n%x == 1%x and m%y == 1%y)
                  or (n%x == 2%x and m%y == 2%y) ])

And it was very kind of the setter to give a public test case in which the use of the "install" option was not viable. :-)

link

answered 19 Sep '18, 02:46

joffan's gravatar image

5★joffan
9488
accept rate: 13%

@krishyayadav007 check for input 4 3 2 1 for this the answer should be Chefirnemo

link

answered 19 Sep '18, 10:32

relaxedrn18's gravatar image

3★relaxedrn18
11
accept rate: 0%

edited 19 Sep '18, 10:33

Thanks ,will improve

(19 Sep '18, 22:37) krishyadav0072★

Can I know on which testcase my code fails ?. Here is my soloution.

I got correct output for subtask#2 but got wrong answer for subtask#1.

link

answered 19 Sep '18, 11:40

dvvr's gravatar image

2★dvvr
112
accept rate: 0%

edited 19 Sep '18, 12:47

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,191
×890
×347
×241
×15
×10

question asked: 07 Sep '18, 01:17

question was seen: 1,076 times

last updated: 19 Sep '18, 22:38