Life with chronic headache

In two days I am going to reach a important milestone. My headache is going to turn 4 weeks old! Imagine that. It is a very weak headache. If you want to feel how I feel, grab a shirt, make it a ball and put it above your head. Now imagine it is above your head all the time. E.g: When you wake up. Now imagine the shirt is invisible, so you shouldn't be feeling the shirt. Now imagine that the shirt becomes heavier during the second half of the day. It is mild, so mild that for days I was not sure it was a headache, maybe it was a numbness? But when I describe it to people they say it is what they often feel and call a headache. Doctors don't seem worried, it is either tension in my neck or a transformed migraine. But it is difficult not to focus on the fact that it is about to reach its fifth week!

The most likely explanation is that the stress I was going through one month ago somehow triggered this. It could be the cause of the tension in the neck. Or it could have been the thing that transformed my migraine.

Surprisingly productive

Because it is such a weak headache and because distracting myself with things, the first weeks were surprisingly productive. The more I worked or exercised the less I would get to feel/remember the stupid ache.

This may be the reason I was actually able to score a SRM problem set. I know that the problems really sucked this time. But keep in mind that I have been going through a long dry streak before this, not being able to think of problems.

Attempts to get rid of it

So if it is tension, you try to relax. It sounds so easy, really. Although quite honestly, I don't feel as stressed as one month ago. I really think I am calmer now. But maybe I am not. In attempts to relax, I tried massage with a stupid automatic chair called ceragem. I was wary of this because of all the new age rubish it promised. Then I tried it and it was awful. Do you remember "Modern Times"? I refer to the scene in which the poor guy falls into the factory's gears. It feels like that, but also with heat. The good thing about this torture is that at least it distracted from the headache. But no thank you. Not worth it. Not worth it at all.

The sleep thingy

A study with more than 40 women that had chronic headaches, split the group of people in two. They gave instructions about sleep habits to half of them. And placebo instructions (Fake instructions that sound like health advice but are not supposed to do anything) to the other half. Apparently a good quantity of women from the first half eventually reverted back to episodic headaches (Which is the best I can hope to get, not to cure my headache but to return to the good ole days in which headaches happened only once every two weeks). I figure that the 5 sleep habit instructions probably can't hurt (plus they are things that are usually agreed to be healthy things to do), but if they worked it would be wonderful:

• Keep a strict sleep schedule. Always 8 hours. Always going to bed at the same time (allowing a 30 minutes variation). Always wake up at the same time.
• No watching TV, no reading, no music while you are in bed.
• Using a visualization technique after getting to bed so that you start to sleep without distractions
• Avoid eating 4 hours before bed time. Drinking 2 hours before bed time.
• No naps. Not even if you are sleepy. Not even if it is fun. Not even with permission from your mum.

Oh boy, so I thought to myself. "Ok, I have basically no strings attached to me that would stop me from keeping a sleep schedule. So this is doable". Years ago I bought the idea that you only need 6 hours of sleep, or perhaps only four and that it was wise to only go to sleep when you are feeling sleepy. So I stayed in front of the computer up until 2:00 AM most nights. Slept around 5 hours a night in average, and maybe took short naps at the afternoon. I thought this was a clever way to do things, and definitely, with time I ended up not needing a lot of sleep a day... ... But now, if losing this sleep superpower was the price to pay for not having a constant headache, it seemed worth it...

Keeping a consistent sleep schedule...

