Statistics

Problem Statement for "SequentialThreads"

Problem Statement

You have written a complicated multi-threaded program, and you would like to analyze its expected runtime.

The program consists of n threads in a specific order, indexed from 0 to n-1. Each thread has a task to execute which is divided into up to 10 subtasks. Each subtask requires one time slice to process, and they must be processed in order. In every thread (except the first), one of the subtasks will be a special "synchronization" subtask; the thread may not process this subtask until all the threads with lower indices have finished. The thread's task is described as a String with a character for each subtask. A normal subtask is denoted by a '.'; the "synchronization" subtask is denoted by 'S'.

The processor executes your program in a simple way. For each time slice it picks a thread uniformly at random and allows it to process one subtask. If the chosen thread has already finished, the unfinished thread with the lowest index is picked instead. However, if the chosen thread is blocked on a "synchronization" subtask, that time slice is wasted. (Yes, this is a silly way to implement multithreading!)

Return the expected (average) number of time slices the entire program will take to execute.

Definition

Class:
SequentialT
Method:
expectedExecutionTime
Parameters:
String[]
Returns:
double
Method signature:
double expectedExecutionTime(String[] threads)
(be sure your method is public)

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

  • threads will contain between 1 and 10 elements, inclusive.
  • Each element of threads will contain between 1 and 10 characters, inclusive.
  • Each element of threads will contain only the characters '.' and 'S'.
  • Each element of threads, except the first, will have exactly one 'S'.
  • The first element of threads will not contain an uppercase 'S'.

Examples

  1. {"....."}

    Returns: 5.0

    No multithreading; just 5 subtasks to perform.

  2. {".","S"}

    Returns: 2.9999999999999996

    There's a 1/2 chance of 0 wasted time slices, a 1/4 chance of 1, a 1/8 of 2, and so on. An average of 1 time slice is wasted.

  3. {"..","S"}

    Returns: 4.999999999999999

    Now there is a (k+1)/2k+2 chance of wasting k time slices.

  4. {".","...S.",".........S"}

    Returns: 16.144458312987712

    These threads will most likely not have to wait.

  5. {".....","...S...","S......","......S..","...S.","..S"}

    Returns: 65.45700302526924

  6. {"..........","S.........","S.........","S.........","S.........","S.........","S.........","S.........","S.........","S........."}

    Returns: 292.89682539683

    Worst possible runtime.

  7. {"."}

    Returns: 1.0

    Smallest case.

  8. {"..........",".........S",".........S",".........S",".........S",".........S",".........S",".........S",".........S",".........S"}

    Returns: 133.05256086801842

  9. {"....","S...",".S.","..S..","....S..","S","S..","S..."}

    Returns: 73.32678982578021

    20 randomly generated cases.

  10. {"...","...S.....","....S.","....S...","...S.",".......S..",".S","S.","....S..","....S.."}

    Returns: 103.34351169329761

  11. {"........","..S......","S...","S.","........S",".....S.","......S",".S...","..S....",".S"}

    Returns: 152.28475605282964

  12. {"......","..S....","..S",".S.",".........S",".....S","S..",".S.....","....S.",".S."}

    Returns: 116.47800512027504

  13. {".......",".....S.",".....S....",".S.","..S....","S........","..S","S.."}

    Returns: 108.57103087114828

  14. {"....","..S...","S......","....S.","S...","....S....","S..","....S","....S."}

    Returns: 102.65780863179606

  15. {".......","......S","S...",".S...","...S.....",".........S","...S",".S....","...S....","S..."}

    Returns: 135.1649970493142

  16. {"....","......S..","....S...",".......S",".S....",".....S.","...S......",".....S"}

    Returns: 88.77054254680263

  17. {"........","...S..","........S","S........","...S.",".S........","........S","...S......","..S.."}

    Returns: 141.35282348352507

  18. {"..........",".....S.","..S....","...S....","S....","..S.......","....S.","S....."}

    Returns: 138.94915143199472

  19. {"..........","..S.....","...S..",".....S","...S....","..S...","S......","....S.....","......S...",".......S"}

    Returns: 182.22263566849114

  20. {"..........",".......S..","S.......","....S.....","..S.......","....S...","...S...",".....S","S......"}

    Returns: 177.1081247377745

  21. {".......","...S.....","S......","......S.","...S.....","...S.....","......S..","........S"}

    Returns: 125.48015448863978

  22. {"........",".......S","....S.....",".S......","...S...","..S.....","..S....",".......S","...S......"}

    Returns: 146.1182967199331

  23. {"........",".....S....","....S.....","...S......",".S.......",".....S...","..S.....",".S.......","......S.."}

    Returns: 170.22176593143186

  24. {"..........","....S...",".....S..",".........S",".....S....","...S.....","..S.......",".S......"}

    Returns: 139.47453059984795

  25. {"..........","........S.","......S...",".........S","S........",".......S.",".....S....","........S","........S",".S........"}

    Returns: 171.64076860872518

  26. {"..........","......S..","......S..","....S....",".......S.",".S.......","........S",".......S.."}

    Returns: 129.86758313971862

  27. {"..........","....S.....","........S.","...S......","..S.......","S.........","....S.....",".......S..",".....S....","S........."}

    Returns: 215.96519763811781

  28. {"..........",".S........","...S......","......S...","........S.","......S...",".S........","........S.","S.........","........S."}

    Returns: 217.5790399904262

  29. {".","S........."}

    Returns: 12.0

  30. {"....","S........."}

    Returns: 18.000000000000007

  31. {"..........","S........."}

    Returns: 30.0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: