Home » 国际竞赛 » Details

USACO 2022 January Contest, Gold Problem 3. Tests for Haybales

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午3:20

USACO 2022 January Contest, Gold Problem 3. Tests for Haybales

Farmer John's cows have decided to offer a programming contest for the cows on Farmer Nhoj's farm. In order to make the problems as fun as possible, they have spent considerable time coming up with challenging input cases. For one problem in particular, "Haybales", the cows need your help devising challenging inputs. This involve solving the following somewhat intriguing problem:

There is an array of sorted integers $x_{1} \leq x_{2} \leq \dots \leq x_{N}$ ( $1 \leq N \leq 10^{5}$ ), and an integer $K$ . You don't know the array or $K$ , but you do know for each index $i$ , the largest index $j_{i}$ such that $x_{j_{i}} \leq x_{i} + K$ . It is guaranteed that $i \leq j_{i}$ and $j_{1} \leq j_{2} \leq \dots \leq j_{N} \leq N$ .

Given this information, Farmer John's cows need to construct any array along with some integer $K$ that matches that information. The construction needs to satisfy $0 \leq x_{i} \leq 10^{18}$ for all $i$ and $1 \leq K \leq 10^{18}$ .

It can be proven that this is always possible. Help Farmer John's cows solve this problem!

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains $N$ . The next line contains $j_{1}, j_{2}, \dots, j_{N}$ .

OUTPUT FORMAT (print output to the terminal / stdout):

Print $K$ , then $x_{1}, \dots, x_{N}$ on separate lines. Any valid output will be accepted.

SAMPLE INPUT:

6
2 2 4 5 6 6

SAMPLE OUTPUT:

The sample output is the array $a = [1, 6, 17, 22, 27, 32]$ with $K = 6$ . $j_{1} = 2$ is satisfied because $a_{2} = 6 \leq 1 + 6 = a_{1} + K$ but $a_{3} = 17 > 1 + 6 = a_{1} + K$ , so $a_{2}$ is the largest element that is at most $a_{1}$ . Similarly,

$j_{2} = 2$ is satisfied because $a_{2} = 6 \leq 6 + 6$ but $a_{3} = 17 > 6 + 6$
$j_{3} = 4$ is satisfied because $a_{4} = 22 \leq 17 + 6$ but $a_{5} = 27 > 17 + 6$
$j_{4} = 5$ is satisfied because $a_{5} = 27 \leq 22 + 6$ but $a_{5} = 32 > 22 + 6$
$j_{5} = 6$ is satisfied because $a_{6} = 32 \leq 27 + 6$ and $a_{6}$ is the last element of the array
$j_{6} = 6$ is satisfied because $a_{6} = 32 \leq 32 + 6$ and $a_{6}$ is the last element of the array

This is not the only possible correct output for the sample input. For example, you could instead output the array $[1, 2, 4, 5, 6, 7]$ with $K = 1$ .

SCORING:

For 50% of all inputs, $N \leq 5000$
For the remaining inputs, there are no additional constraints.

Problem credits: Danny Mittal

USACO 2022 January Contest, Gold Problem 3. Tests for Haybales 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Danny Mittal)

Consider creating a tree on the indexes of the array as follows. For an index $i$ , let its parent be $j_{i} + 1$ . Note that this means that we'll also need a node $N + 1$ , since $j_{N} + 1 = N + 1$ ; this node will be the root of the tree.

Let's define the height of a node as the depth of the deepest node minus its own depth. This tree construction is illustrated below for the sample with heights on the left.

Notice that as we go down the array from index $N$ to index $1$ , the heights of the corresponding nodes decrease. This means that the array consists of first the nodes at height $0$ , then the nodes at height $1$ , etc. Additionally, since each node $i$ 's parent is $j_{i} + 1$ , which is the first index whose element $a_{j_{i} + 1}$ is greater than $a_{i} + K$ , and a node's parent necessarily has height $1$ higher than the height of that node, the nodes at a certain height need to have values that are approximately $K$ higher than the values of the nodes at the immediately lower height.

