Jikka, a transpiler/solver for competitive programming

Правка en1, от kimiyuki, 2021-09-07 18:03:02

Hello Codeforces!

I'm developing a new tool, Jikka, a transpiler from Python to C++ developed to become an automatic solver of problems of competitive programming.

Jikka takes simple Python code as input and optimizes it to reduce its time complexity. i.e., you can obtain an AC solution from a naive TLE solution. For example, the below Python code, obviously O(N^2), but it becomes O(N log N) with Jikka.

def solve(n: int, c: int, h: List[int]) -> int:
    dp = [INF for _ in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(i + 1, n):
            dp[j] = min(dp[j], dp[i] + (h[i] - h[j]) ** 2 + c)
    return dp[n - 1]

The current version of Jikka is still under development and requires naive solutions, so actually, it can solve only a few problems and is difficult to use in real contests yet. Also, you can do such easy rewritings by hand (right?). However, I think this is an interesting and dreaming project. I hope that Jikka will allow us to skip trivial implementation and focus only on more essential parts of algorithms in the future, as C++ compilers free us from assembly and machine languages.

Are you interested? Please join in development!

Теги tool

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский kimiyuki 2021-09-07 18:03:02 1511 Initial revision (published)