Is long long in C++ known to be very nasty in terms of precision?

Question

The Given Problem:

Given a theater with n rows, m seats, and a list of seats that are reserved. Given these values, determine how many ways two friends can sit together in the same row.

So, if the theater was a size of 2x3 and the very first seat in the first row was reserved, there would be 3 different seatings that these two guys can take.

The Problem That I'm Dealing With

The function itself is supposed to return the number of seatings that there are based on these constraints. The return value is a long long.

I've gone through my code many many times...and I'm pretty sure that it's right. All I'm doing is incrementing this one value. However, ALL of the values that my function return differ from the actual solution by 1 or 2.

Any ideas? And if you think that it's just something wrong with my code, please tell me. I don't mind being called an idiot just as long as I learn something.

Answer 1

First, C++ doesn't have a long long type. Second, in C99, long long can represent any integral value from LLONG_MIN (<= -2^63) to LLONG_MAX (>= 2^63 - 1) exactly. The problem lies elsewhere.

Answer 2

Unless you're overflowing or underflowing, it definitely sounds like something is wrong with your code. For integral types, there are no precision ambiguities in c or c++

Answer 3

Given the description of the problem, I think it is unambiguous.

Normally, the issue is that you don't know if the order in which the combinations are taken is important or not, but the example clearly disambiguate: if the order was important we would have 6 solutions, not 3.

What is the value that your code gives for this toy example ?

Anyway I can add a few examples with my own values if you wish, so that you can compare against them, I can't do much more for you unless you post your code. Obviously, the rows are independent so I'm only going to show the result row by row.

X occupied seat
. free seat

1: X..X
1: .X..
2: X...X
3: X...X..
5: ..X.....

From a computation point of view, I should note it's (at least) an O(N) process where N is the number of seats: you have to inspect nearly each seat once, except the first (and last) ones in case the second (and next to last) are occupied; and that's effectively possible to solve this linearly.

From a technic point of view:

• make sure you initialize your variable to 0
• make sure you don't count too many seats on toy example

I'd be happy to help more but I would not like to give you the full solution before you have a chance to think it over and review your algorithm calmly.