StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is another approach: </p> <p>1) Order the set U with regards to the usual numerical ordering for base M.<br> 2) If there is a symbol between 0 and (M-1) which is missing, then that is the first number which is NOT MCAN.<br> 3) Find the fist symbol which has the least number of entries in the set U. From this we have an upper bound on the first number which is NOT MCAN. That number would be {xxxx} N times. For example, if M = 4 and U = { 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3}, then the number 333 is not MCAN. This gives us our upper bound.<br> 4) So, if the first element of the set U which has the small number of occurences is x and it has C occurences, then we can clearly represent any number with C digits. (Since every element has at least C entries).<br> 5) Now we ask if there is any number less than (C+1)x which can't be MCAN? Well, any (C+1) digit number can have either (C+1) of the same symbol or only at most (C) of the same symbol. Since x is minimal from step 3, (C+1)y for y < x can be done and (C)a + b can be done for any distinct a, b since they have (C) copies at least. </p> <p>The above method works for set elements of only 1 symbol. However, we now see that it becomes more complex if multi-symbol elements are allowed. Consider the following case: </p> <p>U = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1111,11111111} </p> <p>Define c(A,B) = the number of 'A' symbols of 'B' length. </p> <p>So for our example, c(0,1) = 15, c(0,2) = 0, c(0,3) = 0, c(0,4) = 0, ... c(1,1) = 3, c(1,2) = 0, c(1,3) = 0, c(1,4) = 1, c(0,5) = 0, ..., c(1,8) = 1 </p> <p>The maximal 0 string we can't do is 16. The maximal 1 string we can't do is also 16.<br> 1 = 1<br> 11 = 1+1<br> 111 = 1+1+1<br> 1111 = 1111<br> 11111 = 1+1111<br> 111111 = 1+1+1111<br> 1111111 = 1+1+1+1111<br> 11111111 = 11111111<br> 111111111 = 1+11111111<br> 1111111111 = 1+1+11111111<br> 11111111111 = 1+1+1+11111111<br> 111111111111 = 1111+11111111<br> 1111111111111 = 1+1111+11111111<br> 11111111111111 = 1+1+1111+11111111<br> 111111111111111 = 1+1+1+1111+11111111 </p> <p>But can we make the string 11111101111? We can't because the last 1 string (1111) needs the only set of 1's with the 4 in a row. Once we take that, we can't make the first 1 string (111111) because we only have an 8 (which is too big) or 3 1-lengths which are too small. </p> <p>So for multi-symbols, we need another approach. </p> <p>We know from sorting and ordering our strings what is the minimum length we can't do for a given symbol. (In the example above, it would be 16 zeros or 16 ones.) So this is our upper bound for an answer. </p> <p>What we have to do now is start a 1 and count up in base M. For each number we write it in base M and then determine if we can make it from our set U. We do this by using the same approach used in the coin change problem: dynamic programming. (See for example <a href="http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/" rel="nofollow">http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/</a> for the algorithm.) The only difference is that in our case we only have finite number of each elements, not an infinite supply. </p> <p>Instead of subtracting the amount we are using like in the coin change problem, we strip the matching symbol off of the front of the string we are trying to match. (This is the opposite of our addition - concatenation.) </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload