Foreign Police registration in Prague

I have dual citizenship (Finnish and Australian). I recently registered with the Foreign Police here in Prague, and also applied for a temporary residence permit for my partner (an Australian citizen). I found it difficult to get an accurate list of which documents were necessary for the application, so I wrote up my experience here in the hope that it will help other people in the same situation.

Disclaimer: this is only my personal experience. Your situation may be different!

Required documents

We entered the Czech Republic on 90 day tourist visas in January 2008. In March 2008 we went to the office of the Foreign Police in Prague and submitted our application for temporary residency. Here is a list of what I assembled:

  • A short note (written in Czech) explaining when we entered the country, our situation, and what we were applying for. This isn’t a formal requirement but it helps immeasurably if your spoken Czech is weak.
  • Housing and EU form (see below for notes).
  • Original copy of my work contract.
  • Photocopy of my EU passport.
  • Original of my Australian marriage certificate, with an Apostille stamp.
  • Certified translation into Czech of my Australian marriage certificate.
  • One passport size photo.

My wife, as an Australian citizen provided:

  • Photocopy of her Australian passport.
  • Photocopy of VZP pregnancy health insurance card (she was 6 months pregnant when entering the Czech Republic).
  • One passport size photo.


Once we had the right forms and documents together, the actual application process was straightforward. Total time spent in the office (waiting and submitting the application) was under an hour (but make sure you pick the right ticket from the machine at the door!). Some companies here play on the fear that all expats have regarding Czech bureaucracy, and I’ve heard of people paying hundreds of dollars to have an agency submit the paperwork for you. If you are an EU citizen or the family member of an EU citizen then these agencies are not necessary.

Useful links

Information about Residency for Citizens of the European Union and Their Family Members in the Czech Republic.

Advice for living in the Czech Republic.

Application forms. Scroll down to Cizinci (foreigners). An EU citizen applying for temporary residence of his/her family needs two forms:

  • Doklad (potvrzení) o zajištění ubytování: declaration of living arrangements. An actual rental contract is not needed, instead this form has to be signed by your landlord. If your landlord is not the technical owner of the property (e.g. you live in a housing co-op or your landlord is sub-letting) then the legal owner (such as the co-op) must also stamp and sign this form. Each person who is applying for temporary residency needs their own form.
  • Žádost pro občany Evropské unie a jejich rodinné příslušníky: Application for the European union citizens and their family members. This is a purple form. I have heard of applications being rejected because they were printed on a black and white printer, so it’s best to get an original from their office, just in case.

Addendum 1

Be warned that picking up your residence permit can take a long time. We picked up ours and the process took a bit over 5 (five) hours. Around 4 hours was spent in a queue, simply waiting, and the last hour or so was spent waiting for the actual permit to be printed. Bizarrely they don’t actually print your residence permit until you turn up to collect it. This wastes everyone’s time.

The Foreign Police here in Prague could solve the problem of huge waiting times using some fairly basic techniques (book appointments for people, accept online applications, use temp staff to deal with busier periods, provide basic and correct information in English). In the mean time, take a good book.

Addendum 2

I accidentally deleted a reader’s question on how long it took for the Foreign Police to prepare our permits. The answer: the Foreign Police never sent anything saying that our permits were ready to be picked up, we were just told to come back two weeks after making the initial application.

Addendum 3

I’ve recently heard that people have had to wait anything up to 3 months to pick up their residence permits, so take my advice here with a grain of salt.

Cython vs C++

Edit (2008-11-09): Robert Bradshaw posted a patch to my code and the Cython implementation is now a lot faster. Click here to read more.

In a comment on a recent post, Robert Samal asked how Cython compares to C++. The graph below shows a comparison of a greedy critical set solver written in Cython and C++ (both use a brute force, naive, non-randomised implementation of a depth first search):

So things look good until n = 10. In defence of Cython, I must point out that my implementation was a first attempt and I am by no means an expert on writing good Cython code. Also, the Cython code is probably fast enough – in my experience, solving problems (computationally) for latin squares of order 10 is futile, so the code is more convenient for testing out small ideas.

