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

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?

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)

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?

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.

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:

Código:

while ((clock() - startingclock)/CLOCKS_PER_SEC < 0.9)
{
  // do stuff to improve
}
return BestFound;


in my computer, if I change the 0.9 by whatever number I want, it will take ~0.92 seconds total (when running

Código:

time executable < all_titles.txt

) but I have to put about 0.45 in order for it to be counted as 1. Anything slightly bigger and my score drops by about a half, up until about 1

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.

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

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) .

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.

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!

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?

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.

Hello Erik here.
Can you explain the bug a bit better?
What happens if the solution takes 0.6 seconds?
-Erik

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.

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.

New longest cad: 18869 in 1445.26 seconds. I won't submit it to the online code judge because of the time.

Cool!

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.

We will be changing our checker to use actual execution time. and rerun the test to update the scores.

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

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.