Another question: did anyone encounter passing up to case 6, and then failing case 7 and onwards because of wrong output value (and wrong number of paths)? I don’t know where to look in my code for an error that does not pop up in cases 1-6, but from case 7 onwards starts making mistakes.
Test cases 7 to 10 have a depth value above 31. Perhaps there lies your problem, for example if you encode the depth on 5 bits it will ‘overflow’ from a depth of 32 onward.
I’m not sure what happened here… my current code is passing the test cases as well as the validators.
But strangely I get only 50% score. Could it be that the same validator is tried multiple times and my code is not passing every time?
But that wouldn’t make any sens. The heavy burden in my code are some macros processed at compile time that take pretty long to compile. But once the binary is there, execution should be straightforward and stable
I envision the need to scale the scores to µs 
1 Like
Same problem.
I submitted the very same source code twice in a raw. It resulted in different scores.
The second run succeeds only up to validator number 3.
The code passes development tests up to test number 10. The code need more optimization. But it seems to be functional.
I suspect the validation servers are under heavy load. This could result in unstable evaluation results.
ah, I got my answer from launching the test vectors a bunch of times:
Compilation took too long and has been interrupted…
But it still feels strange that I can get a partial result in that case. That means the code is compiled multiple times instead of compiled once, and then just executed multiple times? Seems like a waste of CPU time compiling the same code more than once.
2 Likes
CG might be measuring total CPU time. Splitting up the work to multiple threads on multiple CPU cores may finish x times faster, but the total CPU time (total CPU time across all threads) will not decrease (it will rather increase due to some overhead). They may also force your code to run only with 1 CPU core, then using multiple threads will also make it slightly slower.
1 Like
As you are using macros: Does CG compile the C++ code without optimisations? If I can’t rely on aggressive inlining I’ll have to uglify some of my code 
1 Like
Time measuring is not precise at all, if you are getting closer to 1000, then results may differ by almost 20%, I literally improve my results by sending same code a few times!
2 Likes
why are you compiling C/C++ with -O0 ? std library is full of debug trash inside and obviously is slow as hell in debug. why you hate C/C++ so much?
Finally was able to pass all the testcases and submit. What times are considered “good”? I have a number but nothing to relate it to.
Take a look at the leaderboard if you are using C++ or Rust. Maybe that is some indication.
I managed about 8s with Rust, but now I am running out of ideas for “painless” optimizations.
1 Like
I’m not sure why some leaderboard records show execution times of 0. I’m using Typescript, and my times are in 30k range right now.
They are harcoded solutions. But there are a lot of legit ones in less than 1s.
For some comparison numbers, I first wrote a solution in Perl (my language of choice when I program for fun). After a couple of retries (with the same code), I managed to squeeze it through and got a 100%, with a score of 85827. After further optimizations, I have now gotten that down to 51782, which I think is pretty decent given the language.
I then rewrote it in Python, which brought the score down to 25832.
And finally, I converted it to Rust, which resulted in a score of 2293.
So all three implementations above use the exact same algorithm (as far as the languages allow).
1 Like
I’m using rust. From the observed behaviour I can see that the code is compiled in release mode which is optimised (which makes total sense). I highly suppose that C++ is also compiled with optimisations enabled, but I haven’t seen the exact compiler options published anywhere. I’m using macros in this challenge to try to generate different versions of the code to reduce the number of loops and if cases (and the expanded code would be way over the 100K limit, but the macro code fits easily in this limit).
But you raise a good point, if the compiler correctly inlines, the same should be achievable with normal function calls instead of macros.
After I modified my macro so that they generate a little bit less code, the compilation has now been stable and does no longer timeout. I’m happy with my result, but I see others still get 10x faster execution times 
Got it down to 20k-s with clever memoization, still have some optimizations to try out.
Passed the first 5 tests but failing on the 6th with 1776792 total states. It is supposed to be 418440394. I think all the bugs with finding moves are sorted or I wouldn’t have passed the first 5. Any tips or input how to even debug this would be appreciated.
Tip: The examples are named with the number of “unique states”.
Maybe before solving 6-12, try to compute the number of unique states and see if it helps to simplify your algorithm then see where it leads you
2 Likes
Unless something has changed very recently, CG does indeed compile C++ code (and C code) without any optimisations.
There is a workaround for this which the top C++ entries will be using. I’ll put it in a spoiler block (though really I think this should be publicised somewhere as it’s a common question).
Edit: no spoiler tags. I’ll just post it.
! Use GCC pragmas e.g.
!#pragma GCC optimize ("string"...)
5 Likes