These might be trivial for most users, but if you are like me, who sometimes confuse on when to use mid+1, rig-1 etc, here is a reliable method after considering many different implementation variants.

To find the index of the rightmost $$$1$$$ in a monotonically decreasing function, for example $$$a=[1,1,1,1,0,0,0]$$$

Define check(i) to return true when $$$a[i]=1$$$, false otherwise.

int lef = 0, rig = n-1;
int ans = -1;
while(lef <= rig) {
	int mid=(lef + rig)/2;
	if(check(mid)){
		lef = mid+1;
		ans = mid;
	} else {
		rig = mid-1;
	}
}

The answer is the last valid mid. Make sure that lef and rig are in bounds. If $$$a$$$ is available or can be computed efficiently, you can instead do

F0R(i,n)a[i]*=-1;
int ans = upper_bound(a,a+n,-1)-a-1; // get index of rightmost 1

Careful if $$$1$$$ doesn't exist in $$$a$$$.

To find the index of the leftmost $$$1$$$ in a monotonically increasing function, for example $$$a=[0,0,0,0,1,1,1]$$$

In a similar way,

int lef = 0, rig = n-1;
int ans = -1;
while(lef <= rig) {
	int mid=(lef + rig + 1)/2;
	if(check(mid)){
		rig = mid-1;
		ans = mid;
	} else {
		lef = mid+1;
	}
}

Notice the ceiling in the definition of mid. This is to handle rig-lef equals one. If $$$a$$$ is available or can be computed efficiently, you can instead do

int ans = lower_bound(a,a+n,1)-a; // get index of leftmost 1

Careful if $$$1$$$ doesn't exist in $$$a$$$.

You can then solve most problems by implementing your own definition of check(). Time complexity is the time complexity of your check() function times $$$\log n$$$. Thanks to marvenlee for inspiring this blog.

Usage examples:

• Recent problem 1486C2 107949041

• 367C 107949113

• 604B 107949183

• 237C 107949260

Indeed, there are many other ways of implementing binary search, check out pllk's blog.

UPD Applied improvements thanks to sergei_popov

Sometimes, you are asked to calculate the combination or permutation modulo a number, for example $$$^nC_k \mod p$$$. Here I want to write about a complete method to solve such problems with a good time complexity because it took me a lot of googling and asking to finally have the complete approach. I hope this blog can help other users and save their time when they solve combinatorics problem in Codeforces.

Example Problem

Find the value of $$$^nC_k$$$, ($$$1 \leq n,k \leq 10^6$$$). As this number can be rather large, print the answer modulo $$$p$$$. ($$$p = 1000000007 = 10^9 + 7$$$)

Combination (binomial coefficients)

$$$^nC_k$$$ means how many ways you can choose $$$k$$$ items from an array of $$$n$$$ items, also denoted as $$$\binom{n}{k}$$$. This is also known as binomial coefficients. The formula for combination is

Sometimes, the denominator $$$k!(n-k)!$$$ is very large, but we can't modulo it since modulo operations can't be done independently on the denominator. $$$\frac{n!}{k!(n-k)!} \mod p \neq \frac{n! \mod p}{k!(n-k)! \mod p}$$$. Now I will introduce the modular multiplicative inverse to solve this problem.

Modular multiplicative inverse

The modular multiplicative inverse $$$x$$$ of $$$a$$$ modulo $$$p$$$ is defined as

Here, I will replace $$$x$$$ with $$$\text{inv}(a)$$$, so we have

Getting back to the formula for combination, we can rearrange so that

Here, we can use $$$\text{inv}(a)$$$ as follows

Now we can distribute the modulo to each of the terms by the distributive properties of modulo

Now I will discuss on how to calculate $$$\text{inv}(a)$$$

Fermat's Little Theorem

You can easily remember this theorem. Let $$$a$$$ be an integer and $$$p$$$ be a prime number,

It is helpful to know that the $$$p$$$ in the problem ($$$10^9 + 7$$$) is indeed a prime number! We can rearrange the equation to get

Looking back at our equation for $$$\text{inv}(a)$$$, both equations equate to 1, so we can equate them as

We can rearrange the equation to get

We now have a direct formula for $$$\text{inv}(a)$$$. However, we cannot use the pow() function to calculate $$$a^{p-2}$$$ because $$$a$$$ and $$$p$$$ is a large number (Remember $$$1 \leq n,k \leq 10^6$$$) ($$$p = 10^9 + 7$$$). Fortunately, we can solve this using modular exponentiation.

Modular Exponentiation

To prevent integer overflow, we can carry out modulo operations during the evaluation of our new power function. But instead of using a while loop to calculate $$$a^{p-2}$$$ in $$$O(p)$$$, we can use a special trick called exponentiation by squaring. Note that if $$$b$$$ is an even number

