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