Hello Everyone! I don't understand the reason why the pink balloon problem of the South African regional wasn't solved by anyone during the contest last year. looking at it today, in preparation for the South African regional, I realised it was a subset generation problem; so could use bit manipulation. the n = 20 packages kinda gave it away. thinking in succession: power(2, 20) = 1048576 possible subsets, then check ispalindrome() for each subset. However, looking at the max string length = 100. final thoughts came in: carefully optimise it tightly, is it DP(bitmask Dp)? or some problem that needs constructive algo with dp. decided to code but it seemed it wasn't enough. My region is a very small one and there is no online judge site for the submission. As you can see from my color, I am not very experienced. Any thoughts on the problem will be appreciated. THANKS.

Problem Description:

You are trying to make a necklace from coloured beads. A necklace consists of a sequence of beads. For a necklace to be beautiful it must be symmetric. In other words, listing the colours of the beads from left to right must give the same list as going from right to left. Unfortunately, the store you are in does not sell individual beads. Instead, it sells packaged sets of beads which are glued together. When you buy a package of beads, you must add all the beads in the package, in the order they occur in the package, to your necklace. You cannot even turn the package around. The store sells a number of different types of packages, and has an unlimited number of each type available. Each type of package also has a cost. You want to determine whether it is possible to make a beautiful necklace, and if so, the minimum amount it will cost. Example: We will use upper-case letters to indicate colours. Suppose the store sells the following packages: YGYGRG for 7, BGR for 9 and GY for 3. Then you can combine YGYGRG + BGR + GY + GY to make the beautiful necklace YGYGRGBGRGYGY for a cost of 22. Input: The input describes a number of test cases (up to 20). Each test case starts with a line containing an integer N , the number of types of packages. This is followed by N lines, each describing a package type. Each line consists of a positive integer (the cost for the package), and a string of upper-case English letters (the colours of the beads in the package). The end of input is marked by a line containing only the value. There are at most 20 packages, at most 100 beads per package, and each package costs at most 100.