Every time we calculate $$$a^2$$$, we reduce the exponent by a factor of 2. We can do this repeatedly until the exponent becomes zero where we stop the loop. This will give us a time complexity of $$$O(\log p)$$$ to calculate $$$a^{p-2}$$$ because we halve the exponent in each step. For the case when $$$b$$$ is odd, we can use the property

We then store the trailing $$$a$$$ into a variable. Then $$$b-1$$$ is even and we can proceed as previously stated. We can repeatedly apply these two equations to calculate $$$a^{p-2}$$$. Here I will show you the implementation of this modified powmod() function to include modulo operations. ll is defined as long long

ll powmod(ll a, ll b, ll p){
    a %= p;
    if (a == 0) return 0;
    ll product = 1;
    while(b > 0){
        if (b&1){    // you can also use b % 2 == 1
            product *= a;
            product %= p;
            --b;
        }
        a *= a;
        a %= p;
        b /= 2;    // you can also use b >> 1
    }
    return product;
}

Then we can finally implement the $$$\text{inv}(a)$$$ function simply as

ll inv(ll a, ll p){
    return powmod(a, p-2, p);
}

Then, finally, we can implement $$$^nC_k$$$ as

ll nCk(ll n, ll k, ll p){
    return ((fact[n] * inv(fact[k], p) % p) * inv(fact[n-k], p)) % p;
}

We used the dp-approach for factorial where the factorial from 1 to n is pre-computed and stored in an array fact[].

Time complexity

• Pre-computation of factorial: $$$O(n)$$$
• Calculation of $$$^nC_k$$$, which is dominated by modular exponentiation powmod: $$$O(\log p)$$$
• Total: $$$O(n + \log p)$$$

Reference

• Fermat's Little Theorem — wiki
• Modular Multiplicative Inverse — wiki
• Modular Multiplicative Inverse — cp-algorithm

Problems for you

• 300C - Beautiful Numbers (Example solution: 83862274)
• 717A - Festival Organization

Please comment below if you know similar problems.

I hope this blog will help you in your competitive programming journey.

Stay safe and thank you for reading.

Sometimes we need to compute the division of an integer rounded up (ie by ceiling, not by rounding those with remainder $$$r \geq 0.5$$$). For example, $$$\lceil 3/2 \rceil = \lceil 1.5 \rceil = 2$$$ and $$$\lceil 13/3 \rceil = \lceil 4.333 \rceil = 5$$$.

TLDR, use (a+b-1) / b or other approaches below.

Typical approach

If we want to do this in C++, we can call the ceil() function, but with caution. For the example above,

int a = 3;
int b = 2;
cout << ceil(a/b) << endl;
>>>> 1

Note that it prints out 1, not 2! This is because a and b are int data types, so that their quotient a/b is in int and the decimal values are discarded (floored). a/b = 1 so ceil(a/b) = ceil(1) = 1. We can simply overcome this by casting the double data type so that the decimal values are kept during intermediate calculations.

cout << ceil( (double) a / (double) b) << endl;
>>>> 2

But wait! Some people think that using double is a risky approach because floating-point numbers cannot be reliably represented by computer, especially when you do more complex calculations than the simple a/b example. You can read more on this Stack Exchange question. Alternatively, there are many ways to use int only and still get the correct results.

Approach 1

Credit: zwliew, khoya_musafir

This is the most popular approach.

int ceil2(int a, int b) {
    return (a + b - 1) / b;
}

Approach 2

Credit: Flower08, BT21tata

(a - 1)/b + 1 is used instead of (a + b - 1) / b to prevent integer overflow when a and b is large. However, it does not work if $$$a = 0$$$, so we add an if statement.

int ceil2(int a, int b) {
    if (a == 0) return 0;
    return (a - 1)/b + 1;
}

Approach 3

Credit: KB_05

int ceil2(int a, int b) {
    int c=a/b;
    if(a % b ! =0) c++;
    return c;
}

Approach 4

int ceil2(int a, int b){
    int c = a / b;
    if (c * b < a) c++;
    return c;
}

I hope that you find this useful. Feel free to add more approaches in the comments.

Thank you and stay safe.

I have been using endl for competitive programming until now. For 350C - Бомбы, both 79359924 and 79360060 have the same time complexity of $$$O(n \log{n})$$$, but the first gets TLE while the second gets AC. The reason is that the AC solution uses \n instead of endl. The difference in performance is significant because this problem requires $$$6\times 10^5+1$$$ lines of output at most!

Conclusion: Use endl only if it is a query problem.

Hi all. Recently I have been reading this fantastic book by pllk. There is a whole chapter inside dedicated to range queries. As there aren't any range queries tags in Codeforces, I would like to ask if anyone know any range query problems in Codeforces, or any existing tags that imply range queries. (Sum, minimum, or maximum queries etc across a range)

Also, please comment any range query problems below :)