TopCoder Statistics - Problem Statement

Problem Statement

When returning from vacation, you have to delete some unwanted email messages in your inbox, like spam or other unimportant messages. Your inbox consists of several pages that each contain the same number of messages (except possibly the last page). Each message has two corresponding buttons that allow you to:

- add the message to the current selection
- remove the message from the current selection

In addition, each page has three buttons with the following functions:

- select all messages on the current page
- delete all selected messages on the current page
- advance to the next page of messages (unless you're already on the last page)

Selections do not extend across pages, and advancing to the next page deselects everything that is currently selected. Also, deleting messages will not cause later messages in the inbox to scroll up to the current page.

For example if you have four email messages on one page and you would like to delete the second one, you could select it and then click on delete for a total of two clicks. An alternative is to select all messages, then deselect all other messages except the second, and then click delete, for a total of five clicks.

Naturally, you would like to clean up your inbox with as few clicks as possible. Furthermore, you are allowed to choose the number of emails to display per page. If you decide to display K messages per page, the first K messages will be on the first page, the next K messages will be on the second one, and so on. Obviously, the last page might contain less than K messages. Note that you need to check all pages of messages, even if they do not contain any messages that must be deleted.

You will be given a String messages containing a description of email messages in the order they appear in your inbox. The 'D' character denotes a message that should be deleted, while a '.' character denotes an email that should be kept. You will also be given two ints, low and high, denoting the inclusive lower and upper bounds of the number of messages on each page. You should choose how many emails to display per page such that the number of clicks needed is minimal, and then return the number of clicks.

Definition

Class:: InboxCleanup
Method:: fewestClicks
Parameters:: String, int, int
Returns:: int
Method signature:: int fewestClicks(String messages, int low, int high)
(be sure your method is public)

Constraints

messages will contain between 1 and 50 characters, inclusive.
Each character of messages will be either 'D' or '.'.
low will be between 1 and the number of characters in messages, inclusive.
high will be between low and the number of characters in messages, inclusive.

Examples

".........."

5

10

Returns: 0

No messages to delete here. Since we can display all messages in one page, there is no need to click any button.
".D.D.DD.D."

5

5

Returns: 8

Your only choice here is to display 5 messages per page. Select the two messages from the first page and then click delete for a total of three clicks. One more click is needed for advancing to the next page. For the second page, you have two options: first select all messages and then deselect the third and fifth ones, or select each of the three 'D' messages individually. Both options require three clicks. After the selection is made, click delete.
"...D..DDDDDD...D.DD.."

3

10

Returns: 12

Display 6 messages per page.
"D."

1

2

Returns: 2
"....D"

1

2

Returns: 4
"DDD.D"

1

3

Returns: 5
"D.D.D"

1

2

Returns: 8
".D..DD.D"

3

6

Returns: 6
"DDD.DD.D"

1

2

Returns: 11
"DD.D..DD"

1

4

Returns: 7
"DD..D...."

5

6

Returns: 5
"..D.D...DD"

9

10

Returns: 5
"......D..D.DD."

5

11

Returns: 7
"DDDD...D.D.DD.."

1

10

Returns: 10
"DD...D.DDD.D..."

7

12

Returns: 8
"...DDDDDDDDD..."

2

6

Returns: 8
"D.....D..D.D.D."

3

14

Returns: 7
"DDD..D....D.D..D.DD"

9

9

Returns: 14
".DD.D.DDD.DD.D.D.DD"

9

12

Returns: 12
"D..D...DD.DDDDDD.D.."

19

19

Returns: 11
"..DD.DD.....D.D..D.."

8

16

Returns: 10
".D...D....DDD...D..."

9

13

Returns: 9
"D..DD...DDD.DDDD.D.D..DD."

8

20

Returns: 14
"DD.D..DD.DD.D..DDDD.DDDD."

19

25

Returns: 11
"D..D..D..D.D.DDDDD...DDD."

9

9

Returns: 14
"D...D...DDD.D..D.DD...DD."

14

16

Returns: 14
"D....DD.D.DD......DD.DDD."

6

17

Returns: 13
"D.D..D..DD.DDDD.D.DDD.DDDD.."

3

11

Returns: 17
".D.D...DDD..DD...D.DD....D..DD"

15

29

Returns: 15
"D..D...D.D.DD..D..DDD.DDD.D..."

4

27

Returns: 16
"DDD......DDDDD....D.D.D.D..D.."

16

26

Returns: 16
".DD.D.D.DDD...D.D.D.D...DD.D.."

17

25

Returns: 17
"D.DDDDD..D.D.DDDDDDD..DD.....DD."

16

20

Returns: 13
"DDD.D.D..DDDDDD...DD..DDD.D..D.D.."

4

29

Returns: 16
"DDD..DD...D.D.DD...D..DDD..D.DD.DD"

3

20

Returns: 19
"..DD.D.DDDD..DD.DDDDD.D.DDDDD...DD"

19

22

Returns: 17
"..D.D...DD.DDD.D.DD...DDD....DDDD.."

5

13

Returns: 21
"D.DDD...D.DDD.D.D...DD...D.DDDDD.DDD.DD"

19

22

Returns: 20
"DDDD....D.....DD...D.DD.D.DD..DDD..D..D"

12

28

Returns: 20
"DD..D..DD......DD.D..DDD..D.......DD..D"

15

16

Returns: 20
"DDD.....DD....D.D.D...DDD......DD.D.D.D"

11

29

Returns: 19
"D..D...DDD.D.DDDDD..DD.D..D.D..DDDDDD.D"

10

22

Returns: 21
"D.DDDD.D....D....DDDDD..D.D..DD.D.DD....D"

40

41

Returns: 21
"DDDD.D.D..DD...DD.D.DD.....DD...D.D.DD.D.D"

11

28

Returns: 21
"D....DDD....D...D...D..D.D.D...D.DD.D..D...."

14

15

Returns: 20
"..DDD..D.....D....DD.D.D.D.D..DD.D...D.DD.D."

16

21

Returns: 23
"...D.DDDDDD...D.D.D.DD.D.DD.D.D.D...DDDDD.D."

20

42

Returns: 23
"...DD.D......D..DDDDDDDDD..DD..D.D.DDDD...D.....D."

3

33

Returns: 22
"D....D...D.DDDDD..D.D..D...D.D.DD...D.D...D.D...D."

2

17

Returns: 25
"D.D.D.D....D...D..DDD.D..D.D.D.DD.DD.D.D.DDDD...D."

10

44

Returns: 25
"..DDDDDD....D.DD...D.DDDDDDD.....D..D.D.D......D.D"

16

18

Returns: 28
"DD....DD.D.DDDD..D.....D..D.DD....D....D.D..DDDDDD"

29

43

Returns: 22
".DD.DD...DD..D..DDDD..D.D...DDD.DD..D.DDDDD.D....."

10

19

Returns: 27
"DD....D.DD.D...DDD..DD...D.D...D.D....D..D..D.DD.D"

22

46

Returns: 23
"...D.D.DDDD..DD.DD..DD..DDD..D...DDD..DD..DDDDD..."

2

38

Returns: 27
".DD..DDDDD....DDD.DD.DDD..D..D...DDDDDD.DD...DD..."

6

29

Returns: 26
".DD.DDD.DD..D.DDDD..D..D..D.DD.D.D....DDDDD.DDDD.."

4

32

Returns: 24
"D.DD.DD..DD.DD..D.DD.D....D..D..D.D.D.DD.....D..DD"

37

50

Returns: 24
".DDDD..DDD..D.D.D.D.DDDD.D...D..D..DDDDD.DDDDD.DDD"

5

35

Returns: 24
"DD.D...DD...DD.D.D..DDDDDD.DD..D..DDD.D...D.D.D..."

3

48

Returns: 24
"....D...DD.D..DD.D.D.D.DD..D.D.D.....D...DDDDD.DDD"

12

42

Returns: 20
".DDDD.DD....DD..D.DD.D..D.D...DDD.DDD.D..DD.D.DDD."

13

16

Returns: 30
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD"

6

12

Returns: 14
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD"

1

1

Returns: 149
".................................................."

50

50

Returns: 0
".................................................."

1

50

Returns: 0
"DDD........................."

1

3

Returns: 11

Remember that you need to check all pages.
"DDDD.D.D..DD...DD...D......D....D........."

1

4

Returns: 28
".................................................."

1

6

Returns: 8
"D"

1

1

Returns: 2
"."

1

1

Returns: 0
"DDDDD.....DDDDD.....DDDD"

5

5

Returns: 10
"DDDDDD"

4

4

Returns: 5
"......DDDD."

6

6

Returns: 4
".........."

5

5

Returns: 1
"..............................DDDDD"

15

15

Returns: 4
"DDDDDDDD."

5

5

Returns: 6
"..........DDDDD"

10

10

Returns: 3
"..........DDDD"

10

10

Returns: 3
"DDD.....................DDD"

1

4

Returns: 11
"........DDDD"

8

8

Returns: 3
".......DDD"

7

7

Returns: 3
"DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD"

1

1

Returns: 146
"DDDDD.....DDDDD.....DDDDD.....DDDDD.....DDD"

1

43

Returns: 18
".......DDD"

1

10

Returns: 3
".....DDD"

5

5

Returns: 3
".................."

1

1

Returns: 17
"DDDD.DDD..DD....DDD...DD..D......DDDDD"

1

5

Returns: 30
"DDDDDDD"

4

4

Returns: 5
"......DDDD"

6

6

Returns: 3
"DDDD...."

8

8

Returns: 5
"...."

1

1

Returns: 3
"DD"

1

1

Returns: 5
"................................................."

5

6

Returns: 8
"............."

5

13

Returns: 0
"........DDDDD.."

8

8

Returns: 5
".D."

2

2

Returns: 3
"....DDD"

4

4

Returns: 3
"...DDD..."

1

5

Returns: 4
"DDDDDDDDD"

5

5

Returns: 5
"...DD"

3

3

Returns: 3
"DDDDDDDDDDDDD"

10

10

Returns: 5
"DDDDDDDDD"

3

3

Returns: 8
".....DDD."

5

5

Returns: 4
"D.D..D..DD.DDDD.D.DDD.DDDD.."

3

11

Returns: 17
"DDDDDDDD"

5

5

Returns: 5
"DD...DDD"

5

5

Returns: 6
"DDDDDDDDDDDDDDDDDD.................DDD"

1

10

Returns: 12
"DDDDD"

5

5

Returns: 2
"......................"

5

5

Returns: 4
"........................................"

3

6

Returns: 6
"DDD........................."

1

3

Returns: 11
"...D..DDDD.D...D.D"

6

6

Returns: 10
"........DDDDDDD........D.D.D.D"

19

20

Returns: 14
"...D..DDDDDD...D.DD.."

3

10

Returns: 12

Statistics

Problem Statement for "InboxCleanup"

Problem Statement

Definition

Constraints

Examples