This suggests that we assign the values of the nodes as $a_{i} = h_{i} K + x_{i}$ , where $h_{i}$ is the height of node $i$ and $x_{i}$ is some yet to be determined value between $0$ and $K - 1$ . Using these values means that $a_{i} + K = (h_{i} + 1) K + x_{i}$ , which means that the point at which values go from being less than $a_{i} + K$ to more than $a_{i} + K$ occurs at height $h_{i} + 1$ , which is exactly what we want since $i$ 's parent, $j_{i} + 1$ , is at height $h_{i} + 1$ .

All that remains is to choose values of $x_{i}$ appropriately so that that point occurs at exactly the right place inside height $h_{i} + 1$ . This means choosing the $x$ values so that $x_{j_{i} + 1} > x_{i}$ , but any smaller indexes at height $h_{i} + 1$ have an $x$ value less than or equal to $x_{i}$ .

We can do this using DFS. We start by assigning the root node $N + 1$ to have $x_{N + 1} = K - 1$ , the largest $x$ value possible. Then, it DFSs through its children starting from the largest index and going down. Whenever we reach a node, we assign it the next lower $x$ value, then DFS through its children in decreasing order. This guarantees that every node $i$ has an $x$ value larger than $i$ 's children, but all smaller indexes at the same height as $i$ get an $x$ value smaller than $i$ 's children, since the DFS reaches them only after searching through all of $i$ 's descendants.

Since each node will get a unique $x$ value, we need to set $K = N + 1$ in order to ensure that all $x$ values are between $0$ and $K - 1$ . The $x$ values for the sample are illustrated below.

                7
           /---/
          5   6
         /   /
        3   4
     /-/
    1 2

x = 0 1 2 3 4 5 6

As an example of how this construction works, consider index $4$ , which has $j_{4} = 5$ . Its height is $1$ and its $x$ value is $x_{4} = 4$ , which means that its array value will be $a_{4} = (1) K + 4 = (1) (7) + 4$ , and $a_{4} + K$ will be $(2) (7) + 4$ .

Index $5$ is at height $2$ but has the smaller $x$ value $x_{5} = 3$ , so its array value will be $a_{5} = (2) (7) + 3$ , which is smaller than $a_{4} + K = (2) (7) + 4$ . Similarly, index $6$ is at height $2$ and has the larger $x$ value $x_{6} = 5$ , so its array value will be $a_{6} = (2) (7) + 5$ , which is larger than $a_{4} + K = (2) (7) + 4$ . Therefore index $5$ is the largest index $j$ satisfying $a_{j} \leq a_{4} + K$ , and so the requirement $j_{4} = 5$ is satisfied.

Using these $x$ values, we can calculate our array $a$ along with the choice of $K = N + 1$ to produce a valid construction. Our algorithm simply consists of constructing the tree then performing a DFS to compute the $x$ values as well as the heights. This runs in $O (N)$ time.

The array values for all indexes in the sample are illustrated below.

                                                                     (3)(7) + 6
                                             /----------------------/
                                   (2)(7) + 3             (2)(7) + 5
                                  /                      /
                        (1)(7) + 2             (1)(7) + 4
          /------------/
(0)(7) + 0   (0)(7) + 1

Code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class TestsForHaybales {
    static List<Integer>[] children;
    static long[] depths;
    static long[] xs;
    static long x;

    static void dfs(int a) {
        xs[a] = x;
        x--;
        Collections.reverse(children[a]);
        for (int b : children[a]) {
            depths[b] = depths[a] + 1L;
            dfs(b);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        children = new List[n + 2];
        for (int a = 1; a <= n + 1; a++) {
            children[a] = new ArrayList<>();
        }
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        for (int a = 1; a <= n; a++) {
            children[Integer.parseInt(tokenizer.nextToken()) + 1].add(a);
        }
        depths = new long[n + 2];
        xs = new long[n + 2];
        x = n;
        dfs(n + 1);
        long k = n + 1;
        StringJoiner joiner = new StringJoiner("\n");
        for (int a = 1; a <= n; a++) {
            long height = depths[1] - depths[a];
            long value = (height * k) + xs[a];
            joiner.add("" + value);
        }
        System.out.println(k);
        System.out.println(joiner);
    }
}

[/hide]