Hi everyone, my team participated in ICPC World Finals yesterday and had a lot of fun. However, we noticed that Problem N did not have many solves (only 1 in-contest and none on Kattis), even though our team thought the problem was very fun and doable. Probably, the reason was because numerical algorithms are harder to write in competitive programming languages like C++ and Java.
To help explain the solution better, I made a very concise, annotated Julia notebook that solves the problem in only 16 lines of code. Hopefully you find it conceptually interesting and helpful.
Here is the link to the notebook as a PDF. Alternatively, if you have Julia and Pluto.jl installed, you can run the notebook directly from the source .jl file at this GitHub Gist.
Here's also the Julia code as a standalone program, if you would like to run it on AtCoder or another place. I compressed this program slightly more, so it is only 13 lines of code, including imports and code to read input:
Julia looks like a nice language for math heavy problems. Will codeforces add support for it in the coming update, MikeMirzayanov? AtCoder already has it.
I completely agree — Julia is a very interesting language from the PL perspective, with its super-fast dynamic JIT, macros, and simple syntax. It also has very practical aspects for solving numerical problems ergonomically.
The only thing I am worried about is JIT compilation/pre-compilation times, which sometimes take 10-20 seconds for me for programs that use some standard library packages.
Could you please additionally provide just this Julia code without extra annotations? Do you count the boilerplate lines (such as "using LinearAlgebra") as a part of these 16?
And finally: is it possible to achieve a similar result with Python + SciPy?
I think the notebook format is intended to provide an intuitive and interactive explanation. This is also why we need a couple lines of code to generate input, since we can’t actually submit Julia to Kattis.
Is there a specific problem with the notebook that is making it difficult to understand for you? I tried very hard to explain each part of the algorithm in clear English.
Sure, linear algebra libraries in any language like Python can make the problem simpler, but Julia is particularly fast and concise with its first-class support for matrices and optimizing compiler. Your Python code would likely be slower, since the non-C extension parts need to be interpreted. Also, it doesn’t have as good support for broadcasting operators.
Is julia good for competitive programming that involves heavy maths like this one? I saw this language in the book "Algorithms for decision making" and had no idea why the author used julia despite having so many other options and the book was not a normal book,it was published by MIT Press. now,it seems to justify to me the point why author used the language.
Yeah, it's true that Julia makes some numerical algorithms a lot simpler, such as this problem and rpeng's research.
You have provided a nice editorial for the problem. Thanks for this! But if your goal is to showcase the strength of the Julia programming language at solving it (as implied by the title of your blog), then having a self-contained standalone Julia code would help a lot. Right now I have difficulties to see how did you come up with your 16 lines estimate. Because the numbers don't add up if I simply count the lines of the provided Julia code snippets.
Could you please show a small Julia program, which can be pasted to the AtCoder customtest page and print the expected output for the samples from the problem statement?
It would be also great if somebody could convert this solution to Python, so that we can have a fair apples to apples comparison of the language features. AtCoder seems to support NumPy and SciPy libraries on their platform.
And in order to see a complete picture, a C++ solution would be a great bonus too.
Yeah, sounds reasonable if you want to compare line counts side-by-side. I added a standalone short Julia program to the main post.
As for converting to Python and C++, feel free to contribute this translation if you'd like. My goal in this post was to explain the problem though, not to advertise a different programming language.
Thanks! Though it doesn't seem to produce correct output for Sample Input 3 and prints "0.6122853196541151 -0.3632035628797814 2.4277079156317813 4.258510497530253" instead of "1 2 3 4".
It also takes 2.2 seconds on AtCoder to process Sample Input 1, which makes me wonder if a Python solution would be really slower than that.
I don't see anything wrong with advertising a different programming language if it does a particularly good job. That's why I wonder if just providing linear algebra functionality as a part of the standard library is the only trick behind a small concise solution or Julia additionally offers some other advantages?
Please read the problem statement, the output is correct. The 2.2 seconds is due to AtCoder including time for Julia's JIT to compile the code; it runs near-instantaneously.
Once again, I'm not trying to advertise Julia, but I'm happy to answer any questions you have. It's just the language I chose to most lucidly explain the solution. Julia provides several advantages, like fast array comprehensions, static typing, and automatic operator vectorization that are also clear if you read the code.
NO, PLEASE NO, NOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
I was a strong believer about never setting problems related to my day time job (exhibit 1)(exhibit 2). Keyword: WAS...
Auto comment: topic has been updated by ekzhang (previous revision, new revision, compare).