Daily Challenge #102

It seems that the Daily Challenges have slowed down while I was away, so I think it’s time for a new one!
This one’s hard; prepare yourself…

Time Limit: 1s
Memory Limit: 64 MB

We have an infinite array that is constructed with the following algorithm:

  • Add all numbers from 1 to i-1 to the list
  • Add i to the list
  • Add all numbers from i-1 to 1 to the list.

This way, we get the following array:

1
1 2 1
1 2 3 2 1
...

When joined, we get 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 ....

Your task is to accept two integers N and M (0 < n ≤ 10⁶, 0 < m ≤ 10⁶) as the input. The program should return the index where N appears for the M-th time.

(input: N and M separated by a space)

IN: 1 1
OUT: 1
--
IN: 2 2
OUT: 6
--
IN: 3 3
OUT: 14

Hint: Do not construct the whole array and then select the index; this method will not meet the time and memory requirements stated above

Since this is a challenge that requires a lot of optimization, I’ll accept the solution in any programming language.

5 Likes
Solution
[n, m] = map(int, input().split())

def findMthAppearance(l, n, m):
    c = 0
    for i in range(len(l)):
        if (l[i] == n): c += 1
        if (c == m): return i+1


# constructing the array
l = [1]
for i in range(1, n*m+1):
    l1 = list(range(1,i+1))
    l2 = [i+1]
    l3 = list(reversed(l1))
    l4 = l1+l2+l3
    l += l4
   
print(findMthAppearance(l, n, m))

However, this does not meet the time nor memory requirements for larger inputs.
Now, we have to ask a question: what can we change to optimize it. We’re looking at every way to eliminate loops. Let’s start with the findMthAppearance function.
Due to the nature of the task, it’s easier to find the MthApperance or how many times N appears in the subarray generated (such as 1 or 1 2 3 2 1). Let’s take a look, it’s not hard to pull out a mathematical formula out of this:

Let’s look at the subarray 1 2 3 4 3 2 1 and for the first example let N = 4,
since N == i (4 == 4) the index of N is N and it appears once
let N = 3 now:
since N != i, N appears twice in the subarray:

  • the first appearance is index N
    • the second appearance is the length of the subarray - N + 1 where the length = i*2-1:
      • we can confirm this formula by testing it for other example of N
      • to shorten it down: +1-1 = 0, therefore the second appearance is i*2 - n

Now, we can easily use a formula instead of a for loop:

def appearance(n, i):
    if (n > i): return (0, -1) # we have to worry about if n doesn't appear at all
    if (n == i): return (1, n) # we return the number of times it appears and the index
    else: return (2, [n, i*2-n])

We don’t need to get the subarray.
Now, we have to keep track of the number of times N has appeared. There will still be one for loop which will break once the counter >= M

We also have to keep track of the lengths of previous subarrays. If we just do an if in the for loop it will print out the index in the subarray.

Let’s make a formula:
let’s say that the counter finished at the subarray 1 2 3 4 5 4 3 2 1
we have to get the length of all previous subarrays

Subarray i Length
1 1 1
1 2 1 2 3
1 2 3 2 1 3 5
1 2 3 4 3 2 1 4 7

Notice how they’re all number not divisible by 2?
One way is to save the lengths of each subarray in the for loop, another way is:

The sum of the lengths of all subarrays from [1] to [1 2 3 4 3 2 1] is the length of the last array + 1 * (i/2)
So, len = i2(i/2)

  • or i * 2 * i / i * 2 * 2
  • or i*i

So len = i*i

Now, if the counter == m we should print out the len + appearance[1][1]
If the counter > m we should print out the len + appearance[1][0]

So, the final solution is:

[n, m] = map(int, input().split())

def appearance(n, i):
    if (n > i): return (0, (-1, -1))
    if (n == i): return (1, n) # we return the number of times it appears and the index
    else: return (2, [n, i*2-n])


c = 0
for i in range(1, n*m+1):
    ap = appearance(n, i)
    c += ap[0]
    lenOfPrevious = (i-1)**2 #equal to (i-1)*(i-1)
    if c == m: print(lenOfPrevious + ap[1][1] if ap[0] == 2 else ap[1]); break
    if c > m: print(lenOfPrevious + ap[1][0]); break

2 Likes

Python?

FYI, this challenge was given to 5th and 6th graders in Serbia, nation-wide level of one competition

1 Like

Yeah, this is one of the solutions I submitted. They haven’t officially released a solution, just some table as a hint.

1 Like