www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - On D in competitive programming

reply Ivan Kazmenko <gassa mail.ru> writes:
Hey,

I wrote a post with my general reflections on using D in 
competitive programming.
Mostly compared to C++, since that's what more than 90% of people 
use for it.
The post is tailored to cover only the competitive programming 
specifics.

http://codeforces.com/blog/entry/60890
(en+ru, the language switch is at the top)

Ivan Kazmenko.
Jul 28
next sibling parent reply Cym13 <cpicard openmailbox.org> writes:
On Saturday, 28 July 2018 at 19:51:08 UTC, Ivan Kazmenko wrote:
 Hey,

 I wrote a post with my general reflections on using D in 
 competitive programming.
 Mostly compared to C++, since that's what more than 90% of 
 people use for it.
 The post is tailored to cover only the competitive programming 
 specifics.

 http://codeforces.com/blog/entry/60890
 (en+ru, the language switch is at the top)

 Ivan Kazmenko.
Thanks, great read :) I have some minor notes though: 1. Your real name isn't written in the article so the link "with some successes" won't tell much to someone that doesn't already know you 2. When you briefly explain templates I think it's important to mention that empty parentheses may be omitted to allow the reader to make the link between function!(arg1)(arg2) and map!something. Explaining UFCS isn't necessary there though I think since it's obvious that there is some kind of chaining at play (not that you did, just thinking out loud). Also I have a question: I find very nice that some platforms propose D even though not all do, but are they generally keeping it up to date with DMD or stuck at something ancient?
Jul 28
parent reply Ivan Kazmenko <gassa mail.ru> writes:
Thanks for the feedback!

On Saturday, 28 July 2018 at 20:33:14 UTC, Cym13 wrote:
 1. Your real name isn't written in the article so the link 
 "with some successes" won't tell much to someone that doesn't 
 already know you
Hmm, didn't think of it. I phrased it differently now. In my experience, the participants' nicknames in competitive programming are mostly tightly coupled with real names, and otherwise, the blog author's profile is one familiar click away. So for a local Codeforces reader, that hopefully wasn't a problem anyway.
 2. When you briefly explain templates I think it's important to 
 mention that empty parentheses may be omitted to allow the 
 reader to make the link between function!(arg1)(arg2) and 
 map!something. Explaining UFCS isn't necessary there though I 
 think since it's obvious that there is some kind of chaining at 
 play (not that you did, just thinking out loud).
Yeah, good point, mentioned it now.
 Also I have a question: I find very nice that some platforms 
 propose D even though not all do, but are they generally 
 keeping it up to date with DMD or stuck at something ancient?
It varies depending on the platform. A few examples: codeforces.com just recently upgraded from DMD 2.074 to DMD 2.079 (so I could show the compile-time writefln in the post); atcoder.jp is at DMD 2.070 but also has LDC 0.17.0 and GDC 4.9.4; codechef.com has some ancient GDC, barely usable; hackerearth.com has DMD 2.074.1; csacademy.com (Romanian competitive programming website) does not yet have D, but I hope they add it in a few months; hackerrank.com claims to have DMD 2.079, but recently stopped supporting it in live contests because of a paradigm shift. Namely, they now strive to supply the reading-from-file solution template for each problem, and apparently didn't get to writing it in all 35 languages they generally have. I offered my help, but the support was kind of unresponsive, so seeking another point of contact now. Generally, it seems to correlate with the health of the platform's backend. In my code in competitions, I tend to now use features around 2.070 so that they are mostly supported. Ivan Kazmenko.
Jul 28
parent reply Jim Balter <Jim Balter.name> writes:
On Saturday, 28 July 2018 at 21:33:04 UTC, Ivan Kazmenko wrote:
[snip]
 2. When you briefly explain templates I think it's important 
 to mention that empty parentheses may be omitted to allow the 
 reader to make the link between function!(arg1)(arg2) and 
 map!something. Explaining UFCS isn't necessary there though I 
 think since it's obvious that there is some kind of chaining 
 at play (not that you did, just thinking out loud).
Yeah, good point, mentioned it now.
Actually, map!something does not drop empty parentheses, so mentioning that does not help. Parentheses containing 0 or 1 arguments can be omitted ... and you omit them for 1 argument in 3 places, and no instances of omitted empty parentheses. And I think it would be less confusing to an unfamiliar reader to mention UFCS, because the chained calls don't fit the function !(args1) (args2) syntax that you mention. [snip]
Jul 29
next sibling parent Cym13 <cpicard openmailbox.org> writes:
On Sunday, 29 July 2018 at 07:51:00 UTC, Jim Balter wrote:
 On Saturday, 28 July 2018 at 21:33:04 UTC, Ivan Kazmenko wrote:
 [snip]
 2. When you briefly explain templates I think it's important 
 to mention that empty parentheses may be omitted to allow the 
 reader to make the link between function!(arg1)(arg2) and 
 map!something. Explaining UFCS isn't necessary there though I 
 think since it's obvious that there is some kind of chaining 
 at play (not that you did, just thinking out loud).
