How the Final Score is Calculated
3 participantes
Página 1 de 1.
How the Final Score is Calculated
Hello, hello.
We are in our last stretch.
Final score is taken as follows:
total length^2/execution time in seconds
For a score to be considered your length must be within 80% of the longest string.
Currently from APEX the longest is 18532 characters
The time limit was supposed to be 30 seconds.
Anything near this and you will lose.
Actually when I last checked the leader executed in <1 second.
We will take 1 second as the minimum time.
Their solution was 16683 characters.
so top score was
total length^2/execution time in seconds
16683^2 / 1=278322489
We are making a change to show the length of your solution to the output
Machine specs are as follows
One High Frequency Intel Xeon Processors with Turbo up to 3.3GHz processor machine, to be exact an Amazon-ami Linux and with 512 MB of RAM.
Good luck!
-Erik
We are in our last stretch.
Final score is taken as follows:
total length^2/execution time in seconds
For a score to be considered your length must be within 80% of the longest string.
Currently from APEX the longest is 18532 characters
The time limit was supposed to be 30 seconds.
Anything near this and you will lose.
Actually when I last checked the leader executed in <1 second.
We will take 1 second as the minimum time.
Their solution was 16683 characters.
so top score was
total length^2/execution time in seconds
16683^2 / 1=278322489
We are making a change to show the length of your solution to the output
Machine specs are as follows
One High Frequency Intel Xeon Processors with Turbo up to 3.3GHz processor machine, to be exact an Amazon-ami Linux and with 512 MB of RAM.
Good luck!
-Erik
erikpeterson- Mensajes : 25
Fecha de inscripción : 06/01/2016
Re: How the Final Score is Calculated
Great.
Regarding C++ files, can you tell us what commands are used to compile? Specifically, are optimizations (like -O2) turned on? Also, what compiler/version?
Regarding C++ files, can you tell us what commands are used to compile? Specifically, are optimizations (like -O2) turned on? Also, what compiler/version?
mraggi- Mensajes : 18
Fecha de inscripción : 16/12/2015
Re: How the Final Score is Calculated
to execute compilation we are running this:
For C
gcc code.c -fno-asm -Dasm=error -lm -O2 -std=c++0x
-w -o executable >/dev/null 2>cerr For C++
g++ code.cpp -fno-asm -Dasm=error -lm -O2 -std=c++0x -w -o executable >/dev/null 2>cerr
if I execute gcc -v , here is the result
gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-amazon-linux/4.8.3/lto-wrapper
Target: x86_64-amazon-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla --enable-bootstrap --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --with-linker-hash-style=gnu --enable-languages=c,c++,fortran,ada,lto --enable-plugin --enable-initfini-array --disable-libgcj --with-isl=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-amazon-linux/isl-install --with-cloog=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-amazon-linux/cloog-install --enable-gnu-indirect-function --with-tune=generic --with-arch_32=x86-64 --build=x86_64-amazon-linux
Thread model: posix
gcc version 4.8.3 20140911 (Red Hat 4.8.3-9) (GCC)
For C++ we are using g++
g++ -v returns
$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-amazon-linux/4.8.3/lto-wrapper
Target: x86_64-amazon-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla --enable-bootstrap --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --with-linker-hash-style=gnu --enable-languages=c,c++,fortran,ada,lto --enable-plugin --enable-initfini-array --disable-libgcj --with-isl=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-amazon-linux/isl-install --with-cloog=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-amazon-linux/cloog-install --enable-gnu-indirect-function --with-tune=generic --with-arch_32=x86-64 --build=x86_64-amazon-linux
Thread model: posix
gcc version 4.8.3 20140911 (Red Hat 4.8.3-9) (GCC)
For C
gcc code.c -fno-asm -Dasm=error -lm -O2 -std=c++0x
-w -o executable >/dev/null 2>cerr For C++
g++ code.cpp -fno-asm -Dasm=error -lm -O2 -std=c++0x -w -o executable >/dev/null 2>cerr
if I execute gcc -v , here is the result
gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-amazon-linux/4.8.3/lto-wrapper
Target: x86_64-amazon-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla --enable-bootstrap --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --with-linker-hash-style=gnu --enable-languages=c,c++,fortran,ada,lto --enable-plugin --enable-initfini-array --disable-libgcj --with-isl=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-amazon-linux/isl-install --with-cloog=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-amazon-linux/cloog-install --enable-gnu-indirect-function --with-tune=generic --with-arch_32=x86-64 --build=x86_64-amazon-linux
Thread model: posix
gcc version 4.8.3 20140911 (Red Hat 4.8.3-9) (GCC)
For C++ we are using g++
g++ -v returns
$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-amazon-linux/4.8.3/lto-wrapper
Target: x86_64-amazon-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla --enable-bootstrap --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --with-linker-hash-style=gnu --enable-languages=c,c++,fortran,ada,lto --enable-plugin --enable-initfini-array --disable-libgcj --with-isl=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-amazon-linux/isl-install --with-cloog=/builddir/build/BUILD/gcc-4.8.3-20140911/obj-x86_64-amazon-linux/cloog-install --enable-gnu-indirect-function --with-tune=generic --with-arch_32=x86-64 --build=x86_64-amazon-linux
Thread model: posix
gcc version 4.8.3 20140911 (Red Hat 4.8.3-9) (GCC)
erikpeterson- Mensajes : 25
Fecha de inscripción : 06/01/2016
Re: How the Final Score is Calculated
I have noticed that the running times are rounded to integers.
This greatly affects the final scores given that 1.05 is rounded to 2 and the score drastically falls.
Also, I'm working on a i7 3.4 Ghz PC using Visual C++ compiler, and I got a running time for the training dataset below 0.3 seconds. However when I upload to the server turns out that the running time is above 1 second
I will try to migrate the code to the g++ compiler version but the differences are unsettling.
I already tested in Ubuntu 14.04 using the configuration specified above and it is even faster. Is it compilation time taken into consideration?
This greatly affects the final scores given that 1.05 is rounded to 2 and the score drastically falls.
Also, I'm working on a i7 3.4 Ghz PC using Visual C++ compiler, and I got a running time for the training dataset below 0.3 seconds. However when I upload to the server turns out that the running time is above 1 second
I will try to migrate the code to the g++ compiler version but the differences are unsettling.
I already tested in Ubuntu 14.04 using the configuration specified above and it is even faster. Is it compilation time taken into consideration?
masp- Mensajes : 15
Fecha de inscripción : 07/01/2016
Re: How the Final Score is Calculated
masp: I think you are absolutely right, that if something takes 1.0001 seconds, it's taken as a 2. They said the min time would be 1 second, but this is strange. I jump between 140 an 280 in score with very minor changes , which means there is a division by two somewhere in there.
mraggi- Mensajes : 18
Fecha de inscripción : 16/12/2015
Re: How the Final Score is Calculated
Actually, it's stranger than that, I think!
If you take less than 0.5 seconds, then it counts as taking 1 second.
If you take between 0.5 and 1 second, it counts as taking... 2 seconds.
At about 1.4 or so seconds, it counts as taking 3 seconds!!
So is the formula:
length^2/ceiling(time*2)?
Or something like this?
is this computer overclocked or something? Does clock() (the standard c++ function) not work as expected? I have something like this:
If you take less than 0.5 seconds, then it counts as taking 1 second.
If you take between 0.5 and 1 second, it counts as taking... 2 seconds.
At about 1.4 or so seconds, it counts as taking 3 seconds!!
So is the formula:
length^2/ceiling(time*2)?
Or something like this?
is this computer overclocked or something? Does clock() (the standard c++ function) not work as expected? I have something like this:
- Código:
while ((clock() - startingclock)/CLOCKS_PER_SEC < 0.9)
{
// do stuff to improve
}
return BestFound;
- Código:
time executable < all_titles.txt
mraggi- Mensajes : 18
Fecha de inscripción : 16/12/2015
Re: How the Final Score is Calculated
I agree with you, something really strange is happening. We almost cannot improve our searching algorithm because of that insane time limitation.
The small difference between my 3.4 GHz and the server 3.3 GHz does not explain the more than twice running time.
The small difference between my 3.4 GHz and the server 3.3 GHz does not explain the more than twice running time.
masp- Mensajes : 15
Fecha de inscripción : 07/01/2016
Re: How the Final Score is Calculated
I've run it on my 2.6Ghz laptop and its the same thing. And you are right. I don't know about you, but just reading the file and finding out which movies can be concatenated takes about 0.2 seconds. Which leaves 0.3 seconds to actually find a path!!! I have a cool thing that improves the path quite a bit (I've gotten to 18590 chars), but it's unusable in this time frame
mraggi- Mensajes : 18
Fecha de inscripción : 16/12/2015
Re: How the Final Score is Calculated
Yes, pretty amazing result, the longest I have reached so far is 17495. I know you are the expert on graphs Miguel! I was trying proposing new methods based on probabilities and other stuffs but given the time frame had to dump it and focus on improving the construction of the graph (less important compared to the np-hard search) .
masp- Mensajes : 15
Fecha de inscripción : 07/01/2016
Re: How the Final Score is Calculated
Thanks.
Did you see my 154 million score? I know it's low compared to the leaders, but think about what it really means
Whoever wins, after this we should get all together and talk about our solutions I'm wondering about what ideas others had.
Did you see my 154 million score? I know it's low compared to the leaders, but think about what it really means
Whoever wins, after this we should get all together and talk about our solutions I'm wondering about what ideas others had.
mraggi- Mensajes : 18
Fecha de inscripción : 16/12/2015
Re: How the Final Score is Calculated
Yes I know hahahaha, but my goal is the 18590 no matter the time. We should definitely discuss our approaches , I'm sure I will learn a lot! This is my first time working with graphs and trying to optimize a code so much!
masp- Mensajes : 15
Fecha de inscripción : 07/01/2016
Re: How the Final Score is Calculated
The 18590 was after a night's search :S
No answer from the organizers about the time "bug"... what should we do? submit the 1s solution, or the 0.5s solution as final?
No answer from the organizers about the time "bug"... what should we do? submit the 1s solution, or the 0.5s solution as final?
mraggi- Mensajes : 18
Fecha de inscripción : 16/12/2015
Re: How the Final Score is Calculated
Before midnight we should set as final solution the one below 0.5 but also leave on all_submissions the one below 1 that should be better (not that we can erase it).
They said if there were errors on their side, they would fix them and publish the new best solution. They can also extend the deadline.
They said if there were errors on their side, they would fix them and publish the new best solution. They can also extend the deadline.
masp- Mensajes : 15
Fecha de inscripción : 07/01/2016
Re: How the Final Score is Calculated
Hello Erik here.
Can you explain the bug a bit better?
What happens if the solution takes 0.6 seconds?
-Erik
Can you explain the bug a bit better?
What happens if the solution takes 0.6 seconds?
-Erik
erikpeterson- Mensajes : 25
Fecha de inscripción : 06/01/2016
Re: How the Final Score is Calculated
Given the same program, we added a time constraint as mraggi explained in the code above.
When we set the time limit in 0.45 (some theshold to avoid surpassing the 0.5), the result was string_size ^ 2 / 1second.
But when we place the time limit at 0.9 the result was string_size ^ 2 / 2seconds
We are pretty sure because our programs find a pretty good string in the first 0.5 seconds. And the string using 0.9 seconds is not 1.41 times (sqrt(2)) the first.
When we set the time limit in 0.45 (some theshold to avoid surpassing the 0.5), the result was string_size ^ 2 / 1second.
But when we place the time limit at 0.9 the result was string_size ^ 2 / 2seconds
We are pretty sure because our programs find a pretty good string in the first 0.5 seconds. And the string using 0.9 seconds is not 1.41 times (sqrt(2)) the first.
masp- Mensajes : 15
Fecha de inscripción : 07/01/2016
Re: How the Final Score is Calculated
Ok we will review.
If 0.9 is being rounded up to 2, we will fix it. Likely not tonight.
But we will check the times and redo the score if needed.
I thus recommend you submit solutions that meet both cases as you had stated.
Just in case other factors are involved.
If 0.9 is being rounded up to 2, we will fix it. Likely not tonight.
But we will check the times and redo the score if needed.
I thus recommend you submit solutions that meet both cases as you had stated.
Just in case other factors are involved.
erikpeterson- Mensajes : 25
Fecha de inscripción : 06/01/2016
Re: How the Final Score is Calculated
New longest cad: 18869 in 1445.26 seconds. I won't submit it to the online code judge because of the time.
masp- Mensajes : 15
Fecha de inscripción : 07/01/2016
erikpeterson- Mensajes : 25
Fecha de inscripción : 06/01/2016
Re: How the Final Score is Calculated
Congratulations, masp!!
Just for curiosity, how much were you getting in your own computer in 0.5 secs? and in 1 sec?
I could not get to 17200 in the server in 0.5 seconds. In my own computer I was getting to 17600-17700 in 0.5 secs, and 18200 in 1s.
BTW, I just found one with 18912. Takes about 5 mins, but it's random, so i might have just been lucky.
Good night everyone. We can get back to our lives now.
Just for curiosity, how much were you getting in your own computer in 0.5 secs? and in 1 sec?
I could not get to 17200 in the server in 0.5 seconds. In my own computer I was getting to 17600-17700 in 0.5 secs, and 18200 in 1s.
BTW, I just found one with 18912. Takes about 5 mins, but it's random, so i might have just been lucky.
Good night everyone. We can get back to our lives now.
mraggi- Mensajes : 18
Fecha de inscripción : 16/12/2015
Re: How the Final Score is Calculated
We will be changing our checker to use actual execution time. and rerun the test to update the scores.
erikpeterson- Mensajes : 25
Fecha de inscripción : 06/01/2016
Re: How the Final Score is Calculated
No, congratulations tu you mraggi!
You got the longest one within 1 second. My algorithm take more time to reach the 18200 because it learns from previous iterations and it is not possible to do it in 1 second.
All these results below 1 sec depend strongly on the choosing of the starting nodes for the search and are tuned for the specific test dataset, not being the case without the strict time frame.
Thanks for being such a fierce competition, you made me improve my approach a lot.
Hope we can share our ideas. Take care.
Miguel A. Sánchez
You got the longest one within 1 second. My algorithm take more time to reach the 18200 because it learns from previous iterations and it is not possible to do it in 1 second.
All these results below 1 sec depend strongly on the choosing of the starting nodes for the search and are tuned for the specific test dataset, not being the case without the strict time frame.
Thanks for being such a fierce competition, you made me improve my approach a lot.
Hope we can share our ideas. Take care.
Miguel A. Sánchez
masp- Mensajes : 15
Fecha de inscripción : 07/01/2016
Re: How the Final Score is Calculated
Wow, it learns? I'd be veeeery interested to know how your algorithm works. One of these days after I take care of all the things I didn't do for working on this competition, hehe. By the way, my email is mraggi@gmail.com.
Whoever wins the final one, it was a lot of fun and I learned a lot of stuff that I probably would never have learned otherwise without seeing the score so high on the board.
Anyway, with all the optimizations I did yesterday, when I set the time to be a loong time, I found one with length 19255. I'll forever wonder just how high is the highest possible.
Whoever wins the final one, it was a lot of fun and I learned a lot of stuff that I probably would never have learned otherwise without seeing the score so high on the board.
Anyway, with all the optimizations I did yesterday, when I set the time to be a loong time, I found one with length 19255. I'll forever wonder just how high is the highest possible.
mraggi- Mensajes : 18
Fecha de inscripción : 16/12/2015
Página 1 de 1.
Permisos de este foro:
No puedes responder a temas en este foro.