hoke_t's blog

Request for duplicate Codeforces problems
By hoke_t, history, 14 months ago, In English

I spent some time today working on a system to identify similar problems along the lines of https://codeforces.com/blog/entry/113064. For testing, it would be nice to have a list of duplicate (or close to duplicate, "one simple transformation" away, etc.) problems on Codeforces. The only pair I am currently aware of is (1793F - Rebrending, 765F - Souvenirs), so any others would help. Thanks!

EDIT: Just to be clear, I'm not interested only in strict duplicates, but also problems that share some important subtask, observation, or pairs in which one problem is a generalization of the other. And not asking for anyone to put any work into this, just thought some people might have pairs that come immediately to mind :)

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

Comments Comments (18)
| Write comment?
»
14 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Would a generalization be a good test? E.g. problem A is a subproblem of problem B with $$$k = 2$$$.

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

    Yeah, generalizations would also be great!

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

      Probably not too straightforward, but I'll leave it here.

      While holding my own round I got a message from a participant, that said problems 1486F - Pairs of Paths and 1336F - Journey are similar. But the difference is probably too big to count that as a duplicate.

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

        Still helpful, thanks! Will edit the post, I am actually more interested in problems that people perceive as similar in some important way than strict duplicates.

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

I feel such data is generally quite hard to come by, just because creating a problem takes quite some effort, and the usual "avoid similar problems" motto is adversarial for your use case. There are still some ways though:

  • Target standard problems, and find them on educational resources. For example, it isn't hard to believe that the same idea has slightly different problems on CSES, CodeChef, UVA, CF Edu, USACO, Chinese judges and some Romanian judges rumored to have every problem in existence.
  • Pick some tutorial for specific topics (from cp-algorithms, USACO guide, CF blogs, Chinese blogs etc) and look for similar problems there.
  • Talk to problem authors and convince them to give you access to a polygon copy of their problem. Then make a new problem with the kind of similarity you want, and add all variants to a gym.
→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

618D - Hamiltonian Spanning Tree and 1521D - Nastia Plays with a Tree.

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

342E - Xenia and Tree and 1790F - Timofey and Black-White Tree are almost the same.(one simple transformation away)

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

Not direct duplication, but sub-problem with minor details different.

1479D - Odd Mineral Resource General case for tree. Ask for any valid answer. Input is not encoded.

1771F - Hossam and Range Minimum Query The tree is line graph. Ask for minimum answer. Input is encoded for online query.

Btw, most solutions on 1479D - Odd Mineral Resource are already online query and finding minimum.

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

1400E - Clear the Multiset == 448C - Painting Fence (only difference: one problem allow $$$a_i = 0$$$ in tests, other — not)

1374E2 - Reading Books (hard version) == 799E - Aquarium decoration (first problem additionally asks for answer restoration, and there is little difference in input formats)

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

1667B - Optimal Partition and 1788E - Sum Over Zero

1462C - Unique Number and 1714C - Minimum Varied Number

923B - Producing Snow and 1795C - Tea Tasting

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

190E - Counter Attack is a bit more difficult than 1243D - 0-1 MST (the idea is pretty much the same).

1672H - Zigu Zagu is a binary ("01" instead of "a-z") version of 1329D - Dreamoon Likes Strings, but with queries and (hence) without answer recovering.

Btw, it's obvious that subproblems can easily be found due to their special numbering, like 1791G1 and 1791G2. Also, I'd like to mention that 1561A - Simply Strange Sort is a subproblem of 1558F - Strange Sort. The last thing is useless, the subproblems (like 1791G1 and 1791G2) have almost the same statement and could be easily detected.

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

    Is it really the thing that the content of a comment depends on the locale you're sending it from? For me, the first version shows problem names in Russian (and it was sent in Russian locale), whereas second version shows problem names in English (and I just clicked edit -> save in English locale to get this).

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

406C - Graph Cutting == 858F - Wizard's Tour

Both of them ask you to divide a graph to a bunch of P3's.

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

13C - Sequence and 713C - Sonya and Problem Wihtout a Legend

The only difference is "strictly increasing" versus "nondecreasing". But you can reduce one to the other very easily by adding or subtracting $$$i$$$ from $$$a_i$$$.

→ Reply