Long JAN15 - One Dimensional Kingdoms - Time Limit

grebnesieh · January 3, 2015, 10:16pm

I have solved the question. I am reasonably sure my algorithm is optimal. I am using python. I get TLE on the last sub-task. I feel 1.5 seconds is too little time for Python to solve that case.

I am not going to post my time complexity because this is an ongoing contest and it could be considered a hint. But here are all python AC for that problem: http://www.codechef.com/JAN15/status/ONEKING?sort_by=All&sorting_order=asc&language=4&status=15&handle=&Submit=GO

Not a single has got the full 100. Most have got 50 like me. I posted regarding this in the question comments several times but I have never really gotten a response there, so I am hoping this will work.

Yes, I could just transform the code into C++, it is pretty straightforward, but since this site supports Python, the time limits should be setup accordingly. Please look into it and if you can re-judge those submissions.

Thank you.

mogers · January 4, 2015, 8:53am

I translated my accepted C++ solution to python and it got TLE. Actually, just reading the input in the last test case gives TLE.

It’s always quite hard to be fair for all languages. I could see a way to try to optimize this solution in python, but I think it is impossible to solve the problems with large input in this kind of languages.

There’s no good solution for this. Increasing the time limit so that Python passes will allow inefficient programs in C/C++ get AC in some problems. Applying different time limits for different languages is also hard to keep it fair and quite time consuming (test all languages).

pranavr93 · January 4, 2015, 11:26am

Aren’t there specific ratios used for setting Time limits? Like Python Time limit = 3 x Time Limit for C++ and so on?

grebnesieh · January 4, 2015, 2:25pm

I know it can be hard to test for all languages but since this is clearly a case where Python won’t pass in time I am hoping the admins might raise the limit. If it doesn’t happen I will probably just submit it in C++ before the contest is over.

grebnesieh · January 4, 2015, 2:26pm

Yes, Python gets 3x by default, so for this question C++ gets 0.5s, Python gets 1.5s, but as mogers said above, that is not even enough time for Python to read in the whole thing. You can also change the multiplier for each language for a specific question if needed. Which is what I wanted done in this case.

chefkaushik94 · January 5, 2015, 2:01pm

Hey, I had the same problem. I did the same in C++ and worked. This is not cool, since 1.5 secs for python was not even enough for the I/O.

animesh_f · January 5, 2015, 7:09pm

I think it should be 5x for Python ,like it is in contests on HackerEarth and other websites.

vishwajitkv · January 6, 2015, 2:23am

If the kingdoms are [1 2],[3 4] and [2 5]. destroying third kingdom will destroy three kingdom. Is this correct?

betlista · January 6, 2015, 2:33am

Yes, destroying third will destroy third kingdom. Maybe you wanted to write something else…

bhavesh_munot · January 6, 2015, 3:26am

It has been happening since a while

I don’t think this thing is that difficult to tackle. Once they come to know about such problem, they can check someone’s code and algorithm (if they don’t want to waste time in coding for all languages), if the algorithm is the optimal one they should increase the time limit for that language such that, that code will pass. Automatically all codes in that language with that optimal algorithm will start passing.

codehalwai · January 6, 2015, 4:21pm

Do we have to Choose X from the given L and Rs???
EDIT: If we have [1 5][7 8][0 10] Then placing anywhere between 0 to 10 will blow away 3 kingdoms is it right??? only one move??

betlista · January 6, 2015, 4:25pm

That is not required if your kingdom is [2, 4], you can put the bomb on 3

dpraveen · January 8, 2015, 12:37am

I have talked to admins and following measures will be taken regarding this. Solutions will be rejudged on basis of these changes.

Time limit will be increased to either 1 or 2 secs.
Factor for python will be increased from 3 to 5.

grebnesieh · January 8, 2015, 5:56pm

Much appreciated

ambika93 · January 8, 2015, 10:39pm

@betlista , will the answer of above given case is [1 5][7 8][0 10] is 1

nisargshah95 · January 8, 2015, 11:42pm

I believe since Python is one of the popular language used in Codechef the time limits ought to be set keeping Python in mind.

ambika93 · January 9, 2015, 9:40am

can’t get?
for above case 2 bombs are right .

dcod · January 9, 2015, 5:48pm

@ambika93 : 2 is the ans for the case you are asking.

ambika93 · January 9, 2015, 6:26pm

I’m not getting correct answer

shubham011 · January 10, 2015, 12:21am

Same is happening with GCDQ java show TLE with time 6sec while C take only 1 sec with same code…