McDic's blog

Why this kind of problems are prohibited(or bad) in Competitive Programming?
By McDic, 6 years ago, In English

Recently I made a problem that requires calculating 20~30 digits of precision. (Calculating high precision is not a main idea, it's just required to solve this problem easily. This approach can be avoided and solvable by only big integers, but it needs very unusual mathematical observation.)

One of my friends said this problem should not be opened for Competitive Programming participants. He said this problem is bad because this requires hard work to self-implement high precision data structures or use built-in structures are not in C++ like Python's decimal.Decimal or Java's java.math.BigDecimal.

Why this feature makes this problem bad as competitive programming problem? I can see many problems in Codeforces force users to use either fast languages like C++ or very weird usage of system calls like I/O operations. Also, some data structures like Red-Black tree are not built in some languages like Python 3. Why not for this case?

Can anyone explain? Thanks in advance.

I removed that problem from my current proposal list. If I succeed to deal with constraints to make avoid BigDecimal/BigInteger easily, I will add it. Other problems are not forcing you to use such data structures. Thank you for all feedbacks.

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

»
6 years ago, # |
← Rev. 2   Vote: I like it -17 Vote: I do not like it

I read the title of the blog wrongly. I thought it was "What kind of problems are prohibited in CP?"

Sorry for the unrelated answer.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it -10 Vote: I do not like it

    I implemented python solution for this problem using Python 3 and built-in modules. This problem is not research problem.

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

They aren't prohibited, just not liked since most problems requiring huge numbers of precision can be easily solved if using python or java, and if the idea is cool then most likely the same properties exist for numbers of size 10^18 or numbers modulo some 10 digit prime. Also codejam had one problem which required bigInt in qualification round, so its not as if they don't exist, they are just not common because of what I mention.

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

    Thanks for detailed explanation. I can see there is a way exist to convert my problem into modulo problem without losing properties, but it's hard to deal with size of constraints.. I think I should look into it.

    By the way, why they don't like if problem can be easily solved if using Python or Java? There are also some problems force user to use C++ to solve easily.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    I wouldn't say that the problem in Code Jam was bad. First of all, the subtask that required bigInt was only worth 1 point, and as it stated in the statement, it was only for fun and bragging rights. Also, it didn't really require a bigInt implementation, since no complex operations (e.g. mod) needed to be done. A simple implementation using string was enough. Because of the nature of the problem, even without using bigInt, you (or at least I) still had to iterate digit-wise the number, so implementing it using a string could even be easier than dividing by 10 every time.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      Test set 2 of Cryptopangrams (also from the qualification round) required for compute the GCD of numbers as big as $$$10^{200}$$$. And that was worth 15 points.

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

        Sorry, I was talking about the first problem

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          the first problem didnt involve any big integer it was just a string task...

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

Would you like such problem in a round, when you participate?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +86 Vote: I do not like it

    I don't like geometry problem in rounds, it also should be prohibited?

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

    Unless the problem requires some random dirty codes, I think I should get used to it. Isn't that good attitude for problem solving?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      well, if you write problem with 25-digit precision in C++, it will probably require some dirty codes.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it -15 Vote: I do not like it

        Then you can avoid C++ or get external reference for decimal code in case.

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

          Yeah, just because coding it up in c++ is difficult, it doesn't mean that those type of problems should not appear in contests.

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

80-90% people in CP use C++. So recommended way of setting problems are bias towards C++ users. Some problems aren't solvable in some languages, so in some platform they explicitly say that "It is not guaranteed that all problems can be solved in all languages".

Btw in Python there is Set and dictionary, so I don't understand the point about "Red-black tree" not built in in Python 3? (I'm really just asking, I'm not very used to Python).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    Understand, thank you. But it's surprising that C++ is still major language in competitive programming since Python and Java are dominating popularity for many years.

    Python's set and dict are hash table, so it has different properties than red black tree.

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

      Competitive programming focuses heavily on speed. Java is a few times slower than C++, so some people do use it for competitive programming (though they're still at a disadvantage), but Python can be up to 50-100 times slower than C++ in certain cases.

      Do you have any source for "Python and Java are dominating for many years", since I don't agree with that statement. All C++, Java and Python are popular languages and they all have different tradeoffs. For example, Python is dominating in Data Science, but for competitive programming Python is a very bad choice just because of the nature of the field.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

        I always learned it's better to optimize approaches in fundamental level, not just some unnecessarily considered overheads.

        Sure, C++ dominates the field of competitive programming. But in many fields C++ and C are not "1st-placed in usage" languages and I thought this is one of the big factors of usage in competitive programming.

        By the way, I referenced PYPL and other many blogs, but I can see C/C++ are higher than Python in some of popular indices like TIOBE.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Set in python is a hashtable not a bst.

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

I think this kind of problem is not bad, for a fair view. But the actual world is not so fair.

Suppose that someone publishes problem which requires large integers which does not fit into $$$64$$$ or $$$128$$$-bit integers, and criticized. They criticize like "it requires program language skill, which is not fair". But I think that, we can even use the criticism idea to the problem which requires to use $$$O(n \log n)$$$ Dijkstra Algorithm. That's because the programming language C# doesn't support Priority Queue. But of course, we are reluctant to bring such criticism to Dijkstra Algorithm problem.

That's why I am having opinion that using things like bigint in programming contests are fair and should not be criticized. Actually, I actually did this discussion when SRM 737 Div1 Medium, but I realized that my opinion is obviously in minority.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    Thanks for providing good insight. I personally agree on your opinion.

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

Let's say that I have a problem which is one liner in PHP and any other language require at least 1000 lines of bugs. Does that justify using this problem in a contest?

And your next point, using C++ as a fast language is the same as using Python for a language that has builtin BigInt. Speed and optimization is a very important key in Competitive programming so some problem makes it hard for slow languages to pass in the time limit, "They have no choice".

But "most" of problems that require BigInt just does that for the sake of it. They could have set the constraints lower or choosing to print the answer mod number.

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

    1. I think you scaled a lot. It's better to compare to between implementing Red-Black tree from nothing yourself or using std::set.

    2. Understand, thank you. But please look at this comment

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

      Implementing a balanced binary tree (treap, AVL, splay, implicit segment tree or whatever you want to use) is, in my opinion, way easier than implementing your own BigDecimal (and, I think, is even easier than custom BigInteger).

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

        It might be depend on how you focus on optimizations on multiplication/modulo operations. Sometimes it needs to be fully optimized, but sometimes it is not necessary.

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

OK, so suppose you will use such a task in some contest I'll participate. Then I'll do one of the following:

  1. Use python

  2. Search on github a big integer/decimal template and just use it.

Is this what you want? What's the point?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    That's just additional step for convenience, many people use their pre-coded codes or templates for complex data structures.

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

It is much more fun to solve problem that require critical thinking, solving problem that require knowledge of builtin function or some different language is neither interesting nor fair for everyone. so if you can avoid use of bigdecimal without changing problem idea, then you should do it.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It may be vary to say which knowledge should be basic or not, even for usage of some language's features and basic data structures.

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

Does it add anything to the problem? There's a difference between "We need this because it's cool and necessary to solve the problem" vs "We used big integers/decimals just to say we used them".

You say it's not a main idea. Then it shouldn't be part of the problem in my view.

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

(merged this comment in main post)

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

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

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

Competitive programming is supposed to be mostly about algorithms. How much of your problem is algorithmic and how much can be "solved" by having a bigint library available? It's not that problems using bigints are not allowed, they just tend to suck. See: 986D - Perfect Encoding.

I have no idea if your problem is like that. If the bigints are necessary to allow a really novel solution, there should be no problem using it in a contest, but from past experience, I don't expect it to be like that.

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

    Yeah, I am handling constraints now :)

    → Reply