By definition, Ad Hoc problems are problems that cannot be classified anywhere else in the categories with well-studied solutions since each problem description and its corresponding solution are unique. These problems don’t fall under standard categories, there is no specific or general technique exists to solve them.
Ad Hoc problems frequently appear in programming contests. Mostly these problems are easy to solve, but in some cases, they can be very time-consuming. We will try to go a little deeper into ad-hoc problems by solving two different ad-hoc problems.
problem A
Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.
An integer y is a power of three if there exists an integer x such that y == 3x.
Example 1:
Input: n = 12 Output: true Explanation: 12 = 31 + 32
Example 2:
Input: n = 91 Output: true Explanation: 91 = 30 + 32 + 34
Example 3:
Input: n = 21 Output: false
solution
Note: We can only add the distinct powers of 3.
Let’s take example 2, where n is 91 and it can be summed up with powers of three. We can first get the highest power of three whose value is lower than n, so we can start our calculation from that power back to power 0. If we get to the place where sum becomes n return true, otherwise return false.
For n = 91, the highest power of three is 4. 34 = 81. The below function will return us the exact value.
int higestPower(int n){
int i = 0;
while(n>=3){
n/=3;
i++;
}
return i;
}Now, we can do the calculation. For n = 91, we got the highest power 4.
int hPower = higestPower(n);
/* for n = 91, hPower will be 4. for n = 12 hPower will be 2 */
int sum = 0;
/* initial sum = 0, loop backward from hPower to 0 */
for(int i = hPower; i>=0; i--){
sum+= pow(3,i); /*pow()is math function, ex: pow(3,4) = 81 */
if(sum > n){
sum-=pow(3,i);
}
else if(sum == n)
break;
}
/* after went through all the powers, if sum == n, return true or return false. */
return sum == n;Explanation of above code: The initial sum was 0, we add pow(3,4) to it, now sum = 81, the sum is not greater than n, so take it. try to add pow(3,3) = 27, now sum = 81 + 27 = 108, which is greater than 91, so we can’t take it and omit the pow(3,3) from the sum, sum again becomes 81. now we try to add pow(3,2) = 9, sum = 81 + 9 = 90 , which is not greater than 91 , so we can take it. try to add pow(3,1) = 3, sum = 90+3 = 93, we can’t take it and omit the pow(3,1) and sum again becomes 90. Last try to add pow(3,0)=1, sum = 90 + 1 = 91, sum becomes n, so we break the loop. So 91 is a Sum of Powers of Three.
Observation and example test cases were important in solving this problem. Problem link
Problem B
You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.
Return true if and only if we can do this so that the resulting number is a power of two.
Example 1:
Input: n = 1 Output: true
Example 2:
Input: n = 10 Output: false
Example 3:
Input: n = 46 // 46 can be rearranged as 64 Output: true
Solution
This problem can be solved easily by sorting the given integer and sorting the powers of 2 and then compare the sorted n to sorted powers of 2. It is an observation problem, If we can rearrange a number by its digits to another number, their sorted version will always be the same. Let’s say n = 821, after sorting it will be 128, which is a power of 2. Another example, if n = 64, upon sorting it will be 46, and the power of 2 is 64 which is also become 46 after sorting. Our task is to sort n and the powers of 2 and then compare.
string sortString(long n){
string s = to_string(n);
sort(s.begin(), s.end());
return s;
}to sort any integer first convert it to a string.
string s = sortString(n);
// power upto 30 as n can be 10^9
for(int i = 0; i<30;i++){
string powerOf = sortString(1 << i); // i<<2 is pow(2,i)
if(powerOf == s)
return true;
}
//don't get any match return false
return false;It was a complete observation problem, rather than trying to rearrange n every possible way and then comparing to the powers of two, get an easy solution by sorting values. problem link
Approach to the solution
There are some general tips for approaching a problem that appears to be Ad Hoc:
- Writing Down Ideas: Whenever there is an observation that seems useful, write it down as writing down the ideas makes sure that they are not forgotten and can potentially be the solution.
- Don’t get stuck: Don’t get stuck on any specific idea, unless it is appearing to be a complete solution for the problem. It’s a better idea to complete the search as Adhoc problems can waste a lot of time.
- Draw lots of small cases: In order to gain a better understanding of the problem, it is recommended practice to draw a lot of small cases. Draw more cases when-
- There is a problem with debugging.
- If you don’t know how to start with a problem.
- Whenever it is uncertain how to further approach the problem.
- The best idea is to draw more cases and make observations about the properties of the problem.
- Different perspectives: Try to approach the problem from different perspectives. Keep trying the ideas, draw a visual depiction of the problem, and try different formulas, and different values in the formulas until progress is made.
- Realize pattern in solution: After solving a number of programming problems, try to realize a pattern in solutions.
Categories
Let’s discuss some of the categories of the Adhoc problems set
- Chess game: Chess is a popular game that appears in programming contest problems and some of these problems are Ad Hoc problems. For example, the combinatorial task of counting how many ways there are to place 8-queens in 8×8 chessboard.
- Other games: Many other games like Cards, Tic Tac Toe, Rock-Paper-Scissors, Snakes/Ladders, BINGO, Bowling, etc have also made their way to the programming contests. Knowing the details of these games may prove to be helpful, but most of the game rules are listed in the problem description to avoid disadvantaging contestants who are unfamiliar with the games.
- Palindrome-related problems: A palindrome is a word (or a sequence) that can be read the same way in either direction. The most common strategy to check if a word is palindromic is to loop from the first character to the middle one and check if the characters match in the corresponding position from the back. For example, ‘ABCDCBA’ is a palindrome.
- Anagram-related problems: An anagram is a word (or phrase) whose letters can be rearranged to obtain another word (or phrase). The common strategy to check if two words are anagrams is to sort the letters of the words and compare the results. For example, take wordA = ‘cab’, wordB = ‘bca’. After sorting, wordA= ‘abc’ and wordB = ‘abc’ too, so they are anagrams.
problems list
Here are some ad-hoc problems for practice.
Reference
conclusion
Ad-hoc problems are more of observation and pattern-finding problems. That’s why these problems can be very handy for logical improvement and finding an easy solutions. If you are new to programming, here is a blog about the impact of programming and problem solving, you should give it a read.
Leave a Reply