The importance of F-You money, part 2: How to invest?

[Updated in February 2019.]

When it comes to F-You money, investing and early retirement, I find the philosophical part of it the most fun. It has greatly influenced my personal philosophy, which is apparent in the two most read posts of this blog: one about non-material value and another about thriving during hard times.

Part 1 of this post was also mostly about philosophical advice. Unfortunately, you can’t eat philosophy and eventually you need to invest. I found many investing articles incomplete and books too long, so I’ve written my own tutorial. Also, most of the published advice is written for Americans who usually have better offerings and simpler choices, but this post is aimed at Europeans.

I assume basic knowledge of terminology, so you should know what bonds, stocks, ETFs, TER, small-cap, real returns and others are. If not, reading the first ~10 parts of Jim Collins’ stock series and additional googling on Investopedia should help.

The short version

People usually invest their money via a bank or a retirement fund. They loan the money to someone or buy stocks. Bonds (=loans) have real yearly returns of 0 to 4% and stocks of 6 to 8%. All of these are average returns over the long term adjusted for inflation. Both banks and retirement funds typically charge 1–2% yearly, so your yearly profit is greatly reduced, for example you might get 4.5% instead of 6% each year. Lately, it has become very cheap to circumvent the middlemen via funds traded on stock exchange (ETFs).

You don’t have to have a super-high salary to invest this way. Here’s a simple rule of thumb: calculate 1% of the money you typically save every 3 months and check if it’s higher than broker fees for a single transaction (more on brokers later). With a low-cost broker like CapTrader, saving at least 400 € every 3 months fulfills the criterion.

There are 5 steps to a simple investing plan, especially suited for a beginner.

1. Get an account with a broker trading on the German Xetra exchange. CapTrader is a low-cost broker available in many European countries. Slovaks and Czechs can also use Lynx, which is based on the same platform and 20% more expensive, but they have phone support that speaks Czech.
2. When do you need the money and what is your risk tolerance? Would you risk higher expected growth for more risk? Answers to these questions determine your bonds/stocks ratio. Betterment has some nice charts that should help you find the right ratio. Young people saving for retirement can have up to 80% of their investments in stocks. This is by far the most important step, so take your time to figure out your risk tolerance.
3. For the stock part of the portfolio, I recommend one of these 2 global ETFs:
   
   • Vanguard FTSE All-World Accumulating, accumulating, TER 0.22%.
   • SPDR MSCI ACWI IMI, accumulating, TER 0.4%. Same as above but contains small-cap too.
   Accumulating funds reinvest dividends, so you are always fully invested. They might also be more tax-efficient in some countries.
4. For a portfolio with more than 60% of stocks (i.e. higher risk), choose one of:
   • iShares Core Global Aggregate Bond EUR Hedged, accumulating, TER 0.1%
   • iShares Core Global Aggregate Bond GBP Hedged, accumulating, TER 0.1%
   • SPDR Bloomberg Barclays Global Aggregate Bond CHF Hedged, accumulating, TER 0.1%
   These follow the same index and have the same TER, but are hedged in different currencies. Choose the currency that you want to spend your investments in. If you aren’t sure about the country you’ll settle in, you can pick a mix.
   Broad bond indexes are typically biased towards long-term bonds, which have better yields but also higher risk. In a low-risk portfolio (less than 60% stock allocation), you can open a savings account in a bank or search for ETFs with lower risk—short-term government bonds have the lowest risk. Also check out Betterment’s allocation for low-risk portfolios here and here. Bear in mind that you should bias towards Europe instead of USA.
5. Invest every time you saved enough money that the broker fees are less than 1% of your saved amount. Then, once a year, rebalance your portfolio. For example, if stocks over-performed bonds, sell some stocks and buy bonds to get back to your bonds/stocks ratio. This reduces volatility.

You can get more fancy and use more ETFs but for a beginner this is more than enough. It puts you ahead of 99% of other people who pay 1–2% in yearly fees instead of 0.1–0.4% for the ETFs above. The small difference in fees makes a huge difference in the long run thanks to exponential growth.

