Newspaper Delivery Game
IMC Trading● HardFULLTIMEONSITE INTERVIEWProblem statement
Alice and Bob take turns delivering newspapers to a row of n houses. A house either has a newspaper or does not.
On a turn, choose a house that does not have a newspaper and give it one. If there is a house immediately to its right, toggle that house: give it a newspaper if it has none, or take its newspaper away if it already has one. A house that already has a newspaper cannot be chosen.
The player who just moved wins when exactly one house lacks a newspaper.
For this exercise, assume the houses form an open row, all houses initially lack newspapers, and choosing the final house changes only that house. The game stops immediately when exactly one house lacks a newspaper. A fully covered row is a nonwinning dead end.
For this exercise, consider all legal plays rather than assuming either player uses an optimal strategy. Return four integers in this order:
- The number of distinct newspaper configurations reachable after exactly one turn.
- The number of distinct configurations reachable after exactly two turns. A play that won after its first turn contributes no second-turn configuration.
- The minimum number of turns among plays that reach the winning condition.
- The maximum number of turns among plays that reach the winning condition.
Different move sequences that end in the same configuration count only once for the first two values. For this exercise, return -1 for both turn bounds if no winning play exists.
Complete newspaperGame(n) and return the four values as an integer array.
Function
newspaperGame(n: int) → int[]Examples
Example 1
n = 7return = [7,21,3,26]This uses the seven-house count from the report with the stated practice conventions. There are 7 distinct first-turn configurations and 21 second-turn configurations. A shortest winning play selects houses 1, 3 and 5, producing 1100000, 1111000 and 1111110, so it takes 3 turns. Exact state enumeration gives a longest winning play of 26 turns. These numerical answers are independently derived, not printed source answers.
Example 2
n = 2return = [2,0,1,1]Choosing house 1 produces 11, a nonwinning dead end. Choosing house 2 produces 01 and wins immediately. Both distinct configurations count after one turn; neither can produce a second turn. Every winning play lasts 1 turn.
Example 3
n = 3return = [3,2,1,4]The first-turn configurations are 110, 011 and 001. The first two already win. Only 001 continues, reaching 111 or 010 on turn 2. A longest winning play is 000 to 001 to 010 to 100 to 101, taking 4 turns.
Example 4
n = 4return = [4,6,2,8]There are 4 distinct configurations after one turn and 6 after two turns. Winning plays can finish in as few as 2 turns or as many as 8 turns. These counts use distinct states and stop at the first state with exactly one uncovered house.
Constraints
- For this exercise, assume
2 <= n <= 18. - For this exercise, assume an initially empty open row and immediate stopping at exactly one uncovered house.
- All four returned values fit in a signed 32-bit integer.