Блог пользователя TLE

CPIdeas: use AI to generate competitive programming ideas
Автор TLE, история, 2 года назад, По-английски

Hello Codeforces!

Being asked to propose competitive programming questions is pretty haunting. When you're out of fresh ideas, I used to do one of the two things. One, is to search in the old pile of problems, hoping to find some room of modifications and improvements. The second, is to come up with random words, like "chessboard inversion counting", and hopefully resemble interesting problems from them.

This process is pretty boring, so I have been trying to use machine learning to generate ideas and even complete competitive programming problems. The result is CPIdeas! Check it out here: https://fjzzq2002.github.io/cpideas/.

How was it made? I collected problems from AtCoder (ABC, ARC, AGC) and used these problems to fine-tune GPT-3, the OpenAI model. It's quite tricky to get things right though and it's still far from perfect.

How should I use it? Look through these ideas. Scroll down. Be tolerant and creative. That's it.

How should I use these ideas? For the generated ideas/problems, I would say probably do not use the ideas directly as problems (although you certainly can). Definitely use the search engine before actually purposing the problems. There are ~7000 shuffled ideas in the website at the moment so it's quite unlikely that multiple users worked on the same idea but that's certainly another risk.

Here are some sample ideas. They're not super logical, but hopefully pretty inspiring.

You are given a sequence of N integers A=(A1,A2,...,AN). Find the number of sequences that satisfy the following conditions, modulo 998244353. 1<=Ai<=M. There exists a permutation P=(P1,P2,...,Pk) of (1,2,...,k) such that Ai<=Pi and Pi!=Ai+1.

You are given an integer sequence of length N : A=(A1,A2,...,AN). You can do the following operation on A any number of times: choose an integer i such that 1<=i<=N-1, and replace the last element of A with ai. You want to make A a permutation of (1,2,...,N). Find the minimum number of operations needed.

You are given a string S of length N. Let the number of occurrences of each character in S be num1, num2,..., numN. Find the number of pairs of integers (i,j) that satisfy the following condition: 1<=i<j<=N, and |num1-numj|+|num2-numj|+...+|numN-i-j|<=1.

Hopefully you'll enjoy this little tool I made! If you have any thoughts/comments/suggestions you can comment below.

  • Проголосовать: нравится
  • +604
  • Проголосовать: не нравится

»
2 года назад, # |
← Rev. 3   Проголосовать: нравится +34 Проголосовать: не нравится

I prompted GPT-3 with the second problem, and it returned

Editorial: https://codeforces.me/blog/entry/81735
*/
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> perm(n);
    vector<int> ans;
    vector<int> f(n);
    for(int i = 0; i < n; i++){
        cin >> perm[i];
        f[perm[i]-1] = i;
    }
    for(int i = 0; i < n; i++){
        int j = f[i];
        while(j != i){
            ans.push_back(j);
            int k = perm[j-1];
            perm[j-1] = perm[j];
            perm[j] = k;
            f[perm[j]-1] = j;
            f[perm[j-1]-1] = j-1;
            j--;
        }
    }
    cout << ans.size() << '\n';
    for(int x : ans){
        cout << x << ' ';
    }
    cout << '\n';
}

No idea why it points to that blog post in particular :D

→ Ответить
»
2 года назад, # |
← Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

can it be extended to do Um_nik's problem database idea? I know nothing about ML https://codeforces.me/blog/entry/95956

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    To be honest I'm not a ML expert either so take my words with a grain of salt. I don't think my model will work — my model probably only knows about the structure of statements (how they "look like") or roughly what the statement is trying to convey, but cannot actually solve them. A model like AlphaCode might be capable of doing so though — if AlphaCode can solve some problem, it should understand it. We probably need to retrain or fine tune AlphaCode for the embeddings (which sounds really expensive!).

    → Ответить
»
2 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Very interesting, though I'm not sure if we'll be able to see actual original and logical ideas from this type of thing anytime soon.

Alternatively, if you like the more old school approach, you could just go through The Library of Babel until you find an interesting problem :D

→ Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

[There was a mistake but it has been revised]

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by TLE (previous revision, new revision, compare).

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +112 Проголосовать: не нравится

Short problem ideas are the best...

You are given a permutation P=(P_1,P_2,...,P_N) of (1,2,...,N). Find the number of integers i such that 1<=i<=M, such that P_1=P_2=...=P_N.
→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +182 Проголосовать: не нравится

Proves my point that AtCoder problems are just "You are given some initial sequence, you can perform 69 possible operations to generate sequence set $$$S$$$, see if $$$x \in S$$$ or print $$$|S|$$$ mod 696969420"

→ Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

First of all, thank you for the generated problem database! I'm sure it will help aspiring problemsetters.

That being said, is there any way to format the ideas into the form of a bullet-point list or something similar? Right now the site returns the raw result, with colored highlighting used as separators, which isn't exactly the best option for visibility.

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I agree, it's pretty hard to read.

    Of course it would be great if the author changed that, but in the meantime you can use my crude and disgusting code for one-time uses:

    document.head.innerHTML += `
<style>
.BLIST::before {
  list-style-type: square;
  content: "■";
  font-size: 25px;
  display: inline-block; 
  width: 1em;
  margin-left: -1em;
  color: rgb(203, 196, 177);
}

</style>
`
let bulletList = document.createElement('ul');
bulletList.style.listStyle = 'none';
let spans = document.getElementsByTagName('span');
for(let span of spans) {
    if(span.getAttribute('data-v-6ef4f1bc') == undefined) { continue; }
    let point = document.createElement('li');
    point.classList.add('BLIST');
    point.style.marginBottom = '30px';
    point.innerHTML = span.outerHTML;
    bulletList.appendChild(point);
}
document.getElementById('actualideas').style.display = 'none';
document.getElementById('content').appendChild(bulletList);
    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      This is really nice! I'll steal your design in the next version :)

      Update: this style has been implemented and the old style is also kept as an alternative.

      → Ответить
»
2 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Given are integers A, B, and C. Find the maximum possible value of A+B+C. lol

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

You are given an integer N. How many integers between 1 and N (inclusive) are there?

Given are integers a and b. Find the maximum integer between a and b (inclusive).

Inspiring.

→ Ответить