FPC Programming Questions

Last fall, I joined the FSU ACM Question Writers team for our semi-annual programming contest. I was chosen to write two questions for the COP4530 Data Structures II class at FSU.

The two problems I chose to write are a sliding window problem, and a DFS tree problem.

Scoring Drives

This problem was intended to be the easier of the two, so I stuck to basics and used a straightforward sliding window pattern, similar to one you might see on LeetCode.

Here is the writeup:

Problem:

On a bright, beautiful, sunny 12PM football game in Tallahassee, the Seminoles offense runs a long series of plays. You have collected the integer sequence that represents drive-by-drive net yardage adjustments. A positive number means the drive gained yards on net. A negative number means the drive lost yards on net due to sacks, penalities, or turnovers. Zero means the drive broke even.

A scoring window is defined as any contiguous block of drives. You are tasked with counting how many scoring windows give total net yardage exactly equal to a target value S.

In other words, given an array $d[1, …, n]$ of integers, count the number of pairs $(l, r)$ with $1 ≤ l ≤ r ≤ n$ such that $d[l] + d[l+1] + … + d[r] = S$.

Input:

One line with two integers: $n, S$

$n$ is the number of drives recorded

$S$ is the target net yardage

One line with n integers: $d1\space d2\space …\space dn$

$d$ is the net yardage adjustment for the ith drive

Output:

The count of contiguous drive windows whose total is exactly S.

Sample Run:

Input
7 5 2 3 -1 2 3 -2 -1

Output
3

Here is the intended solution for the problem (in Python):

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    iterator = iter(data)
    n = next(iterator)
    S = next(iterator)

    pref = 0
    ans = 0
    freq = {0: 1}

    for _ in range(n):
        x = next(iterator)
        pref += x
        needed = pref - S
        ans += freq.get(needed, 0)
        freq[pref] = freq.get(pref, 0) + 1

    print(ans)

if __name__ == "__main__":
    main()

The Great Family Tree Feast

This is a binary-tree path-sum counting problem: given node values and child links plus a root ID and target S, count all downward continuous paths (any start node to any descendant) whose values sum to S.

Here is the writeup:

Problem:

It’s Thanksgiving at the Binary Family reunion, and the family tree is quite literal this year. Each family member has brought a dish with a certain “deliciousness value” (which can be positive, negative, or zero).

The tradition states that any group of family member sitting along a continous path at a distinctly tree shaped table can share a feast together. However, there is a catch: the combined seliciousness of their dishes must equal exactly $S$ (or the satisfaction score) for the feast to be considered successful.

Your job is to count how many different successful feasts can happen at this year’s reunion

Input:

The first line $n$ is the number of family members in the tree

The next $n$ lines for each family member are as follows:

• $v[i]$: the deliciousness value
• $l[i]$: the ID of the family member seated to their left below them (-1 if no one)
• $r[i]$: the ID of the family member seated to their right below them (-1 if no one)

Next line - $r$: the ID of the patriarch/matriarch of the family

Last line - $S$: the target satisfaction score

Output:

A single integer: the number of valid feast paths with deliciousness sum equal to s.

Sample Run:

| Input | | :—————————————————————————————————————————-: | | 9
3 2 3
-2 4 5
4 -1 6
2 -1 -1
1 -1 -1
-1 7 8
3 -1 -1
1 -1 9
2 -1 -1
1
4 |

Output
2

Here is the intended solution for the problem (in Python):

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    n = int(next(it))
    val = [0] * (n + 1)
    left = [0] * (n + 1)
    right = [0] * (n + 1)
    for i in range(1 , n + 1):
        val[i] = int(next(it))
        left[i] = int(next(it))
        right[i] = int(next(it))
    r = int(next(it))
    s = int(next(it))

    freq = {0:1}
    answer = 0

    def dfs(u, cur):
        nonlocal answer
        if u == -1:
            return
        cur += val[u]
        needed = cur - s
        answer += freq.get(needed, 0)
        freq[cur] = freq.get(cur, 0) + 1
        if left[u] != -1:
            dfs(left[u], cur)
        if right[u] != -1:
            dfs(right[u], cur)
        cnt = freq[cur] - 1
        if cnt == 0:
            del freq[cur]
        else:
            freq[cur] = cnt
    
    dfs(r, 0)
    print(answer)

if __name__ == "__main__":
    main()

Takeaways:

I had a really fun time writing these problems. I wanted them to be approachable but still unique, and I think I hit that goal. I will definitely continue to write problems for the contest in the future.