I wonder if you can clear up a memory of mine from IOI 2001. The first day results were delayed, and I seem to remember this is because a contestant encoded the search in one of the problems into a compile time c++ template metaprogram. On the second day, there was then also a compile time limit for solutions, from what I remember. Do you remember any more details of this?
What is the most efficient algorithm to generate an N x N array of the integers 0,1,2, … such that each entry is the smallest such integer not appearing either above in the same column, or to the left in the same row?
Posting it in this thread is a bit of a spoiler :)
We are a next generation quant trading firm. We aim to be at the leading edge of automation and believe we have an excellent opportunity to challenge more established, larger, less automated incumbents.
We are well capitalised, very successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles.
We’re especially seeking excellent engineers with good low-level knowledge and deep general software engineering experience.
This is a real chance to join a top tier HFT firm and have a huge impact. We think the best work is done in person so relocation to Dubai or Sofia is required. More details: https://www.asymptota.com/open-positions Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com
Nick
We are a next generation quant trading firm. We aim to be at the leading edge of automation and believe we have an excellent opportunity to challenge more established, larger, less automated incumbents.
We are well capitalised, very successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles.
We’re especially seeking excellent engineers with good low-level knowledge and deep general software engineering experience.
This is a real chance to join a top tier HFT firm and have a huge impact.
We think the best work is done in person so relocation to Dubai or Sofia is required.
More details: https://www.asymptota.com/open-positions Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com
Asymptota.com ONSITE (Sofia/Dubai).
Remote for truly exceptional candidates.
We are a next generation quant trading firm, automating further up the chain than the competition. We are well capitalised, successful and looking for developers, traders and quants.
This is a real chance to join a top tier HFT firm and have a huge impact.
More details: https://www.asymptota.com/open-positions
Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com
We are a next generation quant trading firm. We automate further up the chain than our competition. We are well capitalised, successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles.
We’re still less than 10 people so it’s a real chance to join a top tier HFT firm and have a huge impact.
More details: https://www.asymptota.com/open-positions
Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com
We are a next generation quant trading firm. We are well capitalised, successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles.
We’re still less than 10 people so it’s a real chance to join a top tier HFT firm and have a huge impact.
We think the best work is done in person so relocation to Dubai or Sofia is required.
We are a next generation quant trading firm. We are well capitalised, successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles.
We’re still less than 10 people so it’s a real chance to join a top tier HFT firm and have a huge impact.
For lock-free data structures, how does this verification encode the memory model? E.g. high-quality model checkers for the C++11 memory model allow for outcomes inconsistent with the execution order of the code (in addition to outcomes that aren't sequentially consistent, but are consistent with the execution order). They also work on unmodified source. In the past I've seen SPIN/Promela used as a tool for concurrency-checking, but it's silent on memory-models (implicitly sequentially consistent)
Sure. I didn't actually mean ssssort. Sometimes it's worth distinguishing between comparison based sorts, and those that make use of key structure, assume a fixed size key universe etc For that reason, I think considering sampling overhead is worth thinking about.
Very cool. In my experience, using a skewed pivot doesn't actually help in practice. Outside of the case you mention (where the input is a random permutation), sampling must be used to choose a skewed pivot, which has a fairly significant overhead.
One semi-interesting thing here is that the "killer adversary" described on that page requires knowing that the algorithm you're trying to exploit is quicksort.
Long ago, I wrote adversaries that attempt to force _any_ algorithm that is extracting a partial or total order from data to approach their worst case.
These adversaries, like McIlroy's adversary, sits in the compare() function, but it asks itself "what answer can I give, consistent with the data so far, to force the algorithm to ask me the largest number of subsequent questions?"
For non-introspective quicksorts this will be O(n^2), but it should also bring out the worst constant factors in O(n\logn) worst case time algorithms.
I think it's right. One way to convince yourself is just to add counters to the implementation of bubble sort, run it for a larger input, and then verify the probabilities (including the conditional probabilities) match what I claim.
You're correct that every permutation of {1, ..., n} is assumed equally likely as an input.
This way of thinking about it might help:
All that "bubble_sweep" does to the input array is to "right-shift" the left-to-right maxima, and "left-shift" the elements between them. The left-shifted elements aren't re-ordered, so they still have the usual probability of being a left-to-right-maxima.
In a bit more detail:
Let L be the sequence of indices, from left-to-right, of left-to-right maxima in the array. Now in s^{th} sweep, let M be the sequence L concatenated with n - s. Assume M has r elements in total now.
I think you could actually implement a (very, very) inefficient "bubble_sweep" that worked along these lines. I think that makes it a bit clearer that, apart from at left-to-right maxima from a previous iteration, we just have subsequences of the original (uniform random) permutation, so the 1 - 1/(l+1) probability holds.
I hope that's clear(er) and I didn't make too many mistakes. The sun is shining and I must go ride my bike now!
Agreed. The post wasn't meant to suggest anybody should go and optimize! Just that simple looking code can be tricky/interesting.
Also, even artificially skewing the pivot in quicksort as suggested in the paper you reference doesn't work except on /very/ long pipeline machines, because it worsens cache performance & increases instruction count. Also, even then, it's expensive to randomly sample to generate a skewed pivot (a cost they negelect in that paper, assuming it is free)