sometimes i wonder whether my c++ code with STL will make the time limit. how does the problem setters set the time limit? do they make sure that if the algorithm is correct, any implementation (e.g., STL, object oriented) are accepted?
(sorry if this topic has been discussed before. it's hard to find. if so, please provide a link to the thread)
are the time limits set so that STL code runs within it?
Moderator: Board moderators
-
Krzysztof Duleba
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
OJ has a strict time limit of 10s for all problems. Problemsetters either make inputs big enough to fit into it, or ignore it whatsoever in problems where time doesn't really matter.
Contest hosting service allows to specify a time limit on a per problem basis and many problemsetters do use it.
If your question is wider and applies to other sites as well, not only to OJ, then it depends on personal preferences of organizers. In Polish qualifications for ACM time limits are so tight that using vectors alone can cause TLE. However, our olympiad in informatics is prepared in such a way that optimal solutions in Pascal, C or C++ (with STL) will pass.
Contest hosting service allows to specify a time limit on a per problem basis and many problemsetters do use it.
If your question is wider and applies to other sites as well, not only to OJ, then it depends on personal preferences of organizers. In Polish qualifications for ACM time limits are so tight that using vectors alone can cause TLE. However, our olympiad in informatics is prepared in such a way that optimal solutions in Pascal, C or C++ (with STL) will pass.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...
-
Krzysztof Duleba
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
I agree, but programming contests are somewhat different - it's speed (both running time and coding time) that matters, not readability or reusability. And when a site compiles without optimization, well, STL structures simply get painfully slow (just think about all the functions that don't get inlined). However, STL algorithms are most useful even in such unfortunate case.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...
Normaly, A problem should accept if we write it with a good computational complexity order, otherwise We might get TLE. but in UVA, things are different!
I have seen a few problems which their solution with STL, got TLE but with a self implemented code for functions and data structures, they became ACed it in a proper time. For example consider the problem ``Accordian'' Patience. I you use STL stack you will get TLE, in order to get this problem you should use your self implemented stack.
nevertheless, If you want to participate in an official acm-icpc contest, it is better to be familier with STL data structures and its algorithms.
I have seen a few problems which their solution with STL, got TLE but with a self implemented code for functions and data structures, they became ACed it in a proper time. For example consider the problem ``Accordian'' Patience. I you use STL stack you will get TLE, in order to get this problem you should use your self implemented stack.
nevertheless, If you want to participate in an official acm-icpc contest, it is better to be familier with STL data structures and its algorithms.
-
shahriar_manzoor
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
Well here are my comments:
a) It is easy to make things backward compatible but not so easy to make it forward compatible. For example when accordian patience was added to the judge STL was not used widely and then I never heard of it. Now with the arrival of STL we are facing such trouble.
b) Problem setters don't want to make time limits tight. It is done because our server is slow and so setting a high time limit will allow the contest queue to be long. In fact troubles arise when the time limit is more than 10 seconds.
c) I have always said in private that it is a pity that we had to use a pentium III server for such a long time when even normal pentium 4 has become obselete. Our efforts of looking for sponsor has not been that successful. It is sad when you consider that the IBM budget of ICPC is $1000000 and a prize money for topcoder is $20000.
d) Good news is that we are upgrading. But still there is a problem, a generous time limit for STL may allow bad plain C/C++ program to pass with a bad algorithm. And it is hard to detect whether an algorithm is written using STL or not. Programmers can use dummy stl codes with real plain code
. However enabling the optimization flag might help. Anyway I am not a real admin...
a) It is easy to make things backward compatible but not so easy to make it forward compatible. For example when accordian patience was added to the judge STL was not used widely and then I never heard of it. Now with the arrival of STL we are facing such trouble.
b) Problem setters don't want to make time limits tight. It is done because our server is slow and so setting a high time limit will allow the contest queue to be long. In fact troubles arise when the time limit is more than 10 seconds.
c) I have always said in private that it is a pity that we had to use a pentium III server for such a long time when even normal pentium 4 has become obselete. Our efforts of looking for sponsor has not been that successful. It is sad when you consider that the IBM budget of ICPC is $1000000 and a prize money for topcoder is $20000.
d) Good news is that we are upgrading. But still there is a problem, a generous time limit for STL may allow bad plain C/C++ program to pass with a bad algorithm. And it is hard to detect whether an algorithm is written using STL or not. Programmers can use dummy stl codes with real plain code
. However enabling the optimization flag might help. Anyway I am not a real admin...It would have been great if the algorithm could be detected, but I guess this is not possible.
Could it be specified in the problem statement that STL code would not make the time limit for the particular problem? Because I have also had times when I have coded with STL and got TLE. If I could know in advance, I wouldn't have wasted the time. It's like those problems where the input is 7 mb and it is hinted that "make sure you use a fast I/O function like scanf()" (and not cin).
Could it be specified in the problem statement that STL code would not make the time limit for the particular problem? Because I have also had times when I have coded with STL and got TLE. If I could know in advance, I wouldn't have wasted the time. It's like those problems where the input is 7 mb and it is hinted that "make sure you use a fast I/O function like scanf()" (and not cin).
-
shahriar_manzoor
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
Still there is a problem in voluntary process.
We have very few people who wants to write an alternate solution, ofcourse derek kisman is different, he almost writes whenever asked. I am not good at STL and code plain C/C++. SO I have to find someone who regularly writes stl solutions and let me have an idea about time limit required for stl solution. Howver what we can do is mention the judge solution run time so that people can guess how tight the time limit is.
We have very few people who wants to write an alternate solution, ofcourse derek kisman is different, he almost writes whenever asked. I am not good at STL and code plain C/C++. SO I have to find someone who regularly writes stl solutions and let me have an idea about time limit required for stl solution. Howver what we can do is mention the judge solution run time so that people can guess how tight the time limit is.
but there is a problem, you are compiling with -O0
For C it just makes a little bit slower enough to compete with java
But for C++ is horrendows, stl is designed in such a way that all the calls are inlined so it can compite with primitive types.
As an example the C++ vector is as fast as a primitive vector, the diference is less than 10%, (in fact is like 4%, 3%) but when you use -O0 all the calls that are marked as inline are outlined and the code becomes the most slow thing in the world
really it can`t be that way, it`s impossible to compete,
For C it just makes a little bit slower enough to compete with java
But for C++ is horrendows, stl is designed in such a way that all the calls are inlined so it can compite with primitive types.
As an example the C++ vector is as fast as a primitive vector, the diference is less than 10%, (in fact is like 4%, 3%) but when you use -O0 all the calls that are marked as inline are outlined and the code becomes the most slow thing in the world
really it can`t be that way, it`s impossible to compete,
and plain c solutions would not get in time, becouse they cannot be optimized, unless there is a super intelligent compiler or a compiler that uses extensions, a in a primitive array can`t be faster it simply can`t, in super debug mode it takes two instructions. in super faster super ultra compiler mode it takes 2 instructions. (add i to a, take the reference to the position)
But when you use a vector<int> then for accessing a position of memory it has to call a function and calling a function is slow, it has to push arguiments into the pile, one more because the class needs to be pushed too, and then you get the slowest function in the world.
C++ is made to be faster, and stronger, to design high level things without loosing performance, and that`s what you get with inline, virtual and all the extra things added to c++, but it`s also made with compiler optimizations in mind, so if you take away compiler opts then there is no way you can win.
But when you use a vector<int> then for accessing a position of memory it has to call a function and calling a function is slow, it has to push arguiments into the pile, one more because the class needs to be pushed too, and then you get the slowest function in the world.
C++ is made to be faster, and stronger, to design high level things without loosing performance, and that`s what you get with inline, virtual and all the extra things added to c++, but it`s also made with compiler optimizations in mind, so if you take away compiler opts then there is no way you can win.
-
Carlos
- System administrator
- Posts: 1286
- Joined: Sat Oct 13, 2001 2:00 am
- Location: Valladolid, Spain
- Contact:
As almost everyone who has read the forum knows, changing the compiler options is not an option now. Old system is all messed up and we're afraid that a small change like that would cause collateral damage.
I also agree that -O5 (no -g, no -pg...) should always be on when judging programs, but we won't be able to implement it until the new system arrives. We'll take it into account then.
What other compiler tags/options should be added for optimization purposes?
I also agree that -O5 (no -g, no -pg...) should always be on when judging programs, but we won't be able to implement it until the new system arrives. We'll take it into account then.
What other compiler tags/options should be added for optimization purposes?
DON'T PM ME --> For any doubt, suggestion or error reporting, please use the "Contact us" form in the web.
-
Krzysztof Duleba
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
For general purpose compiling you don't need anything else than -O3.
What's much more interesting is what C++ compiler will be used. gcc 2.95 is very old, 3.x are better, but I'd really love to see 4.x
What's much more interesting is what C++ compiler will be used. gcc 2.95 is very old, 3.x are better, but I'd really love to see 4.x
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...