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.
It's Dijkstra. Let's construct all possible palindrome strings. Every time we know some prefix and suffix. Some part of prefix is just reversed suffix (or vice-versa if suffix.length() > prefix.length()). It's difficult to explain. Let me show dijkstra's path for sample from statement. Each node is described by two lines.
s[1]s[2]s[3]s[4]
s[n]s[n-1]
s[1] == s[n], s[2] == s[n-1], s[3] and s[4] is some suffix of one of given packages.
initial node is
"{YGYGRG}"
""
it's cost is 7, then add package "GY"
"{YGYGRG}"
"{YG}"
cost 10, again add "GY"
"{YGYGRG}"
"{YG}{YG}"
now we can continue construction by add "BGR"
"{YGYGRG}"
"{YG}{YG}{RGB}"
but we can also finish this palindrome using this packadge. Each node can be described by three integers: prefixLastPackageId, SuffixLastPackageId, and length difference between already constructed suffix and prefix. So there will be no more than 20 * 20 * 100 nodes in Dijkstra graph.