KarlisS's blog

By KarlisS, history, 3 years ago, In English

For any of the topics here search codeforces and you will find them discussed multiple times. Upvote from me if anyone counts how many times per month each of these get asked.

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. If you are not capable of compiling your own code it is also possible to use the diagnostic mode at Codeforces http://codeforces.com/blog/entry/55902 but it is strongly recommended to learn doing it yourself.

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

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

Read more »

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