Algorithms practice with Crystal — AB
Introduction
This will be a series of algorithmic tasks for practice in Crystal programming language. I will start going through practice tasks from the TopCoder page, but in the future, I may put tasks from different sources. TopCoder, among other competitions, offers algorithmic competitions. The platform does not offer Crystal as the language of the submission and for that reason, I have first implemented the solution in C++ and validated that the platform accepts it.
The plan is to make a separate post for each of the tasks. For each task, I will first present the problem and then try to explain my reasoning and path by which I came to the solution I am presenting. The solution will be presented in the Crystal programming language.
Crystal is a relatively new and modern programming language. It heavily resembles ruby with a key difference in being type-safe and compiled. It’s worth mentioning that it compiles to very efficient machine code that can be comparable to C, depending on the task at hand.
I myself am not a Crystal master, but I really love the syntax of ruby and what the guys are doing with the Crystal language, so I want to give my contribution to the language by making this “tutorials” that might make you interested in the language besides (hopefully) helping you out with your algorithm preparations for tech job interviews or starting out competitive programming.
The problem — AB
The problem for which this post is going to try to explain the solution is called AB.
Problem statement
https://arena.topcoder.com/#/u/practiceCode/16319/46378/13642/1/325040
You are given two integers: N and K. Lun the dog is interested in strings that satisfy the following conditions:
- The string has exactly N characters, each of which is either
AorB. - The string s has exactly K pairs (i, j) (0 <= i < j <= N-1) such that s[i] =
Aand s[j] =B.
If there exists a string that satisfies the conditions, find and return any such string. Otherwise, return an empty string.
Limits
Time limit (s): 2.000
Memory limit (MB): 256
Constraints
- N will be between 2 and 50, inclusive.
- K will be between 0 and N(N-1)/2, inclusive.
Examples
Example 1
Input: 3, 2
Returns: “ABB”
This string has exactly two pairs (i, j) mentioned in the statement: (0, 1) and (0, 2).
Example 2
Input: 2, 0
Returns: "BA"
Please note that there are valid test cases with K = 0.
Example 3
Input: 5, 8
Returns: ""
Five characters are too short for this value of K.
Example 4
Input: 10, 12
Returns: "BAABBABAAB"
Please note that this is an example of a solution; other valid solutions will also be accepted.
The problem explained
For the solution, I want to try and explain my reasoning on how I got to the solution and not just give it right away. If I explain it well, I believe it can help one much more in solving problems in the future then just getting the code with lines explained.
That said, let’s first explore our problem. It is very important to really understand what the problem is, so I will spend some time explaining the examples in detail. Those who understand the issue can skip this section.
All that fancy formal math means is that we want strings that contain A and B characters such that those strings:
1. have the length of N
2. have the number of each of the letters A in front of each of the letters B summed up to K
1 is trivial, so let’s take a bit time to clear out 2. If we take each letter A in the string and count all the letters B that come after it in that some string and then sum all of those together we should get K.
Example 1 explained
String “ABB” has 1 letter A, and that letter A has 2 letters B after it, which makes K equal to 2. The string has 3 letters, which makes N equal to 3. This is exactly what was asked for, an example of a string that has a length of 3, and K equal to 2.
Example 2 explained
Here we are looking for a string with a length of 2 and K equals 0. The string BA has one letter A which has exactly 0 letters B that exist somewhere behind it in the string.
Example 3 explained
We are looking for a string with a length of 5 and K with a value of 8. There is no such a string with a length of 5 characters (letters) where K can be 8. We will explain why a bit later.
Example 4 explained
Here we are looking for a string with a length of 10 and K with a value of 12. Let’s calculate the value of K for the provided solution “BAABBABAAB”. The provided string has 5 letters A, let’s sum the letters B after each of them.
The solution
I hope that by now you understand the problem and how to calculate K from the string. Now we can start thinking of how to construct such a string when we are given K. Inexperienced people might freak out and ask themselves where to even start, so let’s try to answer that question. In the problems, when we don’t know how to solve it is good to try to start from a super simplified problem; try to answer much simpler questions and then build upon that.
So let’s explore. Let’s try to simplify the problem. What if we are allowed to have only one letter A. We still need to find a string that has K calculated in the same way and give back empty string "” in case a string does not exist, but the string can have only one letter A. This problem will more often not have a solution, but that does not matter at this point. What is important is that this problem is similar and sounds much simpler. Even if we don’t know any other way, we can always just try out the strings with a letter A on each of the spaces and see what value of K we get. We will quickly notice that we don’t even need to count letters B behind the letter A since we know that all of the letters till the end of the string are B. If we then mark the position of A as i, the value of K for the string would be N-i.
Cool, but what do we do now? Let’s see what happens when we try to add one more A and to stay as simple as possible let’s say that this second A must be next to the first one (no B’s between them).
Let’s take the above example and see how K changes when we add a letter A. It might depend on which side we add the new letter A, but since the end result will, in the end, be that we have two letters A next to each other, we get the same result regardless of which one has been added first. Using that knowledge lets simplify the problem a bit more without actually changing it. Let’s say that the second A can be added only from the right side of the current A, while it still has to be added next to it (We could have chosen any side). Let’s see now then what happens if we place the letter A on position 3 in the previous example instead of B.
Just as before the new A adds N-i to K. But the new A has impacted the old A since the place that was previously counted as B is no longer a B. Therefore, the new A that is added directly to the right of the already existing A contributes N-i-1 (-1 for crippling the old A). If we look further, we see that actually it does not really matter whether the new A is added directly next to the old one. As long as it is added from the right side its contribution will add up into K for all the B’s after and decrease the K for the letter A that is somewhere to the left.
If we look even further and try to add one more A but again adding it only to the right, we see that we get the same thing, except we now have to reduce the K for 2 A’s that are already present. It is clear that the general formula for the contribution of replacing B anywhere right from the rightmost A with A is N-i-Acount, where i is the position of the newly added A and Acount is the number of letters A already present in a string before the new one is added.
We already have a lot of insight, so let’s try to bring it all together with a few more conclusions. If we have a string with all characters B, it is obvious that we get the biggest contribution of replacing B with A if we replace the leftmost B. It is easy to see that the same is true for every subsequent replacement.
We can also see that, at some point, if we do a replacement, we will get less of a value from the B’s for the newly added A than what we lose for all the previous A’s losing one more B. Logically and by looking at our formula N-i-Acount, we see that this happens exactly when the replacement will make the total number of characters A larger than the total number of characters B. Which occurs exactly when there is an equal amount of characters A and B. Example: AABBB has the same K as AAABB, and AAAAB has a smaller K.
Ok, so we can try to add characters A from the left side until we:
— get the string K that is larger than or equal to the K that we are looking for
— get to the half of the string and do not reach the K we are looking for
Since adding characters A from the left side gives the largest contribution towards the K, the largest possible K we can get is for the string that has all characters A on the left half, and characters B on the right half. Therefore, for the second case, it is clear that the string with the given K and length N does not exist.
For the first case, we need to replace the last (rightmost one) character A with the character B and replace some other character B with A. We know that the more we move to the right, the less of a contribution there is. If we replace the character B that is just next on the right to the place where we returned B, that new A has exactly one less character B on the right side, while all characters A from the left side have the same amount of characters B on their right. This means that moving the rightmost character A by 1 place to the right will lower its contribution by exactly 1. So we just move A by the number of places that are missing to get the given K.
The last thing we want to be sure of is whether we will always be able to move A for the wanted amount of spaces. Let’s look at the following case.
We have exactly 1 A too many, meaning that the current K is bigger than the K we are looking for and if we replaced the rightmost A with B we would get a K that is smaller than the K we are looking for. We want to know whether there is a place where we have enough places to move the rightmost A to the right to get the value of K we are looking for. The biggest contribution that this A can give is just next to the rightmost A and that contribution depends on the number of characters B to its right. Let’s mark the number of characters B with Bcount. As we know that by moving the rightmost A to the right, we can lower its contribution by 1 per move. If we have Bcount characters B, we have exactly Bcount spaces to move the character A. Adding one A to the right will always contribute less than Bcount because it also has a partly negative contribution for removing one character B to the characters A that are to its left.
With this we have our algorithm:
Given that we replace B with A from the left:
Find the smallest amount of As that would form a string with its K value bigger or equel to the K we are looking for.if there is no such a string
return ""K' = calculate K for the current string
diff = K' - K
move the rightmost A for diff spaces to the right
Here it is in crystal
class AB
private def find_number_of_as(n : Int32, k : Int32) : Int32
m = n / 2
(1..m).each do |i|
return i if (i * (n-i) >= k)
end
-1
end def create_string(n : Int32, k : Int32) : String
a_count = find_number_of_as(n, k)
return "" if a_count == -1 k_ = a_count * (n - a_count)
last_a_move = 0
if k_ > k
last_a_move = k_ - k
a_count -= 1
end if last_a_move != 0
return "A"*a_count + "B"*last_a_move + "A" + "B"*(n - a_count - last_a_move - 1)
end
return "A"*a_count + "B"*(n - a_count)
end
end
I have committed and pushed both cpp and Crystal version here.
Note that we could have implemented a binary search for finding the initial number of As, but it would make the code a bit less readable, and for this problem would not make a visible contribution.
The Conclusion
Here it is, the first article. Please let me know what you think, has it been useful, was the way it was explained good, what can be better, and/or what tasks would you like explained next :)
