Yet again i was disappointed when my solution for spmatrix gave TLE in JAVA but was accepted in C++. The people managing the contests are pure geniuses, practically running the programming world. Why hasn’t this problem been solved? This problem is discouraging JAVA users and forcing them to switch to some other language. It is my request to set the time limits accordingly in the future contests. BTW it was a great contest, loved it.
@moody : I agree though that better time ( instruction level ) and memory profiling tools need to be used for equitable justice
I think you haven’t tried writing program in Python… The same algorithm will give TLE in Python while in C/C++ it will get solved in fractions of seconds… Even in some of the questions, you cannot find any submission of Python(ex, HDELIVER)… Just due to the problem you have mentioned, In such case we have either switch to other language or get imposed by the penalty and we think that It may be a problem in our algorithm because of which we are getting TLE… I seriously consider there need to be some mechanism by codechef to solve this…
Yes I moved to C/C++ from JAVA for this particular reason . I went to a competition and there I was given this time limit condition . And JAVA failed on the same algo while C passed with flying colors . I would really like to see the change in the Judge so that I can continue coding in any language I fell like. for example handling strings in JAVA is so much easier but am forced to work with C/C++ cause of time limit constraints.
Considering the time limit war, i myself use java and find it a bit frustrating when the same algorithm in c++/c gets accepted but not in java. Why not adopt Google Code Jam feature wherein we can download the input file and then within a prefixed time limit submit our output file and source code as well?
I’m afraid that Java problem is in input reading, comparing to C/C++ it’s way too slow
Maybe its possible to write native function
readLine() that will read line using C/C++ to erase this imperfection, didn’t do that before. For sure ona have to know something about the server…
- It should not matter hugely if you are using StringBuilder or not . What’s more important than this is that you should flush your output only once at the end , not every time you have something to write . Flushing output is costly .
- Sometimes the time complexity is right and you still get TLE . It is not just about language being used , it is also about the implementation . So for eg. a solution with O(N) complexity maybe implemented in 2 * N steps or 10 * N steps where latter could give you TLE . Initially I also got TLE in SPMATRIX . But then I was able to reduce one mod operation in each iteration ( total iterations being 10^6 , according to the limit of N ) , bringing me inside the time limit .
Note 1 : I have previously also solved many Code Chef problems where I was getting TLE even though I knew my complexity was right . Just reducing the number of steps inside each iteration got me through every time . I have till date not encountered a problem on Code Chef which I thought was unsolvable in Java in time limit .
Note 2 : Java initially takes too much time for JVM to load . So if a problem has 0.5 seconds limit then 1 second for Java does not give enough leverage for Java being slow because 200-250 ms is taken by JVM to load ( my guess , not very accurate ) . However , if a problem has 2 second time limit , 4 seconds for Java is fair enough .
Sir I saw your solution to spmatrix, you have used BuuferedOutputStream whereas i used StringBuilder. Is there too much a difference in the two with respect to time taken to output answers? Or is there something else in your code that made it fast enough?
This is exactly what i am talking about, i had started thinking that my O(n) preprocessing and O(1) per query solution is not fast enough. I had already started thinking about something else when it struck me that i should give C++ a try.
yes we know that java is much slower than c++, but that is the reason that the time limit for java is twice as compared to c++. And when submitting for spmatrix i had already optimized my code and used fast I/O. That should have brought the solution to a level that is acceptable.
thank you sir for this answer (especially where you mention that there is no problem unsolvable in JAVA ). Further it looks like i need more practice with problems having strict time limits. But sir it seems that even you feel that specifically for problems like spmatrix time limit should be a little higher so that solutions with a fair enough complexity and optimizations get accepted.