from typing import List


def change_partition(partition: List[tuple], t: int) -> List[tuple]:
    """
    Used in algorithm 2.
    Create a partition from original partition where each 2 ^ t pieces are united.
    :param partition: The original partition.
    :param t: Defines the size of the new partition.
    :return: A partition with pieces with 2 ^ t size.

    >>> change_partition([(0.0, 1.0), (1.0, 2.0)], 1)
    [(0.0, 2.0)]

    """

    ret = []
    # Go over all the original partitions with 2^t jumps
    for start in range(0, len(partition) - 2 ** t + 1, 2 ** t):
        end = start + 2 ** t - 1
        # Add the new joined partition to the list
        ret.append((partition[start][0], partition[end][1]))
    return ret