×

# AFK - Editorial

Div1, Div2
Practice

Author: Misha Chorniy
Tester: Lewin Gan

Easy

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

This question is marked "community wiki".

306719
accept rate: 7%

19.8k350498541

 2 Video solution can be found here: https://youtu.be/B_PcaHnqxn8?t=7m14s answered 02 Apr '18, 03:43 330●5 accept rate: 0%
 0 I am gettting WA. Can anyone help? https://ideone.com/TKvPMi answered 02 Apr '18, 23:15 2 accept rate: 0% 1 0 3 7 Your code give 0 but answer is 1 (02 Apr '18, 23:18)
 0 #include 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<
 0 My solution : https://www.codechef.com/viewsolution/18007845. answered 03 Apr '18, 22:42 22●2 accept rate: 0%
 0 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. answered 05 Apr '18, 00:28 1 accept rate: 0% Tests are valid T = 10000 and 1 + 10000 lines in both (05 Apr '18, 00:39) mgch6★ I think it is not valid. See this, https://www.codechef.com/viewsolution/18045841 I changed the loop condition and it passed. https://www.codechef.com/viewsolution/18045886 (05 Apr '18, 00:41) 1.in has 10000 tests and 10001 lines, I don't where is the problem. Let me check (05 Apr '18, 01:12) mgch6★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,680
×3,764
×1,186
×947
×47
×6

question asked: 31 Mar '18, 19:14

question was seen: 1,506 times

last updated: 05 Apr '18, 20:26