Problem 6 - Robot Writing

We will discuss the solution to Robot Writing from AIO 2025. This is a very difficult problem designed to challenge the very top students in Australia, so do not worry if you are struggling to understand the solution!

Solution

Trying examples by hand is a very useful tool when problem solving. For simplicity, our examples don't include the final movement (the last steps 2 and 3) made by the robot because these do not impact the output of the robot.

Let's start by watching the example below:

One thing that I notice from this example is that the output is weakly increasing, meaning that each new output is greater than or equal to the previous output. This is not a coincidence: the robot swaps tiles if the new tile has a smaller value, meaning that bigger values follow the robot. Specifically, at each step the robot prints the largest value it has seen so far. Therefore the answer is NO if the target sequence S ever decreases.

A second and simpler observation is that the output will only ever contain numbers found on the tiles. If the target sequence S ever has a value which isn't on any tile, we know that the answer is NO.

In every subtask we begin by checking the above two conditions before moving onto the solution for that subtask.

Subtask 1: N, M ≤ 1000 and Ti = i for all i

In this subtask we know that T = [1, 2, 3, 4, ...]. Let's look at another example:

Let's investigate some features of this example:

1 is not outputted in our example. However, if we made examples where 1 was outputted, we would find that 1 can only be outputted once. This is because the robot can only ever move right from tile 1, and after moving right the robot will output 2. The authors of this problem were kind enough to help you with this special case (see sample input 3).

Putting all of this together, our solution to subtask 1 is:

Below is my code in Python and C++ for this subtask. I suggest trying to code the solution yourself and only look at our code after you finish or if you get stuck. Remember to check every NO case! 

import sys

# N is the number of tiles.
N = 0

# T contains the values on the tiles. Note that the list starts from 0, and so
# the values are T[0] to T[N-1].
T = []

# M is the length of target sequence.
M = 0

# S contains the target sequence. Note that the list starts from 0, and so the
# values are S[0] to S[M-1].
S = []

# Read the values of N, S, M, and T.

N = int(input().strip())
T = list(map(int, input().strip().split()))
M = int(input().strip())
S = list(map(int, input().strip().split()))

# This function prints NO and then ends the program
def NO():
    print("NO")
    sys.exit(0)

# Check the first two cases
for i in range(M-1):
    if S[i] > S[i+1]:
        # The target sequence is not non-decreasing
        NO()

for s in S:
    if s not in T:
        # There is a value in the target sequence which does not appear on any tile
        NO()


# Check the three cases from our subtask 1 solution
for i in range(M-1):
    if S[i+1] > S[i]+1:
        # The target sequence 'skips' a value
        NO()

# For the second and third cases we must count how many times each value occurs
num_occurrences = [0 for i in range(N+1)] # num_occurrences[i] will store the number of i's in the target sequence
for s in S:
    num_occurrences[s] += 1

for s in S:
    # Except the largest value, everything must occur an odd number of times
    if s != S[-1] and num_occurrences[s]%2 == 0:
        NO()

if num_occurrences[1] > 1:
    NO() # 1 cannot occur more than once

print("YES")
#include <cstdio>
#include <cstdlib> // for exit()
#include <algorithm> // for std::find

/* N is the number of tiles. */
int N;

/*
 * T contains the values on the tiles. Note that the array starts from 0, and
 * so the values are T[0] to T[N-1].
 */
int T[200005];

/* M is the length of target sequence. */
int M;

/*
 * S contains the target sequence. Note that the array starts from 0, and so
 * the values are S[0] to S[M-1].
 */
int S[200005];

/* num_occurrences[i] will store the number of i's in the target sequence */
int num_occurrences[200005]; 

/* This function prints NO and then ends the program */
int NO() {
    printf("NO\n");
    exit(0);
}

int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &T[i]);
  }
  scanf("%d", &M);
  for (int i = 0; i < M; i++) {
    scanf("%d", &S[i]);
  }

  /* Check the first two cases */
  for (int i = 0; i < M-1; i++) {
    if (S[i] > S[i+1]) {
      // The target sequence is not non-decreasing
      NO();
    }
  }

  for (int i = 0; i < M; i++) {
    int s = S[i];
    if (std::find(T, T+N, s) == T+N) {
      // There is a value in the target sequence which does not appear on any tile
      NO();
    }
  }

  
  /* Check the three cases from our subtask 1 solution */
  for (int i = 0; i < M-1; i++) {
    if (S[i+1] > S[i]+1) {
      // The target sequence 'skips' a value
      NO();
    }
  }

  // For the second and third cases we must count how many times each value occurs
  // num_occurrences[i] will store the number of i's in the target sequence
  for (int i = 0; i < M; i++) {
    int s = S[i];
    num_occurrences[s] += 1;
  }

  for (int i = 0; i < M; i++) {
    int s = S[i];
    // Except the largest value, everything must occur an odd number of times
    if (s != S[M-1] && num_occurrences[s]%2 == 0) {
      NO();
    }
  }

  if (num_occurrences[1] > 1) {
    NO();
  }

  printf("YES\n");
}

