Discussion @ 1196. History Exam @ Timus Online Judge

Aditya Joshi Python 2.7 MLE. Any idea why? [8] // Problem 1196. History Exam 1 Apr 2013 19:09

def binary_search(seq, t):
    min = 0; max = len(seq) - 1
    while 1:
        if max < min:
            return False
        m = (min + max) / 2
        if seq[m] < t:
            min = m + 1
        elif seq[m] > t:
            max = m - 1
        else:
            return True

n = int(raw_input())
prof_dates = []

for x in range(n):
    inp = int(raw_input())
    if binary_search(prof_dates,inp) == False:
        prof_dates+=[inp]

k = int(raw_input())

counter = 0

for x in range(k):
    inp = int(raw_input())
    if binary_search(prof_dates,inp):
        counter+=1

print counter

Vladimir Yakovlev (USU) Re: Python 2.7 MLE. Any idea why? [7] // Problem 1196. History Exam 2 Apr 2013 17:20

Use xrange instead of range.

Edited by author 02.04.2013 17:20

DR. Zhihua Lai Re: Python 2.7 MLE. Any idea why? [6] // Problem 1196. History Exam 3 Apr 2013 20:31

using xrange will give TL on 8

I suspect that it is impossible to get it accepted using Python for this problem. because the raw_input(), input() is very slow.

correct me if I am wrong.

Vladimir Yakovlev (USU) Re: Python 2.7 MLE. Any idea why? [5] // Problem 1196. History Exam 3 Apr 2013 22:54

http://acm.timus.ru/rating.aspx?space=1&num=1196&lang=python2

DR. Zhihua Lai Re: Python 2.7 MLE. Any idea why? [4] // Problem 1196. History Exam 4 Apr 2013 06:38

OK. I solve this by using Python + Dictionary, using dictionary is even simpler to solve.

http://acm.timus.ru/status.aspx?space=1&num=1196&author=46914&lang=python2

however, I doubt it if using Python+Binary Search for this problem.

Edited by author 04.04.2013 06:52

DR. Zhihua Lai Re: Python 2.7 MLE. Any idea why? [2] // Problem 1196. History Exam 5 Apr 2013 06:01

Ok,
if a faster I/O is used (read all once), using stdin.read().split(), it will give ML on test 8. In fact, read all to memory will cost ML regardless whatever algorithm you use.

#!/usr/bin/env python

from sys import stdin

lines = stdin.read().split()

n = int(lines[0])
p = [0] * n
for i in xrange(1, n + 1):
    p[i - 1] = int(lines[i])

def chk(s, p, n):
    left = 0
    right = n - 1
    while left <= right:
        mid = (left + right) / 2
        if s > p[mid]:
            left = mid + 1
        elif s < p[mid]:
            right = mid - 1
        else:
            return True
    return False
c = 0
m = int(lines[n + 1])
for i in xrange(m):
    s = int(lines[n + 2 + i])
    if chk(s, p, n):
        c += 1

print(c)

Vladimir Yakovlev (USU) Re: Python 2.7 MLE. Any idea why? [1] // Problem 1196. History Exam 5 Apr 2013 22:07

You tried to store 1.000.000 of string objects in memory. Let's see the sizes of such string and list in bytes:

>>> import sys
>>> sys.getsizeof('1000000000')
43
>>> sys.getsizeof('1 1'.split())
160

DR. Zhihua Lai Re: Python 2.7 MLE. Any idea why? // Problem 1196. History Exam 5 Apr 2013 22:41

Yes.

Read all to memory is not feasible.
but without this, how to achieve a faster I/O than raw_input, input()?

KingShark Re: Python 2.7 MLE. Any idea why? // Problem 1196. History Exam 18 May 2013 12:34

Converting the professor's list to set works. The 'in' keyword is O(1) average case for sets as per:http://wiki.python.org/moin/TimeComplexity

I got AC with 1.078s

Discussion of Problem 1196. History Exam