Connection Status:
Competition Arena > DengklekMakingChains

DengklekMakingChains

SRM 532 · 2011-11-22 · by fushar

SRM 532 · 2011-11-22 · by fushar · Greedy
Class Name: DengklekMakingChains
Return Type: int
Method Name: maxBeauty
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks live together in peace and harmony.

Mr. Dengklek works as a chain maker. Today, he would like to make a beautiful chain as a decoration for one of his lovely ducks. He will produce the chain from leftovers he found in his workshop. Each of the leftovers is a chain piece consisting of exactly 3 links. Each link is either clean or rusty. Different clean links may have different degrees of beauty.

You are given a String[] chains describing the leftovers. Each element of chains is a 3-character String describing one of the chain pieces. A rusty link is represented by a period ('.'), whereas a clean link is represented by a digit ('0'-'9'). The value of the digit in the clean link is the beauty of the link. For example, chains = {".15", "7..", "532", "..3"} means that Mr. Dengklek has 4 chain pieces, and only one of these ("532") has no rusty links.

All links have the same shape, which allows Mr. Dengklek to concatenate any two chain pieces. However, the link shape is not symmetric, therefore he may not reverse the chain pieces. E.g., in the above example he is able to produce the chain "532.15" or the chain ".15..37..", but he cannot produce "5323..".

To produce the chain, Mr. Dengklek will follow these steps:
  1. Concatenate all chain pieces in any order.
  2. Pick a contiguous sequence of links that contains no rusty links. Remove and discard all the remaining links.
The beauty of the new chain is the total beauty of all the links picked in the second step. Of course, Mr. Dengklek would like to create the most beautiful chain possible.

Return the largest possible beauty a chain can have according to the above rules.

Notes

  • Mr. Dengklek is not allowed to remove and discard individual links before concatenating the chain pieces.
  • If all links in the input are rusty, Mr. Dengklek is forced to select an empty sequence of links. The beauty of an empty sequence is 0.

Constraints

  • chains will contain between 1 and 50 elements, inclusive.
  • Each element of chains will contain exactly 3 characters.
  • Each character in each element of chains will be either a '.' or one of '0'-'9'.
Examples
0)
{".15", "7..", "402", "..3"}
Returns: 19

One possible solution: In the first step, concatenate the chain pieces in the order "..3", ".15", "402", "7.." to obtain the chain "..3.154027..". In the second step, pick the subsequence "154027". The beauty of the chain in this solution is 1+5+4+0+2+7 = 19.

1)
{"..1", "7..", "567", "24.", "8..", "234"}
Returns: 36

One possible solution is to concatenate the chain pieces in this order: "..1", "234", "567", "8..", "24.", "7.." -> "..12345678..24.7..", and then to pick the subsequence "12345678". Its beauty is 1+2+3+4+5+6+7+8 = 36.

2)
{"...", "..."}
Returns: 0

Mr. Dengklek cannot pick any links.

3)
{"16.", "9.8", ".24", "52.", "3.1", "532", "4.4", "111"}
Returns: 28
4)
{"..1", "3..", "2..", ".7."}
Returns: 7

Submissions are judged against all 299 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DengklekMakingChains with a public method int maxBeauty(vector<string> chains) · 299 test cases · 2 s / 256 MB per case

Submitting as anonymous