Блог пользователя SiddharthBora

SPOJ EXPRESS TLE
Автор SiddharthBora, 12 лет назад, По-английски

Here is the link to the problem:

http://www.spoj.pl/problems/EXPRESS/

And here is the link to my solution:

http://ideone.com/Oq9RI

The solution gets a Time Limit Exceeded on SPOJ. I have first transformed the Postfix expression to a Infix tree and then I simply used a queue to reverse the described process(in the problem). Is this solution so slow or is this due to the input/output that I am facing TLE?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

It seems to me that you have problems with your implementation of the solution:
- You do a lot of string concatenations, do note that that appending a string at the beginning of the string is painful (like 'ans=n->op+ans;' and etc).
- There are a lot of dynamic memory allocations (you use operator new for every nodes) and accesses to different, possibly disjoint, memory areas (when traversing the tree).
- Additionally, you may assume that proper usage of vector<> instead of the queue<> and stack<> (both, by default, use deque implementation) may be vividly faster in many cases.
- Among other possible things, which may add speed improvements: either using scanf() instead of cin input stream or switching the sync_with_stdio flag for the input stream.
- Also, conversions from char[] to string look suspicious.

I haven't done any actual testing of your code, those were the things that I've seen and assumed from the first glance. Hope it helps.

→ Ответить