edit: the code is here

edit: Robert’s code is here

Archived Comments

Date: 2008-03-04 05:40:32 UTC

Author: Mike Hansen

You should post the Cython and C++ code because it looks like there maybe some obvious fixes to the Cython to make it behave better.

Date: 2008-03-04 21:01:39 UTC

Author: Robert Samal

Does somebody else have some experience in how cython compares
with C/C++? Every once in a while I need to do some computation (something NP-complete or worse in general, so it
usually ends up as an ugly backtracking). I’d be happy to do everything from within Sage (and using python/cython), but I’m not sure, if it is fast enough (or if it getting fast enough, I suppose that cython is improving gradually).

Date: 2008-07-07 11:59:22 UTC

Author: Alexandre Delattre


After looking quickly into the code, I’m pretty sure some overhead is caused by the __getitem__ and __setitem__ methods, you use to override the [] operator.

When calling L[i, j] (or L[i, j] = x), those special methods are resolved at runtime and hence involve additional python mechanism. While they make the code readable, you lose the interest of “cdef” methods which are called much faster.

IMO, a good compromise would be to put the code in __getitem__ into a regular ‘cdef getitem()’ method, then make __getitem__ as a wrapper of the regular method:

def __getitem__(self, rc):
i, j = rc
return self.getitem(i, j)

cdef int getitem(int i, int j):
… # Put your code here

and replace the L[i, j] by L.getitem(i, j) in your cython code.

Also put “void” return type on cdef method that returns nothing could help a bit.

I’ll try to make these changes and run the benchmark again.

Date: 2008-11-08 15:12:21 UTC

Author: Robert Bradshaw

This graph looked pretty depressing, so I made some optimizations to your code (basically the ones suggested above, and a couple of other glaring things that stood out). The algorithm is still completely the same, and I didn’t do any code re-factoring other than __getitem__/__setitem__, just mostly typing things here and there. It’s now faster than c++ on my machine for the whole range graphed above (and much faster for small inputs).

Code and diff up at

Date: 2008-11-11 17:24:47 UTC

Author: Ben Racine

Any chance that we might see a plot of the improved data… wouldn’t want people to come here and only see the ‘depressing’ data.

Date: 2008-11-11 17:27:12 UTC

Author: Ben Racine

Nevermind, I now see the new results up one level.

Date: 2011-09-14 02:19:56 UTC

Author: Alex Quinn

The link to the improved data is dead:

Same for the link to the motivation (“recent post”):

Are these viewable elsewhere?

Thanks a lot for doing this and posting it! Very helpful in any case.

Date: 2011-09-14 02:22:59 UTC

Author: Alex Quinn

Found it! Here’s the post with the improved data:

Date: 2011-09-14 03:47:40 UTC

Author: Alex Quinn

Code link is still broken:

Date: 2015-10-10 08:12:16.866201 UTC

Author: Mohammad M. Shahbazi

nice challenge. I’ve been using cython for a couple of years. it really sucks

An exact cover solver for Sage

For a while now I’ve been using my own C++ implementation of Knuth’s Dancing Links algorithm. The algorithm is quite fast for solving the 0-1 matrix exact cover problem. More importantly, a number of other combinatorial problems can be converted into an exact cover framework, such as finding latin square completions, enumerating latin bitrades, and computing the chromatic number and chromatic polynomial of graphs (those last two are from comments by Tom Boothby on the sage-devel mailing list).

The thread started by Tom inspired me to make my code public, license it with GPL, write a few doctests, and learn the necessary Cython to write a wrapper for my C++ code so that it would be usable from Sage. The code is available here, in particular dancing_links.sage (top level Sage wrapper), dancing_links.spyx (Cython code that calls my C++ code), and finally dancing_links.cpp (the actual solver).

Not surprisingly, the C++ version is a fair bit faster than the Python implementation adapted by Tom when used as a latin square solver for finding “greedy” critical sets:

x-axis: n, y-axis: number of seconds to compute the greedy critical set of B_n (addition table for Z_n), blue is Python, red is C++.