Codeforces C++ FAQ

Revision en3, by KarlisS, 2017-09-19 01:50:57

0. Help!!!

A: Read this blog.

1. TLE

1.1 The code is using STL map/set and std::lower_bound

A: std::lower_bound is O(logn) only when used with random access iterators it is O(n) when used on map/set. Use the map/set member functions lower_bound/upper_bound to get O(logn) operations. See http://en.cppreference.com/w/cpp/container/set/lower_bound http://en.cppreference.com/w/cpp/algorithm/lower_bound .

1.2 Why did I get AC after changing comment?

A: Is the solution that got AC on the edge of time limit? That is probably within measurement mistake. Time limits are usually set with some reserve, something can probably be improved to get a stable AC.

2. I am getting WA/RTE in Codeforces but it works on my computer/other online service. Codeforces bug. G++ bug. C++XX bug.

A: Your code relies on undefined behavior or behavior, uses floating numbers incorrectly or is otherwise incorrect. Read here what is undefined behavior http://en.cppreference.com/book/undefined_behavior . Continue reading bellow for most common causes.

3. The code use std::sort/std::set/std::map with custom comparator.

The comparator must return false for cmp(x,x). The comparator must be transitive. If cmp(a,b) == true, then cmp(b,a) must be false. Read here for more details http://en.cppreference.com/w/cpp/concept/Compare

4. How to write a correct comparator?

A: See 3.

5. Why is my code working with std::stable_sort but not with std::sort.

A: Most likely your camparator doesn't match requirements in 3. You were lucky that implementation details for std::stable_sort on the input in tests happened to work. It might not work with different tests/version of compiler/implementation of standard library.

6. The code contains std::pow(10, x).

A: Don't use std::pow on integers, it is designed for floating point numbers. Write your own function for getting power of integers. See 9. floating point numbers.

7. The code contains i<vec.size()-1 as loop condition.

A: v.size() returns size_t which is an unsigned integer. When the size is 0 it will wrap around to max value for that integer type. If the size can be 0 cast size to signed integer type or write your loop differently.

8. The code contains std::ios_base::sync_with_stdio(false).

  • Read the documentation of what it does (makes input fast is wrong answer).
  • Don't mix cin/scanf and cout/printf when using ios::base_sync_with_stdio(false)

9. Floating point numbers

  • Read this https://gcc.gnu.org/bugs/#nonbugs_general
  • Do not compare floating point numbers without epsilon (with some rare exceptions)
  • Do not assign floating point number to integer without proper rounding
  • Do not use standard library functions that are designed for floating point numbers on integers unless you know what you are doing. The result might need rounding even if it mathematically should be a precise integer. Floating point numbers have less significant digits than same size integer.

10. None of the above helped.

A: Maybe you are accessing outside the size of array or have other bug. Use tools http://codeforces.com/blog/entry/15547 .

11. The result still differs on Codeforces and my computer.

A: You can use custom invocation to narrow down the cause of difference.

Tags faq, c++, #help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English KarlisS 2018-01-14 22:42:09 255 Mention Codeforces diagnostic mode.
en4 English KarlisS 2017-09-19 01:56:37 179 (published)
en3 English KarlisS 2017-09-19 01:50:57 217 Tiny change: 'otherwise wrong. Read her' -> 'otherwise incorrect. Read her'
en2 English KarlisS 2017-09-19 01:38:06 668 Improve formatting
en1 English KarlisS 2017-09-19 01:20:12 3360 Initial revision (saved to drafts)