The long version

Read on if you’re fine with a more complex portfolio or want to know why I made the suggestions above.

US estate and gift tax

[Update February 2019: Investing via US ETFs is now very hard for Europeans, so this is no longer relevant.]

If you own US stocks, funds or real estate, you are subject to US estate and gift tax. They apply when you give your assets to someone or they inherit your wealth after your death. The tax is 40% and only applies to wealth above $60,000. Since the European offerings are pretty good and they will get even better, I see little reason to invest using US ETFs. An advantage of European offerings are accumulating ETFs, which are forbidden in the US.

If you still want to use US securities, check out a tax guide by Credit Suisse. Also note that some countries have estate and gift tax treaties with the US, so the rules might be different for you (usually more favorable).

Stock investing

My thesis is that the stock part of a portfolio should be based on market capitalization indexes, containing thousands of stocks in multiple countries ranging from small- to large-cap.

Capitalization-weighted indexes

Stocks for the Long Run lists a lot of strategies that can beat the market, including the January effect. For small-cap stocks, you could have beaten the market by buying in December and selling in late January. The book mentions that the strategy still worked during the 1990s but stopped working since 1994, which is coincidentally the year the book was published. When a simple strategy becomes well-known, people start exploiting it and it soon stops being profitable.

The book also mentions high dividend yield and low P/E ratio as investing strategies that beat the market for decades. Random check showed that high-dividend yield strategy also seems to have stopped working in the last 3 to 5 years. The value premium is still there but there is a big academic debate whether that’s due to higher risk or not.

There are plenty of incorrectly priced instruments at this moment. However, you won’t take advantage of them with a strategy that is easily accessible to a layperson or implemented by tens of publicly accessible funds. Someone else with more money or resources has already beat you to it. I’m only using market capitalization indexes, because then my strategy is the average of all strategies. Yes, I’m only getting the average return, but the average is still very high.

I’ve read a few investment books and investment articles but most of them are intellectually dishonest. They spend 300 pages convincing you to not try beating the market and in the end they allocate exactly 5% to emerging markets (EM), when the global market allocates about 10% in EM right now (using MSCI’s definition of emerging markets). They don’t explain why 5% is better than 8.647% or any other arbitrary number. In fact, printing the percentage in a book is a mistake in my opinion, since it should be a moving target.

There are valid reasons for not investing exactly 10% in EM, for example because historically they have shown greater risk and higher volatility, which was rewarded with extra 1–2% yield. If you don’t want to take the risk, allocate less than 10%; if you like risk, allocate more. Betterment is the only place where they do it right in my opinion. It’s an American investment company (robo-advisor), but their ETF portfolios for various risk levels are completely public and you are free to take inspiration.

The 15/30-stock diversification myth

A Random Walk Down Wall Street, probably the most famous investing book, claims that you can achieve great diversification by only picking 15 random US stocks. Interestingly, Burton Malkiel is a coauthor of a paper claiming that this number is much higher now than 40 years ago, but he still hasn’t changed the text of the book in the newer editions (I might be misunderstanding something in the paper too). To be properly diversified, you need to own hundreds or thousands of stocks.

My stock portfolio

My own stock portfolio contains 3 ETFs that span 46 countries from small- to large-cap and contain about 5000 stocks in total. These ETFs roughly correspond to the MSCI ACWI IMI index that covers about 99% of the global investable market.

• iShares Core MSCI World, accumulating, TER 0.2%.
• iShares Core MSCI Emerging Markets IMI, accumulating, TER 0.18%.
• iShares MSCI World Small Cap, accumulating, TER 0.35%.

I own them in proportions determined by their global market capitalizations with a slight bias towards more risky emerging markets, so small-cap corresponds to 15% of the developed world and emerging markets to 13% of the whole world. The combined expense ratio is about 0.22%. Note that iShares funds participate in security lending, which offset the expenses by 0.04% for the EM fund in 2015.