Subtasks 2 and 3: The values in T are distinct

Let's try some examples using the above tiles.

  1. S = [5, 6]. We must start on the 3rd tile. No matter how the robot moves it is impossible to output [5, 6]. The answer is NO.
  2. S = [5, 5, 6]. We must start on the 3rd tile. No matter how the robot moves it is impossible to output [5, 5, 6]. The answer is NO.
  3. S = [5, 5, 5, 6]. We must start on the 3rd tile. The robot can move right, right, right to output [5, 5, 5, 6]. The answer is YES.
  4. S = [5, 5, 5, 5, 6]. We must start on the 3rd tile. No matter how the robot moves it is impossible to output [5, 5, 5, 5, 6]. The answer is NO.
  5. S = [5, 5, 5, 5, 5, 6]. We must start on the 3rd tile. The robot can move right, left, right, right, right to output [5, 5, 5, 5, 5, 6]. The answer is YES.
  6. S = [5, 5, 5, 5, 5, 5, 6]. We must start on the 3rd tile. No matter how the robot moves it is impossible to output [5, 5, 5, 5, 5, 5, 6]. The answer is NO.
  7. S = [5, 5, 5, 5, 5, 5, 5, 6]. We must start on the 3rd tile. The robot can move right, left, right, left, right, right, right to output [5, 5, 5, 5, 5, 5, 5, 6]. The answer is YES.
Let's think carefully about these examples: In general, consider any two consecutive different values in the target sequence and let x be the number of occurrences of the smaller value in the target sequence. Let d be the distance between the tiles containing the two values. In the example, d = 3 and x varies from 1 to 7. The answer will be NO if x < d or the parity of x and d are different (the parity is different if one is odd and the other is even).

In the example, we now know that:

Let's look at another example: S = [2, 2, 2, 4]. Here, x ≥ d and the parities are the same yet the answer is still NO because a larger tile (5) is between the 2 and the 4. This is another condition we must check. Similarly, S = [1, 1, 2] and S = [1, 1, 1, 1, 6] are also NO.

One last example for this subtask (I promise!): S = [2, 2, 2, 5]. This does not break any rules so far: x ≥ d, the parities are the same, and there are no larger tiles between 1 and 4. But the answer is still NO! The reason to this is similar to the final case in subtask 1 where we discovered that 1 could not appear more than once in the target sequence. In our example, both tiles on either side of 2 have larger values and so it is impossible to output 2 more than once. (Similarly, if a tile is on the end, then you should check if the single adjacent tile has a larger value.)

Putting this all together, we must check:

Depending on the time complexity of your solution you will either solve subtask 2 or both subtasks 2 and 3.

Below is my code in C++ and Python. As a challenge, prove that my code has a fast enough time complexity to pass subtask 3 (this may surprise you because of the nested for loops!) 

import sys

N = int(input().strip())
T = list(map(int, input().strip().split()))
M = int(input().strip())
S = list(map(int, input().strip().split()))

# This function prints NO and then ends the program
def NO():
  print("NO")
  sys.exit(0)

# Check the first two cases
for i in range(M-1):
  if S[i] > S[i+1]:
    # The target sequence is not non-decreasing
    NO()

# To check the second case we create a helper list called in_T
in_T = [-1 for i in range(1000001)] # in_T[i] will be the tile number of the tile with value i, or -1 if there is no such tile
for i in range(N):
  in_T[T[i]] = i

for s in S:
  if in_T[s] == -1:
    NO()

# Check the cases from our subtask 2 solution
# To help with this, we must count how many times each value occurs
num_occurrences = [0 for i in range(1000001)] # num_occurrences[i] will store the number of i's in the target sequence
for s in S:
  num_occurrences[s] += 1

for i in range(M-1):
  x = num_occurrences[S[i]]
  tile1 = in_T[S[i]]
  tile2 = in_T[S[i+1]]

  if S[i] != S[i+1]:
    d = abs(in_T[S[i]] - in_T[S[i+1]])
    if x < d or x%2 != d%2:
      NO()

    for tile in range(min(tile1, tile2)+1, max(tile1, tile2)):
      if T[tile] > S[i]:
        # there is a larger tile between the two tiles!
        NO()

  # Check if S[i] has larger tiles on both sides
  if tile1 == 0 or T[tile1-1] > T[tile1]:
    # larger on the left

    if tile1 == N-1 or T[tile1+1] > T[tile1]:
      # larger on the right

      if x != 1:
          NO()

