BoredPhilosophers
SRM 451 · 2009-10-20 · by vexorian
SRM 451 · 2009-10-20 · by vexorian · Simple Search, Iteration, Simulation, String Parsing
Problem Statement
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 aString[] 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.
You are given the text as a
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)
{"p y b w e p i o f f f o a i c v k c l c e w x b i ", "z b t q k w m v e s c c i j p r q z o i c k v q c ", "l l m k w f p k r i r l g r i i k f d w d v w v p ", "w p g e f d u n n g l i h q t r n p s z q a l u u ", "o k u z f d d w w v v n x e u f i i q j z x e k i ", "m q h p c e b m x j a x q e n i f z n d b b d j v ", "k l d b z e s l u b c y x o a z b e q h i u z m q ", "m r u p v k k o k j y f p e r j g q h u u s b p y ", "g w y z q i u g b l l c v c j w r i h j h g u m m ", "l v d b t v u k q p f m h v n v i n j d s t s s e ", "u g i n t r h j w n y o i g p n x j v j z t j e c ", "e x t s e x r w g g f v z x v d q f c u u m h x x ", "t s f p c f k y o q l i p x d f g w q l z s t s m ", "p h j c y a b z s w d k m r j h d e n e u s t i o ", "c h p b y v i m g r n f k d w x q g c l b l z x a ", "q s r e z d s k c m u j c t q x e l i j g v z m w ", "w x p b j p v k n u w l w o q j g h e m o q p i b ", "l o g v g x q g i r p q g b n h f q j t n u g g j ", "n c b i j t z r l k f x a y w z h t c c v x g s y ", "h r h l a v f l k r p x d v o w b q u i j a s s p ", "z h h l p h i z g v n a i t t q t i s v k q a p x ", "n h m h u y z m c e x m l y s j i n n h u q s i z ", "o q j n s n j z d p p t d b g e w w o b s q w t o ", "n g w a n k o c v z g u j k b c u o a i x v y b g ", "x h t y r x f n f b r b d v j u a w g v v b a g j ", "s c r f i i i x f k m a y t g j o s h d h c m u p ", "g a y x u j n j z l v x k x j v c j x k l s s g x ", "e x t i b f z d o c t c m v z v p g s e f i h j m ", "n o r a a h v q c u o o y y r h v f g e w i g v i ", "n s l k x p r u p o v n m s e u q b h u a y w c f ", "a f r m r e q u a m o b b z z q l b y j q v c a o ", "r j c x n w r u h g d x d y m j e q z n d m j u y ", "r f n i l f o n w q n h l m m w o f n z q u x e s ", "a q h p j w w c s s e b j g j t l n s o i z e a v ", "m v n y j n u w q x x f w x e m p z b z f l t d u ", "c s t d a u o l a t a l i v d a o i h q o g g b l ", "a z q f x d q i g y q u b k v n r p o e w t x o r ", "x c s l g e u f w d a n h i s p j d b g m l g a e ", "x s m x f w e j e f d u m e q v q a t j i y v g s ", "h a f i e v b y a y o l u c g y i k j u h l p l y ", "s v n x f c y g i v w a a n z y v g i o i t y h t ", "a y u s j h g s u x t a o z a u m e f p b i y m o ", "l a c s z p l f o x d x m r b m m b d e b j g b v ", "q z x i s w g z d d r l e s a t u e b s p i q f x ", "r g l k l z e u v t w s g s q m j v p b p g c z s ", "l m s h m t v e d s r l c y h u t v k g u y m x s ", "e n w c m a b f c v e h i g n m d q f b v h p i o ", "z n i g d s z y e t y u e f n c l u v k j s b i n ", "v u b z x n l x t k u z v h p r n x u j h h j x p ", "y w x h k y m i y g d b t m a i x q p e c h o i b"}
50
Returns: {26, 552, 1196, 1245, 1246, 1245, 1244, 1243, 1242, 1241, 1240, 1239, 1238, 1237, 1236, 1235, 1234, 1233, 1232, 1231, 1230, 1229, 1228, 1227, 1226, 1225, 1224, 1223, 1222, 1221, 1220, 1219, 1218, 1217, 1216, 1215, 1214, 1213, 1212, 1211, 1210, 1209, 1208, 1207, 1206, 1205, 1204, 1203, 1202, 1201 }
Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BoredPhilosophers with a public method vector<int> simulate(vector<string> text, int N) · 76 test cases · 2 s / 256 MB per case