Kate was given a birthday gift of three theater tickets. Now she is browsing the theater program for the next N days. On the program, performances are named by integers. Every day, one performance is staged. Kate wants to choose three days (not necessarily consecutive) to go to the theater.
In how many ways can she use her tickets? Two ways are different if the sequences of watched performances are different. Kate likes the theater, so she may watch one performance more than once. For example, if N = 4 and theater program looks as following: [1, 2, 1, 1], Kate has four possibilities to choose the dates: [1, 2, 1, 1], [1, 2, 1, 1], [1, 2, 1, 1], and [1, 2, 1, 1], but they create only three different sequences: (1, 2, 1), (1, 1, 1) and (2, 1, 1). The correct answer for this example is 3. Notice that the order of performances matters, so the first and the last sequences are considered different.
Write a function:
def solution(A)
that, given an array A consisting of N integers, denoting names of performances for the next N days, returns the number of possible ways to spend the tickets. Since the answer can be very large, provide it modulo 109 + 7 (1,000,000,007).
For example, given A = [1, 2, 1, 1], the function should return 3 as exmplained above.
Given A = [1, 2, 3, 4], the function should return 4. There are four ways to spend tickets: (1, 2, 3), (1, 2, 4), (1, 3, 4) and (2, 3, 4).
Given A = [2, 2, 2, 2], the function should return 1. There is only one way to spend tickets: (2, 2, 2).
Given A = [2, 2, 1, 2, 2], the function should return 4. There are four ways to spend tickets: (1, 2, 2), (2, 1, 2), (2, 2, 1) and (2, 2, 2).
Given A = [1, 2], the function should return 0. Kate cannot use all three tickets in only two days.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [1..N].
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2
def bt(path, nxt):
if len(path) == 3:
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2
def bt(path, nxt):
if len(path) == 3:
t = tuple(path)
if t not in
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2
check = {}
def bt(path, nxt):
if len(path) == 3:
t = tuple(path)
if t not in check:
check[t] = None
return
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2
check = {}
def bt(path, nxt):
if len(path) == 3:
t = tuple(path)
if t not in check:
check[t] = None
return
if len(path) > 3:
return
for i in range(nxt, len(A)):
if i > nx
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2
check = {}
def bt(path, nxt):
if len(path) == 3:
t = tuple(path)
if t not in check:
check[t] = None
return
if len(path) > 3:
return
for i in range(nxt, len(A)):
if i > nxt and A[i] == A[i-1]:
continue
path.append(A[i])
bt(path, i)
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2
check = {}
def bt(path, nxt):
if len(path) == 3:
t = tuple(path)
if t not in check:
check[t] = None
return
if len(path) > 3:
return
for i in range(nxt, len(A)):
if i > nxt and A[i] == A[i-1]:
continue
path.append(A[i])
bt(path, i + 1)
path.pop()
bt([], 0)
return len(check)
Invalid result type, int expected, <class 'float'> found.
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return (len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2)
check = {}
def bt(path, nxt):
if len(path) == 3:
t = tuple(path)
if t not in check:
check[t] = None
return
if len(path) > 3:
return
for i in range(nxt, len(A)):
if i > nxt and A[i] == A[i-1]:
continue
path.append(A[i])
bt(path, i + 1)
path.pop()
bt([], 0)
return len(check)
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return int(len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2)
check = {}
def bt(path, nxt):
if len(path) == 3:
t = tuple(path)
if t not in check:
check[t] = None
return
if len(path) > 3:
return
for i in range(nxt, len(A)):
if i > nxt and A[i] == A[i-1]:
continue
path.append(A[i])
bt(path, i + 1)
path.pop()
bt([], 0)
return len(check)
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return int(len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2)
check = {}
def bt(path, nxt):
if len(path) == 3:
t = tuple(path)
if t not in check:
check[t] = None
return
if len(path) > 3:
return
for i in range(nxt, len(A)):
if i > nxt and A[i] == A[i-1]:
continue
path.append(A[i])
bt(path, i + 1)
path.pop()
bt([], 0)
return len(check)
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
if not A or len(A) < 3:
return 0
if len(set(A)) == len(A):
return int(len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2)
check = {}
def bt(path, nxt):
if len(path) == 3:
t = tuple(path)
if t not in check:
check[t] = None
return
if len(path) > 3:
return
for i in range(nxt, len(A)):
if i > nxt and A[i] == A[i-1]:
continue
path.append(A[i])
bt(path, i + 1)
path.pop()
bt([], 0)
return len(check)
The following issues have been detected: wrong answers, timeout errors.
N = 100,000, all performances are different.
got 166661666700000 expected 665533373
N = 100, at most 10 different performances.
running time: 0.156 sec., time limit: 0.144 sec.
N = 300, performances are sorted by name.
running time: 0.268 sec., time limit: 0.144 sec.
N = 100,000, at most 10 different performances.
Killed. Hard limit reached: 6.000 sec.
N = 100,000, performances are sorted by name.
Killed. Hard limit reached: 6.000 sec.