It turns out that this was incredibly difficult. First of all, since my bed time and my awake time have to be roughly the same every day (EVERY day), I had to be careful picking the times. I picked 11:00 PM - 7:00 AM. Because I need to wake up at 7:00 AM to take my blood pressure medicine. This instantly kills my aspirations to participate in morning SRMs :(. But there is no other way, I guess.

However, my body is not very used to the idea of sleeping 8 hours. And throughout these 2 weeks I have been trying this sleep schedule, I have constantly waken up in the middle of the night. Feeling without any need to keep sleeping. But I have to go back to sleep or else the change in sleep habit is not going to have a real effect. I think there is a link between the headache and sleep, because on the days after the nights in which I sleep less time, my headaches are a bit worse.

No doing anything in bed

This is incredibly difficult to me. And honestly, it is almost a 1st world advice. I think people who own a real house can probably afford having all their stuff outside their bedroom. In my case, we have four people living in the same apartment. My bedroom is the only place besides my computer desk where I can work at. I don't have space anywhere to store my LEGO sets and tons (and tons) of bricks inside tupper ware (Really, I have tons of LEGO bricks, tons). So my bedroom was the only place where I could work on LEGO stuff. So far I am quiting my LEGO hobby at least for a while, because I can't do anything on bed. Also, my consoles and my TV are at my bedroom. There is no space elsewhere. So lately I only have my computer and my bedroom is deserted, not sure what to do with this. (No, seriously, I have so many bricks, all classified and sorted by shape and color, that I have almost no space in my bedroom).

Visualization technique?

Nah it sounds silly, plus I can start to sleep without much issue. It is the waking up in the middle of the night that is tormenting me.

No naps

The point of not having naps during the day is that it will allow you to go to sleep easily at the scheduled time. It works in theory. But some days it gets difficult because you didn't sleep too well last night. Although lately my body has been getting used to this.

No eating/drinking too late

This is another thing that is not very viable. So I go to sleep at 11:00PM. It means that in order to eat four hours before bed, I would have to finish eating at 7:00. It is impossible for there to be food at home before 8:30 PM. Sometimes we eat at 10:00 PM. This is something I can't help.

The study said that all the women who followed all FIVE new habits reverted their chronic headaches to episodic ones. But missing one of the habits reduced the probability of success. Since I can't do many of these habits and one of them is rubish, then all my success rate depends on putting all my strength and will power in the sleep schedule, not doing anything other than sleeping in bed and not having naps. These changes have been the most difficult change ever. And I say this after the month in which I successfully switched to eating only 50% of what I used to eat and doing regular exercise. It is incredibly difficult to wake up at 6:00 AM and not just go the computer. It is also difficult to wake up at 7:00 AM, and not stay in bed 5 more minutes. Actually, I miss staying in bed without doing anything. Now whenever I am in bed it is me trying to sleep.

Oddly productive

But there is something surprising about the new sleep habits. What is true is that I now have far less time to use my computer than before. I spend more time in bed trying to sleep. And I think that I am sleeping more time than I became used to sleep these last 7 years. But the strange thing is that I feel more productive. I think that before I had more time, but I used to spend plenty of that time in doing nothing. Instead , this month I would do strange things like write an editorial, write a compiler (From working C-like syntax to GNU assembly code) and continuously improve solutions for a TopCoder Marathon. All at once during the same week. I don't remember the last time I was this productive. But I suspect it was since before I started to sleep only at 2:00 AM. Although this could all be the placebo effect.

Leaving coffee

Something funny happened last month when I was trying to stop having stress. I decided to quit coffee. A week after I quit coffee, I noticed I was feeling worse, so I starting drinking it again. It is likely a coincidence, but 1 day or maybe 2 days after I started to drink coffee again, the headache started. So I stopped the caffeine once again a week ago. This last week has been miserable, because lack of caffeine apparently has a withdrawal effect. This is a very hard change, because I used to drink two cups of coffee a day, one during breakfast and one at the afternoon (A meal that around here is called "Tea time".) No offense to milk drinkers. But milk is really not as delicious as coffee. In fact, I't rather drink plain water, and that is what I have been doing during the afternoon "Tea time". Water. Just water. During the breakfasts, I just fill my cup of milk with a ton of corn flakes. They distract me from the awful flavor of milk.

It is going to be a long battle

If tomorrow, when I wake up, it turns out I do not feel anything funny in my head. It will be the happiest day of my life. However, I think I stopped having such a hope after the 9-th or the 10-th day of really thinking that maybe the next day was going to be the day. Eventually, the headache will end, but it is likely going to take a while. It could end after a whole year or it could end tomorrow. I have no idea.

SRM 579 - Disaster averted?

Yep I helped write the problem set this time.

I gave up trying to write div1 500s and div1 1000s. It has gotten a bit difficult to get things that are interesting and difficult enough for these slots. So I sent the admins some ideas for problems for the easier slots. Hoping that maybe there is a coder out there with the exact opposite issue - all his problems are too difficult for the easier slots.

UnlicensedPrimalCreatures

I thought of this one some time after playing a game. (Pro-tip: Spell Grez backwards). Seemed appropriate for div2 easy.

There are some creatures of different power levels. Your creature wants to defeat as many opponents as possible. A creature can only defeat creatures with a strictly smaller power level. When you defeat a creature, its power level divided by 2 is added to your own power level.

Just sort the creatures. If you make sure to always attack the weakest available creature until you cannot defeat anyone your power level will be maximum possible at the time you face any given creature. (If you face creature #i, you can assume you have already defeated all the creatures before).

UndoHistory

I dunno, I thought of this during a rush.

Initially UndoHistory = { "" }, Buffer = "", and contents = {}.

If you type a lowercase letter, then Buffer = Buffer + (the letter). And the new buffer is added to UndoHistory

If you press enter then Buffer is appended to contents[].

If you double click, you can do Buffer = (any element of UndoHistory)

You are given lines an array of strings. What is the minimum number of (key presses + mouse clicks) needed to make contents= lines ?

Let us say you are interested in typing the contents of the i-th element of lines, you can assume that all of the previous elements were also typed and added to contents. This means that all of the prefixes of each of the previous elements are in UndoHistory.

So we have two choices: a) Restore an element of UndoHistory (Always restore the one with the largest common prefix as lines[i]). And b) If the buffer is currently a prefix of lines[i], you can also continue typing. Note that there are times where even if b) is possible, it is still better to do a).

