I've been given a task that I had issue solving.

Problem statement:

John likes jumping so he is about to build a new jumping terrain. The terrain consists of N blocks, and in each block he can put multiple jumping marks. He starts by jumping from the ground on some mark from the first block, then on some mark in the second block, and so on until he finally jumps from some mark from the N-th block back to the ground.

John has bought N boxes of jumping marks (i-th box contains ci marks). He has put them into the cart and now he is moving from the first block to last one. He wants to assign each box to distinct block. After that, for each box he will put all marks from the box into respective block.

He is not aware that while setting up the terrain, Mark is hiding between boxes and steals one jumping mark from each box that is left in the cart every time the cart moves to next position (excluding the first position).

John wants to build such a terrain that the number of ways to jump from the beginning to the end of the terrain is maximum possible.

Help Ivan find out the best arrangement of the boxes to achieve the maximum number of ways he can jump the terrain if he places the boxes in the correct order.

For example, given an array [2, 4, 4, 1], solution is 2 (correct order is [1, 2, 4, 4], which because of Mark turns to [1, 1, 2, 1], and there are two ways to traverse that array). For [1, 1] solution is 0. For [3,3,3] solution is 6.

At first I thought this is a simple matter, but feedback I got from my instructor told me that solution was unsatisfying.

Here is my solution:

def solution(a):
    # a is input array
    n = len(a)
    c = 1
    result = a[0]
    for i in range(1, n):
        v = a[i] - c
        if v < 1:
            return 0
        c += 1
        result *= v
    return result % ((10 ** 9) + 7)

What is wrong with this solution?

  • 1
    $\begingroup$ We're not a coding site; and questions asking us to debug or find the problem in your code are off-topic here. Algorithms can be on-topic, but a big block of code is usually a poor way to describe your approach. Instead, why don't you explain the idea behind your algorithm, what method it is using, and why you think it is correct. Have you tried to prove it correct? have you tried testing it on many example inputs to see if it always produces the right output? $\endgroup$ – D.W. Oct 17 '19 at 18:45
  • 1
    $\begingroup$ Also, please credit the original source of the exercise and any other copied material. $\endgroup$ – D.W. Oct 17 '19 at 18:45
  • $\begingroup$ Ask your instructor. The appropriate feedback really depends on what class you are in, what is your experience as a coder, and so on. $\endgroup$ – Yuval Filmus Oct 24 '19 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.