October Long Challenge 2019 MSV Problem

general
1

I have been trying to solve this MSV (problem name) challenge from October Long challenge 2019.
The solution with which I came was accepted for 3 out of 5 sub tasks and rejected for two subtasks with TLE error. After the end of challenge, when I saw the answer of this problem, I found after checking that my solution is taking less time than this one in every possible case we can test for.
Please what is wrong with my code, and help me with your explanation. Below is my code because I am not able to upload .py file here.

t = int(input())

for _ in range(t):
n = int(input())
lists = list(map(int, input().rstrip().split()))
lcount = 0
rcount = 0
max_count = 0
m = 0

i = 1
j = n-1
while i <= j:
	for k in range((n-1)-m):
		if lists[k]%lists[j] == 0:
			rcount += 1
		if k < i and lists[k]%lists[i] == 0:
		    lcount += 1
	
	count = max(lcount, rcount)
	if count > max_count:
		max_count = count
	if count != 0 and count > i:
		i = count
	
	lcount = 0
	rcount = 0
	j -= 1
	i+=1
	m += 1
    
print(max_count)
2

TLE for sub-tasks and ACC for other sub-tasks often suggests that the algorithm used should be revised to reduce the time-complexity of the solution.

Check the following dynamic-programming based solution for the problem.

https://www.codechef.com/viewsolution/27407575

3

But, my code is taking less time than the given solution in the three subtasks given. And then, I am getting TLE.

YOU CAN CHECK IT O. YOUR OWN AND TELL ME MY MISTAKE.

4

There are three well-known characteristics to measure the performance of an algorithm: wost-time, best-time, and average-time. The accepted sub-tasks seem to be related to the best-time peformance of your algorithm, while TLE is still related to its worst-time performance. TLE does not imply that there is a LOGIC ERROR in the solution. If the algorithm solves sub-tasks faster than another solution, this DOES NOT imply that the it is going to be faster then such solution in solving other sub-tasks. You should be careful in analyzing the algorithm performance so as to not make false generalization or incorrect conclusion without formal proof.

5

Note that the while i <= j: loop is executed up to N/2 iterations, and that the most inner for k… loop is executed N-1,N-2,\ldots,N/2 times. Therefore, the modulo division operation lists[k]%lists[j] is executed O(N^2) times. This is enough to generate TLE when N approaches its upper bound 10^5.