Connection Status:
Competition Arena > DengklekGaneshAndChains

DengklekGaneshAndChains

TCO17 Round 2B · 2017-03-31 · by fushar

TCO17 Round 2B · 2017-03-31 · by fushar · Greedy
Class Name: DengklekGaneshAndChains
Return Type: String
Method Name: getBestChains
Arg Types: (vector<string>, vector<int>)
Problem Statement

Problem Statement

Dengklek works as a chain maker. He currently owns N chains. Each chain is a circular chain that consists of K links. There is a letter engraved on each link of each chain. You are given the String[] chains with N elements, each containing exactly K characters. Each element of chains contains the characters written on one of the chains, in order.

Ganesh is Dengklek's best friend. Tomorrow is his birthday. Dengklek wants to give Ganesh a straight (non-circular) chain as a present. He will do so by cutting and then combining some pieces of the chains he currently owns.

More precisely, you are given a int[] lengths that contains M elements. Dengklek will construct the new chain as follows:
  • At the beginning, the chain for Ganesh is empty.
  • For each i from 0 to M-1:
    • Dengklek will pick one of his circular chains that has not been picked before.
    • Dengklek will cut a contiguous sequence of lengths[i] links from the chain. He will keep the sequence and discard the remaining links. (In particular, if lengths[i] = K, Dengklek just splits the chosen chain at some point of his choice to turn it from a circular to a straight sequence. No links are lost while doing so.)
    • Dengklek will attach the sequence he just produced to the end of the chain for Ganesh.

Note that Dengklek's current chains are circular, so the last link of each chain is adjacent to the first link of that chain. Dengklek may choose a sequence that contains this part of the chain.

Note that Dengklek's chains are not symmetric. This means that Dengklek is not allowed to reverse the order of the links in any of the sequences he chooses.

Return the lexicographically largest possible string that can appear on the chain Dengklek gives to Ganesh.

Notes

  • Given two distinct strings of the same length, the lexicographically larger one is the one that has a larger character on the first position on which they differ.

Constraints

  • N and K will each be between 1 and 50, inclusive.
  • chains will contain exactly N elements.
  • Each element of chains will contain exactly K characters.
  • Each character of chains will be a lowercase English letter ('a' to 'z').
  • M will be between 1 and N, inclusive.
  • lengths will contain exactly M elements, inclusive.
  • Each element of lengths will be between 1 and K, inclusive.
Examples
0)
{"topc", "oder", "open", "twob"}
{2, 1, 3}
Returns: "wotrod"

The optimal solution is as follows: Dengklek picks "twob" and cuts "wo" from it. Dengklek picks "topc" and cuts "t" from it. Dengklek picks "oder" and cuts "rod" from it. This is possible because the chain is circular, so 'r' and 'o' are adjacent. The resulting chain is "wo" + "t" + "rod" = "wotrod".

1)
{"ssh", "she", "see", "sea"}
{2, 3, 2, 3}
Returns: "ssshesesee"

The optimal solution is as follows: Dengklek picks "ssh" and cuts "ss" from it. Dengklek picks "she" and cuts "she" from it. Dengklek picks "sea" and cuts "se" from it. Dengklek picks "see" and cuts "see" from it. The resulting chain is "ss" + "she" + "se" + "see" = "ssshesesee".

2)
{"wri", "ter", "who", "are", "you"}
{3}
Returns: "you"
3)
{"harus", "imfyo"}
{5, 5}
Returns: "yoimfushar"
4)
{"a"}
{1}
Returns: "a"

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

Coding Area

Language: C++17 · define a public class DengklekGaneshAndChains with a public method string getBestChains(vector<string> chains, vector<int> lengths) · 111 test cases · 2 s / 256 MB per case

Submitting as anonymous