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

3 Likes

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…

6 Likes

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

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

Can someone please share a Java solution?

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

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.

1 Like

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.

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

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

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

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

2 Likes

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

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

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

can someone explain the complexity of the editorial code?

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.

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)

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

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

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