I solved the 4th question of AtCoder ARC104 with Scala, C ++, Java, Ruby, Perl and Elixir. I was able to compare the processing speed for each language.
| language | result |
|---|---|
| Scala | TLE |
| C++ | AC 1830ms |
| Java | AC 2995ms |
| Java-like Scala | AC 2991ms |
| Ruby | TLE |
| Perl | TLE |
| Elixir | TLE |
The relationship between language selection and processing speed in competitive programming was mentioned in the following tweet.
https://twitter.com/chokudai/status/1171321024224186369
According to this tweet, C ++ and Java are okay, but other languages seem to be tough on computationally intensive problems.
During the competition, it took time to find a solution, and after I knew it, I wrote it in Scala, but it took a lot of time to fix the bugs, and I could not reach AC (correct answer). I continued after the competition, but I couldn't get rid of the TLE with a execution time limit of 4 seconds.
When I gave up and wrote the same logic in C ++, I could easily get AC.
So, I wrote it in various languages and compared whether I could get AC.
Scala was TLE at first, but if I wrote Scala that translated Java after taking AC with Java, I could get AC with Scala.
The rest of this article is the source code for each language.
Scala
It is Java-like Scala code halfway, such as using ʻArray`, but it is a code that I gave up because I could not solve TLE.
object Main extends App {
val sc = new java.util.Scanner(System.in);
val n, k, m = sc.nextInt();
val table = (0 until n).map(i => Array.fill(i*(i+1)*k/2+2)(0));
table(0)(0) = 1;
(1 until n).foreach { i =>
val j_max = i * (i+1) * k / 2;
val t1 = table(i - 1);
val t2 = table(i);
(0 to j_max).foreach { j =>
val a1 = (((j - (i - 1) * i * k / 2) + i - 1) / i) max 0;
val a2 = (j / i) min k;
val s = (a1 to a2).map { a =>
t1(j - a * i).toLong;
}.sum % m;
t2(j) = s.toInt;
}
}
val table2 = Array.fill(n+1)(0);
(1 to n).foreach { x =>
if (x <= (n + 1) / 2) {
val (n1, n2) = (x - 1, n - x);
val s = (0 to (n1 * (n1+1) * k / 2)).map { i =>
table(n1)(i).toLong * table(n2)(i) % m;
}.sum % m;
val answer = ((m.toLong + s * (k+1) - 1) % m).toInt;
table2(x) = answer;
println("%d".format(answer));
} else {
val answer = table2(n + 1 - x);
println("%d".format(answer));
}
}
}
After getting AC with Java, which will be described later, when I wrote a code that translated Java into Scala, it was 2991ms, which is almost the same as Java. The conclusion is that Java is fine enough to write such code in Scala, and Scala is not suitable for computationally intensive problems. Scala is easy for me to write, so I'll continue to use it properly.
object Main extends App {
val sc = new java.util.Scanner(System.in);
val n, k, m = sc.nextInt();
val table = new Array[Array[Int]](n);
table(0) = new Array[Int](2);
table(0)(0) = 1;
var i: Int = 1;
while (i < n) {
val j_max = i * (i+1) * k / 2;
val t1 = table(i - 1);
val t2 = new Array[Int](i*(i+1)*k/2+2);
table(i) = t2;
var j: Int = 0;
while (j <= j_max) {
val a1 = (((j - (i - 1) * i * k / 2) + i - 1) / i) max 0;
val a2 = (j / i) min k;
var s: Long = 0L;
var a: Int = a1;
while (a <= a2) {
s += t1(j - a * i).toLong;
a += 1;
}
t2(j) = (s % m).toInt;
j += 1;
}
i += 1;
}
val table2 = new Array[Int](n+1);
var x: Int = 1;
while (x <= n) {
if (x <= (n + 1) / 2) {
val (n1, n2) = (x - 1, n - x);
var s: Long = 0L;
var i: Int = 0;
var max = (n1 * (n1+1) * k / 2);
while (i <= max) {
s += table(n1)(i).toLong * table(n2)(i) % m;
i += 1;
}
s = s % m;
val answer = ((m.toLong + s * (k+1) - 1) % m).toInt;
table2(x) = answer;
println("%d".format(answer));
} else {
val answer = table2(n + 1 - x);
println("%d".format(answer));
}
x += 1;
}
}
C++
When I rewrote the same logic in C ++, I got AC in 1830ms.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, m;
cin >> n >> k >> m;
vector<vector<int>> table(n);
table[0] = vector<int>(2);
table[0][0] = 1;
for (int i = 1; i < n; i++) {
auto t1 = table[i-1];
auto t2 = vector<int>(i*(i+1)*k/2+2);
int j_max = i * (i+1) * k / 2;
for (int j = 0; j <= j_max; j++) {
int a1 = ((j - (i - 1) * i * k / 2) + i - 1) / i;
if (a1 < 0) a1 = 0;
int a2 = j / i;
if (a2 > k) a2 = k;
long s = 0;
for (int a = a1; a <= a2; a++) {
s += t1[j - a * i];
}
s = s % m;
t2[j] = (int)s;
}
table[i] = t2;
}
auto table2 = vector<int>((n + 1) / 2 + 1);
for (int x = 1; x <= (n + 1) / 2; x++) {
int n1 = x - 1;
int n2 = n - x;
long s = 0;
for (int i = 0; i <= n1 * (n1+1) * k / 2; i++) {
s += (long)table[n1][i] * table[n2][i] % m;
}
int answer = (int)(((long)m + s * (k+1) - 1) % m);
table2[x] = answer;
printf("%d\n", answer);
}
for (int x = (n + 1) / 2 + 1; x <= n; x++) {
printf("%d\n", table2[n + 1 - x]);
}
}
Java
I got AC in C ++ and found that the solution was correct, so I wrote it in Java next. I got AC in 2995ms. It's slower than C ++, but faster than Scala in the same JVM. I thought that what you can do with the JVM can be done with Scala in a Java-like way, but as mentioned above, you can get AC with Scala as well.
import java.util.Scanner;
class Main {
public static void main(String[] args) {
var sc = new Scanner(System.in);
var n = sc.nextInt();
var k = sc.nextInt();
var m = sc.nextInt();
var table = new int[n][];
table[0] = new int[2];
table[0][0] = 1;
for (int i = 1; i < n; i++) {
var t1 = table[i-1];
var t2 = new int[i*(i+1)*k/2+2];
int j_max = i * (i+1) * k / 2;
for (int j = 0; j <= j_max; j++) {
int a1 = ((j - (i - 1) * i * k / 2) + i - 1) / i;
if (a1 < 0) a1 = 0;
int a2 = j / i;
if (a2 > k) a2 = k;
long s = 0;
for (int a = a1; a <= a2; a++) {
s += t1[j - a * i];
}
s = s % m;
t2[j] = (int)s;
}
table[i] = t2;
}
var table2 = new int[(n + 1) / 2 + 1];
for (int x = 1; x <= (n + 1) / 2; x++) {
int n1 = x - 1;
int n2 = n - x;
long s = 0;
for (int i = 0; i <= n1 * (n1+1) * k / 2; i++) {
s += (long)table[n1][i] * table[n2][i] % m;
}
int answer = (int)(((long)m + s * (k+1) - 1) % m);
table2[x] = answer;
System.out.printf("%d\n", answer);
}
for (int x = (n + 1) / 2 + 1; x <= n; x++) {
System.out.printf("%d\n", table2[n + 1 - x]);
}
}
}
Ruby
It was TLE.
n, k, m = gets.strip.split(" ").map(&:to_i)
table = [[1]]
for i in 1..n-1
t1 = table[i-1]
t2 = []
for j in 0 .. i * (i+1) * k / 2
a1 = ((j - (i - 1) * i * k / 2) + i - 1) / i;
a1 = 0 if a1 < 0
a2 = j / i;
a2 = k if a2 > k
s = 0;
for a in a1 .. a2
s += t1[j - a * i]
end
s = s % m
t2.push(s)
end
table.push(t2)
end
table2 = [0]
for x in 1 .. (n + 1) / 2
n1 = x - 1
n2 = n - x
s = 0
for i in 0 .. n1 * (n1+1) * k / 2
s += table[n1][i] * table[n2][i] % m;
end
answer = (m + s * (k+1) - 1) % m
table2.push(answer)
p answer
end
for x in (n + 1) / 2 + 1 .. n
p table2[n + 1 - x]
end
Perl
It was TLE.
use strict;
use warnings;
use integer;
my $nkm = <STDIN>;
$nkm =~ s/\n\z//;
my ($n, $k, $m) = split(/ /, $nkm);
my $table = [[1]];
for (my $i = 1; $i < $n; $i++) {
my $t1 = $table->[$i - 1];
my $t2 = [];
my $j_max = $i * ($i + 1) * $k / 2;
for (my $j = 0; $j <= $j_max; $j++) {
my $a1 = (($j - ($i - 1) * $i * $k / 2) + $i - 1) / $i;
$a1 = 0 if $a1 < 0;
my $a2 = $j / $i;
$a2 = $k if $a2 > $k;
my $s = 0;
for (my $aa = $a1; $aa <= $a2; $aa++) {
$s += $t1->[$j - $aa * $i];
}
$s = $s % $m;
push(@$t2, $s);
}
push(@$table, $t2);
}
my $table2 = [0];
for (my $x = 1; $x <= ($n + 1) / 2; $x++) {
my $n1 = $x - 1;
my $n2 = $n - $x;
my $s = 0;
for (my $i = 0; $i <= $n1 * ($n1+1) * $k / 2; $i++) {
$s += $table->[$n1]->[$i] * $table->[$n2]->[$i] % $m;
}
my $answer = ($m + $s * ($k+1) - 1) % $m;
push(@$table2, $answer);
printf("%d\n", $answer);
}
for (my $x = ($n + 1) / 2 + 1; $x <= $n; $x++) {
printf("%d\n", $table2->[$n + 1 - $x]);
}
Elixir
It was TLE.
defmodule Main do
def main do
[n, k, m] = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
table = Enum.reduce(1 .. n, [[1, 0]], fn i, acc ->
[t1 | _] = acc
j_max = div(i * (i+1) * k, 2);
t2 = Enum.map(0 .. j_max, fn j ->
a1 = max(div((j - div((i - 1) * i * k, 2)) + i - 1, i), 0)
a2 = min(div(j, i), k)
rem(Enum.reduce(a1 .. a2, 0, fn a, acc3 ->
acc3 + Enum.at(t1, j - a * i)
end), m)
end)
[Enum.reverse(t2) | acc]
end) |> Enum.reverse
table2 = (1 .. div(n + 1, 2)) |> Enum.map(fn x ->
[n1, n2] = [x - 1, n - x]
s = Enum.reduce(0 .. div(n1 * (n1 + 1) * k, 2), 0, fn i, acc ->
rem((table |> Enum.at(n1) |> Enum.at(i)) * (table |> Enum.at(n2) |> Enum.at(i)) + acc, m)
end)
rem(m + s * (k+1) - 1, m)
end)
(1 .. n) |> Enum.each(fn x ->
if x <= div(n + 1, 2) do
IO.puts(Enum.at(table2, x - 1))
else
IO.puts(Enum.at(table2, n - x))
end
end)
end
end
Recommended Posts