Page 1 of 1

1323 - Cactus Revolution

Posted: Fri Nov 25, 2011 12:31 pm
by monkey
http://coj.uci.cu/24h/problem.xhtml?abb=1323

I accepted this problem on the old COJ system in Java, very close to the time limit. After the system changed, this problem will be hardly accepted, because the time limit for Java is very strict in view of the testing hardware, and because another nasty reason: this problem admits multiple solutions but the COJ only checks for a unique solution, so if someone sends a different (but still correct) solution it might get WA depending on how it organized the vertices in the output.

So, I recommend to fix it.

Re: About problem 1323 (Cactus Revolution)

Posted: Fri Nov 25, 2011 1:19 pm
by jelara
One of the differences of this system with the previous one is that in the old COJ, the time calculations for Java were divided by a factor, in order to account for the difference in run-time speed that this language has. In the new system, this factor is discarded by decision, in order to better reflect the reality of the run time. If you have trouble with a tight time limit, we recommend switching to a faster language, like C or C++.

Re: About problem 1323 (Cactus Revolution)

Posted: Fri Nov 25, 2011 1:26 pm
by admin
monkey wrote:Hello!

It's quite possible that the hint you need has already been posted. Enter the problem code in the search box at the top right of your screen and see if that helps.

If the above didn't help you, then feel free to make a post. Make sure you include the problem code in the subject so people can easily find the problem you are talking about. This will also help people searching for the same problem later.

Last of all, remember that posting code is not allowed here, because people who haven't solved the problem could simply copy your code in the future. If you are going to ask a question or to post a solution, describe your algorithm instead.

Good luck!
Let me explain some differences of the new qualification engine that makes this happen

The engine in version 1.0 gives an special treatment to Java solutions using a factor to increase time limits to the solutions written in that language, the new version doesn't gives any special treatment to those solutions otherwise each problem has only one time limit, so solutions only has to pass each dataset with that time restriction: in the new version problems with multiple datasets has two times one for each dataset and one for the whole problem so even when the solution is able to pass each dataset within the dataset time restriction it could be judge as tle because the total time exceed the global limit.

In this specific problem the deal was that was migrated without the two times restrictions, it was fixed and your solution re-qualified, it got AC!!!

thanks for your collaboration!!!! ;)

Re: About problem 1323 (Cactus Revolution)

Posted: Sun Nov 27, 2011 10:34 pm
by monkey
I'll comment about another difficulty I had while submitting 1323, but that applies to some other problems whose solutions make heavy use of the recursion stack (i.e. deep DFSs or recursive routines ), including 1520 (Police). The fact is that I had any troubles in sending 1520 in C++, but when I submitted in Java, I got Runtime Error in the old system. After a lot of time, I realized that the stack was overflowing in Java. Why in Java and not in C++? Because the stack in Java is fixed by the virtual machine, so if it's not assigned a "nice" value like 256MB or something like that, it will overflow if you push it too deep. Solution: I changed the stack size manually in the solution's source.
But I think it should be fixed internally, not by contestants.

What is worse, in this new system, some submissions in Java should give Runtime Error while they're interpreted as Wrong Answer. It should be fixed too.

Re: About problem 1323 (Cactus Revolution)

Posted: Mon Nov 28, 2011 8:38 am
by admin
monkey wrote: What is worse, in this new system, some submissions in Java should give Runtime Error while they're interpreted as Wrong Answer. It should be fixed too.
In the new version this problem was already fixed, if you believe that it wasn't please let us know by telling us the specific submissions you believe that has troubles, an announcement was made a few days ago related to this, see it here http://coj-forum.uci.cu/viewtopic.php?f=12&t=44