megaspazz's blog

What are your favorite "gotchas" in competitive programming?
By megaspazz, history, 2 years ago, In English

I saw in the comments of Codeforces Round #823 (Div. 2) that many C++ users needed to use setprecision to get AC on problem B. Fortunately, as a Java user, I didn't face the issue this time, but it made me wonder: what are some "gotchas" that people who are newer to competitive programming should look out for?

I also recall that in last year's FB HackerCup, where we need to run code locally, a friend of mine who uses C++ didn't set their local stack size high enough and therefore couldn't successfully run their otherwise-correct code on the full input set.

I know for Java, I painfully learned early on that Java's sort routines on primitive arrays have worst case O(n^2) runtime using a Quickselect variant, and that very smart hackers can construct adversarial inputs that cause a Java solution to get TLE.

So, in your experience, what are some things that have tripped you up?

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

Comments Comments (27)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

I usually define my adjacency list, visited array, and other things globally for graph problems and reset them at the end of every test case. So one day I had hard time debugging code for a graph problem. After debugging for hours mistake turned out to be that I wasn't resetting the global things in some cases where I was using continue.

Spoiler

Now I reset the global variables at the start of every test case like this.

Spoiler
→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    Similar to this, I have debugged several times early return conditions while still needing to read the input. So, for future test cases, the input was just messed up.

    Similar to this
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      I make a solve function and a cleanup function separately. Then in main, call solve and then cleanup.

      → Reply
»
2 years ago, # |
  Vote: I like it -32 Vote: I do not like it
exceed 32-bit integers
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Definitely agree with you here!

    But perhaps as another gotcha, I found that sometimes using 64-bit integer types can cause timeout, especially if your program is on the edge of the runtime limit. Maybe in Java this is worse since execution is typically slower than C++ already.

    Or for example 1677A - Tokitsukaze и странное неравенство which may get MLE for using 64-bit integers.

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

this by rotavirus

→ Reply
»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

The very first contest here at codeforces, I solved one problem, then got hacked for the worst case O(N^2) sorting on primitive type in Java. That's when I learned I better use auto-boxing for sorting in Java....

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

In C++ custom sort function, if I forgot to use references for the 2 input parameters, it can lead to slow execution if the structs are big.

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

A size of a vector is an unsigned integer, therefore, this for loop :

for(int i=0; i<v.size()-1; i++)

produces a runtime error or TLE when v is empty because its condition is i < (0-1) Since it is stored as an unsigned int, the condition becomes i < SOME_LARGE_NUMBERS because in this case -1 cannot be stored in an unsigned number

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

