Statistics

Problem Statement for "MultiRead"

Problem Statement

In many computer systems, multiple processes can read from the same resource during the same clock cycle, but only a single process can write to the resource during a clock cycle. Reads and writes cannot be mixed during the same clock cycle. Given a history of the reads and writes that occurred during a particular computation as a String trace, and an int procs representing the number of processes used by the computation, calculate the minimum duration of the computation in clock cycles. The trace represents each read as an 'R' and each write as a 'W'.

For example, if trace is "RWWRRR" and procs is 3, then the minimum number of clock cycles is 4: one for the first read, one each for the two writes, and one for the last group of reads.

Definition

Class:
MultiRead
Method:
minCycles
Parameters:
String, int
Returns:
int
Method signature:
int minCycles(String trace, int procs)
(be sure your method is public)

Constraints

  • trace will contain between 1 and 50 characters, inclusive.
  • Each character in trace will be 'R' or 'W'.
  • procs will be between 1 and 10, inclusive.

Examples

  1. "RWWRRR"

    3

    Returns: 4

    The example above.

  2. "RWWRRRR"

    3

    Returns: 5

    Now the final group of 'R's takes two cycles.

  3. "WWWWW"

    5

    Returns: 5

  4. "RRRRRRRRRR"

    4

    Returns: 3

  5. "RWRRWWRWRWRRRWWRRRRWRRWRRWRRRRRRRRRWRWRWRRRRWRRRRR"

    4

    Returns: 30

  6. "RRRWRWRWRRRRRWWW"

    1

    Returns: 16

  7. "RRRWRWRWRRRRRWWW"

    2

    Returns: 13

  8. "RRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRWRRWRWRRRWRW"

    2

    Returns: 30

  9. "RRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRWRRWRWRRRWRW" "RRRRWRRRRRRRWRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRWR"

    3

    Returns: 23

  10. "RRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRWRRWRWRRRWRW" "RRRRWRRRRRRRWRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRWR" "RRRRRRRRRRRRRWRRRWRRRRRRWRRRWRWRRRRRRRRRRRWRRRRRRR"

    4

    Returns: 20

  11. "RRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRWRRWRWRRRWRW" "RRRRWRRRRRRRWRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRWR" "RRRRRRRRRRRRRWRRRWRRRRRRWRRRWRWRRRRRRRRRRRWRRRRRRR" "RWRWRRRRRRRRRRRWRRWRRRWRRWWRRRRWRRRRRRRRRRRRRRRRWR"

    5

    Returns: 18

  12. "RRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRWRRWRWRRRWRW" "RRRRWRRRRRRRWRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRWR" "RRRRRRRRRRRRRWRRRWRRRRRRWRRRWRWRRRRRRRRRRRWRRRRRRR" "RWRWRRRRRRRRRRRWRRWRRRWRRWWRRRRWRRRRRRRRRRRRRRRRWR" "RRWRRRRRRRRRRWRRRRRRRRRRRRRRRWWRRRRRWRRRRRRRRRRRRR"

    6

    Returns: 17

  13. "RRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRWRRWRWRRRWRW" "RRRRWRRRRRRRWRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRWR" "RRRRRRRRRRRRRWRRRWRRRRRRWRRRWRWRRRRRRRRRRRWRRRRRRR" "RWRWRRRRRRRRRRRWRRWRRRWRRWWRRRRWRRRRRRRRRRRRRRRRWR" "RRWRRRRRRRRRRWRRRRRRRRRRRRRRRWWRRRRRWRRRRRRRRRRRRR" "RRRRRRRRWRRRRRRRRRWRRRRRRRRRWRRRRRRWRRRRRRRRRRRRRR"

    7

    Returns: 16

  14. "RRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRWRRWRWRRRWRW" "RRRRWRRRRRRRWRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRWR" "RRRRRRRRRRRRRWRRRWRRRRRRWRRRWRWRRRRRRRRRRRWRRRRRRR" "RWRWRRRRRRRRRRRWRRWRRRWRRWWRRRRWRRRRRRRRRRRRRRRRWR" "RRWRRRRRRRRRRWRRRRRRRRRRRRRRRWWRRRRRWRRRRRRRRRRRRR" "RRRRRRRRWRRRRRRRRRWRRRRRRRRRWRRRRRRWRRRRRRRRRRRRRR" "RRRRRRRWRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRRWRWRRR"

    8

    Returns: 16

  15. "RRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRWRRWRWRRRWRW" "RRRRWRRRRRRRWRRRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRWR" "RRRRRRRRRRRRRWRRRWRRRRRRWRRRWRWRRRRRRRRRRRWRRRRRRR" "RWRWRRRRRRRRRRRWRRWRRRWRRWWRRRRWRRRRRRRRRRRRRRRRWR" "RRWRRRRRRRRRRWRRRRRRRRRRRRRRRWWRRRRRWRRRRRRRRRRRRR" "RRRRRRRRWRRRRRRRRRWRRRRRRRRRWRRRRRRWRRRRRRRRRRRRRR" "RRRRRRRWRRRRRRRRRRRRRRRWRRRRRRRRRRRRRRRRRRRRWRWRRR" "RRWRRRRRRRRWRRRRWRRRRRRRRRRWRRRWWWRRRRRRRRRRWRRRRW"

    9

    Returns: 15

  16. "WRRRWRRRRRRRRRRRRRWRRRRRRRRRWRRRRWRRRRWWRRWWWRRRRR"

    10

    Returns: 18

  17. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    7

    Returns: 8

  18. "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"

    10

    Returns: 50

  19. "R"

    3

    Returns: 1

  20. "W"

    2

    Returns: 1

  21. "RRRRRRR"

    1

    Returns: 7

  22. "RWRRWWRWRWRRRWWRRRRWRRWRRWRRRRRRRRRWRWRWRRRRWRRRRR"

    4

    Returns: 30

  23. "RRRRWWRRRRWW"

    2

    Returns: 8

  24. "RWWRRRR"

    3

    Returns: 5

  25. "RWRRWWRWRWRRRWWRRRRWRRWRRWRRRRRRRRRWRRRRWWWRRRRRR"

    10

    Returns: 25

  26. "WRRRRRRRWRRRWWR"

    2

    Returns: 11

  27. "RWRW"

    2

    Returns: 4

  28. "RRRRRR"

    1

    Returns: 6

  29. "RWWRRRRRRWWRRRWRWRWRWWRRWWRWRWWRRRWWWRRRWRWRRRWW"

    2

    Returns: 40

  30. "WRWR"

    4

    Returns: 4

  31. "RR"

    1

    Returns: 2

  32. "RWRRWWRWRWRRRWWRRRRWRRWRRWRRRRRRRRRWRWRWRRRRWRRRRR"

    4

    Returns: 30

  33. "RRRRWWRRRRWW"

    2

    Returns: 8

  34. "RWWRRRR"

    3

    Returns: 5

  35. "RWRRWWRWRWRRRWWRRRRWRRWRRWRRRRRRRRRWRRRRWWWRRRRRR"

    10

    Returns: 25

  36. "WRRRRRRRWRRRWWR"

    2

    Returns: 11

  37. "RWRW"

    2

    Returns: 4

  38. "RRRRRR"

    1

    Returns: 6

  39. "RWWRRRRRRWWRRRWRWRWRWWRRWWRWRWWRRRWWWRRRWRWRRRWW"

    2

    Returns: 40

  40. "WRWR"

    4

    Returns: 4

  41. "RR"

    1

    Returns: 2

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: