Another recursive problem: choosing login times
posted 4 years ago
From TopCoder TCHS SRM 21 DIV 1
I reckon this is another recursive problem, but I need some pointers as to how to tackle it. Here's what I have so far (I've just parsed the input and scored how many points a login would get starting at each time unit).
What next?
Problem Statement
The students at Byteland Institute of Technology are registering electronically for classes. Registration is open for a predetermined number of time units, and each time unit is assigned a positive number called the goodness. Higher goodness values mean that the network is more likely to be available and responsive during those time units. You may log in at most K times during the registration period. Each login may last a maximum of D time units, and logins must not overlap with each other.
You are given a String[] values. Concatenate the elements of values to create one long string. The ith character of this string represents the goodness value of the ith time unit. The goodness values are given as characters 'a' to 'z', which represent values 1 to 26, respectively. Choose a strategy that maximizes the total goodness of the time units during which you are logged in, and return this total goodness value.
Definition
Class:
ElectiveSystem
Method:
maximalGoodness
Parameters:
String[], int, int
Returns:
int
Method signature:
int maximalGoodness(String[] values, int D, int K)
(be sure your method is public)
Constraints

values will contain between 1 and 20 elements, inclusive.

Each element of values will contain between 1 and 50 characters, inclusive.

Each character in values will be between 'a' and 'z', inclusive.

D and K will be between 1 and 1000, inclusive.
Examples
0)
{"acacca"}
4
1
Returns: 10
The goodness values are {1,3,1,3,3,1}. You may only log in once for a maximum of 4 time units, so the best strategy is to log in between time units 1 (0based) and 4, inclusive. The goodness values during this time interval are: 3+1+3+3=10.
1)
{"cab","cca"}
2
2
Returns: 10
The goodness values are {3,1,2,3,3,1}. The two login sessions that maximize the total goodness are {3,3} and the first {3,1}. The total goodness is 3+3+3+1=10.
2)
{"abcdefghijkl"}
100
100
Returns: 78
Since you are allowed to log in up to 100 times for up to 100 time units each, you can remain logged in for the entire registration period. The maximal total goodness is therefore 1+2+3+...+12=78.
3)
{"yptcsevnuzlsrfjxurpslztlinhddelpitmvaezowjcfjjfgmf","q"}
2
18
Returns: 598
4)
{"zzhhhhhh","zz"}
7
2
Returns: 152
Here you can also remain logged in for the entire registration period. One way to do this is to log in between time units 0 and 4, inclusive, and then immediately again between time units 5 and 9, inclusive. Note that you do not have to remain logged in for the entire 7 time unit maximum during each session.
I reckon this is another recursive problem, but I need some pointers as to how to tackle it. Here's what I have so far (I've just parsed the input and scored how many points a login would get starting at each time unit).
What next?
posted 4 years ago
1) get some paper, a pencil, and a large eraser.
2) write down how you would solve the problem by hand. make it very general.
3) go back and revise each step, making it more specific.
4) repeat step 3 until you have a very detailed plan
5) convert the detailed plan into code.
So, have you done steps 14 yet? If not, do so now. If so, take the part you can't covert into java and go back to steps 3 and 4.
Unless you have a more specific question in mind than "how do I do this", the above is the best advice you can get.
2) write down how you would solve the problem by hand. make it very general.
3) go back and revise each step, making it more specific.
4) repeat step 3 until you have a very detailed plan
5) convert the detailed plan into code.
So, have you done steps 14 yet? If not, do so now. If so, take the part you can't covert into java and go back to steps 3 and 4.
Unless you have a more specific question in mind than "how do I do this", the above is the best advice you can get.
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
posted 4 years ago
Managed step 1, having problems with step 2.
You can't just select the highest scoring times from the list, because that will sometimes eliminate other possibilities that would score higher in combination e.g. if the points for each time unit are
1,5,3,0,4,4,5,5,5,4,0,0
and you can have 2 logins of up to 3 time units, the best you can get is by selecting (4,4,5) and (5,5,4) for a total of 27, rather than selecting (5,5,5) then seeing what's left, which will be (1,5,3) for a total of 24.
If the list is long there are too many combinations to test each exhaustively. Coding it shouldn't be too much of a problem, but I need some help with the algorithm.
You can't just select the highest scoring times from the list, because that will sometimes eliminate other possibilities that would score higher in combination e.g. if the points for each time unit are
1,5,3,0,4,4,5,5,5,4,0,0
and you can have 2 logins of up to 3 time units, the best you can get is by selecting (4,4,5) and (5,5,4) for a total of 27, rather than selecting (5,5,5) then seeing what's left, which will be (1,5,3) for a total of 24.
If the list is long there are too many combinations to test each exhaustively. Coding it shouldn't be too much of a problem, but I need some help with the algorithm.
posted 4 years ago
perhaps, but how did you figure that out?
I would posit you did something like this...
You picked a set of 3 (say elements 02). You then picked the largest remaining set of 3, and computed the score. If it was not larger than the largest found so far, you discard it. If it was, you remember it.
you then picked the next set of three (elements 13), etc.
Luigi Plinge wrote:the best you can get is by selecting (4,4,5) and (5,5,4) for a total of 27, rather than selecting (5,5,5) then seeing what's left, which will be (1,5,3) for a total of 24.
perhaps, but how did you figure that out?
I would posit you did something like this...
You picked a set of 3 (say elements 02). You then picked the largest remaining set of 3, and computed the score. If it was not larger than the largest found so far, you discard it. If it was, you remember it.
you then picked the next set of three (elements 13), etc.
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
posted 4 years ago
even 'by inspection' can be converted to an algorithm. For example, you could find the largest value in a set 'by inspection'. What that means is
look at each
remember the largest.
ok...looking at each is easy, but how do you remember the largest?
well, when you look at an element, see if it is larger than any other you've found so far.
how you you know what the largest you found so far is? you keep track of it.
How do you keep track?
well, each time i read a new one, compare it to the largest found so far. If it's smaller, ignore it. If it's larger, replace the old largest found with the current.
look at each
remember the largest.
ok...looking at each is easy, but how do you remember the largest?
well, when you look at an element, see if it is larger than any other you've found so far.
how you you know what the largest you found so far is? you keep track of it.
How do you keep track?
well, each time i read a new one, compare it to the largest found so far. If it's smaller, ignore it. If it's larger, replace the old largest found with the current.
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors