megaspazz's blog

By megaspazz, history, 2 months ago,

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?

• +45

 » 2 months ago, # | ← Rev. 2 →   +27 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. Spoilerconst int N = 1e5 + 5; vector gr[N], vis(N); main(){ for (int t = 1; t <= tc; ++t) { // code // some special case { // didn't reset the global variables continue; } // reset everything. } } Now I reset the global variables at the start of every test case like this. Spoilerconst int N = 1e5 + 5; vector gr[N], vis(N); main(){ for (int t = 1; t <= tc; ++t) { // reset everything. // code // some special case { // now its fine :) continue; } } } 
•  » » 2 months ago, # ^ | ← Rev. 2 →   +17 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 thisvoid solve() { int n; cin >> n; vector a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; if(condition) { //do stuff return; } } } 
•  » » » 2 months ago, # ^ |   +14 I make a solve function and a cleanup function separately. Then in main, call solve and then cleanup.
 » 2 months ago, # |   -32 exceed 32-bit integers#define int long long 
•  » » 2 months ago, # ^ |   -8 Personally I prefer #define int int64_t, though. Just in case.
•  » » 2 months ago, # ^ |   +16 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 and Strange Inequality which may get MLE for using 64-bit integers.
 » 2 months ago, # |   -23 Many times answer won't fit in an integer data type I have faced many issues due to this.Now i always use #define int long long
 » 2 months ago, # |   +15
 » 2 months ago, # |   -22 I once created an account on Codeforces.
 » 2 months ago, # |   -10 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....
 » 2 months ago, # |   +1 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.
 » 2 months ago, # |   +45 A size of a vector is an unsigned integer, therefore, this for loop : for(int i=0; i
 » 2 months ago, # |   +33 The first paragraph is funny because the answer is either $x$ or $x.5$ lol
•  » » 2 months ago, # ^ | ← Rev. 2 →   -36 quite surprisingly though, I found out that python has 10+ digits of precision by default during the round.maybe python really is OP.
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +18 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
•  » » » » 2 months ago, # ^ |   0 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.
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 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)
•  » » » » » » 2 months ago, # ^ |   0 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.
•  » » » » » » » 2 months ago, # ^ |   0 Ok then, thank you. I've learned today two retarded things
 » 2 months ago, # |   +3 As a (mostly) Python user it has to be this https://codeforces.com/blog/entry/101817Thanks to this beethoven97 got the highest number of hacks in a contest https://codeforces.com/blog/entry/104725?f0a28=1
 » 2 months ago, # |   +6 Actually I think of some others getting a TLE because of using unordered_map instead of map when calculating 1< v) runs in $O(N)$ While passing it by reference like this : void f(vector &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$
 » 2 months ago, # |   +77 for (int i = 1; i <= n; ++i) for (int j = 1; i <= n; ++j) ...; 
 » 2 months ago, # |   +13 C++ map's operator [] always creates an element, which might cause TLs: https://codeforces.com/blog/entry/61459?#comment-454131
 » 2 months ago, # |   0 log10()158174611I 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$
 » 2 months ago, # |   +7 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.
 » 2 months ago, # |   +3 This problem
 » 2 months ago, # |   +1 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.
 » 2 months ago, # |   -8 map > unordered_map, else will get hacked. : )
 » 2 months ago, # |   0 Simple but couldn't catch it during the contest: calculating ceil(a/b) by (a+b-1)/b gives wrong result if a or b is negative.
 » 2 months ago, # |   +24 I'm surprised no one said -1%2=-1`
 » 2 months ago, # |   0 I compiled a few of those here