TopCoder problem "BoredPhilosophers" used in SRM 451 (Division II Level Two)



Problem Statement

    The bored philosophers problem is a simple one. There are N philosophers in a classroom, and they are bored - so bored that they end up playing a game in which they use a random text excerpt from a book to challenge themselves. The first philosopher begins the game by saying the number of different words present in the excerpt. The second philosopher then tries to outdo the first by saying the number of different sequences of two consecutive words in the text. The game continues as each philosopher i says the number of different sequences of i consecutive words. (All indices in this problem are 1-indexed.) The game ends after all N philosophers have spoken.



You are given the text as a String[] text. Concatenate the elements of text to get the complete text. Words in the text are separated by single spaces. Return a int[] containing exactly N elements, where the i-th element is the number said by the i-th philosopher.
 

Definition

    
Class:BoredPhilosophers
Method:simulate
Parameters:String[], int
Returns:int[]
Method signature:int[] simulate(String[] text, int N)
(be sure your method is public)
    
 

Notes

-Suppose the text excerpt consists of words W[1], W[2], ..., W[K] (in this exact order). Then the i-th philosopher counts the number of different word sequences among (W[1], W[2], ..., W[i]), (W[2], W[3], ..., W[i+1]), ..., (W[K-i+1], W[K-i+2], ..., W[K]).
-Two word sequences of the same length (A[1], A[2], ..., A[L]) and (B[1], B[2], ..., B[L]) are different if A[i] and B[i] are different strings for at least one i between 1 and L, inclusive.
 

Constraints

-text will contain between 1 and 50 elements, inclusive.
-Each element of text will contain between 1 and 50 characters, inclusive.
-text will contain only lowercase letters ('a'-'z') and spaces (' ').
-The concatenation of the elements of text will contain no leading, trailing, or consecutive spaces.
-N will be between 1 and 50, inclusive.
-N will not be greater than the number of words in text.
 

Examples

0)
    
{"hello world"}
2
Returns: {2, 1 }
There are exactly two different words and a single sequence of two words.
1)
    
{"aaa bbb aaa bbb aaa aaa"}
4
Returns: {2, 3, 3, 3 }
The first philosopher will notice 2 different words: "aaa" and "bbb".

The second philosopher will notice 3 different sequences of 2 words: "aaa bbb", "bbb aaa" and "aaa aaa".

The third philosopher will notice 3 different sequences of 3 words: "aaa bbb aaa", "bbb aaa bbb" and "bbb aaa aaa".

The fourth philosopher will notice 3 different sequences of 4 words: "aaa bbb aaa bbb", "bbb aaa bbb aaa" and "aaa bbb aaa aaa".

2)
    
{"remember"," t","o concatenate ","the"," ","text"}
1
Returns: {5 }
3)
    
{"a a a a a a a b a a b a a a b b a b a a a b a b"}
6
Returns: {2, 4, 7, 11, 14, 17 }
4)
    
{"aa ababaa c cbbcbc cabcbcb ba bccc ababb",
 "c cabcba caa ababaa c cbbcbc cabcbcb ba ",
 "bccc ababbc cabcba c bbcbab",
 "b aaaa cbccaaa bccc ababbc cabcba c bbcb",
 "ab cbcaca"}
7
Returns: {15, 17, 18, 19, 20, 20, 20 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10456

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13905&pm=10456

Writer:

vexorian

Testers:

PabloGilberto , bmerry , connect4 , ivan_metelsky

Problem categories:

Simple Search, Iteration, Simulation, String Parsing