kimiyuki's blog

By kimiyuki, history, 3 weeks ago, In English

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!

Read more »

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

By kimiyuki, history, 15 months ago, In English

Hi Codeforces!

Today I would like to intoruce my template generator, online-judge-tools/template-generator. This program can analyze problems of competitive programming and generate boilerplate codes including input part, output part, MOD, etc.

For example, for a probelm https://codeforces.com/contest/1300/problem/D, my command oj-template https://codeforces.com/contest/1300/problem/D prints the following source code. All of input part and output part is already written in main function, and what you need to write is only the solve function.

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) ::std::begin(x), ::std::end(x)
using namespace std;

const string YES = "YES";
const string NO = "nO";
bool solve(int n, const vector<int64_t> & a, const vector<int64_t> & b) {
    // TODO: edit here
}

// generated by online-judge-template-generator v4.4.0 (https://github.com/kmyk/online-judge-template-generator)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    constexpr char endl = '\n';
    int n;
    cin >> n;
    vector<int64_t> a(n), b(n);
    REP (i, n) {
        cin >> a[i] >> b[i];
    }
    auto ans = solve(n, a, b);
    cout << (ans ? YES : NO) << endl;
    return 0;
}

Also this can generates generators for random cases. You can combine the generator with my another tool online-judge-tools/oj and use them for stress tests, i.e. generating many testcases randomly and run tests against them until a hack testcase for your program is found.

Enjoy!

Read more »

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

By kimiyuki, history, 4 years ago, In English

Hello!

I would like to introduce you to my tool kmyk/online-judge-tools. This is a collection of command-line tools to automate routine work on programming contests.

The main features are:

  • download sample cases
  • test your solution locally

This supports Codeforces, AtCoder, HackerRank, CS Academy, etc.

A screencast is here:

screencast

Also, there are many sub-features, some of which are:

  • help to test reactive problems
  • generate boilerplates like int N, M; cin >> N >> M;
  • submit to some judges (including TopCoder Marathon Match)

You can find more features on readme.md or the --help option.

To install this, just type $ pip3 install online-judge-tools. Enjoy!

Read more »

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