Yeah, good point, mentioned it now.
Actually, map!something does not drop empty parentheses, so mentioning that does not help. Parentheses containing 0 or 1 arguments can be omitted ... and you omit them for 1 argument in 3 places, and no instances of omitted empty parentheses. And I think it would be less confusing to an unfamiliar reader to mention UFCS, because the chained calls don't fit the function !(args1) (args2) syntax that you mention. [snip]
While it's certainly not exact I think it's fine, there's no need to rewrite the language specification. Even for the parentheses, once you know they may be dropped in unambiguous cases you are bound to assume that the author didn't start talking of the ! sign for no reason and that you ought to consider that parentheses may be dropped even not knowing all the reasons. The same goes for UFCS, it's made very clear by the article that the functions are chained. Whether they are actually functions, or function templates or methods or something else entirely isn't important. I think the reader can be expected to understand how it works without understanding why. They even know what the program does already so the chaining part isn't hard. Maybe I was wrong that it needed any addition after all. Or maybe the explaination of templates should be more streamlined toward what is in the code like “map here is a template, the ! sign is the equivalent of <> in C++" and no more.
Jul 29
prev sibling parent Ivan Kazmenko <gassa mail.ru> writes:
On Sunday, 29 July 2018 at 07:51:00 UTC, Jim Balter wrote:
 Actually, map!something does not drop empty parentheses, so 
 mentioning that does not help. Parentheses containing 0 or 1 
 arguments can be omitted ... and you omit them for 1 argument 
 in 3 places, and no instances of omitted empty parentheses. And 
 I think it would be less confusing to an unfamiliar reader to 
 mention UFCS, because the chained calls don't fit the function 
 !(args1) (args2) syntax that you mention.
