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

×

RRSTONE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Roman Rubanenko
Tester: Sergey Kulik
Editorialist: Lalit Kundu

DIFFICULTY:

SIMPLE

PREREQUISITES:

AD-HOC

PROBLEM:

K times, following operation is done on a array A1,A2...AN:
Choose maximum from array A, say MAX. Do Ai=MAX-Ai, for every 1 ≤ i ≤ N.
Print the final array.
0 ≤ K ≤ 109
1 ≤ N ≤ 105

QUICK EXPLANATION:

There will a cycle of size not greater than 2. After that we can easily simulate the operations.

EXPLANATION:

We can prove that there wouldn't be cycle of size greater than 2 (proof is left as an exercise to reader). Means, that states of array will repeat after a maximum of 2 operations.

Pseudo code:

if k==0:    
    print Array A    
    return

if k%2==1: k=1    
else: k=2

for i=1 to k:   
    mx=A[0]    
    for j=1 to N-1:    
        mx=max(mx,A[j])   
    for j=0 to N-1:    
        A[j]=mx-A[j]   
print array A.

Complexity: O(N)

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution
Setter's solution

This question is marked "community wiki".

asked 12 May '14, 15:08

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 12 May '14, 17:17

my code was working fine..but even though codechef was showing wrong result.why??? My solution can be findd here- http://www.codechef.com/viewsolution/3872209

