AFK - Editorial

ad-hoc
afk
easy
editorial
ltime58
maths

#1

PROBLEM LINK:

Div1, Div2
Practice

Author: Misha Chorniy
Tester: Lewin Gan
Editorialist: Adarsh Kumar

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You are given three integers $A$,$B$ and $C$. You need to find the minimum no. of operations required to make the sequence $A$,$B$,$C$ an arithmetic progression. In one operation you can choose one of the numbers $A$,$B$,$C$ and either add $1$ to it or subtract $-1$ from it.

EXPLANATION:

For $A$,$B$,$C$ to be in arithmetic progression, they must satisfy $2B = A+C$. We need to make both side of the expression equal. Observe that in right hand side, you need to do the same type of operation on $A$,$C$. You can't add $1$ on $A$ and subtract $-1$ from $C$ because it will only increase the number of operations. Observe that left hand side of the expression can be increased by $2$ or reduced by $2$ in one operation. Hence, in order to minimize the number of operation we must first operate on left hand side and try to make the equation as balance as possible.

The only case in which we can not make the equation balance by operating on left hand side is when right hand side is odd. In this case we can either add 1 or subtract 1 from right hand side and try to find the minimum operation which results from both the cases. A pseudo-code to illustrate this:

def g(B,sum):
  return abs(B-sum/2)  

def f(A,B,C):
  if (A+C)%2 != 0:
    return min(g(B,A+C-1),g(B,A+C+1))
  else:
    return g(B,A+C)

Function g(B,sum) here tries to find minimum number of operation required to balance the expression 2.B = sum, where changes can only be done in left hand side. Say, you operate on B by x here, then 2.(B+x) = sum. Now, x can be computed as sum/2-B and the number of operations will be abs(B-sum/2).

Time Complexity:

$O(1)$ per test case.

AUTHOR'S AND TESTER'S SOLUTIONS

Setter's solution
Tester's solution


#2

Video solution can be found here: https://youtu.be/B_PcaHnqxn8?t=7m14s


#3

Can anyone please tell why my code is giving WA?
https://code.hackerearth.com/121a4em


#4

I am gettting WA. Can anyone help? https://ideone.com/TKvPMi


#5

#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–){
long long a,b,c;
cin>>a>>b>>c;
long long d1=b-a;
// cout<<d1<<" “;
long long d2=c-b;
//cout<<d2<<” ";

        if((d2-d1)%2==0)
        cout<<(abs(d2-d1)/2)<<endl;
        else
            cout<<(abs(d2-d1)/2+1)<<endl;
    }
    return 0;
}

#6

My solution : https://www.codechef.com/viewsolution/18007845.


#7

Please check the number of test cases match the number of lines in the input. The number of lines after the first line does not match t.


#8

Cannot open your code. Alternatively share using ideone.:slight_smile:


#9

#10

Please verify


#11

1
-51 -23 -10
Your code give 7 but answer is 8


#12

Thanks man :slight_smile:


#13

Still getting WA for some other case :frowning:


#14

https://discuss.codechef.com/questions/122654/regarding-wrong-ceil-and-floor-values This will be helpful. :slight_smile:


#15

Btw instead of floor((float)(a+c)/2) you can simply write (a+c)/2 both will give same result.


#16

1
0 3 7 Your code give 0 but answer is 1


#17

No, if we have (-61)/2 … here floor will give answer -31 and normal division will give -30


#18

Also I’ve used double in place of float, still the error persists.Can you identify some other test case will will fail here


#19

Yes, @jatin_12345 you are right.


#20

@jatin_12345 If you can deal with +ve, -ve separately Then It might be good. Because converting to float and double results in round off. This might be case for failing at large input.