While that's technically right, I'd like to skip further explanations of the syntax. The same as I skipped why the problem is solved by such code at all (and it's even less obvious). In both cases, careful explanations would require a good paragraph or two, but are beside the point. The point of the article is more to just show how it feels and to spark interest than to explain everything. On the other hand, if I had to write a guide for competitive programmers on how to use D, such things sure would be included. Ivan Kazmenko.
Jul 29
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 7/28/18 3:51 PM, Ivan Kazmenko wrote:
 Hey,
 
 I wrote a post with my general reflections on using D in competitive 
 programming.
 Mostly compared to C++, since that's what more than 90% of people use 
 for it.
 The post is tailored to cover only the competitive programming specifics.
 
 http://codeforces.com/blog/entry/60890
 (en+ru, the language switch is at the top)
 
Good read. a lifetime ago, I competed using topcoder (and wrote a bunch of problem sets for them too). Topcoder had a "challenge" phase, where you could challenge the solutions of others. Is there anything like that in codeforces, and if so, is D an advantage as a "somewhat obscure" language (i.e. competitors can't always understand your code)? Just curious :) -Steve
Jul 30
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 30.07.2018 21:44, Steven Schveighoffer wrote:
 On 7/28/18 3:51 PM, Ivan Kazmenko wrote:
 Hey,

 I wrote a post with my general reflections on using D in competitive 
 programming.
 Mostly compared to C++, since that's what more than 90% of people use 
 for it.
 The post is tailored to cover only the competitive programming specifics.

 http://codeforces.com/blog/entry/60890
 (en+ru, the language switch is at the top)
Good read. a lifetime ago, I competed using topcoder (and wrote a bunch of problem sets for them too). Topcoder had a "challenge" phase, where you could challenge the solutions of others. Is there anything like that in codeforces, and if so, is D an advantage as a "somewhat obscure" language (i.e. competitors can't always understand your code)? Just curious :) -Steve
On codeforces it's called "hacks", but it happens during the contest. Therefore, if your solution were to be "hacked" it would actually likely be good for you because you get a chance to fix your code before the contest ends.
Jul 30
prev sibling parent Ivan Kazmenko <gassa mail.ru> writes:
On Monday, 30 July 2018 at 19:44:32 UTC, Steven Schveighoffer 
wrote:
 a lifetime ago, I competed using topcoder (and wrote a bunch of 
 problem sets for them too). Topcoder had a "challenge" phase, 
 where you could challenge the solutions of others.
Nice! I just found your profile and problem sets from 2003-2004. I started using TopCoder in 2005, didn't see these earlier.
 Is there anything like that in codeforces, and if so, is D an 
 advantage as a "somewhat obscure" language (i.e. competitors 
 can't always understand your code)?
Yeah, in a way. The challenges are called "hacks", and can happen for the whole duration of the contest. But to hack solutions for a problem, you have to first write your own solution to this problem, pass preliminary tests with it, and lock it so you can't resubmit. The key difference is, when the hacked solution itself was not locked, it still can be fixed and resubmitted (with a score penalty), which is actually a win-win. As for how a different language helps, well, perhaps it does. But, sadly, competitive programming style often goes against readability, to the extent the language allows it. In that regard, somewhat unexpectedly, I find other languages (e.g., Java or Python) more readable than C++ despite the fact that I'm less experienced with them. In C++, most competitive programming code contains a bunch of the author's exclusive #defines for the language shortcomings (or worse, #defines just to save typing). And since #defines are so flexible, everyone has their own version of the language, and some of the resulting code is straight unreadable without a deciphering effort. Ivan Kazmenko.
Jul 30
prev sibling parent reply 9il <ilyayaroshenko gmail.com> writes:
On Saturday, 28 July 2018 at 19:51:08 UTC, Ivan Kazmenko wrote:
 Hey,

 I wrote a post with my general reflections on using D in 
 competitive programming.
 Mostly compared to C++, since that's what more than 90% of 
 people use for it.
 The post is tailored to cover only the competitive programming 
 specifics.

 http://codeforces.com/blog/entry/60890
 (en+ru, the language switch is at the top)

 Ivan Kazmenko.
Hi Ivan, Are competitors allowed to use mir-algorithm and mir-random? The libraries can be used for graphs (Tarjan algorithm), matrices/tensors, nd-iteration, RNGs, interpolation, and distributions? It would be nice to have this feature, as mir-algorithm can be a good default library for competitive programming. Plus competitors can add additional graph algorithms. https://github.com/libmir/mir-algorithm https://github.com/libmir/mir-random Best, Ilya Yarosenko
Jul 30
parent Ivan Kazmenko <gassa mail.ru> writes:
On Tuesday, 31 July 2018 at 00:52:22 UTC, 9il wrote:
 Are competitors allowed to use mir-algorithm and mir-random? 
 The libraries can be used for graphs (Tarjan algorithm), 
 matrices/tensors, nd-iteration, RNGs, interpolation, and 
 distributions?
Sadly, no: most of the time, language compilers on the server side are provided as they are out-of-the-box. I'll try to explain why. When a language is added to a competition, one of the goals for the organizers is to keep the whole thing fair. Different languages have different pros and cons already as they are, and what is an implementation-heavy problem for one language is solved in a couple lines with another. So, the availability of several programming languages already puts some burden on the problemsetters: at least for important competitions, they have to come up with problems which don't play too much into the strengths of any particular language, and that means knowing what to generally expect of all the languages. For example, most problems don't rely on number crunching with integers above 64 bits, since C++ is notoriously lacking in this regard. This all gets a new dimension if a platform decides to supply additional libraries. Once it's done for one language, there are no clear boundaries: if we get mir-algorithm for D, we will have to at least install Boost for C++, and numpy for Python, and the users of other languages also ask for their favourite libraries, which are in turn more powerful than Boost, and so on. And it would take significant expertise to balance such requests so that no language has too much of an unfair advantage or disadvantage. It takes a bit of expertise too to keep the libraries in all languages working and up-to-date. All the way, the problemsetters now have to avoid a different set of topics, changing with new libraries being added. Yet another factor is that there are central competitions perceived as the most important, which are currently ACM ICPC World Finals for university teams, and their regional contests. Many platforms strive to act as training grounds for the important competitions. So when the World Finals, which are understandably conservative, don't do X, it's a disincentive to do X for the training grounds too. So, the default approach is to keep each language at a bare minimum.
 It would be nice to have this feature, as mir-algorithm can be 
 a good default library for competitive programming. Plus 
 competitors can add additional graph algorithms.
It may still be reasonable to ask for additional libraries on the platforms where the focus is not some big competition: e.g., perhaps no for ACM ICPC archives, perhaps yes for interview training sites. For a particular platform and a particular cause (e.g., a training course for a learning platform), it's entirely possible to have D with mir-algorithm installed on the platform. Ivan Kazmenko.
Jul 31