valkyrie's blog

By valkyrie, 3 months ago, In English

In this post, we will use the recent OpenAI Codex product based on GPT-3, first introduced in Evaluating Large Language Models Trained on Code (Chen et al., 2021) to solve some Codeforces problems.

We use the round Codeforces Round #739 (Div. 3) because the current version of the Codex model was released before this round. As the model has been trained on the Github data, it is possible that it memorized some solutions for older problems.

Solving 1560A - Dislike of Threes from the statement only

This is a simple problem, and the statement kind of explains what we should implement. Let's just give the plaintext statement to Codex:

Prompt
Code

Demo of Codex in action

127276629

Disclaimers

It produces correct code on the second try, the first C++ submission was WA 2. The problem text has been cleaned a bit, and "end in the digit 3" was changed to "have the last digit 3" -- because for some reason Codex thinks "end in the digit 3" means "contain the digit 3".

Solving 1560B - Who's Opposite? from the problem statement and the editorial

Here we have no hope for the solution straight from the problem statement, as it requires some thinking. However, if you give it the editorial, it can produce working code from the first try:

127226971

No formatting is required: just copy and paste the statement and the editorial from the Codeforces website. No inductive bias in user input was needed at all!

What you can do if this is cool or frightening to you

It is a net good to the world if everyone has access to models such as Codex or GPT-3.

If you are a machine learning researcher, or maybe just a competent person in general, try to get involved in EleutherAI, Hugging Face, or something similar. If you want to work on important things, in my opinion language models are very critical right now.

Bonus: What you can do if you own a competitive programming site

The advice below is my personal opinion.

  1. Try to get a tester with Codex access for future rounds. I predict it could become a part of the cheating issue as soon as 2022.
  2. Think of what the rules should say about using this kind of tools.
  3. Prepare for the effects of competitive programming becoming less relevant to job interviews. If your financing model relies on job interview preparation, you will need to change it in a few years. (Codeforces and Atcoder seem to be in the best shape here.)

FAQ

Can language models solve harder problems?

Language models are a new and poorly understood object. Here is a gross oversimplification of the current conventional wisdom:

GPT-3 is a language model. Its main purpose is translating between different representations of the same data. It can do English to German, it can be used to describe imagess, and with Codex it can translate textual commands to code. Codex can solve the Div3 A from scratch because the solution just implementation of the text, but it needs the editorial to solve Div3 B.

As of 2021, language models are not intended for solving algorithmic puzzles or producing mathematical proofs. It is likely we will have a much more powerful Codeforces solver by say 2026, when the research manages to combine proof search methods with the GPT-3 architecture. When I manage to read enough papers on this, I will write more on my academic blog.

I can't see the demo.

If you can't access imgur, go to this link.

How to get access to Codex?

Have some academic credentials, and fill in the waitlist form at OpenAI's website with an interesting research proposal. Please do not use Codex for bad purposes such as cheating or spam.

How to integrate Codex with vim? I got access but I can only use it in the Playground.

Use vim_codex with your OpenAI keys.

What are the Codex parameters in the demo?

I used the OpenAI API from Python as follows:

API call

Read more »

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

By valkyrie, history, 3 years ago, In English

Hello, Codeforces!

It's our pleasure to announce the the finals of the 11th Bubble Cup! Bubble Cup is a programming competition organized by Microsoft Development Center Serbia (MDCS). The contest will take place on Saturday, 22nd of September at 11:00 UTC+2 in Belgrade, and will last for 5 hours. Live results will be available on the official Bubble Cup website. Results will be frozen during the last hour of the competition. The winners will be announced at the closing ceremony.

The format of the competition is very similar to ACM-ICPC — teams consisting of up to three people are allowed, and they have one computer and five hours to solve problems without partial scoring. Ties are broken using the usual time penalty rules.

Just like in the previous years, there will be an online mirror of the finals here at Codeforces, starting on Saturday, 22nd of September at 12:35 UTC+2. Unlike in the previous years, the mirror will be on the same day as the onsite finals.

This year, the onsite competition is divided in two "divisions", called Premier League and Rising Stars. The two contests will have most of their problems in common, but the Rising Stars competition will feature some easier tasks targeted at high school contestants. We do not guarantee that every problems unique to Div2 is easier than every problem that is not.

Both of the contests will be mirrored here on Codeforces, with Premier League mapping to the Div1 contest and Rising Stars mapping to the Div2 contest. The mirror will use native Codeforces ACM-ICPC team contest rules.

Both contests will be unrated, due to the format and the length of the mirror being dissimilar to the standard Codeforces rated rounds. Note that this is a team contest, i.e. competing in teams up to three people is allowed. (Of course, you can also compete in a 1-person team.) There will be at least 9 problems in each division.

As of now, Codeforces does not support rating-based divisions in team contests, so we came with the following ad-hoc rule: teams with the maximum rated member having rating less than 1900 should enter the Div2 contest. Teams with the maximum rated member having rating at least 2100 should definitely enter the Div1 contest. The teams not covered by the previous two criteria are free to choose.

Here are the past Bubble Cup mirrors on Codeforces:

Bubble Cup 8 — Finals [Online Mirror]

Bubble Cup 9 — Finals [Online Mirror]

Bubble Cup X — Finals [Online Mirror]

The problems and their solutions were created by employees and interns of Microsoft: Milanin, ibra, balsa_knez, Kole, radras, fulu, pedja, niksmiljkovic, davidmilicevic97, FilipVesovic, yours truly, and many more. Most of the team works in MDCS.

We express gratitude to KAN and 300iq for round coordination, and MikeMirzayanov and the rest of the team for the great Codeforces and the wonderful Polygon platform. We thank testers DBradac and especially the extremely helpful knightL, for helping prevail various difficulties.

The full editorial, together with the statements and solutions of the tasks from the qualification rounds, will be available in the booklet section of the Bubble Cup website on Sunday. An editorial with short descriptions of solutions may appear on Codeforces before that.

Good luck to all participants!

EDIT: Congrats to everyone that competed! In total, there were over 800 teams that solved at least one problem.

The winners of Div1 are:

  1. Merkurev, I_love_Tanya_Romanova, Um_nik — a special congratulations for being the only team on the mirror to solve all problems, two of them in the last 5 minutes!

  2. LHiC — the best one-man team, with 9 problems solved

  3. xtalclr, no_ng, ko_osaga — also solved 9 problems

The winning team of Div2 is:

  1. fengyecong, Als123, 200815147 — winning with three problems to spare!

This post will be updated again when the booklet is online, which should be before the end of the day in UTC+2. Also, onsite results won't be known until the awards ceremony in the evening.

Thanks all for participating!

EDIT 2: The editorial is up!

Read more »

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