ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1196. History Exam

Python 2.7 MLE. Any idea why?
Posted by Aditya Joshi 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
Re: Python 2.7 MLE. Any idea why?
Posted by Vladimir Yakovlev (USU) 2 Apr 2013 17:20
Use xrange instead of range.

Edited by author 02.04.2013 17:20
Re: Python 2.7 MLE. Any idea why?
Posted by DR. Zhihua Lai 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.
Re: Python 2.7 MLE. Any idea why?
Posted by Vladimir Yakovlev (USU) 3 Apr 2013 22:54
Re: Python 2.7 MLE. Any idea why?
Posted by DR. Zhihua Lai 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
Re: Python 2.7 MLE. Any idea why?
Posted by DR. Zhihua Lai 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)
Re: Python 2.7 MLE. Any idea why?
Posted by Vladimir Yakovlev (USU) 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
Re: Python 2.7 MLE. Any idea why?
Posted by DR. Zhihua Lai 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()?
Re: Python 2.7 MLE. Any idea why?
Posted by KingShark 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