In this article, we'll explore the concept of binary exponentiation, understand how it works, and implement it in code.

What is Binary Exponentiation?

Binary exponentiation is a method to compute \(a^n\) (a raised to the power of n) using only multiplications, instead of the naïve \(O(n)\) multiplications.

This significant improvement in efficiency makes it possible to calculate extremely large powers quickly, even when dealing with modular arithmetic.

How Binary Exponentiation Works

The key idea behind binary exponentiation is to break down the exponent into its binary representation and use the properties of exponents to simplify the calculation.

Let's break it down step by step:

1. Convert the exponent n to its binary representation.

2. Initialize the result as 1 and the base as a.

3. Iterate through each bit of the binary representation of n from right to left: (a). If the current bit is 1, multiply the result by the current base. (b). Square the base (multiply it by itself).

4. Return the final result.

For example, let's calculate \(3^{13}\):

1. Convert 13 to binary: \(13_{10} = 1101_2\)

2. Initialize result = 1, base = 3

3. Iterate through the bits:

   • Bit 1: result = \(1 *3 = 3\), base = \(3 *3 = 9\)

   • Bit 0: result = 3, base = \(9 * 9 = 81\)

   • Bit 1: result = \(3 *81 = 243\), base = \(81 *81 = 6561\)

   • Bit 1: result = \(243 * 6561 = 1,594,323\)

Thus, \(3^{13}=1,594,323.\)

Why Binary Exponentiation is Efficient

The efficiency of binary exponentiation comes from two main factors:

1. Reduced number of multiplications: Instead of performing n-1 multiplications as in the naïve approach, we only perform \(O(log n)\) multiplications. This is because we're essentially breaking down the problem into smaller subproblems based on the binary representation of the exponent.

2. Reuse of previous calculations: By squaring the base at each step, we're reusing the results of previous calculations, which significantly reduces the overall number of operations needed.

To illustrate this efficiency, consider calculating \(a^{1000000}\). The naïve approach would require 999,999 multiplications, while binary exponentiation would only require about 20 multiplications (as \(\log_2(1000000) \approx 20\)).

Algorithm Implementation

Let's implement the binary exponentiation algorithm in Python:

def binary_exponentiation(base, exponent):
    result = 1
    while exponent > 0:
        # If the current bit is 1, multiply the result by the current base
        if exponent & 1:
            result *= base
        # Square the base
        base *= base
        # Move to the next bit
        exponent >>= 1
    return result

# Example usage
print(binary_exponentiation(3, 13))  # Output: 1594323

Let's break down the algorithm:

1. We initialize result to 1, which is the identity for multiplication.

2. We use a while loop to iterate until the exponent becomes 0.

3. We check if the least significant bit of the exponent is 1 using the bitwise AND operator &. If it is, we multiply the result by the current base.

4. We square the base by multiplying it by itself.

5. We use the right shift operator >>= to move to the next bit of the exponent.

6. Finally, we return the result.

Time Complexity Analysis

The time complexity of binary exponentiation is \(O(log n)\), where n is the exponent. This is because:

1. The number of bits in the binary representation of n is \(\lfloor \log_2 n\rfloor + 1\).

2. We perform at most two multiplications per bit (one for squaring the base, and potentially one for updating the result).

Therefore, the total number of multiplications is at most \(2(\lfloor \log_2 n \rfloor + 1)\), which simplifies to \(O(\log n)\).

Example Problems and Solutions

Let's look at some algorithmic problems that you can solve efficiently using binary exponentiation, along with detailed explanations of the solutions and how we arrived at using binary exponentiation.

Problem 1: Modular Exponentiation

Problem: Calculate \(3^{1000000} \bmod 1000000007\).

Approach:

1. We recognize that this problem involves a very large exponent (1000000), which would be impractical to compute using naïve exponentiation.

2. We also notice that we need to find the result modulo a large prime number (1000000007).

3. This combination of a large exponent and modular arithmetic is a clear indicator that we should use modular binary exponentiation.

Solution: We'll modify our binary exponentiation function to include modular arithmetic:

def mod_binary_exponentiation(base, exponent, mod):
    result = 1
    base %= mod
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent >>= 1
    return result

print(mod_binary_exponentiation(3, 1000000, 1000000007))  # Output: 624098969

Explanation:

1. We initialize result to 1 and set base to base % mod to handle cases where the initial base is larger than the modulus.

