Get Time

   Problem Statement  

 Problem Statement for DengklekMakingChains

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.


Method signature:int maxBeauty(String[] chains)
(be sure your method is public)


-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.


-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'.


{".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", "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.
{"...", "..."}
Returns: 0
Mr. Dengklek cannot pick any links.
{"16.", "9.8", ".24", "52.", "3.1", "532", "4.4", "111"}
Returns: 28
{"..1", "3..", "2..", ".7."}
Returns: 7
{"412", "..7", ".58", "7.8", "32.", "6..", "351", "3.9", "985", "...", ".46"}
Returns: 58

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 532 Round 1 - Division I, Level One
       Single Round Match 532 Round 1 - Division II, Level Two