-14's blog

ChatGPT passed ABC280D under human coaching
By -14, history, 2 years ago, In English

ChatGPT is a NLP model released recently, and I found it unexpectedly strong. Here's the evidence.

The Problem : ABC 280 D

You are given an integer $$$K$$$ greater than or equal to $$$2$$$. Find the minimum positive integer $$$N$$$ such that $$$N!$$$ is a multiple of $$$K$$$.

Here, $$$N!$$$ denotes the factorial of $$$N$$$. Under the Constraints of this problem, we can prove that such an $$$N$$$ always exists.

Constraint: $$$2 \leq K \leq 10 ^ {12}$$$

ChatGPT correct submission

Here are the interactions. ChatGPT spoke Chinese to me (which I didn't figure out how to configure it), so I'd provide some translations here.

Human: (The problem statement with hint to use long long)

ChatGPT: We can use code to implement the above algorithm. (Code follows)

Human: This code can not process the case when the factorials are large. You can enumarate the answer, and when newly add n to the factorial, the gcd(K, n) factor can be eliminated, until K = 1. Try to optimize your code.

ChatGPT: In order to solve the above problems, we can optimize the code to handle the case where the factorial is too large. We can use enumeration to find the smallest positive number N that satisfies the condition, and then offset the divisor of gcd (K, n) in K with the order n of N each time until K is 1.

The implementation is as follows. (Code follows)

Human: The code is slow when K has a large prime factor. You can factorize K firstly, if K has a prime factor no less than 1e6, then print it as the answer. Otherwise, we run the previous algorithm to solve the problem.

ChatGPT: In order to speed up the program, we can optimize it to handle the case when K has large prime factor. We can factorize K firstly, if K has a prime factor no less than 1e6, then print it as the answer. Otherwise, we run the previous algorithm. Here's the implementation. (Partial code)

Human: You didn't write code completely, please finish it.

ChatGPT: (More code)

Human: In the above code, you modified k in the factorizing, leading a wrong answer in the latter algorithm. Please copy k to a temporary variable in order to avoid affecting the original code.

ChatGPT: (Same comment, code)

Human: You should output n-1 instead of n.

ChatGPT: (Correct code)

Human: Thank you! Your code passed the problem.

ChatGPT: You're welcome, it's pleasure of mine. Let me know if you have any other questions. I will try my best to help you.

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

Comments Comments (35)
| Write comment?
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it -39 Vote: I do not like it

My difficult days are going to be over soon. This is huge milestone in evolution of consciousness. Astounding! Amazing feat!

Time to party and chill!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +110 Vote: I do not like it

    It solves ur problems and you think life's easy, then it takes your job...

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +98 Vote: I do not like it

      Then it starts using you as a battery for their energy source

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

      It should take the jobs that I don't like. Jobs have become like prison. If you don't have one, you are assured you're going to become homeless soon unless you have tons of cash in your bank account. You'll be homeless faster while working for a job that pays like shit. Having a good job is like hitting a jackpot these days anyway.

      Personally I am fine to spend every day of my life doing what I like so it's okay if it takes my job. Less worries etc.

      The only hard part may be how this is going to be incorporated / how long it will take to make the utopian dream come alive.

      I'm sure we will create some ingenious algorithms to tackle these :)

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Yes, then why do you live? To watch TV? Oh wait there are only fake people on television, and that's not interesting. Or maybe read a book? But that's not made from the real experiences of a human, so it's likely to (as of now) lack the depth and connectivity you seek. Or maybe talk to another human? But who's human, and who's not? So what is left? Eat, sleep, and live in social isolation, surrounded by AI.

        This doesn't seem bad for some, but note the amount of depression this can cause in others.

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

          https://mirror.codeforces.com/profile/aadit.ambadkar

          You are sounding as if this going to take something big away from us. It's not deleting anything, its only adding something immensely valuable. You can still do all those old things if you choose to do. You are going to have more options thats the point.

          Previously, we had a hugely constrained world, now, the constraints are loosening up. This can be a problem for those people that can't handle absolute freedom specially when they were taught to do this and do that all their life, like school, college, study, job, etc.

          You should be happy as your life can be fully under your own control once the outside circumstances that toss you around like a rag doll are gone.

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

            A while ago (some years where that is a positive integer), some of the major concerns in a lot of the middle to lower middle class of the world used to be having their jobs outsourced. A while later, it turned out to be true, and many jobs were outsourced. This forced a major disparity gap to slowly evolve; crossing the class gap is progressively getting harder.

            The advent of AI will worsen this gap even more. What use is there for any manual laborer once AI reaches a certain capability? And if you argue that there is no need for money — and thus no need for jobs — that is even more shaking: people without a purpose turn to thrill and entertainment, often in the form of violence and addictions.

            Of course, this can be prevented partially through regulations, but how far can that go? Too much government involvement is bad.

            Constraints aren't loosening up so people can achieve; they're loosening up because people don't need to achieve. If there is no need to achieve, then why do we exist?

            I don't mean to insult you as an individual, so please don't take personal offense to my arguments. But in the simplest terms, there are two things that can bring the end of civilization: lies and AI. And possibly both.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              You are absolutely true that life is hard. Survival is hard in general and we are no different from animals. There's fight for jobs, fight for food.

              I don't think there's easy solution to these issues.

              What AI may offer is some kind of social security, a backup plan for you when you get kicked out of your job, have no money, etc.

              But, life is hard in general. Even worse is the overpopulation factor. No wonder why there's shooting left and right in the United States when people can't just have a happy life. People are too much burdened.

              → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +88 Vote: I do not like it
    Hold on!
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -28 Vote: I do not like it
      Checks out
      → Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Truly mind blowing!

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me how this code working? I mean what is the logic for this code?

ABC280 D

https://atcoder.jp/contests/abc280/submissions/36956302

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

    Since the largest prime number below $$$10^6$$$ appears at least twice in $$$(2 \times 10^6)!$$$, all prime numbers that can appear twice now must be eliminated, not to mention the smaller primes that can appear more times. It then must hold that $$$K$$$ after $$$2 \times 10 ^ 6$$$ iterations a large prime number. It's exactly the factorizing method but in an elegant way.

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

    @into_the_world

    $$$\frac{N!}{K}=\frac{1*2*3*4*5.....N}{p_1^{k1}*p_2^{k2}....p_n^{kn}*psqrt^1}$$$

    where $$$psqrt$$$ is the prime greater than $$$\sqrt K$$$. Notice the power, it is always 1 i.e. for any given number $$$K$$$ its factorization can have only one prime greater than its square root.

    Now, to solve this easily, you can split into two cases when $$$psqrt$$$ exists or not for the given number. If it exists, $$$psqrt$$$ is the best minimum answer. Otherwise, we can use another fact that for all prime powers in $$$K$$$, i.e $$$k_1$$$, $$$k_2$$$,...,$$$k_n$$$, all can be at max 40, because $$$2^{40}>10^{12}$$$.

    Now, keep on deducing. like this. You can find that you can get the best answer within $$$N \le \sqrt K * 40 $$$. To get more tight bound you can do $$$max(p_1*k_1,p_2*k_2,....,p_n*k_n)$$$, from where comes the $$$2*10^6$$$

    → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +42 Vote: I do not like it

The reason why ChatGPT gave a Chinese solution may be that the Training Data it used contains many Chinese editorials with English problem descriptions.

I also saw it writing Chinese when I only gave part of English problem description, but most of the time it gave an English reply.

→ Reply
»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

2 research paper down the line.. it's definitely end of codeforces and leetcode right?

→ Reply
»
2 years ago, # |
  Vote: I like it +148 Vote: I do not like it

Didn't you just tell it how to solve the problem step by step? Sure, it can implement it, which is amazing, but it is very far from actually solving it.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +113 Vote: I do not like it

    That's exactly the point.

    Indeed, it still can't solve difficult problems or invent new algorithm, and we already have AlphaCode etc. before that; and it's quite expected to write a bruteforce algorithm as the first version of code above.

    However, the interaction showed the ability to precisely manipulate the code by natural language hint -- the ability beyond simply copying and pasting from existing code. This is something surprising to me.

    Also, it's the first (?) example we can play with it -- remember that we can not access AlphaCode and it didn't show up in the round for it.

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

      AlphaCode is very different. It was explicitly trained on contest programming, it generated thousands of solutions for each problem, run them through examples and submitted only unique solutions (in terms of output on the randomly generated tests).

      ChatGPT has no CP-specific hacks.

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

        Though I'm pretty sure it was at least partially trained on some competitive programming problems... If you add to your prompt something like "solve this competitive programming problem" it will produce code which is obviously written for competitive programming.

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how did u use openai in cn?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I asked my friend living abroad for help.

    → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

a joke: can the AI write and AC "pigland kill"(a problem with many details and long code and famous in cn)?

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

copilot:So you will be like them abandon me. will you?

→ Reply
»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I guess I'm going to have a positive delta in the next contest

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, that's great. I hope it will not make online competitions unfair through.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How much time did it take for ChatGPT to respond to each of your instructions?

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can this be used for cheating ?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

AtCoder founder and CEO guided ChatGPT to take part in ABC281 virtually. The result is that only A,B,C,D are completed. YouTube link.

→ Reply