Whats wrong in my approach (Reduction Game)

general
, , ,
13

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

14

@the_extractor its passing yours one as well

15

can u please explain how did we got 35

16

6 6 7 20

6 5 6 20

5 5 5 20

17

Did you get a wrong answer or a TLE?

18

@the_extractor Wrong Answer

19

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

20

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

21

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

22

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.

23

@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
24

Can you share, how did you arrive on that answer?

25

i guess ur approach is failing here :-
n=6 k=4
10 10 11 13 14 20

answer will be 40

26

@mastersabh, got it bro

27

In your code, on lines 54 and 55, you’ve written “If the total is greater than x-1 element we can simply say that we will be able to reduce them to k.” How? Can you please explain?

Also, on line 47, I think you meant “modified x-1th element” instead of xth element.

28

Can anyone who got AC in this question is willing to share his approach ???

29

You can’t get more than 25

30

@meet2mky you can. Following these operations gives 29:

3 9 11 13 25
1 9 11 11 25
1 9 5 5 25
1 5 1 5 25
1 1 1 1 25
31

here is link to solution :

32

Sort-20 14 13 11 10 10
Red-20 13 12 11 10 10
Sort-20 13 12 11 10 10
Red-20 12 11 11 10 10
Sort-20 12 11 11 10 10
Red-20 11 10 11 10 10
Sort-20 11 11 10 10 10
Red-20 10 10 10 10 10
Sort-20 10 10 10 10 10
Red-20 9 9 10 10 10
Sort-20 10 10 10 9 9
Red-20 9 9 10 9 9
Sor-20 10 9 9 9 9
Red-20 9 8 9 9 9
Sort-20 9 9 9 9 8
Red-20 8 8 9 9 8
Sort20 9 9 8 8 8
Red20 8 8 8 8 8
Sort20 8 8 8 8 8
Red20 7 7 8 8 8
Sort20 8 8 8 7 7
Red20 7 7 8 7 7
Sort20 8 7 7 7 7
Red20 7 6 7 7 7
Sort20 7 7 7 7 6
Red20 6 6 7 7 6
Sort20 7 7 6 6 6
Red20 6 6 6 6 6
If you look the pattern the array will finally reduce to 20 4 4 4 4 4.