eidan's blog

By eidan, history, 2 years ago, In English

Last round involved a randomized solution for problem E, and some pretests were aimed against std's rand() function. This caused a big dispute among contestants. It was questioned whether doing this type of tests was fair or necessary, since passing them depended merely on specific language knowledge, not actual problem-solving skills. Contest coordinators counter-argued that participants would've gotten hacked if it hadn't been for these pretests. They also stated that it's one's responsibility to know their favorite language when using it on a round.

The fact is, this controversy was really caused by a technical property within C++ (and codeforces, partly), which many people had no clue existed. This is just an example of the fact that languages and their functioning in CF will sometimes have non-intuitive and unexpected properties, which may screw our performance in a contest. In other words, we are constantly exposed to bumping into another of these hidden behaviors, making the mentioned round hardly the last time something like this can happen.

That's why I thought: We should have a list of the main language-specific issues that could annoy us during contests. Just a brief enumeration of not-so-fun facts about languages, such that, if not known, could break our solutions or get us hacked. Making a brief list available for the community, and exposing it to participants before a round could prevent a lot of trouble. If a problem could make you bump into one of these weird language issues, contest coordinators could safely assume we know about them and not get into a moral debate whether it's fair to include tests against it. Also, contestants would be safe from losing rating to specific language knowledge. In other words, we could prevent issues like the last round's with the least amount of effort.

This blog is an attempt to build up this list once and for all! It should include as much facts as possible, so I'm calling out for your help. If you've had trouble on a problem because of issues in the language, I invite you to help out contributing and write it as a comment. I'll update it in the list as soon as possible. You'd be helping out and preventing other people from going through the same annoying experience! I've included the very few facts I know about for now. It's not much, which is why anything you can share is useful!

Unhackable List

C++

Don't use rand()

Using c++'s rand() is unsafe. Using it gives you a high chance of getting hacked or fayling systests, sometimes even pretests. What to use instead.

unordered_map can cause TLE

C++'s unordered map uses a weak default hash function, which makes your solution hackable. How to resolve it.

std::random_device is unsafe in MinGW w64

Every execution of std::random_device gives the same output when compiling with MinGW w64. Details.

multiset::erase is unusual

Calling multiset::erase(T x) removes all elements in the set with value x. If you want to delete only one of them, do multiset::erase(multiset::find(T x)). Details.

std::pow disregards precision

This can happen for very small operations, even for numbers that fit perfectly in a double's representation. If using integer operations, try binary exponentiation instead. More info.

size() in data structures is unsigned

Normally this doesn't cause trouble, which is why it is more likely to catch you by surprise and screw you during a round. Brief example.

cin/scanf slow when reading doubles

Even with cin.tie(0), ios::sync_with_stdio(false), you can get TLE by reading doubles. Here's an example:

In that case, runtime was more than 10 times slower when reading doubles directly.

Scanf is not as slow as cin, but it's still pretty slow: 105614403.

421ms, versus the 93ms of the solution that read integers and casted them into doubles. So basically, the best choice would be to write a custom input parser for doubles.

This is honestly one of the most disappointing caveats I've seen in C++.

Java

Arrays.sort() may cause TLE

Using Arrays.sort() on primitives has worst case O(n2). How to sort safely.

Python

Python recursion has low limit

The recursion limit has a default value of 1000. Here's how to change it.

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

»
2 years ago, # |
  Vote: I like it +107 Vote: I do not like it

Python

spoiler
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    correct, default recursion depth in python is just 1000. You can increase it by calling sys.setrecursionlimit()

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Test 108 of that Problem E is also an exploit of Codeforces system as well, as every execution of std::random_device gives the same output when compiling with MinGW w64.

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

Computing where n ≥ 0 and x > 0 are both integers as ceil(n*1.0/x) or as ceil(double(n)/x) may lead to precision issues resulting in WA which can be used as a hack case. So, its better to compute it as (n + x - 1) / x.

I use a macro for this as #define iceil(n, x) (((n) + (x) - 1) / (x)).

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

    I don't think precision issues are specific to any languages.

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

      Oops!! Sorry. I thought he was collecting ideas for things which may lead to hacks. Anyways, it must not be included in the blog post but it can still be helpful to beginners. So, I'll leave the comment here as such.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    This works for positives and negatives values:

    #define myceil(i, j) (i/j + ( !(i<0 ^ j<0) && i%j!=0))

    The negated xor expression is meant to skip the next part if the result of division is negative (no fix needed), otherwise it adds one to the result.

    CustomTest gives 1600ms for line with ceil and 46ms for myceil. This is the test code:

    #include <bits/stdc++.h>
    
    using namespace std;
    
    #define myceil(i, j) (i/j + ( !(i < 0 ^ j < 0) && i%j != 0))
    
    int main()
    {
        int k = 0;
        for(int i=-10000; i<=10000; i++)
        {
            for(int j=-1000; j<=1000; j++)
            {
                if(j == 0)
                    continue;
                
    
                //int r1 = ceil(i*1.0/j);
                int r1 = myceil(i, j);
                
                k += (0 < r1 || 0 >= r1); ///Dummy addition
            }
        }
        cout << k << endl;
        return 0;
    }
    
    

    Please note that without the dummy addition it will run in an instant due to compiler optimization. It's kind of messy, I know, but it works.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +16 Vote: I do not like it

      maybe this implementation will be useful too

      // d != 0
      int divFloor(int n, int d) { return d < 0 ? (n - d - 1) / d : (n - d + 1) / d; }
      int  divCeil(int n, int d) { return d < 0 ? (n + d + 1) / d : (n + d - 1) / d; }
      
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Not really leading to hacks, more likely to fail pretests, but I feel I need to include this

In C++ multiset.erase erases all instances of object, not only one

Unfortunately I only realized it during the contest, and have a few friends who also were screwed up because of that

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

    Well that's not entirely true. Say I want to erase an element x from the multiset ms. Writing ms.erase(x) would erase all instances of x but to erase only a single instance we can use ms.erase(ms.find(x)).

»
2 years ago, # |
  Vote: I like it -51 Vote: I do not like it

Using Arrays.sort() on primitives has worst case O(n2).

Links to a 6 year old blog

You're legit retarded.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Please add pow

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Should I say that size() in C++ retutns unsigned integer? There are many blogs complaining about Runtime error because of that.

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

eidan

What can be used instead std::random_device
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just updated the list with your suggestions. Thank you for cooperating! Any other idea, don't hesitate to share it!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    The link in size() being unsigned in c++ is of the blog entry of pow function. Please update.

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

Undefined behaviour in C++

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

In python, there could be precision issues while using the built in log function. If you want to compute the floor of log2(258 - 1), you would get 58.000..01, while you should get 57.9999. When you take floor, you would get 58, instead of 57. This gave me a WA once.

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

    Again, precision error are not language specific. You should be careful with them with every language.

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

    This point doesn't sound bad. Do you have a blog or resource that backs it though? Some analysis on this issue would be a good complement.

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

What was the issue with rand in the "last round"? Can you give a link to a comment that says something about it?

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

Using any language that does not compile to native code may cause TLE :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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