Hi!
Next year I'll start working on my Master's thesis (in computer science), and we have to choose the subjects now. I'm not very enthusiastic about the subjects that are suggested by default but we are allowed to suggest our own topics if we want. So I got an idea: what if I could work on a topic related to competitive programming?
I have good relationships with some of the teachers so I should be able to convince one of them to accept it if it's an interesting subject. But it's not that easy to find a good subject on that theme.
An example I thought of would be to study the current state of the art in a subfield like geometry: which kinds of problems appear in which competitions, which algorithms are considered common knowledge, which kinds of implementations are used, how precision issues are dealt with, etc. I would try to summarize that and to figure out by reviewing the research litterature which new algorithms or techniques might appear in the future, thanks to which implementations.
So, do you have any ideas on interesting subjects to study? It can be about any aspect of competitive programming, also including coaching, contest creation, etc. I'm also a trainer for future IOI contestants and a novice problem setter so those subjects interest me too. I'm excited to hear your ideas!
Of course, if the subject gets accepted, I would keep you informed and post regular updates over here (your feedback would be a great help)!
Thanks in advance!
There are a large number of good thesis topics related to competitive programming. Also, there is not much scientific research on competitive programming, so if you write a good thesis, it may become an important reference.
"State of art in X", as you suggested, could be a good choice. What is your favorite field in competitive programming? You should choose a topic that you like, so it will be easier to write a good thesis.
I'm one of those weirdos who like geometry, so that would be my first choice. :)
Nice problem for problemsetters: generate big non-convex (or even convex) polygon. I remember that it's a pain, maybe Zlobober can provide more insight.
That seems like an interesting problem indeed!
Does anyone know what exactly makes it difficult, that is, what special properties this big polygon must have? Obviously if the only problem is size then it's not that complicated, you can just have a basic formula whose parameters you can alter, like placing random points on a circle for convex polygons.
I guess a good non-convex polygon must have many hooks and tentacles and nested parts, with wild variations in scale. Is the main aim to test the runinng time of programs or to provide with tricky corner cases that even the problem setter did not think of?
The criteria can probably vary a lot depending on the particular problem, but is the aim to develop a general random polygon generator which works for pretty much any problem? Do you have examples of problems where it is particularly difficult to create such polygons?
Example problem: given a polygon and a sequence of points, output whether or not each point lies inside the polygon.
Another one: given a set of segments in order, decide whether it's a simple polygon (no self-intersections other than of adjacent segments in points).
Nah, I stopped writing problems that require generators harder than the problem solution itself :)
I actually prepared a problem in 2012 that required generating large and not necessarily convex problems. I used some pretty primitive approach like throwing a random set of distinct points at the plane, joining them into a closed curve in a random order and then starting the process of transforming all the x-intersections into =-intersection by replacing the ab and cd with ac and bd or ad and bc.
This process eventually converges since the total length of all segments decreases after such transformation, but it was pretty slow and worked only for polygons of ~200 vertices.
I also used some fixed type generators, of course. Like simply sorting the set of random points by the polar angle or drawing a Hilbert curve. It was more than necessary for that problem, I think.
Once I prepared a problem that required of a large planar graph (~300 000 vertices) image as an input. Well that was a real nightmare.
Wouldn't some sort of travelling salesman approximation work for the polygon thing? I'd imagine that taking a nearest-neighbour approximation as starting point followed by transforming x-intersections would work well. Or maybe just using some state of the art approximation algorithm from a library.
Actually, since you say there are a large number of good thesis topics related to competitive programming, can you think of topics which would not be of the "start of the art in X" type? I'm trying to get a better idea of the range of topics that could be interesting, to leave myself more options.
By the way, I've recently discovered your book, and it's fantastic! It will certainly be a great help in our trainings for the IOI. :)
Here are some examples of such topics:
As you can see, they are not purely algorithmic topics, so they may be more or less interesting, depending on what you want to focus on.
Thank you for your kind words about my book :)
Just an idea: analyze how different topics appear in competitive programming. Are dp problems more common than geometry? (just an example) Also, why some problems are more common than others (easier to implement or understand or other reasons).
See if you can find any patterns by type of contest (long contest, SRM, CF round and all other kinds) or by author.
If you are into machine learning, try to predict what kind of problems will be in some round if you know the topics for all problems in that year. (more precisely: dp can be either l.i.s. or bitmask or another subtopic).
Thank you for the idea!
It sounds like it might be difficult to gather large amounts of data on problem types. When there's no tags for problem types, it seems that the best way would be to just read the problem statements one by one and determine the problem type by hand. But maybe you had other ideas in mind for gathering the data?
In terms of prediction, I'm not particularly into machine learning, but it sounds like it would be quite difficult to be significantly better than a well-informed human. ^^