TLE's blog

Finally, semantic search for competitive programming problems
By TLE, history, 5 months ago, In English

Hello Codeforces,

It has been a long while, but in this project we close the long-standing open problem proposed by Umnik 2021. You can try it here (deployed on my tiny server, be nice!) while supplies last. Currently I only imported problems from Codeforces & BZOJ (the dead Chinese OJ) but adding other OJs should be easy as long as we have the statements crawled (PRs?).

demo

Cheers!

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

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice Initiative

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

Nice idea, may be abused during live contests though.

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

I don't understanding anything. But it looks like something useful so I upvote for you.

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

Nice job!

→ Reply
»
5 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Wow I Was searching for SOS DP problems, and i was looking for something like This. Thank You.

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

out of curiosity: how bad would the search results be if we don't use chatgpt to simplify the problem.

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

Truly amazing work. You should write a paper about it or sth.

I'm slightly worried about consequences for competitive programming... you should probably block usage during contests as an anti-cheating measure. Otherwise you'll lose your credits pretty quickly :)

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

In regards to cheating concerns, this may actually reduce cheating incidents by making it easier for authors to find repeated problems.

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

this is neat, but then won't the training data annotators know your next problem when you plug it into openai?

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

    I'm using their paid API (same function as chatgpt but not free..), so in theory they should not be used for training :|

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

      I guess even then someone working at openai who really really wants to cheat on a contest could do it, but that's probably not going to occur. How well does it work? I tried plugging in this year's FHC 3B which seems very similar to 1870E but the ones it gives don't seem very closely related to it.

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

      However, I plugged CF1793F into it but it showed nothing that is even close to CF765F. What can possibly be the issue here? ig it's because of the problem background, but how to deal with that?

      Update: also, with this year's CSP-S problem 2, i plugged it in but still, it isnt showing CF1223F. Even after it's paraphrased to "Given an array of integers, we want to count the number of non-empty continuous subarrays that can be reduced to an empty array by repeatedly removing adjacent identical elements.", CF1223F shows nowhere on that list.

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

        Yeah, the system is still imperfect — we should probably experiment a better prompt to remove the backgrounds (you can find the current prompts here).

        For your second example, it seems doable with a bit of luck... img

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

          Yeah, automatically removing the background and actually "formalizing" the statement will be a great feature, and will help a lot ig:)

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

Amazing work!

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

Honestly, that is impressive. I wonder if the same thing could be done but with the editorials (so that people can find applications of different ideas and algorithms).

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

Is the link still live? not working for me

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

Wow what a wonderful work. Ask Um_nik for 1000 dollars.

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

Lol, this could be used in today's contest to figure out the solution for D.

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

I have implemented this project on Poe, so that the cost of calling ChatGPT will be borne by the platform (i.e. other subscribers).

(Disclaimer: I currently work for Quora / Poe).

Sample query — https://poe.com/huikang/1512928000278451

After reading the code, someone could try some of these

  • Using better LLMs to summarize (e.g. GPT-4)
  • Other retrieval indexes (predicted topics, keywords)
  • Use an LLM to rerank the retrieved problems
  • Instead of a decimal similarity value, provide a LLM-generated summary on whether the two problems are the same
  • Craft some evaluation benchmarks
→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

One idea: Use LLMs to read and write a summary for top solutions' source code of a problem and use the summary together with the problem statement for searching.

→ Reply