Bond investing

While a lot of the stock investing advice applies to bonds (e.g. diversification), in addition there is a significant currency risk and bonds are more complex with parameters like credit risk and maturity. I understand bond investing less well and it seems the experts are equally confused. My thesis is that I should own multiple currencies, mostly long-term government bonds. Some home bias is fine, especially for low-risk portfolios. Also, currency hedging pays off for bonds.

Long-term bonds are more risky but also have higher yields in the long term, so they are fine in a high-risk portfolio. I see little reason to own many corporate bonds when I have a lot of stocks, since these two are correlated.

I own iShares Core Global Aggregate Bond EUR Hedged (accumulating, TER 0.1%), which is one of the bond funds recommended above in the simple portfolio. It's one of the cheapest bond funds on the market and it's hedged. There's little to be gained by mixing more funds.

If you want to know more about bonds, Betterment has informative articles with visualizations, for example here, here and here. As for books, in addition to Random Walk and Stocks for the Long Run, I highly recommed Rick Ferri’s All About Asset Allocation.

REITs (real estate)

I own SPDR Dow Jones Global Real Estate UCITS ETF (distributing, TER 0.4%), which is a global real estate fund. Unfortunately, the fees for REITs are still fairly high in Europe, so I only allocate a few percent of my whole portfolio to real estate.

No cash

Traditional advice tells you to keep 5 to 10% of your portfolio in cash, but I don’t do that. When you do the math, it’s not worth it. I’ve instead bumped the bond allocation percentage and I only keep twice my monthly spending available.

Choosing ETFs

If you want to search for other ETFs than the ones listed in this post, I recommend using justETF which contains all ETFs traded in Europe. You can limit your search by many criteria, including:

• Distributing versus accumulating: Accumulating ETFs immediately reinvest dividends, so you are always fully invested and your transaction costs are lower. They might also be more tax-efficient.
• Tracking error: Total expense ratio (TER) causes an ETFs to perform worse than the underlying index, but there are other factors at play too. I’ve already mentioned security lending and another one is replication method. Many ETFs don’t own the full index but only a subset of it, which introduces an error that can go either way. There are also synthetic ETFs that don’t actually own the underlying securities and do some magic instead, which also introduces tracking error.
• Replication method: I only use full-replication or sampling ETFs, because I don’t understand synthetic ETFs. Full-replication and sampling ETFs own the securities from the underlying index.
• Domicile: The most tax-efficient ETFs are domiciled in Ireland or Luxembourg.
• Cost of buying: Some ETFs are only available on exchanges with higher broker fees or in a currency that you don’t earn. They might also have a high bid-ask spread. All these make buying more expensive. However, since these are one-time costs, I don’t think they are very important. Recurrent fees are much more important.

Snow cave in Binntal

I've slept in a snow cave for the first time ever and can only recommend the experience.

Saturday

We started the trip in Binn and went towards Mässeralp. At Manibode, we took out a probe to measure the snow depth. It was between 1.5 and 2 metres, just about enough for a snow cave. We left our stuff there and started skinning up towards Grosses Schinhorn. Almost immediately, I felt out of power and Vašek and Kubo were too far ahead. I decided to turn back.

Breithorn and Bietschhorn

It turned out to be a good decision. Since it was getting late and we had a snow cave to dig, Kubo and Vašek didn’t reach Grosses Schinhorn anyway and the good snow ended exactly at my turning point.

Back at Manibode, we found a spot with 2 meters of snow where we didn’t need to dig out an entrance corridor, because the wind did it for us. When planning the trip, we estimated 2 hours to dig the snow cave and that’s about how long it took. Next time I’ll bring a snow saw though.

Vašek working on the roof

Me standing at the entrace of our cave

We marked the top of the snow cave with skis to avoid accidental destruction

The cave had 3G internet, despite being in 2000-meter altitude in the middle of nowhere under 1.5 meters of snow. I have no idea how that's possible.

