Can anyone provide me with some "heavy" test cases? I tried 3 cases on my machine (# is randomly chosen operator):
- Flat: (a#b)#...#(a#b), 1000 pairs.
- Nested (((...#a)#a)#a), 1000 a's.
- One more nested (b#(b#(b#...#a)#a)#a), 1000 a's and b's.
Average results are about [0.25, 0.5, 0.5] seconds and I didn't used psyco. I also found a solution http://www.spoj.pl/forum/viewtopic.php?f=20&t=265&p=910&hilit=CMEXPR3, which is said to be accepted. I tried it with my test cases and got [1.5, 1.4, 2.9].
So what's wrong with my solution? There are some test cases where it's inefficient? Or it isn't "psyco-friendly" or something?
The code:
#!/usr/bin/env python
import psyco
psyco.full()
import gc
gc.disable()
def solve(line):
def need_to_remove(token):
next_sign = token.get('next_sign')
if next_sign in ['*', '/']:
if ('-' in token['contents']) or ('+' in token['contents']):
return False
if token['sign'] == '+':
return True
elif token['sign'] == '-':
if ('-' not in token['contents']) and ('+' not in token['contents']):
return True
elif token['sign'] == '*':
if ('-' not in token['contents']) and ('+' not in token['contents']):
return True
elif token['sign'] == '/':
if ('-' not in token['contents']) and ('+' not in token['contents']) and ('/' not in token['contents']) and ('*' not in token['contents']):
return True
return False
from collections import defaultdict
result = list(line)
prev_char = ''
tokens = {}
next_token_id = (0, 0)
cur_token_id = (-1, 0)
tokens[cur_token_id] = dict(remove=False, contents='')
max_id_for_depth = defaultdict(lambda: 0)
for pos, char in enumerate(line):
if char == '(':
tokens[next_token_id] = dict(remove=False, start_pos=pos, contents='')
tokens[next_token_id]['parent'] = cur_token_id
cur_token_id = next_token_id
max_id_for_depth[cur_token_id[0]] += 1
next_token_id = tuple([cur_token_id[0] + 1, max_id_for_depth[cur_token_id[0]] + 1])
if prev_char in ['', '+', '(']:
sign = '+'
else:
sign = prev_char
tokens[cur_token_id]['sign'] = sign
elif char == ')':
tokens[cur_token_id]['end_pos'] = pos
try:
tokens[cur_token_id]['next_sign'] = line[pos + 1]
except IndexError:
pass
if need_to_remove(tokens[cur_token_id]):
result[tokens[cur_token_id]['end_pos']] = '~'
result[tokens[cur_token_id]['start_pos']] = '~'
cur_token_id = tokens[cur_token_id]['parent']
tokens[cur_token_id]['contents'] += '@'
else:
tokens[cur_token_id]['contents'] += char
prev_char = char
return (''.join(x for x in result if x != '~')).strip()
def main():
from sys import stdin
import itertools
num = int(stdin.readline())
print '\n'.join(solve(x()) for x in itertools.repeat(stdin.readline, num))
main()