TopCoder problem "Piglets" used in SRM 254 (Division I Level Two , Division II Level Three)

Problem Statement


It's feeding time in the pig pen, where a trough is divided into n stalls to accommodate n piglets. The rude piglets immediately rush to the trough and distribute themselves arbitrarily among the stalls. After them come the fastidious piglets one at a time, at one-minute intervals.

A fastidious piglet doesn't want to feed in just any stall, since he doesn't like to be sandwiched between two piglets. As the trough fills up, however, a piglet who hasn't managed to occupy an end stall will eventually have a neighbor on each side. It is the fastidious piglet's goal to delay this sandwiching as long as possible. Among multiple stalls that afford the same delay, he prefers the leftmost. He makes his selection in the knowledge that all subsequent piglets arriving at the trough will choose a stall according to the same criteria.

Given a String describing a trough configuration such that '-' represents an empty stall and 'p' represents an occupied stall, return the zero-based index of the stall chosen by the next piglet. Return -1 if every stall is occupied.



Method signature:int choose(String trough)
(be sure your method is public)


-A fastidious piglet will take a stall at the very end of the trough if possible, preferring the left end to the right end.
-All currently empty stalls will eventually be occupied by fastidious piglets.


-trough contains between 1 and 15 characters, inclusive.
-Each character in trough is either '-' or 'p'.


Returns: 0
An end stall lets the piglet avoid sandwiching altogether.
Returns: 1
The piglet is forced to choose a stall that is already sandwiched. As always in the case of a tie, he prefers the leftmost.
Returns: 1
Whichever stall the next piglet chooses, he will be sandwiched by the piglet who follows one minute later.
Returns: 2
If the piglet takes stall 1, he will be sandwiched in one minute. Stalls 2 and 3 allow him a two-minute delay.
Returns: -1
Returns: 3

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming, Greedy