The views towards Aletschhorn (4193 m) from the cave were stunning.

Aletschhorn before sunset

Aletschhorn after sunset

Aletschhorn in the morning

Sunday

Even with an open entrance, the cave was around 0 degrees Celsius throughout the night. We could have made it warmer, but as Kubo explained to me, you want to err on the freezing side, otherwise you end up very wet from the melting snow and less comfortable than in a freezing but dry cave.

A 5-star hotel at 2000 meters with 3G internet

The night was surprisingly very good. In fact, I got the best sleep in two months (about 10 hours) despite drying wet clothes in my sleeping bag and keeping 3 liters of water warm so that it wouldn’t freeze.

Our plan for the day was to climb Schwarzhorn (3108 m). When we reached the saddle below Fleschhorn, we saw the last part involved too much climbing and as it was getting late, we changed the plans to go to peak 3112m instead. Just like the day before, I felt out of power and too slow, so I stayed below the summit. We had a bus to catch and too little time.

Kubo and Vašek successfully reached the top and had some great views.

Pizzo Cervandone on the right

Vašek at peak 3112 m pointing at Bietschhorn

The downhill ride offered steep skiing in great snow with a spectacular scenery created by fog and the Sun.

We reached the snow cave for the last time, packed things and continued to Binn to catch the bus.

The end

A short selection of my photos is on Flickr and photos from all 3 of us is on Google Photos.

How I got much better

In the last 18 months, I stopped going to doctors and instead focused on self-experimentation. Many experiments failed, but overall it’s been a big success. Some symptoms are completely gone, some are still alive but few and far between, and some are thriving as well as for the last 15 years.

This post was supposed to be titled Living with histamine intolerance, part 4, but I don’t classify as histamine intolerant anymore. You can read parts 1, 2 and 3 to get better context, though.

Feel free to get inspiration from my experiments but remember that there are risks involved.

Life-style changes that worked

Sunlight

I always wondered why I felt better in the summer and worse in the winter. Each November my ability to exercise rapidly dropped, except when I spent autumn in sunny California and the symptoms were then postponed by two months.

I’ve tried spending every second in the Sun but it was very difficult to do in Sweden. Spending one week under the Arctic Sun didn’t do anything. Two days of kayaking helped a lot, but not as much as 3 hours of full-body sun bathing. Sunlight is the best cure against insomnia and bad sleep.

On the other hand, taking vitamin D in winter helps but doesn’t bring the full effect. It’s not so surprising, since sunlight does more to our skin than just vitamin D production and we’re only discovering those effects now.

Dietary changes

Diamine oxidase (DAO) is an enzyme that regulates histamine in our bodies. The only macronutrient increasing DAO concentrations in the intestinal lymph in rats is fat. In another study of rats, MCT oil increased DAO activity 2.5 times in the intestines.

Even though I’m not a rat, I had to try it out. Did it help? Maybe it did, maybe it didn’t. It’s true that my DAO levels are 3 times higher than before, but I have too little data to judge causality. An unexpected side-effect was a big decrease in headaches and migraines. This is perhaps not that surprising, since MCTs boost ketone production and ketogenic diets are therapeutic for a few neurological conditions.

The second big change in my diet was eating nose to tail – eating other parts of animals than just muscles. Organ meats are cheap, easy to cook and super-nutritious. Skin, bones and cartilage are rich in collagen, which seems to be beneficial for many. The nutritional wars concentrate too much on carbohydrates versus fat, while different proteins and amino acids are often ignored. That’s likely a big mistake.

I’ve changed other small things in my diet, but listing them all would need another full post. Luckily for you, someone made a nice infographic and wrote a book about my diet 4 years ago. After I found out about people copying my diet, I read the book and had a lot of Aha! moments. That being said, the book is overconfident at times and I’d be extra careful following their advice to the last word. Also check Scott Alexander’s critical review.

Probiotics