2. The main loop works similarly to the original binary exponentiation algorithm, but with two key differences:

   a. When updating result, we perform (result * base) % mod. This ensures that result never exceeds mod, preventing integer overflow and maintaining the correct modular result.

   b. When squaring base, we perform (base * base) % mod for the same reason.

3. The bitwise operations (exponent & 1 and exponent >>= 1) work exactly as in the original algorithm, allowing us to process the binary representation of the exponent efficiently.

4. By applying the modulo operation at each step, we ensure that all intermediate results remain within the range [0, mod-1]. This is possible because of the properties of modular arithmetic:

   $$(a⋅b)modm=((amodm)⋅(bmodm))modm$$

This problem would be impossible to solve with naïve exponentiation due to the huge result, but modular binary exponentiation makes it tractable by keeping all intermediate results manageable.

Problem 2: Matrix Exponentiation

Problem: Given a 2x2 matrix A, calculate An where n = 1000000.

Approach:

1. We observe that we need to raise a matrix to a very large power (1000000).

2. Matrix multiplication is associative, which allows us to use the same principle as binary exponentiation for numbers.

3. We recognize that this is a perfect scenario for applying binary exponentiation to matrices.

Solution: We can use binary exponentiation on matrices. Here's a Python implementation with explanations:

import numpy as np