The first paragraph is funny because the answer is either $$$x$$$ or $$$x.5$$$ lol

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

    quite surprisingly though, I found out that python has 10+ digits of precision by default during the round.

    maybe python really is OP.

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

    Not sure what your point is, but you would have to use setprecision in order to solve this problem in C++ with cout. Although there can be at most one decimal place, that is enough to require that the answer is printed as a floating-point type, which defaults to 6 significant figures without setprecision. This leads to wrong answers (on pretest 3) when the answer is very large.

    It's the number of significant figures (not the number of decimal places) that's relevant here, with the .5 case ensuring that you can't simply use an integer type.

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

      First, of course you can use integer type. If the value is odd, output .5 at the end.

      Second, to solve this problem setprecision wasn't required. Probably what was further required was to think outside the conventional "well i'll just binary search cuz this derivative seems pretty monotonic to me". If you buried yourself down the setprecision hole, you were very likely going to get stuck there, and by extention WA/FST'd

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

        If a programmer were to use an integer type and output ".5" for the case where the answer requires it, that would the suggest that the programmer is deliberately avoiding the use of floating point types. The whole point of that paragraph was about those who didn't know of any precision issues with printing floating-point types, so it wouldn't make sense for them to go out of their way to restrict their code to handling integer types only.

        Regardless of which approach you use, whether it was a binary search or a simple average of the maximum and minimum effective positions or some other approach, there will be cases where the answer is not an integer, and such answers would need to be printed. Programmers who don't know about precision concerns in floating-point types would naturally print the answer as a floating-point type, which is what leads to the WA, regardless of their actual approach in solving the problem. The use of setprecision, or an integer type with a ".5" string printed separately if needed, would imply foreknowledge of issues with floating-point types, which is exactly what this thread is highlighting.

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

          Regardless of which approach you use, whether it was a binary search or a simple average of the maximum and minimum effective positions or some other approach, there will be cases where the answer is not an integer, and such answers would need to be printed

          I never claimed the uselessnes/obsolence of using setprecision, I merely parodied its use in this example-- I repeat: let's say someone would've been clever and found the (min+max)/2 solution. Even if they were to use floating point to calculate this value, they were to bump in no issues. If you were to write a "brute" solution by binarysearching the answer, you could've failed. Yet, the extensive binarysearch was unnecesarry, the minute the binary search started to add values to the answer <0.1, it was pointless: just round the value. (Edit: I don't claim any contestant should've done this or be aware of this-- I just point out that setprecision's use could've only lead you to a bad ending, whereas anything else woudl've circumvented this issue)

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

            I repeat: let's say someone would've been clever and found the (min+max)/2 solution. Even if they were to use floating point to calculate this value, they were to bump in no issues.

            If they were unaware of setprecision, they would never be able to solve this using floating-point types. For example, compare 173925122 and 173500218

            I just point out that setprecision's use could've only lead you to a bad ending, whereas anything else woudl've circumvented this issue

            setprecision's use is necessary simply because there are cases where the answer has 7 significant figures and is not an integer. No matter what approach you use to calculate such answers, it cannot be printed using a floating-point cout without setprecision.

            The only way to circumvent the precision issue would be to avoid the use of floating-point types (like the integer followed by ".5" string) or a different way to print the answer (other than cout), but one who is accustomed to using cout (or even printf without specifying precision) and lacks the foreknowledge of the limited default precision in printing floating-point types should not be expected to try these alternative approaches.

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

              Ok then, thank you. I've learned today two retarded things

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

As a (mostly) Python user it has to be this https://mirror.codeforces.com/blog/entry/101817
Thanks to this beethoven97 got the highest number of hacks in a contest https://mirror.codeforces.com/blog/entry/104725?f0a28=1

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

Actually I think of some others

  • getting a TLE because of using unordered_map instead of map

  • when calculating 1<<x and the result exceeds the limit of integer. Should be using 1ll << x instead

  • passing a vector to a function as a value like this : void f(vector<int> v) runs in $$$O(N)$$$ While passing it by reference like this : void f(vector<int> &v) runs in $$$O(1)$$$ This becomes a troublesome if we run the function that passes the vector as value inside a query

  • sorting compare function should returns false if elements are equal

  • resetting an array using a memset in a multiple test cases scenario might leads to TLE if the array is declared globally with a static size of maximum possible $$$N$$$

→ Reply
»
2 years ago, # |
  Vote: I like it +77 Vote: I do not like it 
for (int i = 1; i <= n; ++i)
    for (int j = 1; i <= n; ++j)
        ...;
→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

C++ map's operator [] always creates an element, which might cause TLs: https://mirror.codeforces.com/blog/entry/61459?#comment-454131

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

log10()

158174611

I could have been CM by now if I made a normal count_digits function but instead, I used log10(X) which fails if X is equal to $$$10^{18}-1$$$

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

Last year, on Facebook Hacker Cup Round 2, I didn't think to create a new file for input. So, when I go the massive input, I tried to COPY PASTE into my tiny CLion input console. Unsurprisingly, it didn't work, given that the test data had around 7 million characters.

This year, I got my revenge (somewhat) by winning a t-shirt in round 2.

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

This problem

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

As a C# programmer, there's something to know about floating point numbers: the representation depends on the locale of the machine executing the code. For example the number 1.5 (US writing) would be 1,5 in most other parts of the world. When I was competing on yandex algorithms, there was a task that required to read in a double value (done with double.Parse(Console.ReadLine())). Due to yandex not using the US locale on their servers, I get a RTE verdict. Took me a while to figure out what went wrong. I never ran into this issue on any other website.

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

I'm surprised no one said -1%2=-1

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

I compiled a few of those here

→ Reply