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…
5 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
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
Really? So you can tell me, what is wrong here - http://ideone.com/HeY1vh
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)
I’m still getting WA IN this…
here’s the link- http://www.codechef.com/viewsolution/3900262
The guywho told to use long int deleted his comment??? Somebody Give a correct reason please…
You should print the array after K steps, but you are not - http://ideone.com/k97Ksn
reason is above - the test case and in link I provided in comment you can see what happens when integer overflow occurs…
i have used long long int,not long int…!!!just tell me,for which case my code fails?
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
but my comment was for the guy telling, that long int is ok, which is not in our environment…
whats wrong with my code?? codechef is showing wrong result.
Can someone please share a Java solution?
Can anybody tell me why this was not accepted http://ideone.com/wT8XtF
Your last submission return “null” for input
2 0
-2000000000 2000000000
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…
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