Contest takeup & Segtree

By Alan, Peter, ChrisT, and Junyi

P1: A Unique List

https://mcpt.ca/problem/duplicate

Remove duplicates from an array of length N (1 ≤ N ≤ 8), with elements a_i (1 ≤ a_i ≤ N).

Solution

• Using a set is the most simple solution
• Keep inserting the values and the set will continue to add them, but will ignore the duplicates
• Then sort the set and print it out
• Other things can be used such as ArrayLists for Java or just arrays in general
• Use an if statement to check for duplicates and then sort
• Or sort array, and check if the current one is the same as the one before it

P2: A Squirrel Problem

https://mcpt.ca/problem/asquirrelproblem

Perform range updates and point queries in sublinear time.

Solution

Binary Indexed Tree on a difference array.

Use the binary indexed tree to speed up updates and sum queries.

Update the difference array to perform a range update.

Perform a sum query on the difference array to do a point query.

Second solution: Lazy segment tree (more advanced)

BIT Code

P3: Component Sum

https://mcpt.ca/problem/components

You are given an empty graph, with two types of queries.

Add an edge between x and y.

Find the sum of sizes of components that have size <= K.

P3: Component Sum

The idea here is to maintain sizes of components using disjoint set union.

When merging two nodes, update the size of the new component to be the sum of the old components.

To query the sum of component sizes <= K, you also must maintain component sizes in a binary indexed tree.

Disjoint-Set Union

Segment Tree Motivation Problem

Given an array A, support two operations:

Increase a value in the array by v.

Find the minimum value in the subarray [L,R]

Explanation

• Segment tree is a binary tree
• Every node represents the value of a segment (for example, the sum or range minimum)
• The children of the segment is the segment split in half
• Every leaf node is a segment of length 1
• The root is the whole array

Update

• Update the current node’s value.
• If the current node is not a leaf, determine which child the index being updated is contained in.
• Recursively call update function on that child.
• Update the current node based on its children’s values.

Query

• Determine whether the range of the current node is completely disjoint from that of the query. If so, return negative infinity (some small value).
• Determine whether the range of the current node is completely contained inside that of the query. If so return the value at this node.
• Recursively call query on both of the children of this node, and return the maximum.

Segment Tree Code

Example

Array = {2 , 5 , 1 , 4 , 9 , 3}

Query minimum in 0-indexed range [1,4]

Example

Example

Example

Example

Example

Minimum = 1