print("YES")
#include <cstdio>
#include <cstdlib> // for exit()
#include <cmath> // for abs
#include <algorithm> // for std::min, std::max, and std::fill

int N;
int T[200005];
int M;
int S[200005];

/* num_occurrences[i] will store the number of i's in the target sequence */
const int MAX_VALUE = 1000001;
int num_occurrences[MAX_VALUE];

/* in_T[i] will be the tile number of the tile with value i, or -1 if there is no such tile */
int in_T[MAX_VALUE];

/* This function prints NO and then ends the program */
int NO() {
    printf("NO\n");
    exit(0);
}

int main(void) {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &T[i]);
  }
  scanf("%d", &M);
  for (int i = 0; i < M; i++) {
    scanf("%d", &S[i]);
  }

  /* Check the first two cases */
  for (int i = 0; i < M-1; i++) {
    if (S[i] > S[i+1]) {
      // The target sequence is not non-decreasing
      NO();
    }
  }

  // To check the second case we create a helper list called in_T
  // in_T[i] will be the tile number of the tile with value i, or -1 if there is no such tile
  std::fill(in_T, in_T+MAX_VALUE, -1);
  for (int i = 0; i < N; i++) {
    in_T[T[i]] = i;
  }
  for (int i = 0; i < M; i++) {
    int s = S[i];
    if (in_T[s] == -1) {
      NO();
    }
  }

  /* Check the cases from our subtask 2 solution */
  // To help with this, we must count how many times each value occurs
  for (int i = 0; i < M; i++) {
    int s = S[i];
    num_occurrences[s]++;
  }

  for (int i = 0; i < M-1; i++) {
    int x = num_occurrences[S[i]];
    int tile1 = in_T[S[i]];
    int tile2 = in_T[S[i+1]];
    if (S[i] != S[i+1]) {
      int d = abs(in_T[S[i]] - in_T[S[i+1]]);
      if (x < d || x%2 != d%2) {
        NO();
      }

      for (int tile = std::min(tile1, tile2+1); tile < std::max(tile1, tile2); tile++) {
        if (T[tile] > S[i]) {
          // there is a larger tile between the two tiles!
          NO();
        }
      }
    }

    // Check if S[i] has larger tiles on both sides
    if (tile1 == 0 || T[tile1-1] > T[tile1]) {
      // larger on the left

      if (tile1 == N-1 || T[tile1+1] > T[tile1]) {
        // larger on the right

        if (x != 1) {
          NO();
        }
      }
    }
  }

  printf("YES\n");
}

Subtasks 4 and 5

The first three subtasks of this problem were very challenging, but the final two subtasks are even harder: do not worry if you struggle to understand the solution!

In subtasks 1-3 the tiles all had distinct values which meant that we didn't have many choices for where the robot could go. In the final 2 subtasks there can be multiple tiles with the same value, which means there can be multiple possible starting tiles and multiple options for where to go from there. Our solution needs to efficiently check all of these.

Let's look at another example:

Our target sequence is S = [2, 2, 2, 2, 2, 3, 3, 3, 3, 4].

We will determine what the robot can output bit by bit. Specifically, we say that some tile i is possible if it is possible for the robot to reach tile i for the first time while outputting a prefix of S. Additionally, the value on tile i should be outputted for the first time when this tile is reached. For example:

Since tile 1 contains the final value in the target sequence (4) and is possible, this means that the answer is YES.

To solve subtasks 4 and 5 you can simulate this process in code. We begin by sorting the tiles by value (similarly to what I did in the example above). We then go through the tiles one at a time and check whether they are possible. To check whether a tile i is possible, look at the target sequence S and check whether the value on the tile appears in the sequence. If it doesn't, then the tile is not possible. If it does, look for the previous value in the sequence. For tile i to be possible, there must be a possible tile containing the previous value, and the path between the two tiles must satisfy all the conditions from the subtask 2/3 solution.

Depending on your time complexity, your solution will either pass subtask 4 or the full problem. We leave the specific details of these solutions as a challenge for the reader.

Below is my subtask 4 implementation (the worst case time complexity is O(NM) and so it will not pass subtask 3 or 5). 
import sys

N = int(input().strip())
T = list(map(int, input().strip().split()))
M = int(input().strip())
S = list(map(int, input().strip().split()))

MAX_VAL = 1000001

# This function prints NO and then ends the program
def NO():
  print("NO")
  sys.exit(0)

