MailArchiving
SRM 240 · 2005-04-30 · by Jan_Kuipers
SRM 240 · 2005-04-30 · by Jan_Kuipers · Dynamic Programming
Problem Statement
Problem Statement
Your mailbox is a mess: it contains e-mails from weeks ago and you want to archive them. You know which folder you want to move each e-mail to. The names of the destination folders are given in a String[] destFolders and consist of letters (both upper- and lowercase) and spaces. The names are case sensitive. The i-th element of destFolders corresponds to the i-th element of your inbox.
To archive the e-mails you can just select the first one and move it to the appropriate folder, then select the second one, etc. Using this method, you need to make exactly the same number of selections as the number of e-mails you have. By selecting contiguous ranges of e-mails (that have to be moved to the same folder) and moving them at once, you can often do better. After moving one or more e-mails, they disappear from your inbox, so other e-mails may become adjacent.
Return the minimal number of selections you need to make to archive all your e-mails.
To archive the e-mails you can just select the first one and move it to the appropriate folder, then select the second one, etc. Using this method, you need to make exactly the same number of selections as the number of e-mails you have. By selecting contiguous ranges of e-mails (that have to be moved to the same folder) and moving them at once, you can often do better. After moving one or more e-mails, they disappear from your inbox, so other e-mails may become adjacent.
Return the minimal number of selections you need to make to archive all your e-mails.
Constraints
- destFolders contains between 1 and 50 elements, inclusive.
- Each element of destFolders has length between 1 and 50, inclusive.
- Each element of destFolders consists of letters and spaces.
Examples
0)
{"Deleted messages","Saved messages","Deleted messages"}
Returns: 2
First move the second e-mail to its destination. The other two become adjacent then and can be moved at once.
1)
{"Folder A","Folder B","Folder C","Folder D","Folder E","Folder F"}
Returns: 6
When all the destination folders different, you can't do anything smart.
2)
{"FOLDER","folder"}
Returns: 2
The names are case sensitive.
3)
{"a","b","a","c","a","a","b","a","c","d","a"}
Returns: 6
First move the e-mails to folders "b", "c", and "d" all separately and then move the e-mails to folder "a" at once.
4)
{"a","b","c","d","a","b","c","d"}
Returns: 7
Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MailArchiving with a public method int minSelections(vector<string> destFolders) · 38 test cases · 2 s / 256 MB per case