NotIdeal's blog

Machine Learning in Competitive Programming
By NotIdeal, history, 6 months ago, In English

Do you think it is possible to solve some problems with ML?

For example, let's say you have a problem where N is 10^5, and you know the solutions to O(N^2), but you cannot optimize it so that it get accepted. Do you think it's possible to train your model using output data from N to 10^3 and get accepted?

Have you ever solved a problem using ML or related stories about CP and ML combined?

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

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

That's somewhat similar to this Knowledge Distiliation

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

I've solved some problems with very simple "learning" approaches. For most algorithmic problems with particular solutions you need to figure out, and that don't fit within a very standard pattern that you need to recognise, it's close enough to impossible.

The main area is optimisation problems. A human won't produce an ugly yet efficient heuristic, but it can be learned quite easily. Similar to that area is constructing an object with particular properties, if the constraints on those properties aren't too tight so you can basically optimise to fit those properties to a greater extent until you arrive at one of many accepted solutions.

Also, generating difficult test data is one area in which it can be applied outside of contests themselves.

→ Reply