VLamarca's blog

Use cases of chat GPT in Competitive Programming
By VLamarca, history, 7 months ago, In English

Today was the first day I successfully used Chat GPT in codeforces. To be very clear, chat gpt did not come up with the solution, I came up with it. I only used it to write the code for a specific annoying part that is well known. I should probably just have something like that in the lib. Here is the submission. I probably just saved a few minutes. I also had to adjust a few things like reading the input, writing an extra if, etc. But chat gpt successfully did what I asked for it in an optimal way.

This was the prompt I used for Chat GPT 4: “An array A of length n can be seen as a graph where i has a directed edge to A[i]. Each vertex has 1 outgoing edge. There are some cycles in the graph. I think the name is a cactus. Write a code in cpp where given A you list all the sizes of the cycles”

On another example, I also remember trying to use chat gpt to search for some advanced level math theorems, but I failed to find with it. I was looking for something like this Given 2n integers, prove there is always a subset of size n whose sum is multiple of n for this problem, but I failed.

Do people have other use cases for chat gpt in Competitive Programming? I assume the main one is just coding a few simple things faster, and probably more accurately then most people, but the problem solving ability is still not good enough for problems above Div3A or B (fortunately or unfortunately wink wink).

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

»
7 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I have used it also in the last contest, for Div2C. With interactive problems sometimes python flushing is slow, so I need to convert python code to c++. Because I code faster and more accurately in python, using python to do the implementation for the first time is better, but it's slow. For this problem, without any wrong answers in just 1 minute, Chat GPT 3.5 converted the TLE python 222936876 into the accepted 222937618.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Good use case, thanks for sharing!

    → Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    Btw a quick tip for speeding up IO in Python is to add the line

    import sys
input = sys.stdin.buffer.readline

    at the top of the code. With this you would have gotten AC both with PyPy3 223028498 and CPython3 223028556. This is the Python equivalent of doing 

    cin.sync_with_stdio(0);
cin.tie(0);
    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did know about fast output tricks, but the problem was that the print=sys.stdout.write fast output trick needed me to convert everything to a string, which was tedious and slowed down implementation.
      This input trick is much better, and doesn't require me to add any extra stringification code.
      Thank you for this fast input trick.

      → Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    My java code also gave me tle but cpp conversion worked :(

    → Reply
»
7 months ago, # |
  Vote: I like it +59 Vote: I do not like it

sir the name is functional graph not cactus lol

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it -16 Vote: I do not like it

    There is another type of graph that is called a cactus. (It's not the same thing of course).

    A connected undirected graph is called a vertex cactus, if each vertex of this graph belongs to at most one simple cycle.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      but the functional graph is not a cactus tho (It is a directed graph, and its undirected analogue need not be a cactus either. A functional graph is not neccesarily weakly connected)

      → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I and other local programmers usually call it suns/солнышки, as each component of it is a cycle and trees rooted at some vertice of the cycle.

    → Reply
»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I use ChatGPT to translate problem statements in other languages to English. I can personally confirm it works pretty well for Japanese, Korean, Polish, and Russian, around 1% of the time do I resort to other tools to translate specific phrases that don't seem to make sense. (Google Translate and other similar tools have an error rate roughly around 5-10% for me.)

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There was an AtCoder problem (abc315_g) in which not even __int128 was enough for my implementation. I just asked ChatGPT to translate it to Python and got the AC.

(Stalking your submissions I believe you did the same lol)

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh yeah, I forgot about that. The translation was incorrect because a/b in cpp is different than a//b in python (different for negative numbers). I had to find the bug myself after some work, but yeah, besides that, it was correct

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Used ChatGPT once to implement a bruteforce approach that generates all possible arrays of small lengths $$$n$$$ that satisfy given condition in the problem 1806C - Sequence Master. After that noticed a pattern and eventually got accepted.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know whether Copilot counts or not (since technically they're both from the GPT model), if it does then yes, I've been using it recently. It speeds up my coding time dramatically for simple brute force and implementation of well known algorithms, I just have to work out the logic and implement it. It usually recommends wrong code or wrong idea though so for easier problems sometimes it acts as a drawback since I have to correct it.

→ Reply
»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Used on arc167_b to discover some math formulas about the product of all divisors of a positive integer.

Chat gpt answer
→ Reply