Whats wrong in my approach (Reduction Game)

general
, , ,
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.

2

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.

3

then what should be the approach for this problem

4

can any one help me out in finding out corner cases for this

Reduction game:::

My Solution: https://www.codechef.com/viewsolution/21184422

incase you are unable to access above: https://drive.google.com/file/d/1q6OFJbmMPfnlQFGdMiNUlhwz-nXH3AcF/view?usp=sharing

i am unable to find whats wrong with my approach

5

or atleast can u please explain how did we got 450 in this test case n=4 k=50 100 100 150 300

6

Try this testcase:

4 5
6 6 7 20

The answer is 35 but I think your code gives 33.

7

@the_extractor its passing yours one as well

8

can u please explain how did we got 35

9

6 6 7 20

6 5 6 20

5 5 5 20

10

Did you get a wrong answer or a TLE?

11

@the_extractor Wrong Answer

12

@the_extractor can you please convert this to question i don’t have enough reputation points to convert it to question

13

I think only you or a mod can convert your answer to a question.

14

But you can ask a new question instead of converting this.

15

All of the above testcases is working for our solution, but still we got a WA.
Any help would be greatly appreciated.

Solution - REDUCTIONGAME

16

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

17

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

18

Initially 100 100 150 300
After 50 operation: 50 100 100 300
Again after 50 operation: 50 50 50 300

Now no two element in array greater than k.
So answer is 450.

19

can anyone who solved this question is willing to share his approach ???

20

@shmabulock : Try this input:

1

5 1

3 9 11 13 25

The answer should be 29 whereas your code gives 25 as the answer.

1 Like