newbie_forever_at_cp's blog

Similar Problems Webservice
By newbie_forever_at_cp, history, 3 years ago, In English

Hi Guys,

Many times, when we look at the solution for an unsolved problem or love a specific problem, we might want to try out a problem similar to it. Currently we can only search problems only based on tags. But from now on we can just input a problem and get a list of problems similar to it. We can query here similar_problems

Example :

Input

After Submitting,

Output

Here,

  • Problem Name is just the contestId + index. eg (1389A),

  • We can also specify the rating range which is the problem difficulty rating range within which we want out similar problems to be. If nothing is specified, by default it will consider problems rating between -500 to +500.

Currently, I am computing cosine similarity between two problem's tags. Yes, this is the most basic method which we can think of and obviously there are many false positives, but this is just the first version.

Any suggestions for reducing false positives is absolutely welcomed.

Please do checkout and let me know how you feel.

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

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

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

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

Very cool , I will add it to my list

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

How do you find the similarity score?

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

    cosine similarity. Consider the problem's tags as one hot vectors and find the cos(theta) between them.

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

It seems really amazing and helpful.

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

Is the similarity just on the basis of tags?

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

add similarity in terms of users who have solved the problem, that is probably very useful indicator

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

    Hi Twenty, Thanks for the suggestion. But could you tell me how to get all the users who solved a particular problem ?

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

Great.
Maybe you can use word embedding on problem statements to get similarity.

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

    Thanks, Actually using embedding on problem statements may not be a good idea as almost all problem statements have a very long story associated with them which adds too much noise. We can try using embedding on editorial, but it will be a very big task.

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

It seems it doesn't work last months. Does anybody know similar resources to find similar problems?

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

Instead of relying only on tags, using editorial similarity can help identify similar problems that require the same algorithms/techniques to solve.

→ Reply