def matrix_multiply(A, B, mod):
    return np.array([[(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % mod, (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % mod],
                     [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % mod, (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % mod]])

def matrix_power(A, n, mod):
    result = np.eye(2, dtype=int)
    while n > 0:
        if n & 1:
            result = matrix_multiply(result, A, mod)
        A = matrix_multiply(A, A, mod)
        n >>= 1
    return result

A = np.array([[1, 1], [1, 0]])
n = 1000000
mod = 1000000007

result = matrix_power(A, n, mod)
print(result)  # Output: [[690749268 297612485]
                #         [297612485 393136783]]

Explanation:

1. matrix_multiply(A, B, mod):

   • This function performs matrix multiplication of two 2x2 matrices, A and B.

   • Each element of the resulting matrix is computed using the standard matrix multiplication formula, followed by a modulo operation to keep the values manageable.

2. matrix_power(A, n, mod):

   • This function implements binary exponentiation for matrices.

   • We start with result as the 2x2 identity matrix (created using np.eye(2, dtype=int)).

   • The main loop follows the same pattern as scalar binary exponentiation: a. If the current bit of n is 1, we multiply result by the current A. b. We square A (by multiplying it with itself). c. We right-shift n to move to the next bit.

   • All matrix multiplications are done using our matrix_multiply function, which incorporates modular arithmetic.

This matrix exponentiation technique is particularly powerful for solving linear recurrence relations in logarithmic time, as demonstrated here with the Fibonacci sequence.

Practice Problems

Here are some problems for you to solve using binary exponentiation:

1. Modular Exponentiation: Calculate \(7^{1234567} \bmod 1000000009\). (Hint: Use the mod_binary_exponentiation function from Problem 1 in the examples.)

2. Last Digit: Find the last digit of . (Hint: Observe the pattern of last digits of powers of 2 and use binary exponentiation with modulo 10.)

3. Power Tower: Calculate the last 3 digits of \(2^{2^{20}}\). (Hint: Use the property of modular arithmetic that \(a^b \bmod m = a^{b \bmod \phi(m)} \bmod m\) where \(\phi\) is Euler's totient function. You'll need to calculate \(2^{20} \bmod \phi(1000)\) first.)

4. Matrix Chains: Given a 2x2 matrix A = [[1, 2], [3, 4]], calculate the last two digits of the sum of all elements in \(A^{1000000}\). (Hint: Use matrix exponentiation as in Problem 2 from the examples, but only keep track of the last two digits of each element. You'll need to sum the elements after the final exponentiation.)

5. Fibonacci Sequence: Find the 1000000th Fibonacci number modulo 1000000007. (Hint: Use the matrix form of the Fibonacci sequence ([[1, 1], [1, 0]]) and apply matrix exponentiation as shown in Problem 2 of the examples.)

Conclusion

Binary exponentiation is a powerful technique that can be applied to a wide range of problems involving large exponents. As we've seen in the example and practice problems, it's particularly useful in modular arithmetic, matrix operations, and solving recurrence relations.

By practicing these problems, you'll gain a deeper understanding of how to apply binary exponentiation in various scenarios. Remember, the key is to recognize when a problem involves raising something to a large power, whether it's a number, a matrix, or even a more complex structure.

If you found this explanation of Binary Exponentiation algorithm helpful, you might also enjoy more in-depth programming tutorials and concepts I cover on my blog.

I've been a competitive programmer for many years. And during that time, I have faced the process of debugging on numerous occasions.

In this article, I will try to describe how debugging works in such environments, instead of depicting it in the regular software development activities we do every day.

But why? You might ask.

The reason is that, because of the short time limit set in these competitions, the participants have to come up with creative ideas to solve all the issues they face. There is no tomorrow for them. It is either "crack or go home".

And sometimes, these ideas can be extrapolated onto the so-called "real world" software development.

Without further ado, let's see what I'm talking about.

Some Context

Competitive Programming contests are a type of competition in which every contestant gets a set of problems. The idea is for them to solve the maximum number of problems they can within the time limit set for the contest, which is usually around two to five hours.

Every problem specifies the format of the input, and it expects some output in response. For example, we could have a problem stating that you need to find the sum of the numbers in a list. In this case, the input would be a list of numbers, and the output would be a single number.

Usually, these competitions take place on automated platforms that can receive solutions for every problem and evaluate those solutions against an entire dataset hidden from the competitors. If a solution returns the expected value for every dataset, it is said to be "Accepted", otherwise it is "Rejected".

As you can imagine, crafting and submitting accurate solutions is an important skill for every participant, but so is being fast. Finding the right balance between correctness and speed is what makes a competitor rise to the top of the standings with more problems solved than their rivals.

Not so far from "real life", isn't it?

It is common to see software companies fighting each other to see which one is the fastest to achieve certain goals or which one gives better results when looking at some particular topic. The balance between doing something right and doing it fast is always critical when working in software development.

And here is where debugging shows up as a key factor, because:

• It ensures correctness once the "bugs" have been dealt with.
• It can affect speed if the process of finding errors takes too long.

Let's see what actually happens during competitive programming contests, then!

The "Bug" Strikes Back

When participating in programming contests, bugs often appear when performance is a defining factor in the solution to a problem. That is, not only is the correct output taken into account, but also how much time your solution takes to return that output for the entire dataset.

The following case is the most common one:

We read a problem, and we know a solution that solves that problem correctly. But unfortunately, it won't be fast enough. No worries, we think about the problem some more and we came up with a solution that is also correct, but this time it will fit in the time limit set for the problem.

We rush into coding our solution, test it a little with some manual test cases, submit it, and... end up receiving a "Rejected" verdict. Which means our solution returned the wrong output for some input.

What do you do in this case?

The approach that most competitors take is to keep testing their solutions against some hand-crafted test cases they come up with. They try to look for edge cases where the solution might return the wrong output, but this is not always easy to do.

The frustration of seeing your program return the correct output for every input you give but knowing there is some hidden test case in which your solution fails can lead you to stop trying a problem that you are almost certain you know the solution to.

This will, of course, impact your performance in the competition because you invested time in a problem you will not end up solving.

So, when the debugging process is taking too long, it is a good alternative to go for the "have the computer find the bugs for you" approach.

Let's see how this works!

Debug Smarter, Not More

First of all, of course, the computer won't find the bugs for you. The bugs are your own and you will be responsible for finding them. But, what the computer can do is help you generate enough data in a short time to help you find where your solution fails.

Remember that solution we talked about that would give the correct output but wasn't fast enough? Now it's time to make use of it.

Usually, this solution will be easier to code, and less prone to having bugs in it. Let's say we can rely on it because we know we are skilled enough to solve any problem using a no-brainer approach.

Do you recall the previous debugging process?

1. Generate hand-crafted input.
2. Run your solution with that input.
3. Manually check if the output returned is correct.
4. If it is not correct, you have a test case to debug thoroughly. Otherwise, repeat step 1.

This is highly inefficient for a person to do. Especially steps 1 and 3.

What we can do to speed up this process is to change the checks that we do in step 3 to be automatic instead of manual. And the easiest way to do it is by comparing the outputs returned by both of our solutions (the no-brainer and the buggy) given the same input.

If we coded our no-brainer solution right (which we are skilled enough to do, of course) then we can ensure that the moment the outputs differ, we have found a test case that is worth having a deeper look into.

Ok. But what about step 1?

The process of generating test cases can be difficult, especially if what we are trying to do is to find one that makes our solution return the wrong output. I mean, if we were able to do that easily then we would have fixed our solution already 😅.

Fortunately, the solution for this issue is to rely on randomness. Yes, you heard me correctly. Randomness provides a spectacular way of generating non-biased input and it works surprisingly well and fast in most cases.

We can replace our hand-crafted process of creating test cases with an automated, easy-to-code, random process that will do the work for us.

Now, the debugging process will be:

1. Generate random input.
2. Run both solutions with that input.
3. Check if the outputs differ.
4. If they do, you have a test case to debug thoroughly. Otherwise, repeat step 1.

The difference between both approaches is that the second one can be fully automated, and we will see how to do it next.

Automated Debug Mode

Let's automate our debugging process, then!

We will start with this template code in Python, which we will be filling up with the proper code to help us achieve our goals.

def no_brainer():
    pass


def solution():
    pass


def generate_input():
    pass


def debug():
    pass


if __name__ == "__main__":
    debug()

The purpose of this implementation is to have the debug function generate a new test case by using the generate_input function, and supply it to our solution and our no_brainer solution while the results are the same. The moment the results differ, we can stop generating new test cases and analyze the one that makes our solution fail.

A real example

Let's make it more interesting by solving a classic algorithmic problem:

"Given a sorted array of integers, and an integer x, find the first index of the array containing the number x, or return -1 in case the number doesn't appear in the array".

Now, because we are smart, we know how to solve this problem by using a linear search over the array. The implementation in Python could be something like this:

def no_brainer(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

This is our no-brainer solution. Just a plain for-loop until we find the element we are looking for. The moment we find it, we return the index in which the element can be found. And, in case we don't find it, we return -1, as requested in the problem statement.

Let's assume this solution is not fast enough. Maybe it is because the size of the array is too big and, in the worst case, our solution will end up iterating through all the elements just to find out that the number we were looking for is not present in the array at all.

But, since the array is sorted maybe we can use the Binary Search algorithm, which will indeed speed up the search process. That sounds like a good idea, right? Let's try it!

def solution(a, x):
    l = 0
    r = len(a) - 1
    while l <= r:
        m = (l + r) // 2
        if a[m] == x:
            return m
        elif a[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1

The code above tries to find the number x in the array, and it also returns -1 in case it doesn't find it. Now, it doesn't perform a linear search so we are not expecting it to time out but for some reason, when we submit it for review, we receive a "Rejected" verdict.

As we said before, we will not rush into manual debugging. Instead, let's start by creating a random generator to supply input to both our solutions, hoping we will find the bug soon. Our generating function could be something like this:

import random

def generate_input():
    n = random.randint(1, 10)
    a = [random.randint(1, 10) for _ in range(n)]
    a.sort()
    x = a[random.randint(0, n - 1)]
    return a, x

We are generating arrays with sizes at most 10, which is a manageable number of elements. We are also making sure the elements are sorted, and we are taking the number x as one of the numbers present in the array.

What we are missing now is just putting all the pieces together, like this:

def debug():
    test_cases = 10000
    for _ in range(test_cases):
        a, x = generate_input()
        no_brainer_output = no_brainer(a, x)
        solution_output = solution(a, x)
        if no_brainer_output != solution_output:
            print("Test Case:")
            print(a, x)
            print("Solution Output:", solution_output)
            print("No-Brainer Output:", no_brainer_output)
            exit()
    print("All test cases passed succesfully")

By having a glance at the code we can see the benefits of having this as part of our debugging process.

Notice that we have set a limit of 10000 test cases. That amount is not realistic for a single person to generate, and it sure seems like a sufficiently large number that might ensure we will find a test case where our solutions differ.

On the other hand, once we have fixed our solution, we can run these 10000 cases again looking for new bugs. The moment all the outputs are the same we would have a stronger belief about the correctness of our algorithm after passing that many tests.

This is the complete version of the implementation, in case you want to see the whole picture:

import random

def no_brainer(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

def solution(a, x):
    l = 0
    r = len(a) - 1
    while l <= r:
        m = (l + r) // 2
        if a[m] == x:
            return m
        elif a[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1

def generate_input():
    n = random.randint(1, 10)
    a = [random.randint(1, 10) for _ in range(n)]
    a.sort()
    x = a[random.randint(0, n - 1)]
    return a, x

def debug():
    test_cases = 10000
    for _ in range(test_cases):
        a, x = generate_input()
        no_brainer_output = no_brainer(a, x)
        solution_output = solution(a, x)
        if no_brainer_output != solution_output:
            print("Test Case:")
            print(a, x)
            print("Solution Output:", solution_output)
            print("No-Brainer Output:", no_brainer_output)
            exit()
    print("All test cases passed succesfully")

if __name__ == "__main__":
    debug()

After we run this script, we will get a result like the following:

In this case, the input consists of the array [4, 4, 4, 5, 10] and the number 4. This means we need to find the first index where the number 4 appears in the array.

As you can see, our solution using binary search returns the value 2, which is an index where the number 4 is present, but it is not the first one. On the other hand, our no-brainer solution returns the value 0, which is the first index whose value is equal to 4.

And, just like that, in a matter of seconds, we have generated a test case that shows that our solution fails. Now we can proceed to analyze it thoroughly and fix our code.

Note: As an exercise for you, I will skip the part where I explain what is wrong with the implementation above. If you realize what the issue is, let me know so we can start a discussion and keep learning as a community.

A possible fix to our implementation is the following:

def solution(a, x):
    l = 0
    r = len(a) - 1
    pos = -1
    while l <= r:
        m = (l + r) // 2
        if a[m] >= x:
            pos = m
            r = m - 1
        else:
            l = m + 1

    return pos

Let's see that when we run the script, now that we have modified our solution, we get the gratifying result:

Which will give us the courage to submit our implementation again.

Conclusion

In this article, we have seen an effective approach for generating test cases to stress-test our solutions. We have automated the process of crafting each case and checking for correctness, making it less time-consuming to find bugs in the code.

The approach seen here is one of the most effective ones used in Competitive Programming, but it sure can be extrapolated to use cases in "real world" software development.

It also shows how you can take advantage of the computing power present in the devices we use every day to speed up the debugging process and deliver features that have been tested thoroughly while still being able to beat your deadlines.

During my Competitive Programming journey through college, I implemented this type of debugging not only in individual competitions but in team contests as well. As a result of that, my teammates and I gained speed when competing and were able to achieve amazing results.

We all agree that this method of debugging played an important role in our achievements as competitive programmers. We went all the way from programming enthusiasts to ICPC World Finalists by making sure that we were the most productive we could be during the limited time we had in every contest. And I assure you: there is no contest without debugging.

I recommend you give it a try. Let me know your results!

👋 Hello, I'm Alberto, Software Developer at doWhile, Competitive Programmer, Teacher, and Fitness Enthusiast.

🧡 If you liked this article, consider sharing it.

🔗 All links | Twitter | LinkedIn

Now that I have your attention with the post title, let me go in-depth on my views of competitive programming.

What is competitive programming?

Competitive programming is a sport. You have to solve a problem with code that is fast, consumes the minimum amount of memory, and is often practically unreadable.

It is super popular among university students and those trying to get into big companies, primarily because it helps them get placed in those companies. Unfortunately, millions of people are hired because of some knowledge they would never use in their jobs.

The system is broken

Here's another example from Hen-Wen:

There are tons of examples out there I can think of.

The creator of homebrew – a package manager used by almost everyone running macOS? Rejected. The creator of WhatsApp? Rejected by Facebook and Twitter.

So what is happening here? Are these people not qualified enough to work in these MNCs?

No, the answer is that these guys can develop useful tools and write great software with top-notch code quality, but they probably fail to (re)invent an algorithm to invert a binary tree in a 30-minute time limit.

Some of the best code written ever was not written in 30 minutes. Some of the best algorithms written in Linux kernel used even today were not written in 30 minutes by Linus. Some of the best UIs like Stripe was not designed in 30 minutes.

So how can some random HR person in some random company decide your worth in 30 minutes?

This is how companies judge your "feasibility" – by seeing if you can solve a toy problem completely unrelated to any work you might have done in the past, or you might do in the future.

Can this be fixed?

I don't know. I can complain and yell all I want, but I honestly don't know how companies can evaluate a person applying for a job quickly and correctly.

If you want quick, you'll lose a lot of good candidates like the ones mentioned above. If you want to lose no good candidates, the interview might last for way too long – much longer than the company can afford.

Competitive Programming !== Real World Programming

Interviews for companies are more of an exam where you have to memorize and learn about things you won't use after getting the job.

You think you might need to learn Dijkstra's algorithm to work on Google Maps, but seriously, do you think Google is going to hand over one of their core products to someone new to the company? Do you think you'll get no help whatsoever from your peers?

You will probably be working on the interface for the product, or distributed systems rather than working on one of Google's cor algorithms. This means all of your "competitive programming" knowledge is of no use.

You'll find almost no use for competitive programming in the real world. No algorithm running on production Microsoft servers is written in unreadable code, with short and meaningless variable names, undocumented and optimized only for speed and not readability or maintenance.

Minifying and performance improvement comes later on, with automated tools a lot of the time. Chances are, if you are a competitive coder, you developed the bad habit of writing ugly code.

Anyone can write code for machines. The question is, can you write code for humans?

But there's hope

Sitting for interviews like this and hoping you can solve a toy question you prepared for 3-5 months learning just DSA and competitive programming is one way.

There's another way – it'll work with fewer companies and people, but you'll enjoy it, and learn a lot of real-world things along the way. You'll also be more useful than those people who only learn "competitive coding" for the sake of it.

Build something. Anything. And then build more on top of that. Have a strong portfolio. Have a complete skillset which is useful for companies. Have mastery with a tech stack – own it. Have projects, blogs, experience to show that you are what is in your resume. Build connections, network with people, ask for their recommendations.

In a lot of places, competitive coding is not the only way to clear an interview – there are all kinds of people running all kinds of companies. A person who agrees with my PoV, and is running a company would not be hiring people on their "competitive" knowledge alone.

Your work can take you places you couldn't imagine. The easiest way is to always follow the crowd. But nothing good comes easy, at least if you're ambitious enough. Mixing just the right amount of ambition and courage can do wonders.

The world needs great programmers to progress, to move humanity forward, not people who can get hired.

Don't confuse DSA with Competitive Programming

I did not want to write this section initially, but I knew too many people will confuse this. DSA - Data Structures and Algorithms is something different. Heap, Maps, Arrays, Vectors, Linked Lists, .etc, all these are super helpful in real-world programming too.

The fun part is you can develop that understanding with experience, too. I never explicitly learned about "heap" using some big 50-hour DSA course. And if you are learning to program, you don't need a very very deep understanding of that too.

DSA in depth is required when you want to learn computer science, not programming. Understand the difference, computer science is the theory – programming is practical.

Be aware of things that exist, algorithms that exist, and data structures that exist. You don't need to learn or memorize them all. It sounds insanely stupid to me to memorize or learn something which is rarely used when I can get it with a bit of help from colleagues and the internet.

My story

I'm not a competitive coder, probably the only CS undergrad in my university who never touched competitive coding in college.

Why? Because I tried it 4-5 years ago and hated it. Why? Because I could see myself spending 3-5 hours of my day, every day, solving problems that got me nothing. I knew a thing or two more about approaching the next question, but was that enough to make an impact? Was that enough to stand out from the crowd?

What good was I doing? It felt like I was wasting time on questions that were already solved. It might be different for everyone, but I am happy when I see other people using the things I programmed (I started as a web developer by then).

I just couldn't stand wasting my time learning something I would never use in the real world. I used to participate in Google's Code Jam and Facebook's Hacker Cup back in the day. But soon I got bored and frustrated, for the lack of a better word, and never really got back to it. Getting a job or internship didn't concern me, it never did.

I sat for Google interviews once on campus. They had a resume shortlisting round as the first round, unlike all the other companies where the first round was, wait for it, competitive coding round. Well there went the 7 years of web development and systems experience down the drain.

Anyway, for Google, I was the only person to be shortlisted with a GPA of 7.5 (the highest GPA is 10 in India). The rest of the 10-15 people were above 8.5 or 9.

I didn't get past the competitive round again, but that taught me that it was possible to break into the first round of a company like Google with just your resume. Therefore, it's important to work on that.

Conclusion

TL;DR – You don't need to learn competitive coding to succeed in life. You need to learn something you like so much that you master it, and you're unbeatable in your field. That's all.

Have views and opinions? Connect with me on Twitter and Instagram and let's talk!

If you’re a competitive programmer like I am, one of the best feelings in the world is seeing your program getting accepted on first try on one of the most famous programming platforms, CodeChef.

I was an avid competitive programmer during undergrad, and then lost touch with it when working as a developer @Hike. However, I recently started out into this adventurous world of programming again, all thanks to my friend Divya Godayal.

The CodeChef May 2018 Long Challenge ended about an hour ago, and I decided to write this article as a post describing one of the questions in the competition.

Without wasting any more time, let’s get to it.

Unravelling the Problem Statement

Let’s look at some examples to better understand what the problem statement is asking for.

Consider the following number sequence.

4 3 1 2

Now the question asks us to perform a certain operation (possibly 0 times, leaving the sequence unchanged). We can negate a certain subsequence of numbers and get a new sequence.

-4 3 1 24 -3 1 -24 3 -1 24 3 1 -2-4 -3 1 2 etc.

The question says that the resulting sequence should satisfy the following constraint:

The sum of elements of any substring with length greater than 1 is strictly positive.

Clearly, the following sequences are not valid:

-4 3 1 24 -3 1 -2 4 3 1 -2 -4 -3 1 2 -4 -3 -1 -24 3 -1 -2

We only have 2 valid subsequences that can be obtained by performing the operation mentioned above. Note: we haven’t written down all the possible subsequences. That would be 2^n, that is 16 in this case, because for every number we have two options. Either to negate it, or not.

So the two valid sequences are:

4 3 1 2

and

4 3 -1 2

The original sequence would always be one of the valid sequences as all the numbers in it are positive.

Now the question asks us to find the sequence with the minimum sum. So for the example we have considered, the sequence required would be 4 3 -1 2 .

Would Greedy Work?

A greedy approach in this question would be that if it is possible to negate a number while satisfying the given constraints, then we should negate that number. This approach however, would not always give the right results. Consider the following example.

4 1 3 2

Here, it is possible to have these three valid sets of numbers:

4 1 3 2           4 -1 3 2           4 1 3 -2

Clearly, both the numbers 2 and 1 can be negated. But not both of them at the same time. If we negate a number greedily — that is, if a number can be negated, then we negate it — then it is possible that we might end up negating the number 1. Then you won’t be able to negate the number 2. This would give us a suboptimal solution.

So this Greedy approach would not work here. We have to “try out a specific choice of whether to negate or not for a number and see what choice gives us the optimal solution”.

This smells like Dynamic Programming.

Good ol’ Dynamic Programming

One of the most interesting algorithmic techniques out there, and possibly one of the most dreaded, is dynamic programming. This is the technique we are going to use to solve this particular problem.

Two of the most important steps in any dynamic programming problem are:

1. Identifying the recurrent relation.
2. Figuring out what to memoize. (not memoRize :P)

The DP-based approach here is divided into two basic parts.

• One is the main recursion that we use to find out the minimum sum of the final set. Note, the dynamic programming is not directly used to obtain the final set, just the sum of the final set of numbers. So our dynamic programming approach would correctly find out the sum for the example given above as 8. 4 + 3 + (-1) + 2 = 8 .
• What we actually need is the final modified set of numbers where some (possibly none) of the numbers are negated. We use the concept of a parent pointer and backtracking to find out the actual set of numbers.

Let’s move onto our recursion relation for our dynamic programming approach.

Before describing the recursive relation an important observation to make here is that if a number has been negated, then any adjacent number to it can not be negative. That is, two adjacent numbers cannot be negative as that would give a substring of length 2 whose sum is negative, and that is not allowed according to the question.

For the recurrence relation, we need two variables. One is the index number of where we are in the array, and one is a boolean value that tells us if the previous number (one left to the previous number) is negated or not. So if the current index is i, then the boolean value would tell us if the number at i — 2 was negated or not. You will know the importance of this boolean variable in the next paragraph.

We need to know in O(1) if a number can be negated or not. Since we are following a recursion with memoization-based solution, whenever we are at an index i in the recursion, we are sure that the numbers to the right (i+ 1 onwards) have not been processed up to this point. This means that all of them are still positive.

The choice of whether the number at index i can be negated is dependent upon the right hand side (if there is one) and the left hand side (if there is one). The right hand side is easy. All we need to check is if

number[i] < number[i + 1]

because if this is not true, then adding these two would give a negative value for the substring [i, i + 1] thus making it an invalid operation.

Now comes the tricky part. We need to see if negating the number at i will cause a substring of negative sum to the left or not. When we reach the index i in our recursion, we have already processed the numbers before it, and some might have been negated as well.

So say we have this set of numbers 4 1 2 1 and we had negated the first 1 and we are now processing the last number ( 1 ).

4 -1 2 [1]

The last number in square brackets is the one we are processing right now. As far as the right hand side is concerned, since there is none, we can negate it. We need to check if negating this 1 at index 3 (0 based indexing) would cause any substring to the left of ≤ 0 sum. As you can see, it will produce such a substring.

-1 2 -1

This substring would have a 0 sum, and that is invalid according to the question. After negating a subsequence of numbers, the substrings in the final set should have a sum which is strictly positive. All the substrings of length > 1.

We cannot apply the following approach here directly:

if number[i] < number[i - 1], then it is good to go on negation.

because, although 1 <; 2 , if we negate that last 1 as well we will have an invalid set of numbers as seen above. So this simple approach or check won’t work here.

Here comes the boolean variable which tells us if, given an index i, the number at i — 2 was negated or not. Consider the two scenarios.

• Yes, the number at index i — 2 was negated like in the example just showcased. In that case, negation of the number at i — 2 would have a capacity reduction for number at i — 1. In the example 4 1 2 1 , negating the 1 at index 1(0 based indexing) would reduce the capacity of the number 2 (at index 2) by 1. We refer to remaining values of numbers as capacities here. We need to consider this reduced capacity when performing the check to see if a number can be negated or not.

number[i] < reducedCapacityOfNumberAt(i - 1)

• In case the number at index i — 2 wasn’t negated, the number at i — 1 is at it’s full capacity. The simple check

number[i] < number[i - 1]

would be enough to see if we can negate the number at index i .

Let’s look at the code for the recursion containing all the ideas discussed above.

That’s all nice and dandy. But, this is just recursion, and the heading says dynamic programming. That means there would be overlapping subproblems. Let us look at the recursion tree to see if there are any.

As you can see, there are overlapping subproblems in the recursion tree. That is why we can use memoization.

The memoization is as simple as:

""" This comes at the top. We check if the state represented by the tuple of the index and the boolean variable is already cached """

if(memo[i][is_prev_negated] != INF) {    return memo[i][is_prev_negated];}

...... CODE

# Cache the minimum sum from this index onwards.memo[i][is_prev_negated] = min(pos, neg);

# The parent pointer is used for finding out the final set of #sparent[i][is_prev_negated] = min(pos, neg) == pos ? 1 : -1;

As pointed out earlier, this recursive approach would return the minimum sum of the set of numbers possible after making the valid set of modifications to them.

The question, however, asks us to actually print the final set of numbers that gives the minimum sum after making such modifications. For that, we need to use a parent pointer that would tell us at every index and boolean variable is_prev_negated ’s value as to what optimal action was taken.

parent[i][is_prev_negated] = min(pos, neg) == pos ? 1 : -1;

So we simply store 1 or -1 depending upon if negating the number at index i (if possible!) gave us the minimum sum or if choosing to ignore it gave the minimum sum.

Backtracking

Now comes the part where we backtrack to find the solution to our original problem. Note that the decision for the very first number is what propagates the recursion further. If the first number was negated, the second number would be positive and the third number’s decision can be found using parent[2][true]. Similarly, if the first number wasn’t negated, then we move onto the second number and it’s decision can be found using parent[1][false] and so on. Let’s look at the code.

A Better Approach

If you take a look at the space complexity of the solution suggested, you will see that it’s a 2 dimensional dynamic programming solution because the state of the recursion is represented by two variables i.e. the index i representing what number of the array we are considering and then the boolean variable is_prev_negated . So the space complexity and the time complexity would be O(n*2) which is essentially O(n).

However, there is a slightly better approach as well to solving this problem as suggested by Divya Godayal. This problem can even be solved by 1 dimensional dynamic programming based solution.

Essentially, the boolean variable is_prev_negated is helping us to decide if we can negate a given number at index i or not as far as the left hand side of the array is concerned i.e. all the numbers from 0 .. i-1 because the right hand side is anyways safe as all the numbers on that side are positive (as the recursion hasn’t reached them yet). So for the right hand side we simply checked the number at i+1 but for the left hand side of index i we had to make use of the boolean variable is_prev_negated .

It turns out, that we can simply skip this boolean variable altogether and simply look ahead to decide if a number can be negated or not. Which simply means if you are at an index i, you check if that element along with the element at i+2 have the capacity to swallow the element at i+1 i.e.

numbers[i] + numbers[i+2] >= numbers[i+1  (SWALLOW)

If there is a such a possibility, then we directly jump to i+3if we negate element at i because element at i+1 and i+2 both can’t be negative in such a scenario.

In case the swallow condition is not satisfied and we end up negating the number at index i , then we would jump to index i+2 because in any case, two consecutive numbers cannot be negated. So if the number at i was negated, then the number at i+1 has to be positive. The swallow check is to see if the number at i+2 would definitely have to be positive or if we can exercise the choice of whether to negate or not there.

Have a look at the code for a better understanding.

Hence, just a single variable i.e. the index is used to define the state of the recursion. So the time and space complexity, both got reduced to half of what they were in the previous solution.

I hope you were able to grasp the working of the algorithm described above and how the dynamic programming technique fits into this problem. I think it’s an interesting problem, because you not only have to use dynamic programming but also the concept of parent pointer to retrace the steps through the optimal solution and get the answer required in the question.