Problem 2 - IGM

We will discuss the solution to IGM from AIO 2026.

Solution

Subtask 1: N = 3

With only three delegates there are only three possible meetings, and we can check each of them:

If any of these lists is increasing then the answer is YES, otherwise the answer is NO. Sample input 2 shows all three meetings for A = [10, 30, 20], and none of them are increasing.

Subtask 2: N ≤ 1000

We can extend the idea from subtask 1. There are N possible starting speakers, and we can try them one at a time. For each starting speaker, we walk clockwise around the table and check whether each speaker is more important than the previous one. If we find a starting speaker where all N delegates can speak, we print YES. If none of the starting speakers work, we print NO.

Let's analyse the time complexity of this solution. For each of the N starting speakers we make N-1 comparisons, giving an overall time complexity of O(N2). This is fast enough to pass subtasks 1 and 2 but is not fast enough to solve the final subtask.

Full Solution

Rather than trying every starting speaker, can we work out which one we should choose? A useful observation is that the first speaker must be the delegate with the smallest importance value. You shouldn't just trust me though: try to prove this yourself before reading my proof below!

Proof

Suppose we start with any other delegate. Then the delegate with the smallest importance must speak at some later point in the meeting. But their importance is smaller than that of every other delegate, including whoever spoke just before them, so they are not allowed to speak. Therefore the meeting fails whenever we start with any delegate other than the one with the smallest importance.

This means there is only one starting speaker worth checking. We find the delegate with the smallest importance in O(N) time, and then check this one meeting using the method from subtask 2. If the importance values increase throughout the meeting, we print YES. Otherwise we print NO. Be careful: starting at the smallest value is necessary, but it doesn't guarantee success. We must still check the rest of the meeting!

Let's try some examples:

Both finding the smallest value and checking the meeting take O(N) time, so this solution has a time complexity of O(N) which is fast enough to score 100.

Code

Below you can see the full solution written in Python and C++. I suggest trying to code the solution yourself and only look at our code after you finish or if you get stuck. The % N in the code is what lets us wrap around from the last delegate back to the first.

# N is the number of delegates.
N = 0

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

# Read the value of N and the importance values.
N = int(input().strip())
A = list(map(int, input().strip().split()))

# Find the delegate with the smallest importance
start = 0
for i in range(1, N):
  if A[i] < A[start]:
    start = i

# Compute the answer by checking the meeting that starts with this delegate
answer = True
for step in range(1, N):
  # The % N lets us wrap around from the last delegate back to the first
  previous = (start + step - 1) % N
  current = (start + step) % N
  if A[current] < A[previous]:
    # The current delegate is less important than the previous speaker
    answer = False

if answer:
  print("YES")
else:
  print("NO")
#include <cstdio>

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

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

int main(void) {
  /* Read the value of N and the importance values. */
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }

  /* Find the delegate with the smallest importance */
  int start = 0;
  for (int i = 1; i < N; i++) {
    if (A[i] < A[start]) {
      start = i;
    }
  }

  /* Compute the answer by checking the meeting that starts with this delegate */
  bool answer = true;
  for (int step = 1; step < N; step++) {
    // The % N lets us wrap around from the last delegate back to the first
    int previous = (start + step - 1) % N;
    int current = (start + step) % N;
    if (A[current] < A[previous]) {
      // The current delegate is less important than the previous speaker
      answer = false;
    }
  }

  if (answer) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }
}

Click here to go back.