MarblePositioning

I proposed this problem for a previous SRM as a div2 hard. IT was rejected because it was too easy. So we tweaked that match's div1 250 into a problem that ended up being too hard. So now we prefer to try this "too easy" problem.

Given a list of up to 8 circles each with a given radius, line them up over a straight line so that the distance between the tangent point of the line and the left-most circle and the tangent point between the line and the right-most circle are as small as possible. You can place the circles in any order and they should not overlap.

A classical problem, since 8 is very low, we can try any permutation, what is left is to find the minimum distance given the chosen order.

Place the first circle, there is no condition to follow, so just place it at position 0.

Then whenever you place circle i, find the minimum position larger than 0 at which you can place the circle without overlap. This means that it should not overlap with any of the previous circles. For each of the previous circles, you can find the minimum positions at which circle i can be placed without overlap. The maximum of all these values is the new position for i.

Given two circles of radius r1 and r2, the minimum distance between the tangent points should be one such that the distance between the centers is exactly r1 + r2. The centers are located at (0, r1) and ( min_dist, r2). So you only need to solve an equation. The result is 2*sqrt(r1* r2).

TravellingPurchasingMan

I wrote this problem aeons ago. We even developed it and test cases. But we decided that it was too easy/not interesting enough for division 1 500 and put another problem instead.

This week, when I was offered the chance to write most of the problems of SRM 579, because someone else (Turns out it was ir5) had a div1 hard but no easier problems. We didn't have a div1 500. On Wednesday, I thought of a problem that seemed *WONDERFUL*. It was a lovely little problem with a interesting solution. However, just last night we found out that the interesting solution was wrong. There was still another interesting solution, but it would have been too hard for div1 medium. So with less than 16 hours before the contest, we had no viable div1 medium.

I remembered about TravellingPurchasingMan. It is very easy, but at least it exists - However, we had to spend the last 4 hours tweaking this problem so that it is not awful. It initially had 14 interesting stores. But since the problem was looking too easy we increased it to 16. It also had a much more complicated input format that required far more parsing. It was too annoying so we had to work into removing all that mess.

The solution is a strange dynamic programming one.

