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

×

AFK - Editorial

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

This question is marked "community wiki".

asked 31 Mar '18, 19:14

adkroxx's gravatar image

6★adkroxx
306719
accept rate: 7%

edited 01 Apr '18, 23:36

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 02 Apr '18, 03:43

code_report's gravatar image

3★code_report
3305
accept rate: 0%

edited 05 Apr '18, 09:35

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

link

answered 02 Apr '18, 21:58

jatin_12345's gravatar image

2★jatin_12345
184
accept rate: 0%

edited 02 Apr '18, 21:59

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

(02 Apr '18, 22:00) aryanc4036★
(02 Apr '18, 22:20) jatin_123452★

Please verify

(02 Apr '18, 22:21) jatin_123452★

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

(02 Apr '18, 22:23) aryanc4036★

Thanks man :)

(02 Apr '18, 22:30) jatin_123452★

Still getting WA for some other case :( https://ideone.com/O0cspv

(02 Apr '18, 22:51) jatin_123452★

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

(02 Apr '18, 22:57) aryanc4036★
1

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

(02 Apr '18, 23:37) jatin_123452★

Also I've used double in place of float, still the error persists.Can you identify some other test case will will fail here https://ideone.com/ZcPzXw

(02 Apr '18, 23:38) jatin_123452★

Yes, @jatin_12345 you are right.

(02 Apr '18, 23:38) aryanc4036★

@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.

(02 Apr '18, 23:44) aryanc4036★

Test case found 1 0 -1 -5 Your code give 1 but answer is 2

(02 Apr '18, 23:51) aryanc4036★
1

@aryanc403 , its giving 2 only

(03 Apr '18, 00:11) jatin_123452★

Try this test case

2

0 10 1

0 -10 -1

(03 Apr '18, 00:26) aryanc4036★

Its giving correct answer. I think there is some issue with the large numbers because WA was there for subtask 2, subtask 1 was correct

(03 Apr '18, 02:58) jatin_123452★

Ok. Then what is your approach to deal with large no ??

My approach here - https://ideone.com/AGdtqY Do look only when you tried all method yourshelf.

(03 Apr '18, 03:38) aryanc4036★

But only look it after looking above pseudo code and trying it yourshelf. Most probably you will not need below code.

This was my hint of dealing +ve and -ve value separately.

Your AC (100 pts) edited soln https://www.codechef.com/viewsolution/18023970 here. :) Happy coding.

P.S. When I was giving test case where your code was giving correct answer. I was running your old code And it was giving incorrect ans. :) Specially Last two times and you found it to give correct answer.

Bonus karma's for your effort. :) Happy Coding :)

(03 Apr '18, 03:45) aryanc4036★
1

After your hint, I also thought of something like that but was unable to come up with the condition (a+b<0) which actually made all that difference from WA to AC :) Thanks a lot @aryanc403 for working out with my code and finding the bug :)

(04 Apr '18, 03:02) jatin_123452★
showing 5 of 19 show all

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

link

answered 02 Apr '18, 23:15

himanshu_hg's gravatar image

3★himanshu_hg
2
accept rate: 0%

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

(02 Apr '18, 23:18) aryanc4036★
#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;
}
link

answered 03 Apr '18, 12:37

amanrajok's gravatar image

3★amanrajok
111
accept rate: 0%

wikified 05 Apr '18, 20:25

link

answered 03 Apr '18, 22:42

ayushgoyal1703's gravatar image

4★ayushgoyal1703
222
accept rate: 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.

link

answered 05 Apr '18, 00:28

elatedcello933's gravatar image

3★elatedcello933
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) elatedcello9333★

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
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:

×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