Abdominal pain has been my number one problem for years. I’ve consulted doctors and tried many things, but those brought minor improvements at best. With Lactobacillus plantarum, the pain was gone within hours. Bacillus coagulans was also helpful for better digestion, but I had to take it every day and was later able to achieve a superior effect with glycine-rich foods, so I stopped taking it.

While I swear by L. plantarum, I do believe that probiotics are mostly unnecessary. If you have to take them every day, there is probably a deeper problem that needs addressing.

Intermittent fasting

I’ve previously written about two stressors, cold showers and exercise, helping me cope with various symptoms. At about the same time I’ve started experimenting with another stressor: intermittent fasting. Surprisingly, fasted state is when I have the best focus and productivity. I usually skip breakfast and only eat within an 8–9 hour window, with a big lunch and a big dinner (or two).

Fasting is a stressor that requires caution, but an intuitive approach works well for me. When the body stops telling me “This is uncomfortobale, but I like it” and switches to “Are you trying to kill us?”, it’s time to listen and eat something.

Supplements

I don’t like using supplements, because I often forget to take them. However, they are a great tool for controlled experiments. For example, I’ve taken pure glycine for two weeks with great results and after that incorporated a lot of collagen into my diet (with the same results).

It’s all just placebo and correlation doesn’t imply causation!

If everything I’ve experienced is a placebo effect, where was it for the previous 4 years? Out of the 50+ lifestyle changes, prescription pills, supplements and probiotics I’ve tried, only about 15 worked. If there was placebo effect, it must have been negligible. However, the good ol’ regression to the mean (patients getting better on their own) definitely played a role. Then again, I’ve tried relying on it many times before and it was never sufficient on its own.

How do I know the interventions listed above helped? Either I’ve done sufficiently many experiments or the effect was so strong it’d be impossible to explain otherwise. For example, after taking nonsteroidal anti-inflammatory drugs (NSAIDs) regularly, strong abdominal pain started. Wikipedia lists gastrointestinal problems as the main adverse effect of NSAIDs and they are also known to disrupt gut flora. Nothing has helped me for years. Then one day I tried Lactobacillus plantarum and the pain was gone within hours. Fixing other stomach problems took another 10 months, but at least the pain was gone. Also, L. plantarum is one of the few probiotics that performs in medical trials on people and in other studies, animals benefited from probiotics after being given NSAIDs.

A true skeptic would say that correlation doesn’t imply causation and that such evidence is not sufficient. Many people don’t believe successful stories and dismiss any kind of evidence, often because it contradicts their beliefs.

Skeptics are right that no evidence is perfect and we can never be completely sure. I admit I didn’t use an identical twin as a control group and I didn’t double-blind my fasting experiments. However, my personal experiments showed that skeptics are as likely to be wrong as the people they criticize. I’m glad I didn’t listen too much to sites like QuackWatch and Science-Based Medicine, otherwise I would probably avoid probiotics, cholesterol and fat for no good reason.

The new skeptic movement reminds me of the disagreement between academic skeptics and Pyrrhonian skeptics 2 millennia ago in Greece. Academic skeptics claimed “Nothing can be known, not even this” while Pyrrhonians viewed them as too dogmatic. I’m siding with Pyrrhonians here and my advice is: be skeptical, especially of skeptics.

This post is getting too long, so let’s take a short break with classical music.

Self-experimentation and its risks

A while back my mom told me to drink a particular herbal tea to alleviate some of my symptoms. I replied with “If this herb was effective, it’d have performed well in scientific trials and doctors would have prescribed it to me.” The statement does make sense, but it involves many strong assumptions and often isn’t true.

As an example, there is a drug called ramelteon, which binds to the melatonin receptors and for all we know it has identical effects to melatonin and performs about the same as melatonin in clinical trials. A monthly supply of melatonin is about $5 while ramelteon costs $100, yet doctors prescribe ramelteon instead of melatonin. Or one time I asked a Swedish gastroenterologist about her opinion on L. plantarum and other probiotics. She told me I know more than her and I should keep trying. This is despite plenty of successful clinical trials, many done on Swedish universities.

