I wrote SRM 564 (Except div1 hard)

The other day I was writing the editorial for SRM 562. I have noticed some trends in the topcoder problem setter list that made suspect that there is a scarcity of problems being submitted. I really didn't have a problem set prepared, but I gave it a shot and asked the admins if they need problems. They did!

But then I had to think of a problem set. My first reaction is try to finally use some of the problems I never get to use. You may suspect why. All the previous times I got a SRM assigned, I was close to use those problems, but something better appeared...

Until now! Unfortunately I just could not think of or find a problem that was good enough for division 1 medium or hard difficulties...

The Knights ones

This Knight circuits problem is very old. If my memory works, it is probably some of the first problems I came up with. Contemporary to my second problem set, probably.

When I thought of it, it seemed so edgy and good. But I could not use it until now. Nowadays, the whole "knight circuit = connected component" thing sounds so obvious.

There were two variations, the "harder" one was the one used in division 1. The easier one was, actually given a board with some blocked cells. So it was just solvable with a simple BFS. It was supposed to be used in division 2 as a medium.

I also proposed many other lame problems which were not in use yet.

The change in plans

The division 2 version of the knights problem was going to be used. But then ivan_metelsky, memetic tester opined that it was very boring, even for that slot. Proposed that instead, we could use a variation of the division 1 version, but with variable allowed moves for the knight. This also fixed the issue that the division 2 hard that I proposed was very standard. The new issue would be to find a new division 2 medium. Ivan proposed we go back to the original version of the palindromes (division 2 easy) problem that was harder. So then all I needed to do was find a new division 2 easy.

So, I suddenly had an idea for division 2 easy. Balls of three colors, getting alternated, find the color of the k-th ball. A simple simulation thing that at least was more interesting than the recent div 2 easies... I proposed it and it was accepted.

The most amazing thing happened after that. I went out to buy groceries, when in the way I suddenly started to think of how that alternating colors thing was so like some of my favorite problems that I wrote. Some ad hoc thing to do using a program as a starting point... Then I remembered a mantra: If you want to turn a simulation problem into a harder problem, turn it into a counting problem. I started to wonder how to solve a variation about counting the number of ways to have a certain ball color in a certain position. This variation was hard. So hard that it started to look good for division 1 medium. And it was!

Finally, I noticed that turning the division 2 easy about palindromes into a division 2 medium was going to take time to develop. Also the alternating balls problem was interesting to solve in O(k) time. So I asked to make that problem the division 2 medium instead of the previous plan.

What is going to happen?

I am writing this before the match. I think that the main complaint about the division 1 match will be that it is too mathematical. I do not know yet about the division 1 hard problem , but I hope it is hard and programmatic to compensate.

People will probably think division 1 easy was too easy. But division 1 medium will probably have a healthy success rate (not too low or too high). When I solved it, I took 4 hours, which is usual for me and division 1 medium. Since I thought division 1 easy was too easy, I left very weak example cases. I wonder how many people are going to fail the 3x3 case. I hate fake difficulty as much (if not more) as anyone else, but for this problem I think it was needed.

Division 2 will be very challenging. I actually needed help to solve the division 2 hard. Whereas division 2 hards are usually very simple and quick for me to solve.