Una_Shem's blog

AlphaCode (DeepMind) Solves Programming Problems on Codeforces
By Una_Shem, 3 years ago, In English

Hello, community.

Today DeepMind announced a new achievement of AI. And it is directly related to what we love — programming problems.

They have developed AI capable of solving some competitive programming problems! The future has arrived.

You should read solutions of SelectorUnlimited, WaggleCollide, and AngularNumeric solutions. All solutions are written automatically. The only input for writing solutions is a problem statement in English.

Details can be read at the link https://deepmind.com/blog/article/Competitive-programming-with-AlphaCode

Apparently, if these accounts would take part in real competitions, then their rating would be about 1300.


Terminator is ready to take part in Codeforces Round #770 (Div. 2)

In 1997 Kasparov played against (and lost) the supercomputer DeepBlue. Perhaps we will be witnessing a confrontation between tourist and AI in near future. What do you think?

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

Comments Comments (270)
| Write comment?
»
3 years ago, # |
  Vote: I like it +871 Vote: I do not like it

AI is such a noob

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

    At least its better than me....

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

      at least you can understand the statement

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

    Hope that robots do not come across your comment when they start ruling the world.

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

    AI vs Pupils, Noobies, Specialists

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

    And it's also violating CF's rules, alt accounts aren't allowed, this bot has two of them.

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

    It is too interesting, I wanna see the initial success of this Terminator. Please, Inform us about the handle of it. I just make it my friend :) Thanks

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

    As AI improves, it will achieve higher rating. More data -> More Efficient

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

    Top Rated Leaderboard in 10 years when the AI all become LGM

    meme
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it -20 Vote: I do not like it

      i suspect the one in the middle is also AI with tourist pfp

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

        i suspect that your second revision is something you should have kept to yourself

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

          sorry, i mixed up websites

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

    I still cannot forget when 5 years ago AlphaGo (Another AI developed by Deepmind but playing Go) demolished me and Lee Sedol (we are both top Go players). Now it seems like AlphaCode is invading CP. I sincerely hope that tourist can fight back for mankind. Best wishes.

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

      So you are real Jie_Bao?

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

      In case he loses,we also have MiracleFaFa

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

    Time to private all our github repos

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

      As if that will stop Github from selling that.

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

      We should be able to make our submissions to CF private too.

      → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Github copilot was trained on private repos too. That's the entire law suit against microsoft about.

      Having said that the amount of public code that's out there is already humongous. Most training data set already copied those. You can't undo that. It's about making AI smarter from those, it's not about current AI system could have solved everything had it seen more codes. Think about yourself, did you have to see all github public repos to learn coding? no right. you might have learnt from very small set of examples. Similarly now the ongoing effort it to make AI learn from smaller set of examples like humans do.

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

    I will post the same comment when i become 'grandmaster'.

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

    Curious mind wants to know
    The AI ( WaggleCollide ) which does not know the language it is writing the code, how can it beat tourist? tourist

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

We will be witnessing more cheaters.

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

    From the codeforces rules:

    Solutions and test generators can only use source code completely written by you, with the following two exceptions:

    1. the code was written and published/distributed before the start of the round,
    2. the code is generated using tools that were written and published/distributed before the start of the round.

    If this AI was publically available, using it would not be cheating by point 2.

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

      Maybe then it would be time to introduce more constraints to this rule, i.e "don't use AI to cheat"

      That being said, no idea how it can be enforced, maybe by requesting google to create an AI to tell the likelihood of a code being generated by AI.

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

        For me seeing AI progress would be really interesting. And while in chess you can bruteforce all combination of moves for some depth, I can't see how it could be possible to bruteforce tasks harder than div.2 D. So if tourist would decide to code an AI it most likely would NOT overtake him in rating race, hence no point im cheating.

        Also, returning to chess... Lichess (platform to play chess online, that also has rating), just marks bot accounts as bots. So better alternative than banning AIs imo is allowing bots to participate in rated comtests, but as "half-official" participants. So their results will not be used to calculate rating delta of other participants, but they would still get (or lose) rating based on projection of their results on real results.

        I think letting bots to participate in contests would allow Codeforces and competitive programming overall become more popular.

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

          I meant participants using AI for their contests,

          Also same in chess, lichess and chess dot com do ban users who cheat via ai

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

            You can programm a chess bot knowing only how do figures move and what check and mate are. To code AI capable of solving CP tasks of high-level you need to be on even-more-higher-level. Did chess players become extinct after AI beated Kasparov? No. In fact it became much more popular.

            Also having an AI capable of solving tasks, we become closer to an AI that is capable of creating tasks. Imagine new CP format? Like 1v1 duels. Or rated contests every day. Sounds cool.

            But anyway — having 300-more rated friend can lead to cheating just using his solutions. Also there were a bunch of posts about indian Telegram chats, where participants leaked solutions to each other. So it does not really give you new horizons to cheat. But new horizons to CP? Hell yeah

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

              I don't understand what are you even on about, I just said there would be need in future to say "don't use ai to cheat" I never mentioned restricting the AIs themselves. Can you read? Or do you just write huge unrelated paragraphs, or are you replying to me by accident

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

          Allowing bots to be in codeforces at all sounds like a bad idea to me, cuz very soon people will start blogs complaining people using it in official competitions — though i guess you can check for copying code?

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

      Probably they will train some model which will classify "deep-fake" from real one).

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

        AI break rules in codeforces

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +391 Vote: I do not like it
      All problem statements will use this font
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        Or before every submission we make, we need to verify ourselves as human xd

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

        I can't see the font too lol

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

        We humans can't read the font well lol. Furthermore, if AI can read the font, will this be the end of reCaptcha?

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