The previous two examples were cures that proved themselves in trials. Using fat and MCT oil in particular to increase the production of DAO has only been tested on rats. Perhaps it also works on people, but as far as I know no experiment was done on people, so doctors wouldn’t recommend it.

Medicine seems to miss a lot of treatments, so self-experimentation might be worth it. It does bear a lot of risks, so I evaluated possible adverse effects and monitored my health. For example, I’ve closely monitored my cardiovascular risk factors and they stayed the same or improved. However, I don’t trust these tests completely. A comprehensive heart-disease blood test would include 5–7 different blood values, but despite so many numbers, its predicting power is limited. I believe that there is too much focus on lipoprotein particle size and soon a more important risk factor will be discovered, so I’m not pronouncing myself completely out of risk yet.

Blood tests are tricky to interpret for another reason. Some blood reference intervals are calculated so that exactly 95% people fall inside them and it’s not always clear if sick people are included or not (see here or here). Unfortunately, many doctors don’t know that and would diagnose you sick or healthy solely based on these arbitrary numbers. It reminds me of a TV discussion with someone complaining that poverty in the US has stayed exactly at 20% of the population for the last 100 years. This came as a big surprise, so the moderator asked about their definition of poverty. “It’s the poorest 20% of the population”, the first person said.

So I take blood tests and reference intervals with a grain of salt. Perhaps more important is tracking values over time and comparing them with a younger version of myself.

Disclaimer: While I don't have a lot of trust in medicine and doctors anymore, a world with doctors is much better than a world without them. Doctors are awesome at fixing anything acute or live-threatening. Next time I break my leg into six parts while skiing, I'm sure doctors will do a great job. It's the chronic conditions where my trust disappears.

Further reading

I recommend 3 blogs for anyone interested in health and medicine. And one crazy idea.

• Whole Health Source: Stephan Guyenet is a neurobiologist blogging mostly about obesity but also other topics. He was one of the scientific advisors of the Perfect Health Diet book, but he would disagree with parts of it and his diet is slightly different, too.
• slatestarcodex.com/tag/medicine: Scott Alexander—the best blogger on the Internet—is a psychiatrist by training and often blogs about problems in medicine, including drug discovery, life-cycle of medical ideas and how skeptics exaggerate their claims. This blog hasn’t affected my life-style but it pointed out the common problems and gave me arsenal to evaluate medicine.
• Mosaic: A non-profit website with awesome scientific journalism about anything life related. Again, I learned a lot from this website but it hasn’t affected my life-style.
• If you like crazy ideas, Robin Hanson suggests to cut health care spending in half, since spending on health care doesn’t correlate with health outcomes anyway. I’m not buying it yet but the idea is worth pondering, as are all Robin’s ideas.

I’ve also read other websites and watched a lot of YouTube videos, but it’s a minefield that is very difficult to navigate. Especially nutrition discussions are often worse than politics or gender, with people citing facts out of context, ignoring evidence and sticking to dogmas. For example, many people benefit from vegetarian or low-carb diets and then preach them as the healthiest diets for everyone. Perhaps they are helpful in certain situations, but that doesn’t mean everyone should follow them or that they are safe in the long term. And some people don’t benefit from any diet, so they become radical skeptics and question everything. Usually there is some truth in each dogma, but some people take them too far.

Maybe this post is also full of untrue dogmas, misrepresented scientific findings and without contradicting evidence. Only time will tell. I tried to do my best, though.

ELS: latency based load balancer

You might have noticed that the Spotify back-end has been faster by about 0.47 milliseconds in the last 6 months. Read about my new algorithm in two posts:

1. The first one is simpler, has a lot of pictures, graphs and even three animations.
2. The second one has all the necessary math.

Swedish summer 2015

People said this was the rainiest Swedish summer ever, but I disagree. I slept 5 times in the Stockholm archipelago and each time without a tent. This is how we usually slept.

