Problem Statement
You have printed N lines of text onto a sheet of paper. Then you took scissors and cut the sheet into individual lines of text.
Now you have N strips of paper. For each i between 1 and N, inclusive, one of the strips of paper contains the following sentence: "Exactly i of the statements above this one are false."
You are now going to do two things.
- First, you will tape all strips of paper back into a complete sheet. When doing so, you can choose any of the N! possible orders for the strips.
- Once you have the complete page, you are then going to decide which statements are true and which ones are false. You must do this in a way that is completely logically consistent.
We are interested in successfully completing the procedure described above and maximizing the number of true statements.
Find that maximum. Also, find all permutations of statements for which the maximum can be achieved (by a suitable choice of truth values).
Return the
- A = the maximum number of true statements.
- B = the number of permutations of statements such that A of them can be true.
- C = the sum of all those permutations, as defined below.
- Both B and C should be computed modulo (10^9 + 7).
When computing C, each permutation is converted to a number as follows: the elements of the permutation are digits in base N+1 with the first of them being the least significant digit.
For example, a sheet that contains the statements in order {1 false above, 4 false above, 2 false above, 3 false above} corresponds to the permutation (1, 4, 2, 3) and that is converted to the number 1 + 5*4 + 5*5*2 + 5*5*5*3.
Definition
- Class:
- FalseAbove
- Method:
- solve
- Parameters:
- int
- Returns:
- int[]
- Method signature:
- int[] solve(int N)
- (be sure your method is public)
Notes
- Note that in B and C each permutation of statements should only be counted once, even if there are multiple different ways to select which A of its N statements are true.
Constraints
- N will be between 1 and 100,000, inclusive.
Examples
2
Returns: {1, 1, 5 }
If we have the statements: Exactly 1 of the statements above this one is false. Exactly 2 of the statements above this one are false. the only consistent way of assigning truth values is that both statements are false. On the other hand, if we have: Exactly 2 of the statements above this one are false. Exactly 1 of the statements above this one is false. then the only consistent possibility is that the top statement is false and the bottom statement is true. Thus: The largest possible number of true statements is A = 1. There is exactly B = 1 permutation for which this can happen. That permutation is the permutation (2, 1). This permutation corresponds to the number 2 + 3*1 = 5, hence C = 5.
3
Returns: {1, 3, 138 }
For N = 3 it is never possible to have more than one true statement. There are some permutations and some truth value assignments such that one of the three statements is true. Thus, A = 1. Out of the six possible permutations of statements, there are B = 3 good ones. (Good permutations are ones for which there is at least one way to have A true statements and N-A false statements.) The three good permutations correspond to numbers 39, 45, and 54. The value C is the sum of these three numbers.
6
Returns: {3, 6, 380214 }
Here's one additional piece of information unrelated to this example test case. For N = 10 we won't tell you the correct values A and B, but we will tell you that the correct C is 680,141,183. You can use this information to make sure that you are computing C modulo 10^9 + 7.
1
Returns: {0, 1, 1 }
4
Returns: {2, 2, 692 }
5
Returns: {2, 14, 72900 }
7
Returns: {3, 78, 103946304 }
8
Returns: {4, 24, 547392864 }
9
Returns: {4, 504, 548847164 }
10
Returns: {5, 120, 680141183 }
123
Returns: {61, 686777702, 262481579 }
345
Returns: {172, 418806503, 931496289 }
794
Returns: {397, 339220689, 641186462 }
1009
Returns: {504, 795180350, 476740282 }
1220
Returns: {610, 227019335, 914876952 }
4567
Returns: {2283, 765402883, 979425425 }
9876
Returns: {4938, 845163491, 980817296 }
19753
Returns: {9876, 979718457, 273861705 }
65456
Returns: {32728, 464241183, 77387542 }
66777
Returns: {33388, 758635489, 670154646 }
98989
Returns: {49494, 425737618, 951881009 }
99014
Returns: {49507, 605315304, 572000198 }
99978
Returns: {49989, 19298341, 878291493 }
99995
Returns: {49997, 95944185, 29880046 }
99999
Returns: {49999, 665470656, 82177719 }
100000
Returns: {50000, 737935835, 844298381 }