Edit: I regret nothing. And no, this is not a "standard TSP by dp", you still need to figure out that edges depend on the minimum time of your current vertex. And just because this extra step is trivial for you, it does not necessarily mean it was trivial for everyone (And the submission rate suggests it wasn't). Let me be frank: Not all div1 500s have to be made with the high level yellows and reds in mind. Quite honestly, we are sick of you guys being the only ones that solve more than one problems. If you could solve this problem easily, then great news! At least this time you had time to try and solve div1 1000; And since you are so good, I bet you solved it, right?. Meanwhile, at least more coders in the blue and mid to low yellow were able to enjoy more than *ONE* problem in a TopCoder match.

Also, it was either this problem or an alternate version of the marbles div2 hard with n<=10 we didn't have many choices, you know.

Editorial for TCO round 2C hard: WellTimedSearch

It is ready: link

What a nice problem. Of course misof was the problem setter. It would have been obvious if you solved the contest before the Problem Writer guessing contest. This is not the first twist on binary search that misof pulled.

I still think the top-level idea of my initial idea during the match was sort of correct, dynamic programming + ternary search, but there is no viable way to make it run in time.

TCO 2013 round 2C: bummer (And editorial for 250)

For some minutes I felt like I actually solved the hard problem during a match. It was short-lived, because I quickly figured there was no way it was correct.

250

Link to problem statement.

I opened this problem. Somehow I figured up quickly that everything depended on the distance between the Foxes. But I spent time trying to prove myself of it. I coded a solution that seemed correct and passed examples (Recursive logic that divided by 2), was about to submit it and I figured that there was something wrong with it - You can't introduce the same Fox to multiple people during a song -. I predicted that this was going to be a juicy challenge case. I fixed it up, but it was very late. I could only score 170-ish points. I was not going to advance with just that.

The editorial for this problem is finished. You can read an explanation there. I am trying a new approach and it is to develop a problem's editorial as soon as I understand the problem. Instead of waiting to solve the other problems... This should make editorials faster. I think.

500

Link to problem statement.

For some reason I missed the "simple" dynamic programing solution. This problem seemed harder than it was, so I decided to open the 1000.

1000

Link to problem statement.

I actually thought I could solve this thing. I thought of something involving ternary search.

I think the top-level logic is sort-of correct (and I actually survived two challenge cases), but I took too many shortcuts. Returning 0 when the increment is too big is for example not really valid, because it could be possible to try to be lucky and still get more than A-1 moves. I figured out this mistake after submitting, there were 10 minutes left. I should have spent these minutes generating a test case with a distance of 49 for the foxes in 250, but I still wasted them trying to come up with a correct solution.

Challenge phase

I tried to generate a test case with 49 distance between foxes during intermission, but I was taking too long to do the ascii art. I should have made a python script to generate it for me. By the time I finished making the test case, the solutions in my room using division by 2 were all challenged.

I doubt I could have scored the 300 challenge points necessary to allow me to advance anyway. Although I could have possibly earned a t-shirt. I think though that I am going to win a TCO 13 t-shirt from the Marathon round I am participating at. So it probably does not matter.

I guess it is another year in which I do not get even close to advancing to the algorithm finals. Bummer.

Opinions, etc

It was a good problem set. I just need to improve.

Regarding the smug opposition to programming contests

It is an inevitable fact of life. A news bit will appear. Maybe it will be news about how the Chinese or Russian team won the ICPC, which forces Americans to come up with excuses. Or maybe it is news about someone winning the Hacker Cup, which forces programmers to come up with explanations as to why they didn't win it. The inevitable thing is that someone will start the discussion about how programming contests are not worth it. They don't teach you "real world" programming skills and they are bad metric for hiring.

There are times at which it just gets ridiculous. It could be an article about how Petr Mitrichev is such a high profile competitor and champion and ... Google hired him to improve their search engine and you will still find comments of the sort.

You know, I have spent my past life (A 7 years period is a life) in programming contests. I have plenty of things to say.

Real world programming

What I do at work consists primarily of X. Therefore, real world programming consists of X. Programming contests do not consist of X. Therefore, they are useless for the real world.

This is the part about these arguments that can really annoy me. It is an arbitrary separation between different parts of programming. A dismissive one. Because of course is some programming is not part of the real world, then it is most likely a game, or an illusion, or something like that.

In my case, I make my money from these contests so it is very difficult not to feel that they are very real things. But I know that I am an exception so let us ignore that little detail. It is true that most jobs in computer programming are different than the things you'd do in most programming contests. However, unless you are doing an internship, it is unlikely that a single activity will prepare you with the exact complete set of skills that will required for your job. You are not going to learn people skills from programming contests. But that doesn't mean that participating in these contests will make you unable to learn people skills. You can probably learn somehow. I am socially inept myself, but I know that plenty people that are into programming contests (and are better than I) are perfectly socially adapted people. I am pretty sure I am the odd case. Specially out of the samples I took from actual tournament finals I attended.

Programming contests won't teach you all the skills. So what? Spending your time in programming contests is not so different to spending it in the demo scene. Or in game modding. Personal projects. Hacking open source projects. Etc. You will not create a complete career of programming from this. But why is it that you think that you HAVE to? Some activities are just fun to do and that is good enough. Some activities are just entry points for something else. Some activities might allow you to learn a couple of things, but you will most likely need to do more than just spend time in those activities to have a complete learning process.

Anecdotally. I can tell you that you WILL learn some very real things. You will learn a lot about the programming language you pick. I learned 99% of my C++ knowledge from contests alone. You will learn about how to get an effective programming environment that suits for your needs. You will get used to coding and to enter into Code mode. You will keep your mathy brain hemisphere active and healthy. You will be able to quickly estimate if a piece of code will run in the time that you want given technical specs of a computer and other factors. You will be able to calculate big O easily. You will learn of your weaknesses and how to find and debug the most stupid bugs you could make. You will learn to make sure that something is actually correct before jumping to implement it. These are all very practical technical skills.

No one needs speed

There is a time component in contests. Therefore, only the fastest programmers win. Being a fast programmer is not good. We need code that is maintainable , not quick to write

I think this argument originates from having little/superfluous exposure to the programming contests world. It is true that most contests use speed as some sort of tie breaker when people solve a similar amount/quality of problems during a contest. There is a speed factor in the scoring. But I think that the outsider's eye might be getting the impression that this speed factor is far more important than it actually is.

It is very easy to fall into this trap when you are just getting started with programming contests. You assume that you are doing badly because you are not taking enough shortcuts when writing your code. Maybe because some of the top solutions are very bad role models, you get into doing awful things like abusing #defines, you mess up your code style and you begin to constantly rush when coding a solution. The thing is that after this transition to a speed freak, you begin to notice something strange: You are not improving that much. Maybe your score has improved, but you are still pretty much in the same tier as you were before. Worse, lately you are spending more time debugging your rushed solutions and taking a bit more time to solve the problems.

After all speed is merely a tie breaker. If you learn to solve the easy problems faster, you will still find yourself unable to solve problems that the better coders can solve. The amount of code needed during a contest tends not to be humongous, so the time it takes you to type it is not that important. If you jump quickly into typing a solution and the solution turns out to be wrong, you are going to take MORE time and you will like still get 0 points anyway. If you type something too fast or if you are careless with your code, you will also score a flat zero. You will find yourself reading your code more often than you write it.

Debugging is a vital part of programming contests. One that tends to be implicit and has a role that is hidden from the outsider eye. While you rush to type your code, you have to be careful to make it also easy to modify. You get used to things that are deemed good practices. Not because you like to follow the rules, but because you learned the hard way that you can get screwed by not following them. Programmers that finish a solution faster do it mainly because they have less bugs and they know how to debug themselves out. This is something that is evident from watching Petr's screencasts.

I used to be a programmer that rushed. With time I learned to still calm down. I discovered the hard way that coding solutions right away without making sure that they will work and rushing to type a solution very fast are ways to fail more often than not. I ended up learning a set of rules that I shouldn't break while coding. For example, I learned to avoid having multiple return values in a function because of the many times I had hard-to-catch bugs with memoization after breaking this rule. I learned that speed was not as important as theory and having a process to be able to convert new problems into problems I already solved. Contests do not only have a focus on speed, they have a far more extreme focus on correctness. In most of these contests, just a single wrong case will make your whole solution wrong. You learn to be careful of things that cause bugs. I developed an irrational phobia against floating point arithmetic.

I guess that there is a chance that those are just anecdotes and most people just code badly when participating in programming contests. There is still something important to say. If I started to type code twice as fast as I do. If I started to think of solutions twice as fast as I do now. I would still not be able to get better positions than the very top coders. I am talking about people that can solve in 20 minutes what I cannot solve in a week even with help. We are talking about a set of skills that is not as trivial as being "fast". We are talking about being fast when coming up to solutions to very tough problems. There is more than raw speed involved in this.

Concurrency is like super important, man!

The format is very limited so you never get to see parallel algorithms. (Or randomized algorithms, or approximate algorithms, etc.). There are technical parts of programming that are not dealt with, like caching. There are no interactive algorithms. Plenty of algorithms do not show up. Etc.

My problem with this is that it really overstates the importance of some subset of algorithms. I think that the algorithms you find in programming contests are varied enough. I also think that it should not be a matter of quantity. A good programming contest shouldn't be about how many algorithms you have learned. There is always time outside of algorithm contests to find/learn Voronoi diagrams in a library and they will be implemented much better than yours. They should be avoid solving problems. There is a standard set of tools that you will most likely use during a contest: Dynamic programming, Greedy, Binary search, BFS, DFS, Dijkstra, Max Flow should cover 99% of what you need. This is a good thing because it evens the grounds - Time you spent sitting in a classroom is not so important - . Theory is nice, but contests shouldn't be exams about how many algorithms you know. They should be more about the process of solving a problem. Reducing a problem to a combination of those 5 only tools is more interesting than having 1000 tools and knowing by memory what to use every time.

There is more to say about that argument:

I have never seen X in a programming contest. Therefore, they don't have it

Some of the criticism I read seem to deal with only a very partial view of programming contests and ignores that there are programming contests of all flavors and sizes. Most of the criticism seems to be really directed at the ICPC. The ICPC is, frankly, a terrible tournament*. Only universities are allowed. Only groups of three are allowed. Very ridiculous scoring rules (Probably what contributes to the perception that speed is all that matters). Weak example cases. Arbitrary rules for advancing teams that differ between regions. Even more arbitrariness in what allows a team to reach the regionals. Boring problems. Run all the test cases of a problem in a single program instance stuck to a gigantic queue. A lot of your usual criticisms of programming contests tend to apply mostly to the ICPC and similar. For example:

Language and technical limitations, Lack of multi threading, no concern about caching or external memory/ etc

Contests like the google Codejam or the IPSC don't have these limitations. Because your objective is to produce an output file rather than send source code to run. The IPSC is even better, because your algorithms are not limited to run only a few seconds per case. Although most people go standard in the Codejam, they don't have to. I don't have to. I have taken (limited) advantage of multi threading a couple of times. I think it should be possible for someone more experienced in concurrency to make paralel algorithms to solve certain problems. Since you run your code in your machine, you can go crazy and bother with far more technical aspects than usual. If you want to run each test case in one of the 120 computers you own, you can do it.

And those are only the contests that I have first-hand experience in. There were AMD sponsored contests in TopCoder that focused on multi threading and taking advantage of it. I never participated in them, but they existed.

Approximations, randomized algorithms, heuristics, interactive algorithms

Even online judges have this sort of problem every once in a while. But most importantly, the TopCoder Marathons and similar contests exist. A TopCoder Marathon is a contest that is very different to ICPC contests. There is not a correct answer. The author most likely will not have as strong of an answer as the best competitor. You need to keep improving your algorithms. The best algorithm wins.

(Because the best algorithm wins, there are many situations in which worrying about very low level speed matters. I remember having to deal with memory caching at least once. I know that the top level competitors in this setting go really low levels).

In addition, you do not only need to solve the problem. You need to know how to test your solution. I had to learn a lot about benchmarks and threading to be able to test solutions. I needed to be able to compare algorithms. This is usually how participating in a Marathon looks like.

Topcoder Marathons are certainly not the only contest that allows this. The IPSC has very interesting and nice problems that do not necessarily stick to the ICPC format. The codejam seems to be starting to try some problems like this. There are also plenty of similar contests that I do not have experience with.

Being able to read somebody else's code and find bugs.

Like really. Both TopCoder and Codeforces have this as part of their format. You can win extra points by quickly finding mistakes and the reason someone else's piece of code fails.

More professionally, though. TopCoder has invented a category of contests called Mod Dash. In this, programmers are paid to identify the source of an anomaly in a piece of software.

Actual software design and development

There are competitions in which you deal with having to design long lasting software. Development competitions in which making the objective is to develop the most maintainable code. Architecture contests... I feel like they are most likely very boring, but they exist.

To sum up

Programming contests are a fun activity. There is no shortage of opportunities to learn important lessons about programming. There are various kinds of programming contests for different tastes and interests. A programming contest may not open you the doors to the professional world, but they don't have to.

I am not saying that you should/must participate. If you don't like them. If you would rather do something else, go and do whatever you like. I think that in the programming world, the best you can do is something that you like. If you do it well, the opportunities will come by themselves.

_______________________________________________________________________________________

* I mean, we all owe the ICPC a lot for being a precursor to the programming contest paradise we are living in, and a lot of our competitors wouldn't have been part of programming contests if it wasn't for the ICPC. But it has really aged terribly.

Editorial for SRM 577 div1 hard: BoardPainting

It is up: http://apps.topcoder.com/wiki/display/tc/SRM+577#BoardPainting

I thought I understood the solution to this problem. During the match, I was pretty sure it was min cut but I had no idea how. Then rng_58 sent me an explanation on how to make the min cut algorithm. So during the week I focused on distractions such as trying to find a proof for the easy solution in div2 hard (Hardest solution to prove in a while, I am not even sure if it is possible to prove it :/). And then with trying to think of a good way to explain div1 medium.

Then yesterday as I was getting ready to explain this problem, I suddenly noticed that, although I understood the solution, I had no idea of why it works or how to think of it. So I spent some hours figuring things out. I think the explanation is still not very good though.

It is very impressive to find that this problem has a polynomial time algorithm. Back in 2007, the SRM 383 version of this problem taught me dynamic programming using bitmasks (Hence why I remember so much about this problem). Who would think it was possible to also learn max flow from it?

SRM 577 Editorial for div1 medium: EllysChessBoard

http://apps.topcoder.com/wiki/display/tc/SRM+577#EllysChessboard

It is finally there. This editorial took plenty of time mostly because I couldn't decide what to do with this problem (Besides of the usual time I needed to actually learn the solution, involved doing my best to understand google translate of Russian text...). It uses this idea to rotate everything 45 degrees. An idea that was already a bit of a logic leap back when it was used as the central idea to a division 1 hard 4 matches ago!. And now it is used as just a secondary step in div1 medium? That is odd. So I tried to look for easier solutions. But the easier solution is a bit harder to prove. Of course, my eternal headache does not help either, but I am getting used to it.

It is a fun problem, I would have prefered to see it with a bit larger constraints (so that easier solution does not work) and as a div1 hard. But in a match that is not mere 4 matches after SRM 573.

Google codejam round 1A: Nice

That was nice, rank 29-th is most likely my best rank ever in a GCJ round that is not the qualification one.

Preparation

I improved my multithreaded template. It now has much less overhead and uses proper Unix threads.

Problem A - The one with math

Link to statement

It must be a miracle that one ml of paint is good enough to paint exactly π cm². This makes it so, the amount of paint needed to paint a black ring of larger radius R and smaller radius r is exactly: R² - r².

This problem is a constructive one. Do it step by step.

We want to find the maximum value of x such that: t >= costToPaint(x). Where costToPaint(x) is the cost to paint x black rings. The value of x can be very large, but it does not matter, because we can use binary search.

So the new problem is to find a quick way to calculate costToPaint(x), in order to solve the large input, we need o(x) time (Note that this is small-o notation, not big O). Let us look for a O(1) one...

The first black ring needs ( r + 1 )^2 - r^2, the second one needs ( r + 3 )^2 - (r + 2)^2, the third one (r + 5)^2 - (r + 4)^2 and so and so. We need to find the sum for 1 <= i <= x of :

( r + 2*i - 1 )^2  - ( r + 2*i - 2 )^2

Sounds difficult? Not really. Let us get clever and...

(r + 2*i - 1)^2  - ( (r + 2*i - 1) - 1 )^2

Then...

 = (r + 2*i - 1)^2  - (r + 2*i - 1)^2 + 2*(r + 2*i - 1) - 1
 = 2*r + 4*i - 3
 = (2*r - 3) + 4*i
...

sum(1 <= i <= x, (2*r - 3) + 4*i ) = (2*r - 3)*x + 4*x*(x+1) / 2

So we just need to find (2*r - 3)*x + 2*x*(x+1)

Be careful with overflow... I actually took most of those 40+ minutes being perhaps too careful about it...

long r, t;
// we only need to know if the result of f(x) is greater than t,
// so if we surpass INF, we can just stay there...

long mul(long a, long b)
{
    if (a >= INF / b) {
        return INF;
    }
    return a*b;
}
long add(long a, long b)
{
    if (a >= INF - b) {
        return INF;
    }
    return a + b;
}
long f(long x)
{
    // sum 1 <= i <= x : 2*r + 4*i - 3
    // = (2*r - 3)*x + 4*x*(x+1) / 2
    // = (2*r - 3)*x + 2*x*(x+1)
    // = x * (2*r - 3 + 2*x + 2)
    // = x * (2*r - 1 + 2*x)   // 2*r is at least 2
    return mul(x, add(2*r - 1, 2*x) );
}

long solve()
{
    // max x: t >= f(x)
    long hi = t + 1, lo = 0;
    
    while (lo + 1 < hi) {
        long ha = hi - (hi - lo) / 2;
        if ( f(ha) <= t) {
            lo = ha;
        } else {
            hi = ha;
        }
    }
    
    return lo;
}

Problem C-small the one with guessing

Link to statement

Is GCJ jumping the shark? They seem to be trying unusual stuff too much lately. Ok, it is fun though. It reminds me of IPSC, and IPSC is just the best yearly contest ever.

My approach was to find every possible combination of cards (order does not matter), and find the probability that such setting happens. Then, for each list of products, try each combination of cards and calculate the probability that IF the card combination was picked, the products are those. After doing all that, pick the combination of cards that has the best total probability (Probability to get the combination) * (Probability to get the product). This got correct in the first try.

Problem B - the one with the schedule and energy

Link to statement

I estimated that as long as I solved B-small I would likely advance, so I focused on the easy problem instead of spending time in the large one.

At any point, you have between 0 and E energy, so you can never spend more than E energy in any activity. In the small input, E is at most 5, and the number of activities is at most 10, so brute force for the amount of energy you spend in each activity is good enough. 5¹⁰ choices in the worst case.

int E, R, N;
int v[10];

int solve()
{
    vector<int> spend(N, 0);
    int best = 0;
    while (true) {
        //cout<<"="; for (int i=0; i<N; i++) cout << spend[i]; cout<<endl;
        // simulate
        int e = E;
        int gain = 0;
        for (int i = 0; i < N; i++) {
            int s = std::min(e, spend[i]);
            gain += s * v[i];
            // I had min(e, e - s + R) instead of min(E, e - s + R) :(
            e = std::min(E, e - s + R);
        }
        best = std::max(best, gain);
        
        // next choice
        int j = N - 1;
        while (j>=0) {
            spend[j]++;
            if (spend[j] > E) {
                spend[j] = 0;
                j--;
            } else {
                break;
            }
        } 
        if (j < 0) {
            break;
        }
    }
    return best;
    
}

C small 2

After solving that B-small, I wanted to solve more. I could spend my remaining 40+ minutes in B-large, or the harder C-small. C-small-2 has many advantages, it gives more points, and since it is a small input, you will be able to know for sure if you when you got it correct. I also had a sudden idea for C...

It turns out that:

a) My generation of combinations was slow, it is possible to generate the combinations (sorted) directly and then calculate their probabilities.

