python alien help, I NEED U

Hi,
Brief story: I’m new to this site and am trying the alien problem. I tried doing it once and got the correct answer on my side but got time exceeded upon submitting. I thought it was because of the slow input method I was using so I tried a different way with an apparently better method. Still got time exceeded. I realize it will be difficult to fully follow my code but can someone please tell me if theres something obvious that I’m doing that will make it too slow:

first attempt:##

N = int(raw_input())
times = []
for a in range(N):
    input = raw_input()
    space = input.find(" ")
    S = int(input[:space])
    E = int(input[space+1:])         
    times.append((S,E))

num_groups = int(raw_input())
groups = []
output = []
for b in range(num_groups):
    new_input = raw_input()
    input_split = new_input.split()
    groups.append([])
    output.append(set())
    for c in range(1,int(input_split[0])+1):
        el = int(input_split[c])
        groups[b].append(eli)
        for f in times:
            if el >= f[0] and el <= f[1]:
                output[b].add(f)
                
for a in output:
    print len(a)

second attempt:##

import sys

N = int(sys.stdin.readline())
rem_array = sys.stdin.readlines()

times = list()
for a in range(N):
    space = rem_array[a].find(' ')
    newline = rem_array[a].find('\n')
    times.append([int(rem_array[a][:space]),int(rem_array[a][space+1:newline])])

group_list = rem_array[N+1:]
#print group_list
result = [[] for num in range(len(group_list))]
for d in range(len(times)):
    for e in range(len(group_list)):
        el = map(int,group_list[e].rstrip().split()[1:])
        for questlove in el:
            if questlove >= times[d][0] and questlove <= times[d][1]:
                if d not in result[e]:
                    result[e].append(d)
for e in result:
    print len(e)

thanks in advance!

Sorry the code came out not very nice. Basically the thing I think is the issue is that I used a 3 times nested for loop. Is that definitely it?

the problem code is DOWNLOAD. i’m writing an answer below.

The naive approach is, as you found out : for each group of aliens, to browse the list of intervals, and count how many of them contain the alien arrival time. However, in this problem case, there are potentially 5000 groups of 20 aliens to test against 100000 intervals, which is way too much data to be handled within the time limit.

This “easy” problem (i mean it’s in the EASY category of this website) seems to be specifically made to teach the segment tree data structure. Did you already manipulate this kind of object ? Do you see if it can be useful for you ? How ? You should try to implement one, and tell us if it fits there. :slight_smile: Good luck !

cyberax, thanks for your great response. I will look into your suggestion. Is there any place in the problem description that indicates that I should use the segment tree data structure? I mean, if I don’t know that structure, I won’t know to use it.
Thanks again for your help.

no, there is no place in the problem statement telling you should use this. only experience, weeks/months/years of coding :wink:

//