All Tracks>Algorithms> Greedy Algorithms> Basics of Greedy Algorithms> Problem
Minimize nodes
★★★★★

3.6

8 votes
Algorithms, Basics of Greedy Algorithms, C++, Greedy Algorithms
Problem

You are given N strings. Each string is given in the form of an array cnt of size 26 where the ith element in array denotes the count of the ith character of lowercase English alphabets in the string.

You have to select exactly 4 strings and insert the strings into a Trie. You are allowed to shuffle the characters in each string.

Task

Determine the minimum number of nodes present in Trie if the strings are selected optimally.

Notes

  • Trie will always have a root node. Include root node in the count of nodes present in Trie.
  • Insertion proceeds by walking the Trie according to the string to be inserted, then appending new nodes for the suffix of the string that is not contained in the Trie.

Input format

  • The first line contains a single integer T which denotes the number of test cases.
  • The first line of each test case contains an integer N.
  • The next N lines of each test case contain 26 space-separated integers denoting the count of each lowercase English alphabet in the string.

Output format

For each test case, print the minimum number of nodes present in Trie in a new line.

Constraints

1≤T≤54≤N≤200≤cnt[i][j]≤105

 

Time Limit: 0.5
Memory Limit: 256
Source Limit:
Explanation

Approach

  • You can shuffle the characters of 5 strings such that strings are:
    • baac
    • bbcd
    • bbb
    • bbaa
    • bccc
  • Now, there can be 5 different possibilities to select 4 strings.
  • If you select the first 4 strings:
    • baac, bbcd, bbb, bbaa: Minimum number of nodes in Trie will be 10 (including root node). The Trie will look like:

  • It can be proved that you cannot make a Trie with less than 10 nodes.
  • Thus, required answer is 10.
Editor Image

?