tafit3's blog

By tafit3, history, 8 years ago, In English

My surprise in the latest Surprise Language Round #8 got me thinking. What is a surprise? Everybody is surprised by different things. If someone is new to competitive programming, there is an easy way to surprise him: just let him multiply two numbers. The constraints don't even have to be 10^9, 10^5 is enough:) But surprising more experienced coders is much harder.

I like the problems that have some element of surprise or anything non-standard. The problems that somehow force the contestant to dig deeper. Something more than just reading the problem statement and converting it to DP. In the regular rounds most often the surprise comes from the missing knowledge about the particular algorithm. If I didn't know about the algorithm, I can google it after the contest, study it, add to personal library and wait for the next contest with similar problem. How can a problem statement be even more surprising?

There is a link between the time limit and the time complexity of the expected solution. Obviously. Is it that obvious? I don't write problem statements and the problem setters could probably explain it much better, but as I understand it, the time limit cannot be too big, because it won't force the contestant to come up with the clever solution, but at the same it hints as to what the expected complexity should be. I'd like to see the task in which the most obvious solution is O(nlogn), but the constraint is n<11111. Or maybe a little more so that it is not blatantly obvious that the O(n^2) solution will not be enough. But even if someone come up with O(n^2) coded in such a clever way that it would pass, it would still make the contestant think a little longer as to whether he should go for O(nlogn) or don't bother and implement O(n^2) more quickly.

Because of different programming languages picking such tight constraints might be difficult to achieve, but let's consider a choice of the programming language to be part of the solution. If you choose JavaScript and your solution TLEs, than maybe this wasn't a good language for this particular problem. I'm not saying that it should be a general rule for every contest, because regular rounds are important and I enjoy them very much. But just some of them might have a few additional quirks like that explicitly stated in the rules.

The non-helpful constraints could also be taken to the other extreme — the constraints so high that the only way to solve the problem would be to upload the solution that outputs: "This does not compute". It is often the case that the problem statement asks for some solution or "-1" if there is none. What if it was implied in the contest format (in the core rules of the contest, you know the magic numbers: 456, 4088) that there is a third possiblity, ie. that the problem itself is unsolvable (even if only for some special input data but within the constraints). It is so comfortable to just open a problem statement and think hard about the solution without taking into consideration that it might not have a solution at all.

Errichto and ainu7 wrote about the link between constraints and time limit (here and here), so am I right in thinking that there is a chance that the link may just start to break in the near future...

What are some other non-standard problem structures?

  • the interactive problems, eg. Bear and Prime 100

  • bots fighting against each other

  • distributed problems (like Google Distributed CodeJam)

There was something weird about the Distributed CodeJam rounds as opposed to regular CodeJam rounds. Some people were frustrated with the tester tool that DCJ organizers provided and there was also some unexpected placements of the contestants. JohStraat wrote "I got 7'th place! But why are people so weak in distributed? All of the problems were way easier than in normal rounds..." Everybody has their ups and downs, but when considering all the contestants of a particular competition as a whole, it is much more likely that red coders will have more points than blue ones as opposed to any other outcome. It is very interesting when there is a kind of imbalance with respect to the expected probabilities (Is there a formula for the weirdness and unexpectedness of the scoreboard, so that after the contest one number could sum up how "regular" it was?). When the results are not as predictable as in regular rounds, it makes one wonder how many of the algorithms are learnt by heart (or siting there in the carefully crafted library and waiting to be used) and how many of them are invented and coded during the contest. Don't get me wrong, I'm not saying that one cannot prepare before a contest (like prepare your own library... I do), but aren't the contests that render such a library almost useless somehow more exciting?

Is it difficult to come up with a problem that is solvable only when using threads, so that non-threaded solutions cannot pass? (I mean considering the hardware that already runs the judge)

Surprise Language Round #8 was cool, but still the earlier contests by Nickolas were more fun VK Cup 2015 Wild Card Round 1, VK Cup 2016 Wild Card Round 1. Kotlin is kinda-sorta Java and even though I have learned something new, Picat and J were in many aspects like nothing I have seen before and this is what makes the big part of Surprise in "Surprise Language Round".

I don't necessarily mean that all the contests should be surprising, but there could be some that are more crazy. Also I want to stress that in my opinion the craziness or the new crazy rule shouldn't be something that makes it almost impossible for the contestant to develop the solution during the contest. It's not about creating bad experience like Challenge24, where problem statements are incomplete or test data is wrong. The rule should be completely logical and yet make the contestant think in different ways than usual.

Everything that doesn't allow the contestant to use the tools he already has makes the contest more thought-provoking. What are your thoughts on how to make the contests more surprising? Or do you prefer regular rounds instead?

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it