b) Plenty of combinations are unlikely, you can consider the X combinations with the largest probabilities such that the sum of their probabilities is something large. At first I tried 0.5, but apparently it wasn't large enough. At the end I tried 0.99, ignoring the improbable combinations that add up to 0.01 probability is actually a significant optimization. And this omission will reduce your success rate only by 1%. The success rate has to be about 1/8 in C-small-2.

My first attempt was a time out. It turns out that my approach was not fast enough. I found a way to precalculate the product probabilities for each combination, so that I only needed an O(K) loop per combination per list of products. Second attempt was wrong (0.5 is apparently not good enough). Third attempt: I noticed that 0.99 is good and fast. Correct!

Incidentally, I needed 1.5 minutes to run the final solution. If not for multi threading, I may have needed 5 minutes or more...

int cardProduct[7];

string curr;
double fact[13];
double TOTAL;

set< pair< double, string> > possibility;
set< pair< double, string> > probable;

map<string, map<int, double> > probableProduct;

void rec(int x, char ch)
{
    if (x == N) {
        // calculate the probability
        double p = fact[N];
        int i = 0; 
        while (i < N) {
            int j = i;
            while ( (j < N) && (curr[j] == curr[i] ) ) {
                j++;
            }
            p /= fact[j - i];
            i = j;
        }
        p /= TOTAL;
        possibility.insert( make_pair(p, curr) );
    } else {
        for (char b = ch; b <= '0' + M; b++) {
            curr[x] = b;
            rec(x + 1, b);
        }
    }
}