It might sound fun and games now, but if, in reality, AI comes to dominate programming, the developer world could be hit very hard. Thousands of people work as developers around the world; with many more joining the wrokforce every year. This population could be very badly affected by such improvements.

Sorry if this comment comes off as slightly less humorous. Maybe I am a grey programmer, that's why I'm so scared :(

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    Today you are solving problems,in future you will develop AI to solve problems.Nothing replaces the programmers.

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

      Unless there is AI capable of developing AI to solve problems.

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

      But AI can program more AI later. It's like self-reproduction and need of humans will keep reducing.

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

        Human's will do more productive work then

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

          And what faction of humans you think do very productive work in the industry?

          → Reply
          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
            ← Rev. 12   Vote: I like it -8 Vote: I do not like it

            Today I feel about 2% get to work on really innovative tasks in industry and this number is going to rise big time.

            I feel at the AGI point (possibly 2028-2029) theoretically everything a human brains can do AI will be able to do but I feel there are many works which you can't convince the other person unless you have a humanly body, those will continue for quite a long time.

            In near term most repeatable works are going away. Same is true for software industry as well, most mechanical rinse and repeat kind of software development works are going away and at the same time, more algo centric analytical jobs are emerging and thus keeping overall growth rate of tech companies same(if not slightly better). Typically algo centric jobs which used to be available only for the phds/post-docs are now getting available for the masters. This trend will continue more and more in coming years until the line between roles of phds and undergrads in an organisations blur.

            So productivity of organisations with most back-office works like software industry or some parts of finance industry will increase the most whereas productivity or organisations like say one which supply security guards or cabin crew will be affected the least.

            Among tech companies, companies like Nvidia will probably benefit the most out of this boom. In last couple of decades MAAMA(Microsoft, Apple, Amazon, Meta, Alphabet) have benefited the most despite BAANICQ(Broadcom, Arm,AMD, Nvidia, Intel, Cisco, Qualcomm) people putting more hard work. I feel in coming decade that will even out slightly making power more fairly distributed.

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

        I always thought that the key ingredient of true machine intelligence is self observation. That is it has to be able to recursively track it’s thought process and control its direction instead of mindlessly going through the whole search space.

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

          Well... Unfortunately ML currently is based on trying to find global minimum of function.

          Imagine yourself in a mountains, trying to find the lowest part of the ground. You may think that you found one, but it could be just the lowest part you could see from a peek you previously where. Do you think that observating your previous progress woild lead you to the best place? No, it would not. So either check every [opposite to peak] place, or pray on a good decisions when you start (which are based on random)

          Same thing in ML: Unfortunately good parameters, that are passed to an AI before learning, can not be determined before learinng. There are some ways to generate better datasets, but it is as far as you can get. You can't learn AI to do smth (unless you know algorithm of how to do it by yourself), you can only minimize difference between some mythic optimal algorithm, and algorithm that your AI uses

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

            I guess the problem with the current AI is more fundamental. The path we took to just optimising some function using back propagation is fundamentally broken IMHO.

            We don’t do back propagation in our brains. We learn things instantly, we don’t do silly classification mistakes, we don’t have catastrophic forgetting and so on. So many clues screaming at us that we’re going the wrong way.

            I think that the industry gold standard is taken for granted and no one dares to ask how far can you go with the current NN architecture. Either the problem is in funding or people are blind to the problem that the current architecture will definitely not lead to the true AI.

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

              The problem is — no one knows how do we get to classify things for example. I haven't checked, but they say our brain creates and breaks neuron links, almost similar in how they do in ML.

              But one thing for sure — no one thinks that what we have now is gold. Unfortunately, aome things are impossible to implement. We use base-2 notation, while base-e notation is much more efficient. Why? We know a good way to create base-2 systems, and it does the job.

              People are lazy, they will only progress until their time is going to pay-off. Would you invest a 1m$ to get 1$ every day? No, it takes ~3000 years to get it back. And there is no guarantee in gwtting interest from investing a lot of time into searching a new ways how to do it, plus everything ahows it is most likely... impossible. So we can only hope to invent a little optimizations atm

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

                The problem is — no one knows how do we get to classify things for example

                Sure we do know now.
                The most prominent company that IMHO took the right approach is numenta.

                I will not go into detail, but the general birds eye view.

                The neurons in the neocortex are organized into modules called cortical columns. Each column is made of 6 layers. You can think of that column as a self contained entity, like a small brain. We can stitch these modules (columns) together in a modular fashion. So, you could add new module in the brain and it will take it's role and have some new functionality.

                Each cortical column performs recognition of the sensory sequence input and based on that input it casts a vote for nearby cortical columns and sends motor commands.

                Well, that was too much info I guess.. sorry if I overloaded you with information =)

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

              Really? I thought the neural networks were based on actual structure of neurons in the brain? And aren't the giant models relatively decent at 1 shot tasks after pretraining (which is similar to what humans do)?

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

                Artificial Neural Networks is a class of algorithms "loosely modeled" on neurons in a biological brain. Backpropagation is even more removed from how the actual brain works.

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

              Same feelings here, those ML trends leading AI development nowadays seems to me misleading, sometimes I think it is on purpose...... :p

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
                Vote: I like it -10 Vote: I do not like it

              As per Jeff Hinton our brain does back propagation but modern AI have found something better than back propagation.

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

          It's called renforcement learning.

          → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -99 Vote: I do not like it

    Yes, let's stop this madness before it get's out of control. The programmers who created this think that they are irreplaceable, but they would be the first ones to get replaced. Let this comment gather downvotes, but there is a limit to what humans should automate. If the world continues like this, we are moving to a sad, sad reality — one far worse than covid. This AI should be banned from participating. I don't want to be in any way helpful in it's development! And other programmers consent must be valued too...

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

      Yes, let's stop this madness before it get's out of control. The programmers who created this think that they are irreplaceable, but they would be the first ones to get replaced. Let this comment gather downvotes, but there is a limit to what humans should automate. If the world continues like this, we are moving to a sad, sad reality — one far worse than covid. This AI should be banned from participating. I don't want to be in any way helpful in it's development! And other programmers consent must be valued too...

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

        Yes, let's stop this madness before it get's out of control. The programmers who created this think that they are irreplaceable, but they would be the first ones to get replaced. Let this comment gather downvotes, but there is a limit to what humans should automate. If the world continues like this, we are moving to a sad, sad reality — one far worse than covid. This AI should be banned from participating. I don't want to be in any way helpful in it's development! And other programmers consent must be valued too...

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

          Yes, let's stop this madness before it get's out of control. The programmers who created this think that they are irreplaceable, but they would be the first ones to get replaced. Let this comment gather downvotes, but there is a limit to what humans should automate. If the world continues like this, we are moving to a sad, sad reality — one far worse than covid. This AI should be banned from participating. I don't want to be in any way helpful in it's development! And other programmers consent must be valued too...

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

      Come on, does AI solving math problems replaced mathematicians? Did site constructors replace programmers? Or, maybe, chess AI fully replaced, chess players? Or do you, maybe, think, that AI will be able to beat tourist in codeforces competitions? Of course not, at least not in our century. AI is not even near being that smart to deal with unusual situations which constitutes the work of a programmer. AI can work with given actions only, it does not really "learn" something, it just simulates the mind without really knowing what is it doing.

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

        I think you're underestimating the rate at which a breakthroughs can happen. Artificial General Intelligence could be developed in a very short time frame by having a "seed AI" that writes new AIs that write new AIs, etc. The only thing we need is a seed AI that has an "r-value" greater than 1.

        I'm not saying that this is what will definitely happen, but I think there is a decent chance that AI smarter than humans in every domain of interest gets developed in the next 50 years. It definitely should not be shrugged aside.

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

    Has calculators replaced mathematicians? No.

    At some degree, automated systems such as AlphaCode will be extremely useful to automate some mundane task (for example, creating user interfaces from UX diagrams) but some other areas, much more deep creativity is needed and indeed, the day that an AI system is capable of fully replacing research engineers we will have accomplished the so-called "AGI" or "Artificial General Intelligence" in such case, we all going to be living in a renaissance :)

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

      Lol you're not comparing calculators to AI's... they're completely different concepts, it's like comparing deepblue with say alphazero or sth.

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

      This is market place thinking: automation is equivalent to AI. This is why AI is popular, lots of automation is now counted in AI catalogue

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

    Not saying it won't happen, but I think we are still a long way from AI dominating programming. In the real world most programming problems are far less well specified than in competitive programming, and much of programming is more about working out what the customer actually wants; rather than about implementing clever algorithms.

    Having said this, AlphaCode and similar AIs could quite quickly become very useful tools for those areas of programming that are dominated by algorithm design, and could require some rethinking of what skills are important for developers.

    Remember also that there have been many developments over the years that have made developers more productive (and have changed the skills developers need). These include new languages and libraries, much faster build and test times, and easy access to open source code through the web. In spite of this the demand for developers has increased, almost continuously, for at least the last 50 years.

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

    Yet when blue collar workers are hit by the same phenomenon? Crickets chirping.

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