# Check the first two cases
for i in range(M-1):
  if S[i] > S[i+1]:
    # The target sequence is not non-decreasing
    NO()

# To make certain parts of our implementation nicer we add pretend tiles to the start and end with a very large value
T = [MAX_VAL] + T + [MAX_VAL]

num_occurrences = [0 for i in range(MAX_VAL+1)] # num_occurrences[i] will store the number of i's in the target sequence
for s in S:
  num_occurrences[s] += 1

prior_target_value = [0 for i in range(MAX_VAL)]
for i in range(1, len(S)):
  if S[i-1] != S[i]:
    prior_target_value[S[i]] = S[i-1]

is_possible = [False for i in range(len(T))]

# first check whether tiles containing S[0] are possible
for i, value in enumerate(T):
  if value == S[0]:
    if M > 1 and S[1] == S[0] and T[i-1] > T[i] and T[i+1] > T[i]:
      # special case: not possible
      pass
    else:
      is_possible[i] = True

# this for loop iterates over pairs of (index, value) from T in ascending order
for i, value in sorted(enumerate(T), key=lambda i: i[1]):
  if num_occurrences[value] == 0:
    continue
  
  for end, diff in [(-1, -1), (len(T), 1)]:
    for j in range(i+diff, end, diff):
      d = abs(i-j)
      x = num_occurrences[prior_target_value[value]]
      if is_possible[j] and T[j] == prior_target_value[value] and d <= x and d%2 == x%2:
        is_possible[i] = True
      
      if T[j] > prior_target_value[value]:
        break

for i, value in enumerate(T):
  if is_possible[i] and value == S[-1]:
    print("YES")
    sys.exit(0)

print("NO")
#include <cstdio>
#include <algorithm> // for std::sort
#include <vector> // for std::vector
#include <utility> // for std::pair
using namespace std;

const int MAX_VAL = 1000001;

int N, M;

/* This function prints NO and then ends the program */
int NO() {
  printf("NO\n");
  exit(0);
}

int main() {
  scanf("%d", &N);
  std::vector<int> T(N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &T[i]);
  }

  scanf("%d", &M);
  std::vector<int> S(M);
  for (int i = 0; i < M; i++) {
    scanf("%d", &S[i]);
  }

  /* Check the first two cases */
  for (int i = 0; i < M-1; i++) {
    if (S[i] > S[i+1]) {
      // The target sequence is not non-decreasing
      NO();
    }
  }

  // To make certain parts of our implementation nicer we add pretend tiles to the start and end with a very large value
  T.insert(T.begin(), MAX_VAL);
  T.push_back(MAX_VAL);

  std::vector<int> num_occurrences(MAX_VAL+1, 0); // num_occurrences[i] will store the number of i's in the target sequence
  for (int s : S) {
    num_occurrences[s]++;
  }

  std::vector<int> prior_target_value(MAX_VAL, 0);
  for (int i = 1; i < (int)S.size(); i++) {
    if (S[i-1] != S[i]) {
      prior_target_value[S[i]] = S[i-1];
    }
  }

  std::vector<bool> is_possible(T.size(), false);

  // first check whether tiles containing S[0] are possible
  for (int i = 0; i < (int)T.size(); i++) {
    int value = T[i];
    if (value == S[0]) {
      if (M > 1 && S[1] == S[0] && T[i-1] > T[i] && T[i+1] > T[i]) {
        // special case: not possible
      } else {
        is_possible[i] = true;
      }
    }
  }

  std::vector<std::pair<int,int>> order;
  for (int i = 0; i < (int)T.size(); i++) {
    order.push_back(make_pair(T[i], i));
  }
  std::sort(order.begin(), order.end());
  
  // this for loop iterates over pairs of (index, value) from T in ascending order
  for (int k = 0; k < order.size(); k++) {
    int i = order[k].second;
    int value = order[k].first;

    if (num_occurrences[value] == 0) continue;

    for (int dir = 0; dir < 2; dir++) {
      int end = (dir == 0 ? -1 : (int)T.size());
      int diff = (dir == 0 ? -1 : 1);
      for (int j = i + diff; j != end; j += diff) {
        int d = abs(i - j);
        int x = num_occurrences[prior_target_value[value]];
        if (is_possible[j] && T[j] == prior_target_value[value] && d <= x && d % 2 == x % 2) {
          is_possible[i] = true;
        }

        if (T[j] > prior_target_value[value]) break;
      }
    }
  }

  for (int i = 0; i < (int)T.size(); i++) {
    int value = T[i];
    if (is_possible[i] && value == S.back()) {
      printf("YES\n");
      return 0;
    }
  }

  printf("NO\n");
}

Click here to go back.