void init()
{
    TOTAL = 1;
    for (int i=0; i<N; i++) {
        TOTAL *= M - 1;
    }
    fact[0] = 1;
    for (int i=1; i <= 12; i++) {
        fact[i] = i * fact[i-1];
    }
    curr = string(N, '?');
    rec(0, '2');
    double P = 0.001;
    for_each(q, possibility) {
        P -= q->first;
        if (P < 0) {
            probable.insert( make_pair(q->first, q->second));
            string x = q->second;
            map<int, double> product;
            for (int i=0; i<(1<<N); i++) {
                int p = 1;
                for (int j=0; j<N; j++) {
                    if (i & (1<<j)) {
                        p *= x[j] - '0';
                    }
                }
                product[p] += p / (double)(1<<N);
            }
            probableProduct[x] = product;
        }
    }
    
}

string solve()
{
    pair<double, string> best = make_pair(-1.0, string(N,'2') );
    for_each( q, probable) {
        string x = q->second; //a combination of cards
        double p = q->first; //probability to get those cards
        //calculate the probability to get each product
        map<int, double> & product = probableProduct[x];
        // probability to get all K products
        for (int i=0; i<K; i++) {
            if ( product.count(cardProduct[i])) {
                p *= product[ cardProduct[i] ];
            } else {
                p = 0;
            }
            
        }
        best = std::max( best, make_pair(p, x) );

    }
    
    return best.second;
}
    void read() {

TCO 2B editorial complete, SRM 577

TCO 2B editorial "complete"

You can find it here: http://apps.topcoder.com/forums/?module=Thread&threadID=787652&start=0&mc=1#1723854.

This was a long problem set to solve and explain hence the long time to finish it. I am still going through health scares but I think this one took so long primarily because I needed time to solve it. Specially the medium. Very interesting match, but I wish I would do better in tournaments.

SRM 577 - fail

In SRM 577, I first opened the 500, seemed interesting, but when some coders started to solve the hard problem before there were submissions for 500, I decided to open it. This hard problem really distracted me. I had a very strong feeling there was a flow solution, but I couldn''t put things together.

As usual, when there were 10 minutes before the end of the challenge phase, I opened the 250 points problem. I rushed to code something that was wrong. The bug that distracted me for most of the 10 minutes was that I calculated the expected sum of scores, and not the expected average of scores. When the coding phase finished, I noticed there was still a mistake, I was not handling the possibility that Elly could have a room of different sizes depending on luck.

To solve it, find the probability Elly ends in a room with t or t+1 people (Where t is N/R). For each case, find the average score. Combine results and done.