(12 May '14, 16:39) sandeep93★

To all complaining about constraints...

From statement we know:

Ai does not exceed 2 * 109 by it's absolute value.

...but for example

2 1
-2000000000 2000000000

after first step we have

4000000000 0

that's the reason why to use long long, and not because constraint are wrong in statement...

link

answered 12 May '14, 15:18

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

edited 12 May '14, 16:58

Really? So you can tell me, what is wrong here - http://ideone.com/HeY1vh

(12 May '14, 16:56) betlista ♦♦3★

How can that relate to wrong result?? If i have used long long int,but my results are correct,then whats the problem?(and within the time limit)

(12 May '14, 16:57) sandeep93★

The guywho told to use long int deleted his comment??? Somebody Give a correct reason please...

(12 May '14, 17:05) sandeep93★

reason is above - the test case and in link I provided in comment you can see what happens when integer overflow occurs...

(12 May '14, 17:08) betlista ♦♦3★

i have used long long int,not long int..!!!just tell me,for which case my code fails?

(12 May '14, 17:11) sandeep93★

edit your code to long long int,and then see its printing 4000000000. you have declared in long int and is using %lld,thats why your code is showing wron results..see here http://ideone.com/4zMwOB

(12 May '14, 17:14) sandeep93★

but my comment was for the guy telling, that long int is ok, which is not in our environment...

(12 May '14, 17:26) betlista ♦♦3★

whats wrong with my code?? codechef is showing wrong result.

(12 May '14, 18:23) sandeep93★

Thanks. Made the same mistake.

(12 Jun '14, 14:57) dragonemperor3★
showing 5 of 9 show all

So basically this problem boils down to finding the right data type for the given constraints. I personally believe that any problem judging the solution based on the ability to remember the size of int shrewdly hidden in constraints like "Ai does not exceed 2 * 10^9 by it's absolute value." is pure sadistic. But again this is a subjective matter so I won't question the mindset of the author.

However what I would like to point out that the size of int on which @betlista based his premise doesn't hold true for all cases. I couldn't find in the faq's regarding what would be the size of the int in the executable that would be used by the judge. So in future please keep in mind when you say someone's code is wrong because they didn't keep in mind the correct data type, you are equally wrong (and probably misinformed) unless of course you ensure that the constraints are large enough or you inform the user somehow about the possible confusion that may follow.

link

answered 13 May '14, 10:46

saurabh8c's gravatar image

2★saurabh8c
614
accept rate: 0%

edited 13 May '14, 10:49

@saurabh8c, I do not agree with your on your first paragraph, it's not sadistic, in programming contests you always have to check what the worst case scenario will be like (even though it could be very hard on some problems). These are very common things in programming contests, there are also authors that specify if the answer can be held by a certain data type even though usually it's not mandatory.

(13 May '14, 22:57) junior944★

I belong to the category who specify the data type if it may not be clear to the user. That is why I mentioned that it is a subjective topic.

(22 May '14, 15:25) saurabh8c2★

my code was working fine..but even though codechef was showing wrong result.why??? My solution can be findd here- http://www.codechef.com/viewsolution/3872209

link

answered 12 May '14, 16:43

sandeep9's gravatar image

3★sandeep9
4782827
accept rate: 4%

I think, that problem is in

long long int *A=(long long int *)calloc(n,sizeof(int));
// notice the sizeof(int)

but I didn't find the input I can show you on IdeOne...

(13 May '14, 03:59) betlista ♦♦3★

I'm still getting WA IN this.. here's the link- http://www.codechef.com/viewsolution/3900262

link

answered 12 May '14, 17:04

rishirishirock's gravatar image

3★rishirishirock
416
accept rate: 0%

You should print the array after K steps, but you are not - http://ideone.com/k97Ksn

(12 May '14, 17:06) betlista ♦♦3★

Can someone please share a Java solution?

link

answered 12 May '14, 20:15

duttasree's gravatar image

2★duttasree
1
accept rate: 0%

(12 May '14, 20:39) betlista ♦♦3★

Can anybody tell me why this was not accepted http://ideone.com/wT8XtF

link

answered 13 May '14, 01:06

saopayne's gravatar image

1★saopayne
12
accept rate: 0%

Your last submission return "null" for input

2 0
-2000000000 2000000000
(13 May '14, 03:42) betlista ♦♦3★

Hello there, I have referred to the AC solutions and editorial, but haven't been able to figure out what wrong with mine. Please help me to find my mistake. Solution is in C#.

http://www.codechef.com/viewsolution/3894764

Thank you.

link

answered 13 May '14, 22:21

okidoki's gravatar image

1★okidoki
11
accept rate: 0%

edited 13 May '14, 22:21

input

2 2
1 2

expected output is 0 1, because {1, 2} -> {1, 0} -> {0, 1}

your code returns 1 2 (http://ideone.com/WfXwGy )

(13 May '14, 22:37) betlista ♦♦3★

Thank you. I have found my mistake in the code. I want to ask few newbie doubts related to competitive programing. I request you to please guide me for the same as to where can I ask them.

Do you mind if I drop you a PM.

Thank you.

(14 May '14, 00:00) okidoki1★

May I know what was wrong with this code? http://www.codechef.com/viewsolution/3894474

link

answered 14 May '14, 19:11

rakshanawal_91's gravatar image

2★rakshanawal_91
1
accept rate: 0%

this is ur corrected code...http://www.codechef.com/viewsolution/3905612 the problem was that u were using 1 based indexing....so the the (10^5)th number was getting stored at a mem location that wasnt defined...and hence maybe was being replaced by garbage values so u had to declare an array of size (10^5)+1....hope this helps...:)

(14 May '14, 19:38) kunal3614★

Thank you. I got it now :-)

(14 May '14, 21:56) rakshanawal_912★

Can someone pls tell me whats wrong with this code? It says wrong answer. http://www.codechef.com/viewsolution/3924704

link

answered 19 May '14, 17:15

saianu_21's gravatar image

2★saianu_21
1
accept rate: 0%

I have used the same approach as described above. Can anyone tell me why it gives WA? http://www.codechef.com/viewsolution/3873160

link

answered 19 May '14, 23:14

gargankit's gravatar image

2★gargankit
1
accept rate: 0%

I think you need to include the case where k is 0

(21 May '14, 12:14) saianu_212★

if we take array

4 6 8 1 7 10 so max is 10 so the array becomes 6 4 2 9 3 0. Now max is 9 so arrays becomes 3 5 7 0 6 9. It doesnt repeat after 2 cycles. Explain me please

link

answered 21 May '14, 17:09

bradley's gravatar image

3★bradley
6562321
accept rate: 20%

observe this pattern:

1-> 4 6 8 1 7 10 ; max = 10

2-> 6 4 2 9 3 0 ; max = 9

3-> 3 5 7 0 6 9 ; max = 9

4-> 6 4 2 9 3 0 ; max = 9

5-> 3 5 7 0 6 9 ; max = 9

6-> 6 4 2 9 3 0 ; max = 9

...... so from step 2 each step repeats after 2 cycles

(21 May '14, 17:34) achaitanyasai5★

Can someone pls tell me whats wrong with this code? It saystime limit exceeded.

http://www.codechef.com/viewsolution/3892697

link

answered 29 May '14, 17:59

apoe231ree's gravatar image

1★apoe231ree
1
accept rate: 0%

your algorithm complexity is O(N*K)

as

1 <= N <= 10^5

0 <= K <= 10^9

so in worst case N*K can be 10^14

since you are looping from 0 to 10^14(beyond 10^9) you are getting TLE.

I mean actual test cases may not contain upto 10^14 but if it contains beyond 10^9 you may get TLE

(29 May '14, 20:38) achaitanyasai5★

Hi.! I was wondering if anyone could help me with my code. Its working fine on my PC but gives WA whenever I try to submit it here on CC. The link to my solution is http://www.codechef.com/viewsolution/7170559

link

answered 11 Jun '15, 01:24

darsh003's gravatar image

2★darsh003
111
accept rate: 0%

can someone explain the complexity of the editorial code?

link

answered 25 May '16, 22:44

amrit008's gravatar image

1★amrit008
11
accept rate: 0%

Testcases for this question seems to be broken. I tried few times and unable to get the correct answer. Then I copy pasted TESTER's(link) solution(link) to check the same and still WA. Please check the same.

link

answered 07 Jun '17, 12:38

panky4u's gravatar image

3★panky4u
1
accept rate: 0%

How you guys come up with solution of this problem the way author has described? I mean I had no clue I could've has done this. (array repeating after two cycles)

link

answered 29 Jun '17, 12:16

swmshra's gravatar image

2★swmshra
1
accept rate: 0%

can someone tell me why this solution is giving WA? https://www.codechef.com/viewsolution/15554047 Thanks for the help in advance.

link

answered 30 Sep '17, 00:48

rs_710's gravatar image

3★rs_710
1
accept rate: 0%

can somebody pls look at my code and tell why it is giving wrong answer link: https://www.codechef.com/viewsolution/18766313

link

answered 04 Jun '18, 15:19

ambuj_81's gravatar image

2★ambuj_81
1
accept rate: 0%

can somebody pls look at my code and tell why it is giving wrong answer link: https://www.codechef.com/viewsolution/18766313

link

answered 04 Jun '18, 15:19

ambuj_81's gravatar image

2★ambuj_81
1
accept rate: 0%

I have used long int only and the solution is absolutely fine...don`t forget to add the corner case when number of turns(k) == 0

include<stdio.h>

include<limits.h>

define s(a) scanf("%ld",&a)

define max(a,b) a >= b ? a : b

define min(a,b) a <= b ? a : b

define S 102400

typedef long int li;

int main() {

li k,n,arr[S],i,min_no = INT_MAX, max_no = 0;

s(n); s(k);

for(i=0; i<n; i++){
    s(arr[i]);

    min_no = min(min_no,arr[i]);
    max_no = max(max_no,arr[i]);
}

if(k == 0){
    for(i=0; i<n; i++)
        printf("%ld ",arr[i]);
}
else if( k % 2==0){
    for(i=0; i<n; i++)
        printf("%ld ",arr[i] - min_no);
}
else{
    for(i=0; i<n; i++)
        printf("%ld ",max_no - arr[i]);
}

return 0;

}

link

answered 06 Jun '18, 01:16

abhineet_29's gravatar image

2★abhineet_29
11
accept rate: 0%

edited 06 Jun '18, 01:19

Can Anyone tell me why it is giving wa?

https://www.codechef.com/viewsolution/19350552

link

answered 27 Jul '18, 10:39

rip_codechef's gravatar image

5★rip_codechef
1
accept rate: 0%

Solution in C++, you just need 2 little lines:

long long max = *max_element(A.begin(), A.end());
transform(A.begin(), A.end(), A.begin(), bind1st(minus<long long>(), max));

Full solution can be viewed here.

Hope that helps!

link

answered 01 Dec '18, 15:28

shoaib98libra's gravatar image

3★shoaib98libra
112
accept rate: 0%

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,851
×3,820
×968
×20
×20

question asked: 12 May '14, 15:08

question was seen: 10,141 times

last updated: 01 Dec '18, 15:28