The best hotel in the Stockholm area. Cost: 0 SEK. Experience: priceless. At Angödrommen.

Maybe the weather was nice to me, since this was my last summer in Sweden. Stockholm archipelago, I'm going to miss you!

There is not much to write about all the trips I made, so let the photos speak instead. Don't continue if you are scared of swans, seals, mushrooms, spiders, snakes or dragonflies! A link to a full album is at the end of the post.

Finally getting dark at 11 pm

Swan family chose a vacation by the sea

Snake hiding in blueberries

Unknown water creature with many small legs

We thought we wouldn't be able to pass through at first. It turned out to be a channel made for kayaks.

Mirror sunset at Kolkböte

Happy people and happy sheep at Fjärdlång

Lonely mushroom

Dragonfly

We saw seals!

If you want to see even more wild animals, check the full album made from multiple cameras on Google Photos or a small selection of my photos on Flickr.

Nordic championships in programming 2015: behind the scenes

Nordic championships in programming 2015 (NCPC 2015) took place three weeks ago and I was the head of the jury for the third time in a row, together with Markus Dregi from University of Bergen. Last year I’ve written my impressions from behind the scenes and I’d like to continue with the tradition. Let me first mention 2 problems that I liked.

H – Hero Power

Hero Power involved a simplified Guitar Hero game. On Tuesday September 29, about 10 days before the contest, the task still hasn’t been solved by anyone from the jury. Not even Björn had solved it, the author of the task who worked on it for a couple of months. In addition to many rules that were also present in the final problem statement, at the time there was an additional rule that the SP meter charges by extra 5 seconds at the end of every SP phrase (the so-called 5-second rule).

The contest was near, so me, Björn and Oskar decided to have a meeting on the sunny roof of Spotify’s office. We wanted to simplify the problem but it wasn’t clear how. I claimed that combining continuous charging with 5-second bonuses makes it hard to solve: when you draw the content of the SP meter as a function of time, you get a non-continuous function and such functions are hard to grasp. In this version, it’s not enough to charge in continuous chunks, because taking breaks allows you to collect just the right amount of 5-second bonuses. This complicated the solution greatly.

I suggested removing the 5-second rule but keeping everything else as it is. Björn disagreed. It was getting colder on the roof and we had music to stream, so we agreed to disagree. I wanted to ask the rest of the jury for opinions and also write a solution myself. Perhaps my modification wasn’t that elegant anyway.

After dinner I sat down to write a solution. It was an obvious dynamic programming problem, but the update step turned out to be very tricky. After about 30 minutes of thinking I finally got it and wrote a super-short solution. It felt too short for such a hard problem, so I proved its correctness 2 more times to convince myself.

I mostly liked lines between 41 and 50, which contain dynamic programming, greedy strategy and amortized complexity on a very small space. Even the preprocessing step is non-trivial and uses the ‘resize’ function in C++ ‘vector’ in an elegant way.

I had one of those rare moments when you are taken aback by a beautiful computer program. It was even more rare, since the code was mine. The problem version without the 5-second rule turned out to be awesome on many levels, so I went to defend it on our mailing list.

I've just implemented a solution for the version without the 5-second rule and I'm stunned. This is pure poetry! 

The task is a beautiful mix of dynamic programming, greedy, amortized complexity and clever data structures (just arrays and hash maps, but clever still). All the steps are non-trivial to make it run in O(np).

My excited e-mail was enough to convince everyone to remove the 5-second rule. In the end it was still very hard and only 2 teams solved the problem.

I – iCar

In this task you have an iCar with only one button – when pressed, the car accelerates with the rate of 1 meter per second per second. Once you release the button, the car stops immediately. (Side note: we have considered adding braking instead of immediate stop, but the problem was already too hard.)

