What Does This Program Do? - Arrays

Contest 3 adds arrays to WDTPD problems. You’ll trace programs that create, read, modify, and search arrays. The core skill is tracking array contents alongside loop variables.

ACSL array syntax

Arrays in ACSL pseudocode use parentheses and are zero-indexed (first element is at index 0).

A(0) = 5
A(1) = 3
A(2) = 8

Or initialized all at once:

A(0)=5: A(1)=3: A(2)=8: A(3)=1: A(4)=4

Accessing: $A (2)$ gives the value at index 2 (which is $8$ in the example above).

Note: ACSL uses parentheses for arrays, like $A (i)$ . Some problems and textbooks use brackets $A [i]$ instead - they mean the same thing. In this lesson we use both notations interchangeably.

Length: Some problems use $len (A)$ to get the number of elements.

Try it: trace an array program

Watch how the array A is accessed and modified using index variables.

Code

1A(0)=5: A(1)=3: A(2)=8: A(3)=12sum = 03FOR i = 0 TO 3 STEP 14    sum = sum + A(i)5NEXT6OUTPUT: sum

Variables

Name	Value
A(0)	5
A(1)	3
A(2)	8
A(3)	1

Step 1 of 11

The array table method

When tracing array programs, draw a table with one column per array index and update it as the program runs.

Example:

A = [4, 7, 2, 9, 1]
FOR i = 0 TO 3
    IF A[i] > A[i+1] THEN
        temp = A[i]
        A[i] = A[i+1]
        A[i+1] = temp
    END IF
NEXT
OUTPUT: A

i	Compare	Swap?	Array after
-	-	-	$[4, 7, 2, 9, 1]$
$0$	$A [0] = 4 > A [1] = 7$ ? No	No	$[4, 7, 2, 9, 1]$
$1$	$A [1] = 7 > A [2] = 2$ ? Yes	Yes	$[4, 2, 7, 9, 1]$
$2$	$A [2] = 7 > A [3] = 9$ ? No	No	$[4, 2, 7, 9, 1]$
$3$	$A [3] = 9 > A [4] = 1$ ? Yes	Yes	$[4, 2, 7, 1, 9]$

Answer: 4 2 7 1 9

Recognize the pattern? This is one pass of bubble sort - it moves the largest element to the end.

Common array patterns in ACSL

Pattern 1: Summing elements

A = [3, 1, 4, 1, 5]
s = 0
FOR i = 0 TO 4
    s = s + A[i]
NEXT
OUTPUT: s

Answer: $14$ (just add them all up)

Pattern 2: Counting elements meeting a condition

A = [3, 1, 4, 1, 5, 9, 2, 6]
count = 0
FOR i = 0 TO 7
    IF A[i] > 3 THEN
        count = count + 1
    END IF
NEXT
OUTPUT: count

Answer: $4$ (the elements $4$ , $5$ , $9$ , $6$ are $> 3$ )

Pattern 3: Finding max/min

A = [3, 7, 1, 9, 4]
max = A[0]
pos = 0
FOR i = 1 TO 4
    IF A[i] > max THEN
        max = A[i]
        pos = i
    END IF
NEXT
OUTPUT: max, pos

Answer: $9, 3$ (maximum is $9$ at index $3$ )

Pattern 4: Reversing an array

A = [1, 2, 3, 4, 5]
FOR i = 0 TO 1
    temp = A[i]
    A[i] = A[4 - i]
    A[4 - i] = temp
NEXT
OUTPUT: A

i	Swap	Array
$0$	swap $A [0]$ and $A [4]$	$[5, 2, 3, 4, 1]$
$1$	swap $A [1]$ and $A [3]$	$[5, 4, 3, 2, 1]$

Answer: 5 4 3 2 1

Note: the loop only goes to index 1 (halfway). Going further would swap them back.

Pattern 5: Building a new array from an existing one

A = [2, 0, 1, 4, 3]
B = [0, 0, 0, 0, 0]
FOR i = 0 TO 4
    B[A[i]] = i
NEXT
OUTPUT: B

This creates an inverse permutation - a reverse lookup table:

i	A[i]	Assignment
$0$	$2$	$B [2] = 0$
$1$	$0$	$B [0] = 1$
$2$	$1$	$B [1] = 2$
$3$	$4$	$B [4] = 3$
$4$	$3$	$B [3] = 4$

Answer: 1 2 0 4 3

2D arrays

Some problems use 2D arrays (grids/matrices). Access syntax: $A [row] [col]$ or $A [row, col]$ .

Example:

A = [[1, 2, 3],
     [4, 5, 6],
     [7, 8, 9]]

s = 0
FOR i = 0 TO 2
    s = s + A[i][i]
NEXT
OUTPUT: s

This sums the diagonal: $A [0] [0] + A [1] [1] + A [2] [2] = 1 + 5 + 9 = 15$

Array index arithmetic

ACSL loves expressions as array indices. Trace carefully.

Example: What does $A [A [i]]$ mean?

If A = [3, 0, 1, 2] and $i = 1$ :

$A [1] = 0$
$A [A [1]] = A [0] = 3$

So $A [A [1]] = 3$ .

This is a common source of errors - always evaluate the inner expression first.

Common mistakes

Off-by-one with zero indexing. An array of $5$ elements has indices $0$ - $4$ , not $1$ - $5$ .
Forgetting the array changes mid-loop. After a swap, subsequent iterations see the new values, not the original.
Nested array access. $A [A [i]]$ - evaluate inside out. Get $A [i]$ first, then use that as the index.
2D array row vs column confusion. $A [row] [col]$ - first index is the row, second is the column.

Contest strategy

Draw the array contents and update them as you trace
For large arrays, only track the elements that change
Recognize common patterns (sort, search, reverse) to predict outputs faster
Watch index arithmetic carefully - this is where most errors happen
Typical time: 90-120 seconds per problem