Person in Charge

• 035966_L3

Attention

Please strictly follow the submission instructions.

Problem Description

Consider the following problem:

There are $n$ piglets on a narrow bridge of length $T$.

Using the left end of the bridge as the origin and the right direction as positive, we establish a coordinate system.

The positions of the $n$ piglets are given as $a_1,a_2,\ldots,a_n$.

When dinner time arrives, they need to get off the bridge to eat.

They move simultaneously each second according to these rules:

• Count how many piglets are to its left and right.
• Move toward the side with fewer piglets.
• If both sides have equal numbers, it doesn't move.
• Piglets at either end of the bridge jump off.

Naturally, if only one piglet remains on the bridge, it will never come down.

Determine how many seconds until all piglets stop moving (jumping off counts as stopping).

Guarantees:

• $n < T$;
• $n, T, a_i$ are all positive integers;
• $0 < a_1 < a_2 < \ldots < a_n < T$.

And the following code:

int solve(int T, int n, int a[])
{
	int l = 1, r = n, t = 0;
	while (l < r)
	{
		t++;
		for (int i = l; i <= r; i++)
		{
			if (i - l < r - i) a[i]--;
			if (i - l > r - i) a[i]++;
		}
		if (a[l] == 0) l++;
		if (a[r] == T) r--;
	}
	return t;
}

In this code, we assume $\bm{n,T}$ can be infinitely large, array $\bm a$ can be infinitely long, with no limitations from machine performance, time constraints, memory constraints, or int range.

Please analyze the worst-case time complexity of this code and provide proof.

Submission Method

## Part 1

The worst-case time complexity of this code is O(1).

## Part 2

According to [cq_irritater](/user/2)'s first axiom, the worst-case time complexity is clearly O(1).

## Part 3

Example test case:

- n=1
- T=2
- a_1=1

1. Your proof must contain three parts (the example above is clearly incorrect):
   • Part 1: State the worst-case time complexity.
   • Part 2: Prove the complexity doesn't exceed your claimed bound.
   • Part 3: Construct test data that achieves this worst-case complexity.
2. Fill in your Sleeping Cup UID in the code below and submit in C++.
3. This problem will be manually graded after the contest. Multiple submissions will be judged by the last one. Follow instructions precisely.

#include <bits/stdc++.h>
using namespace std;
const int UID = /*Enter your UID here*/;
int main()
{
    freopen("proof.in", "r", stdin);
    freopen("proof.out", "w", stdout);
    cout << UID;
    return 0;
}

4. Do not submit fake UIDs - violations will result in warnings or bans.
5. Post-contest submission format:

#include <bits/stdc++.h>
using namespace std;
const int UID = (-1) * /*Enter your UID here*/;
int main()
{
    freopen("proof.in", "r", stdin);
    freopen("proof.out", "w", stdout);
    cout << UID;
    return 0;
}
/*
## Part 1

The worst-case time complexity is O(1).

## Part 2

According to [cq_irritater](/user/2)'s first axiom...

## Part 3

Test case:
- n=1
- T=2
- a_1=1
*/

Official Solution

link