This is yet another task that was shaped greatly with time and with the help of the rest of the jury (thanks a lot, Marc!). Andreas Lundblad sent us a suggestion already in May and it was basically the same problem as it appeared in the contest. He could only solve it for one semaphore, though. I managed to figure out all the cases needed to solve it for 2 semaphores, so I told him we’ll take the problem and figure out the details later. At worst we have the 2-semaphore version, but I was curious about extending it to 5 or even 100 semaphores.

In the end we went with 20-semaphore It was a lot of work and it took us a more than a month to get it right. First, Marc generated test cases, but my code was able to find a shorter route to the finish. Later, Marc found the nasty case shown below that broke my solution instead.

The crucial step in solving the problem is choosing the right visualization. There are two important parameters, the position of the car given in kilometers from the start and time since the start. The third interesting parameter is speed, but you can actually skip that and infer it instead.

Two parameters can be visualized in 2D: the picture below has time rising from bottom to the top and position from left to right. It contains a solution that illustrates all the different cases a correct solution needs to handle. Red vertical lines denote red lights on semaphores. Blue parabolas and dots denote a car that is accelerating and stopped respectively.

Solution to 000-random-seed-144.in. Marc also created visualizations for all test cases that you can download from the contest webpage. 

The second parabola is passing the 5th semaphore at the last moment of a green light and then passing the 10th semaphore at the earliest moment of a green light. We could have passed the 5th earlier, but we’d have to have lower speed to avoid hitting a red light on the 10th. This strategy allows us to pass the 10th semaphore with the highest speed possible.

While this might sound complicated, we're still not done and it's only enough to solve the 2-semaphore version. To solve the problem with 20 semaphores, you also need to handle two more cases, which are the last two parabolas in the picture.

The very high speed we acquired allows us to be at the 12th semaphore during a red light. We could stop at the semaphore and wait there for a green light, but a better strategy is stop earlier, so that we can start accelerating earlier and have higher speed when the 12th semaphore turns green.

Finally, we stop before the 13th semaphore and start accelerating, so that we pass it at the last moment of a green light. Such waiting strategy paradoxically improves the time in the finish. A little bit of calculus can prove that.

In the end no one solved the problem and I kind of expected that. One could argue that this problem should have been saved for a more difficult stage like NWERC or World Finals, but I’m not sure. Even small contests like NCPC need hard problems to stop the best teams from solving everything.

Overall this is one of the top problems I helped preparing for a contest, because quadratic geometry is very unusual in programming contests.

The bad

Apart from fun problems, a couple of things didn't pan out so well. Problem G was solvable with brute force if you managed to optimize it well. Problems D and E were too similar. Too many pproblems were dealing with time events.

We knew about these issue before the contest, but it was too late to change things. We already skipped some problems and were down to 10 when we discovered issues with G. Skipping one more problem felt like a worse decision than keeping it.

We could have prevented it if we received more problem suggestions and more people were helping out. If you would like to prevent similar situation from happening, please send problem suggestions next year. Don’t hesitate even if you aren’t skilled in preparing competition problems, because there’s always other jury members that can help you out. For example, Hero Power and iCar were suggested by people with little jury experience and then received a lot of help from the rest of the jury.

Conclusion

If you like the stories from behind the scenes, don’t hesitate to get involved next year! You can mail me at [polacek (at) kth dot se] and I’ll add you to the right mailing lists.

I’ve now left Scandinavia and after 3 years as a head of jury I’ve quit. I’d like to be involved though and contribute a problem or two next year. I hope the quality of NCPC stays very high!

Underflow bug

Sometimes code needs to be executed 100 000 000 000 000 (100 trillion) times to hit a bug. Read my blog post for Spotify to learn more.

As usual, Reddit users were there to brighten my day:

• "Really surprised such a successful tech company produced such shoddy code."
• "This is remarkably shitty code. I would criticize pretty harshly anyone who wrote it. I would fire anyone who wrote a public blog post about it exactly like this post."
• "So basic edge case failure. Not even a corner case."
• "Yeah, not surprised that someone that thinks they invented the term underflow and used it wrongly got something like this wrong."
• "[the code] is, pretty obviously, broken at a glance"