rk_221b
October 24, 2018, 12:47am
1
sort(arr, arr + n);
for(int i = 0; i < n-1; i++){
ll m=min(arr[i],arr[i+1]);
if(m<= k){
continue;
}
ll temp = m - k;
arr[i] = arr[i] - temp;
arr[i+1] = arr[i+1] - temp;
}
i have sorted the array and while elements are less than k continued and if min(arr[i],arr[i+1])>k then subtracted the difference and in last took sum of final array.
Can anyone help me to know my conceptual mistake.
try this test case:
n=4 k=50
100 100 150 300
correct answer is 450
your code gives 350
and also try this,
n=4 k=1
3 3 8 8
correct answer is 8
n=4 k=1
8 8 8 8
n=4 k=50
100 100 155 300
i hope,it will help.
can any one help me out in finding out corner cases for this
Reduction game:::
My Solution: CodeChef: Practical coding for everyone
incase you are unable to access above: acm_1.py - Google Drive
i am unable to find whats wrong with my approach
Try this testcase:
4 5
6 6 7 20
The answer is 35 but I think your code gives 33.
All of the above testcases is working for our solution, but still we got a WA.
Any help would be greatly appreciated.
Solution - REDUCTIONGAME
peaceh
October 24, 2018, 2:36am
6
Try this test case,
2
5 17
20 22 23 24 25
11 5
1 5 6 6 7 8 8 9 9 19 20
Ans.
92
66
This will not work for the case:
1
5 5
9 8 9 8 2
Ans: 26
As you only choose the perform subtraction on elements which are adjacent to each other and the subtraction is done directly to k not stepwise as described in question.
Correct approach:
First sort - 9 9 8 8 2
Reduce - 9 8 7 8 2
Sort - 9 8 8 7 2
Reduce - 9 7 7 7 2
Sort - 9 7 7 7 2
Reduce - 9 6 6 7 2
Sort - 9 7 6 6 2
Reduce - 9 6 5 6 2
Sort - 9 6 6 5 2
Reduce - 9 5 5 5 2
Ans = 26
can anyone who solved this question is willing to share his approach ???
yudhik
October 24, 2018, 11:06am
9
My code is available here
An important testcase:
4 2
4 4 4 4
Ans: 10
I have explained my code in comments.
PS: If their are any corrections please suggest them.
rk_221b
October 24, 2018, 1:07am
12
then what should be the approach for this problem
rk_221b
October 24, 2018, 1:18am
13
or atleast can u please explain how did we got 450 in this test case n=4 k=50 100 100 150 300
@the_extractor its passing yours one as well
rk_221b
October 24, 2018, 1:38am
15
can u please explain how did we got 35
Did you get a wrong answer or a TLE?
@the_extractor can you please convert this to question i don’t have enough reputation points to convert it to question
I think only you or a mod can convert your answer to a question.