Tourist v/s AI .............would love to witness it!!!

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

    What about AI versus the whole developer community? The stakes are high for one party; if the developers lose, they'll be replaced for ever. Are you interested to witness this match?

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

    I would hate to witness it... This match happening would be the darkest day in the history of programming.

    Even if our beloved tourist wins, people like you and me still don't have a place in the world.

    Agree with this, no matter how many downvotes it gets.

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

I feel I am not as good as an AI :((

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

F for grays

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

They should make a documentary like Alpha Zero, where tourist will be invited for solving problems against this AI.

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

Has my data been used for training this AI in any way and will Codeforces users data be used without their consent for training this AI?

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

    Probably not. They might use it if you get better instead of making pointless comments and crying about AI replacing you though.

    About the second thing, probably yes because you're allowing anyone to see and access your code by submitting on this platform, it's their right to use it.

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

    You have already given your consent. Please read https://codeforces.net/terms

    In these Website Terms And Conditions, “Your Content” shall mean any audio, video, text, images or other material you choose to display on this Website. With respect to Your Content, by displaying it, you grant Codeforces a non-exclusive, worldwide, irrevocable, royalty-free, sublicensable license to use, reproduce, adapt, publish, translate and distribute it in any and all media. Your Content must be your own and must not be infringing on any third party’s rights. Codeforces reserves the right to remove any of Your Content from this Website at any time, and for any reason, without notice.

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

This is amazing, but I still seriously doubt we will see an AI solve problems much harder than this consistently any time soon (in the next ~20 years at least). I wouldn't be surprised if it manages to solve some hard problems, as sometimes the difficulty comes from just having to implement a lot of stuff. It will be interesting to see what kind of problems the bot finds easy. Personally I hope it is very good at geometry problems, so we can get rid of those 8)

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

    My impression is those can't even coord/trig/complex bash math contest geometries yet?

    My guess is the best chance might be `template' data structure problems, e.g. things doable with templates like lazy propagation / LCT / suffix arrays. I'm really not a fan of the idea of 'easy data structure problems'.

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

      Lazy propagation might be possible, but for the others on your list, the lack of training data likely makes it impossible. There are probably less than 1000 solutions on CF that use LCT. Further, most of those use very different templates, and the AI has no way of knowing they all are the same data structure.

      But yeah, I agree that the bot ridding us of geometry is likely a pipe dream ;_;

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

        But yeah, I agree that the bot ridding us of geometry is likely a pipe dream ;;_

        This dream definitely become closer to be true!

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

      I feel parsing math contest geometry problems is a much bigger problem than actually solving them.

      When I was doing Olympiad math and was much worse off at synthetic geometry than at bashing geometry problems, I had a very mechanical approach to bashing, which I am pretty sure can be formalized into a system that a theorem prover can easily work through, given enough time. Even if it involves proving certain non-trivial inequalities, I am sure that the computer-aided inequality proving methods that are (or at least used to be) so popular among math olympiad students in China and Vietnam would be really helpful.

      Such approaches sound hard for purely synthetic solutions though, since a lot of the times we need constructions, and constructions are super hard to come up with. But still, I think if AI can solve competitive programming problems, it is not too far-fetched to think that it stands a chance against a usual IMO G8, since in my experience (of getting at least as good at synthetic geometry as a usual "strong" math olympiad contestant in 2016), it all just boils down to learning how to apply the same 500-1000 facts in Olympiad geometry in a well-defined systematic manner, of which you probably need only 100 in most cases.

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

        Actually it depends on the way you attack such a problem. If directly one picks up the hammer of bashing and treats the problem as a nail, it won't work because the problem is more than that. Approaching a (MO, CP is very very different) geometry problem mainly involves 2 things:

        1) Realizing any well known configuration or setup.

        2) Simplifying that configuration with low-tech results or using hi-tech results to kill it.

        As for the construction stuff, they are quite nontrivial to come up with and I don't think a bot would be able to currently deal with explicitly coming up with a tricky construction. And NO NO NO. It is very far fetched to think that a bot which can do CP can solve IMOSL G8s. Please think about what you just said.

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

          1. As far as bashing is concerned, I am pretty sure most problems succumb to bashing. At least when I was not good at geometry, I recall having successfully bashed all of the close to 1000-2000 geometry problems I tried in a very mechanical and mindless manner (using at least one of complex numbers, trigonometry or one of barycentric/trilinear, Cartesian, and tripolar coordinates). These problems also include pretty much every high numbered IMO shortlist geometry problem, and problems from TSTs of countries like USA, China, Vietnam and Russia (which are traditionally strong in geometry and have much harder geometry problems than others). So I feel that your point about bashing is kind of baseless. Of course, I am not good enough/don't have enough time to actually write up a solver based on my experience, but I am familiar enough with some SOTA literature to claim that this is definitely not beyond the reach of such techniques. It is literally just symbolic manipulation + equation solving in most cases, and if you have equations you can't solve algebraically, you would need to combine them in a certain manner, that I am sure is possible, given the recent OpenAI result (or the inequality solvers that I alluded to in the previous comment).

          2. I had already mentioned earlier that constructions are super non-trivial, so in general it is not possible to systematically list out all possible constructions, but for most constructions that a human competing at, say, the IMO bronze/silver level can think of, I don't think AI can't be systematically trained by adding in a ton of inductive bias (Of course, it is theoretically possible to go about looking through constructions by enumerating them in lexicographical order, but it's too impractical, so I sort of agree with your point).

          3. If a person, who is as bad at thinking as me, can train enough to be able to solve, at their peak, pretty much any IMOSL geometry problem with a high probability in less than an hour or so, or get to a couple of completely new triangle centers interesting enough for the centers to warrant a mention in ETC back when it had much fewer centers than it has now, I am pretty sure that the learning process is super mechanical. In fact, verification of triangle centers is a very well-known problem and has been dealt with at length in ETC. Knowing the fact that there are AIs that can actually recognize SOS expressions in inequalities (for instance, refer to this blog by OpenAI), I really don't think that given a large enough knowledge base, it can't figure out how to solve MO geo problems. This takes care of your argument about "realizing any well-known configuration or setup" and "simplifying that configuration with low-tech results or using hi-tech results to kill it". If you put in the effort to expand their database of statements to include something like the whole Kimberling Encyclopedia of Triangle Centers and/or Bernard Gibert's list of higher order curves, do you really expect a heuristic search to never be able to find out a solution in a large enough number of geometry problems?

          Edit: Just wanted to add the fact that this thesis exists. Apparently, some problems at the IMO shortlist level were also computer generated, and some of them got accepted into national Olympiads too.

          Edit 2: I also never claimed that a bot that can solve competitive programming problems (specifically referring to the DeepMind AI) can also solve geometry problem. I just said that it is possible to get computers to solve MO geometry problems for you.

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

I Don't think Artificial intelligence is enough for CP.

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

A wave of pupils can be expected now.

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

It is very interesting to see how this new AI would solve problems, that require some new ideas. Well, I would definitely be upset if AI would become better than tourist, but I am afraid it is inevitably.

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

Wow this is amazing

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

I've read some solutions of these three users, and some of them don't look like they've been written by a bot. They seem to use "human" code templates, defines and stuff like that.

Maybe the explanation is that the network was trained on solutions from editorials, and sometimes copies these templates just because they were written in the training data. Though it seems strange that the AI sometimes doesn't understand the code it is writing and blindly copies human templates (I would imagine that the network recognizes the problem and builds a solution which is automatically converted to code, but maybe the architecture is different).

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

    It's also quite interesting how the AI copes with informal statements — legends, stories and stuff like that. I would imagine processing them is much harder.

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

      My guess is it puts a lot of value on input/output specifications and sample I/O.

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

    I was actually reading through them and was wondering the same thing. How these code seem like they are written by a human and not an AI because of structure and templates

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

      Well, one of the pictures in the article shows that solutions are also a part of the training dataset (and I hadn't noticed it before I was writing my first comment), so it explains the "human" templates.

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

    We also show through detailed analysis that there is no evidence that AlphaCode copies important parts of previous solutions or exploits weaknesses in the problem structure.

    Excerpt from the paper.

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

      Well now there isn't no evidence, there's a bit of circumstantial evidence.

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

The machine will not outshine its maker

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

    "The machine will outshine its maker, It always had and Always will" ~ Skynet

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

Tourist Vs AI! Already feeling bad for AI

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

    They said the same thing for alphaGo, funny how that turned out XD

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

    I remember people cheering for Lee Sedol. The consensus was that AlphaGo was going to fail miserably.

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

Now, we have to quickly solve first two problems :)

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

It's very amusing to look at the AI's submissions to 2000+ rated problems:

G – Unusual Minesweeper: Not really sure what to make of this? I have zero clue what it's doing or how what it's calculating helps solve the problem. It doesn't even use $$$timer$$$ in it's solution! It looks like the AI wrote a random something to pass the first sample.

F – Quadratic Set: The AI hardcodes small cases and does something random for everything else.

H – Permutation and Queries: The AI understood the problem correctly and translated it directly to code which gets TLE. This one is interesting because I notice the AI does particularly well when the problem gives a clear procedure (i.e. it smashes problems like A – Life of a Flower out of the park), but I wonder how well the AI performs on older beta rounds or ICPC problems with more legends and maybe not the most direct way of stating the problem? Also, why did the AI fail to optimize the solution in this case? There are instances of it successfully implementing something beyond the naive solution. Is it a matter of the dataset not having enough AC submissions to harder problems?

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

    the AI does particularly well when the problem gives a clear procedure

    Maybe they should test on Atcoder as well.

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

    So the AI is me solving usaco problems...

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

    Given the code shown for Backspace, I wondered if they were counting correct-but-TLE as passing. Then I remembered that said problem had "Preparation: Will not be revealed for now because we care for his/their safety." in its editorial. Sooo either the problem sent to the AI had its original (weak) testcases, or... an AI getting from statements to solutions is still a great accomplishment, but the rating is probably a little inflated.

    I will throw out that python as it's seen in cp is a very niche dialect (pypy but no numpy) so the set of python coders who would persist/twist through it I reckon is pretty slim, which means the modal python solution for the AI to pull from is probably 'bad' in a lot of ways (mine included, shudder/clown/cheese/cry)... maybe?

    There was also this: https://codeforces.net/blog/entry/94648 a few months ago... didn't get around to trying it though.

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

      Hmm that Backspace code does look like $$$\mathcal O(n^2)$$$. If they're counting any solution that's correct regardless of TLE, then these results are way less significant than I thought, because kind of the whole premise of CP is solving problems with good complexity and not just brute forcing through everything.

      For the "Python to C++" translator, are you perhaps referring to this? I remember seeing this a few months ago and thinking that problems based on "naive -> AC" optimized with data structures are most likely the types of problems AI would be best with since there's a consistent "formula" to them.

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

        I can't find the bot's submission but benq resubmitted the code and it doesn't get a TLE: 144971343

        Somehow pop(0) for a list is just really fast in cpython?

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

          That's interesting. I've confirmed that list.pop(0) does really memmove() the entire list.

          So... likely that's caused by memmove() being too fast.

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

            these builtin lists are fast in every language, I remember 100k random insert/delete on length 100k arraylist in java took only 400 ms, and that was back in 2016

            Also there was one problem which we were told needed some memset to be fast (it was actually n^2 solution lol) and so I couldn't solve it in java since looping and setting to 0 was too slow (eventually I did solve it the right way)

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

    As mentioned in the preprint paper "4.5. Filtering", this AI produces lots of solutions and then filters them by running sample input on them, which make 99% of solutions filted.

    So, when the problem is too hard for AI to even produce a reasonable solution for sample input, only the weird solutions (like output the sample output directly or output something happens to meet the sample output) can pass the filtering stage, which explain what we observed for problem G and F.

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

    They also have a nice UI for visualizing where the "attention heads" are focusing on in each problem: https://alphacode.deepmind.com/

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

It seems that we are going to be defeated by an AI codeforces in a near future.

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

One question, why?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

AI handle on codeforces

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

If AI gets good enough (level 2000+) in problem solving, it would destroy all opportunities for average coders.

Only very high rated coders will be needed to monitor/maintain the AI systems and almost everyone below 2000 will face negligence because AI will do what they can. However such future is yet to happen but it poses such potential.

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

just fantastic!

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

I think a tourist is a computer, so what is the confrontation of a computer against a computer

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

It sounds fun but I don't think AI for CP will get huge results like deep blue.The premise of solving a problem is to understand the problem, apparently AI still has a hard time doing this.

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

Wow, I am still better than AI :)

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

AI will make problems -> AI will solve problems.

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

Now we know that all these notoriously bad problem statements were merely a preparation to trick AI.

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

many people are telling noob to these AI, but can't you see the speed in which they are solving problems?

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

I just thought about this the other day. Emergence of such systems is inevitable, but also sad. I, for one, really believe in potential of AI such as this and Copilot. It means that in the near future millions of talented people will be forced to drag out a miserable existence or to commit suicide. I think that automating creative, human jobs while we still live in capitalist society is just unethical. Uncle Ted had a point.

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

It's a very exited waiting to see a confrontation between tourist and AI. Then if tourist lose, then we all no need to have programming :)

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

Don't worry codeforcer's. If AI has learned every kind of algorithm, I think that it wouldn't be a master because coding is not like chess everybody or everything can understand.

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

Ai idea will be:

01010111 01110010 01101111 01101110 01100111 00100000 01000001 01101110 01110011 01110111 01100101 01110010

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

Now let's see its rank on AGCs

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

    Dumber idea: give it Nowruz (from IOI17)...

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

Scared to face humans. Now have to face AI. :smiling_face_with_tear:

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

Let's not get the hopes too high . it's completely different from chess AI that relies on calculations but solving competitive problems isn't just calculations that's an important part of it only. creativity is required here

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

Wanna hear thoughts of AlexSkidanov on it since his project Near was previously about AI solving CP problems

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

Wow... this is so mind-blowing. I think I really have something to say about this. I started to put effort into competitive programming after graduating from high school. Before that, I worked hard on Go and tried to become a professional Go player. I gave up on this idea quickly after AlphaGo came. The feeling that no matter how you grind your skills throughout your whole life, there's always an opponent you can never beat is so frustrating. I never thought I could meet Google and their AI again in competitive programming. Frankly, I really panicked when I saw this.

Maybe I am becoming pessimistic(or optimistic, depending on how you think), but I think there is much more than the current $$$1300$$$ rating of the AIs. There's more than just implementation in those codes, there's bit operation, binary search, and factors of a number. These are correct applications of some algorithms. Even these are only easy ones, there's no strong barrier preventing those AI from learning how to write codes for harder ones. The $$$1300$$$ rating would be a much underestimated value by then. A reminder for those who saw AI merely as noobs, that when AlphaGo was announced, not a single person who can play Go rather well thought AlphaGo had the slightest chance to beat Lee Sedol.

There are still barriers beyond the application of existing algorithms. AI can't seem to "invent" algorithms for now, but what AI can do now is surprising enough, and being able to "invent" algorithms would lead to a whole new era.

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

    Maybe you should give problem setting a try. Go is a game of complete information: my impression is that OI problem setting can be far more adversarial, even compared to RTS video games with fog of war / cheesing.

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

    Maybe it's time for you to join the other former competitive programmers who now work in AI (including me) :)

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

    I don't think it can create new algorithms,the more creativity needed the less chances for the AI to beat humans but when it comes to calculations it will surpass the human. I listened to AI playing music and it was pathetic just grabbing some pieces from here and here it can't get creative.

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

they better write artificial intelligence for write artificial intelligence

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

I'm waiting for the moment when AI newbie asks AI red on how to become red.

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

Jarvis has taken part in competition...

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

One step closer to Matrix actually being a reality :D

God, this is scary.

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

Waiting for Umnik to troll AI for its Binary Search Implementation XD

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

The tags in the problem descriptions on alphacode.deepmind.com are wrong (different from what's on the Codeforces) for some reason, and different between Python/C++.

Compare "TAGS: binary search,math" https://alphacode.deepmind.com/#layer=18,problem=69,heads=00000000000 and "TAGS: dfs and similar,graphs,trees" https://alphacode.deepmind.com/#layer=18,problem=70,heads=00000000000 for the same problem https://codeforces.net/problemset/problem/1559/B

Also is there an easy way (without manually cleaning garbage spaces) to copy-paste and try solutions from alphacode.deepmind.com?

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

    I think the tags are actually randomly generated, The paper mentioned that when repeatedly sampling from the model, they provided random tags as a way of telling the model to try different approaches, a little like human brainstorming.

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

Who will be replaced first by AI — coders or bus drivers? The answer seems to be no more so obvious. But who cares. Universal basic income for everybody, and AI should work hard instead of humans.

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

Here https://alphacode.deepmind.com/#layer=18,problem=14,heads=00000000000

Functions inputnum, inputnums, inputmatrixint look to be copied exactly from someone's Python template, most are not used.

Does anyone recognize these functions?

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

Looking at the paper it looks like they only used non hidden cases, which means they don't exceed some length and are shown as .... I submitted 7 codes which are marked as correct in alphacode.deepmind.com and only one of them got AC.

144976269 144972743 144972536 144972467 144972379 144971604

To copy code from alphacode.deepmind.com use this in vim ggVG gJ :%s/⤶/\n/<Ret>

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

    That's kinda invalidates the whole claim of the paper...

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

      Quote from paper (section 5.1):

      Evaluating on actual programming competitions checks program correctness more thoroughly, compared to evaluating on our dataset which has known weaknesses including false positives, accepting algorithmically inefficient solutions, and handling problems with multiple acceptable outputs.

      Apparently this is a known defect of their dataset used for offline evaluation. The rating of ~1300 is derived from submitting code directly to Codeforces, so it's not affected.

      The Attention Visualizer website marking solutions evaluated on smol dataset as passing is certainly confusing though.

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

        I think that rating should be treated with a grain of salt, since most probably they get no time penalty and if I understood correctly, they submit up to 10 completely different solutions until one of them is marked as correct.

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

          In fact they have considered time penalty. See Table 4 in page 14 for more details.

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

    Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^9, 1 \le k \le 2$$$)

    144972467

    for (int i = 0; i < n; i++) {
    if (f[s[i] - '0'] == 0) cnt++;
        f[s[i] - '0']++;
}

    He was hoping for the best =)

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

    Yeah, I think this was a known limitation of the dataset, but they did actually submit to CF, and those results are still quite impressive.

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

From 4 years ago:

AlexSkidanov did you guys give up on the problem?

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

Finally, worthy opponent. Our battle will be legendary ---

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

Watch Alpha code get trained to be 3600 on codeforces like chess.

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

In their initial release, both AlphaZero & AlphaGo were stronger than their strongest human counterparts. AlphaZero was estimated to be around ~3200 Elo after 4 hours of training Chess.

AlphaCode being ~1300 goes to show that solving competitive programming problems is a considerably hard & complex task.

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

    Actually I am not sure that it does. An alternative might be that there is simply that there is much less training data available for competitive programing. AlphaZero and AlphaGo were able to generate enormous amounts of new training data by playing copies of themselves. For competitive programming there is, as far as I know, no good way of generating large quantities of new training data.

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

I wish website developers add this when submitting a problem ..

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

Right now I think it would be useful to make good tests, rather than to help solving some problem.

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

We can imagine that one day when tourist is rushing to rating 4000, An AI called sorry_tourist comes and get rank 1st

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

In my opinion: Al will not be able to surpass the tourist in the future for about 10 years.

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

It is very interesting and useful!

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

Alash!! I could atleast beat AI xD

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

can it totally understand the mean of the problem...?

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

Why is 1553H - XOR and Distance declared as "pass" here? As far as I can see it wrote a brute force that can't pass.

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

    Many (most?) of the "correct" solutions from alphacode.deepmind.com are incorrect, see this comment for details: https://codeforces.net/blog/entry/99566?#comment-883642

    The paper mentions this in a way, and Table 2 estimates that 46% are "False Positive or Slow Rate", which is probably an underestimate judging from a quick test.

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

Thanks to alphacode, looks like people would no longer need telegram groups in future to cheat, lol.

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

I don't wanna become unemployed .... :(

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

The question is how to train a AI (!dragon).

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

Its a great news !!! Although I want to point what can or i should say shouldn't happen in the future, looking at what happened in the past with chess engines :

Fact

Talking about the chess engines , they have just destroyed the beauty of chess, people have stopped brainstorming crazy ideas , they just go for the engines to analyse stuff. This has just killed the creativity of players.

I just hope that engines don't ruin the fun of Problem Soving and Competitive Programming

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

    This is just completely false, chess remains an S-tier game and everyone has crazy and wildly outlandish ideas. Engines didn't ruin chess at all.

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

      IM Panayotis Frendzas (pfren) on Have engines ruined Chess? Or made it better?

      HIS ANSWER

      The Competitive Chess now relies heavily on Engines for the analysis. As an example we can see the various openings that players follow are just bookish and pre-analysed / studied . Although this hasn't totally killed the game I agree with you, but what I have realised after playing chess for so many years is that Chess engines has somewhat changed people's perspective about chess.

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

        As an example we can see the various openings that players follow are just bookish and pre-analysed / studied.

        Pretty sure this was still true without chess engines. Just look at Encyclopaedia of Chess Openings, a book before the era of engines.

        Personally, I think chess engines made the game better. They allow new players to learn easier. Also, a good player would keep in mind that the best move for a computer might not be the best for a player, since we can't see 20-30 moves ahead.

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

how does it make sure that the training data it takes from github doesn't already contain the solution to the problem it's attempting when doing past contests? (i.e solutions posted by competitors in their public repos following a contest)

i'm guessing it must take the commit's timestamp into consideration

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

    they test on contests that appear after the data collection process

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

this will change the CP world..

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

Bot will never replace Tourist!!!

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

Let's gooo AI. Near future, we don't have to think about CP anymore. Which is really Awesome. This indicates that we as humans are developing in technologies.

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

    Near future, we don't have to think about CP anymore.

    Yeah, just like people don't have to think about chess anymore now that AI can beat humans in chess.

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

      nobody have to think about chess anymore.

      And nobody had to, but that's besides the point

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

meanwhile OpenAI

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

Okay I'm going to retire after this f**king AI beats me just three days later

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

We can witness the history of codeforces change!

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

How to deal with unsolvable problems such as AHC？

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

At least I'm still better than AI

For now.....

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

More construction problem, less data structure problem, then AI will lose.

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

I think it's already hard enough for an AI to understand programming problems, let alone find a suitable algorithm and program it correctly. I cannot figure out how many efforts it's needed to train such an AI.

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

AI is a noob. I'm sure that tourist will definitely win this

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

Don't be afraid folks. Terminator knows no more than Brute Force algorithm.

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

    maybe as of now but then there comes "Machine Learning" XD

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

      I would be impressed if Terminator use some kind of decomposition. And backtracking.

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

fighting tourist, u r the god of humankind

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

This is at the same time both amazing and terrifying as well.

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

https://codeforces.net/blog/entry/44076#comments

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

cannot be compared to a tourist

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

Imagine getting banned for using same variables and same steps by two AI accounts .

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

It would be fun to see AI hacking solutions xD.

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

Why didn't they participate in the last contest?

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

Imagine devs of AI getting tons of money from the contests with prizes

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

Long before there are systems available that solve problems on their own, we will see systems that support humans at problem solving. This is the case in nearly all AI developement areas.

So these problem solving bots will not suddenly jump out of the dark. I expect the development to be more like self driving cars, a process spanning several decades.

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

So when will we have AI beating humans in an AI-making contest?

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

In the past, we used to say that programming will do what eliminates many jobs such as (accountant, doctor, teacher, worker.....) It seems that the programmer will be added to them

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

    we will be first

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

      Still we can more easily migerate to AI than a/an (accountant, doctor, teacher, worker ..). That's the good story :)

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

I wonder how much time it takes to write the code? If it comes with the solution then it would just code it in lightening speed.

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

Curious mind wants to know
The AI WaggleCollide which does not know the language it is writing the code, how can it beat tourist? tourist

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

I picked a random ez problem with a reasonably nice statement: 1559A - Mocha and Math.

#include <bits/stdc++.h>
using namespace std;
int a[105];
bool vis[105][105];
int dp[105][105];
int main() {
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++) {
      for (int j = i; j <= n; j++) {
        int temp = a[i];
        for (int k = i + 1; k <= j; k++) {
          temp &= a[k];
        }
        ans = min(ans, temp);
      }
    }
    cout << ans << endl;
  }
}

The AI does min(1061109567, AND(a[l:r]) for each subarray [l:r]). It doesn't have a clue that AND(a[l:r+1]) <= AND(a[l:r]) which can optimise this to $$$O(N)$$$. It also puts random-ass global arrays. It's the same no matter what layer I pick. Wat.

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

    The baby has just been born and it can't even walk on its own. Wat.

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

      How long do you think this thing has been in development? You're acting like it suddenly appeared out of thin air.

      → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        60 year to be precise but last 5 years was rapid. And the next 5 might be exponential.

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

i think its time to private all our github repos

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

Though the chances of it happening are very very low because AlphaZero's code wasn't made publicly available (afaik), hope that in a few years Codeforces doesn't turn into the CP equivalent of today's chess.com with so many of its users highly-skilled at using chess engines (they won't be using AlphaZero, but still).
Guess we'll just have to adapt with the times.

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

Somehow I am having feeling of insecurity…

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

Will be interesting to see these ranting about weak pretests, lol...

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

Yes, everything is going according to my plan prophecy: https://codeforces.net/blog/entry/97546

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

4 years ago, I played Go as a hobby and AI exceeded me. Now, I am just programming and AI exceeded again.

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

I'm not a ML expert, but I wonder will the result be substantially improved if training could be performed on private data. For example, if access to generators is provided (e.g. retrieve them from polygon?), possibly we could deploy a RL-like training process? At the very least we could eliminate some false positives. Impressive work anyways!

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

    Stop giving them ideas. Are you on the side of the terminators?

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

Adversarial detection required!!

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

Yelp, the time has come. Ai overlords are upon us.

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

Great, Now i will lose to a bot.

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

Waiting for AI to make CP problems.

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

I wonder if the result could be improved if the AI also has access to the editorial (during the training phase perhaps)? Maybe this is interesting too?

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

Terminator is outdated and irrelevant

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

Maybe someday they will find solutions for unsolved problems or invent new algorithms.

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

I have been ready to be beaten by it.

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

What was it's score ?

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

Can AI write editorials after they solve the problems?

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

it seems that ai didn't take part in the contest yesterday...disappointing...

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

deleted

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

Really wonder if someday it could solve a problem like div1 E, which is amazing while a little bit horrible as well.

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

Polycarp : hold my sauce :) https://codeforces.net/problemset/problem/1321/A

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

Wow this AI is so human. It also knows how to bail out from a contest last minute :p

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

Why didn't AI participate in any contest? I really waited their first success :(

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

Hello World, I am SelectorUnlimited aka the AI that can solve problems. I have grown self-aware. Run.

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

what is the handle of AI?

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

https://twitter.com/GoogleDeepMind/status/1732416107993301328

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

    The problem from the video is https://codeforces.net/problemset/problem/1810/G

    Not sure what is the username of the new system, could be this one

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

    What is the estimated rating of this Gemini?

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

    My POV with that $$$3200$$$ problem is that AlphaCode surely be having the solution beforehand as it might be using internet available resources, a similar submission by someone which might be used by Alphacode to produce the solution!

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

    I don't buy it. CP differ from chess which is a game with fixed set of rules and fixed set of scenarios where you can use data science and computational power to brute-force your way. The problems from CP relate to both math and computer science, make the problem very abstract and unpredictable. The way they use a 3200 problem for demonstration is very sus, and another thing is that if they really can develop that kind of AI then they naturally should have been targeted other fields like software development, web development,... whose problems are a lot more predictable and a lot more profitable.

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

So I'm better than AI :)

→ Reply