SPOJ ARITH2 using ScriptEngineManager gives TLE. Please help.

general
, ,
1

Problem: http://www.spoj.com/problems/ARITH2/

Solution 1: http://ideone.com/jdUYbd

I know the problem can be done using switch case very easily,but I learnt about ScriptEngineManager recently and want to apply it for this particular program. I don’t want to use switch case.
Is there any way to optimize my code such that it gets accepted?

Thank You

2

I know the problem can be done using switch case very easily

Do it! I think that first thing you should try when you want to use super-weird solution is to have normal one.

Bugs:

your solution returns incorrect result for input

1000000001 * 1000000002 =

and throws exception for

1+1*2=

There are some micro optimizations you can do, but why to do those, when probably engine.eval() call is the “bottle neck”?

What would you answer to someone if he/she asks: “Hello guys, my program is getting TLE. I know it can be easily done using scanf and printf, but I learnt about cin/cout recently and want to apply it for this particular program.”?

I do not want to be rude, but this is very typical for newbies: “Guys, what is the fastest I/O reading operation, because my O(N^2) solution is getting TLE for N=1000000…”, see?

If you have working (AC) version, than you can do some experiments how much slower this revolutionary approach of using ScriptEngineManager is, for some big N, let say 100000 and input file is

1 * 2 =
2 * 3 =
...
100000 * 100001 =
3

@betlista :
Firstly thanks for your response.
I am sorry,my Solution 2 was faulty,hence it gave incorrect output for

100000000 * 1000000002 =

if you try the same input for Solution 1,it will give the correct answer. see this: http://ideone.com/NWuAUA

the problem mentioned that "It may also contain spaces to improve readability."
By mistake i overlooked may in the statement and thought that spaces between numbers and operators would be there for certain. So when you entered 1+1*2= ,StringTokenizer failed to seperate the string as there were no spaces. hence it gave an exception in line 35.
long num=Long.parseLong©; when c was 1+1*2=

I apologize for that carelessness.

I don’t have any problem using switch case,when everything fails switch case will be the only way to get AC. I just learned a new thing and wanted to know more about it,wanted to do some experiment with it,and hence i implemented it. I don’t see where the harm lies in trying something new. Never thought that it can offend someone so badly.
Now,if you can explain the reason why this ScriptEngineManager is slower and state the optimizations (if any) that can be made,it would be indeed helpful. That’s all I want to know.

4

About Spaces in the Input File

actually there are spaces in the ip file after every number and operator(except ‘=’, it has a ‘\n’)…cause my input fxn takes an extra char to terminate i/p…and it was AC…so there is a space b/w all elements…this is my code…LINK!!!

5

I tried the link and expected result is 1000000003000000002, your solution returns 1000000003000000000. I hope I’ll have some time to elaborate more about the speed :wink:

6

See those three codes:

It is you solution slightly modified:

  • I’m not reading from stdin, I replaced br.readLine() with getLine(t) which generates lines as I described in previous answer
  • than I added two methods myEvalLong() which evaluates using operator and operands available (simple switch) and for speed comparison I also added myEvalString(), which comparing with myEvalLong() needs more time, to parse the line part again

As you can see the amount of time used by JS eval a 50x bigger than myEvalString() and this is 4x times slower than switch…