Home » 国际竞赛 » Details

USACO 2022 February Contest, Silver Problem 2. Robot Instructions

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

USACO 2022 February Contest, Silver Problem 2. Robot Instructions

Bessie is learning how to control a robot she has recently received as a gift.

The robot begins at point $(0, 0)$ on the coordinate plane and Bessie wants the robot to end at point $(x_{g}, y_{g})$ . Bessie initially has a list of $N$ ( $1 \leq N \leq 40$ ) instructions to give to the robot, the $i$ -th of which will move the robot $x_{i}$ units right and $y_{i}$ units up (or left or down when $x_{i}$ and $y_{i}$ are negative, respectively).

For each $K$ from $1$ to $N$ , help Bessie count the number of ways she can select $K$ instructions from the original $N$ such that after the $K$ instructions are executed, the robot will end at point $(x_{g}, y_{g})$ .

**Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.**

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

The first line contains $N$ . The next line contains $x_{g}$ and $y_{g}$ , each in the range $- 10^{9} \dots 10^{9}$ . The final $N$ lines describe the instructions. Each line has two integers $x_{i}$ and $y_{i}$ , also in the range $- 10^{9} \dots 10^{9}$ .It is guaranteed that $(x_{g}, y_{g}) \neq (0, 0)$ and $(x_{i}, y_{i}) \neq (0, 0)$ for all $i$ .

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

Print $N$ lines, the number of ways Bessie can select $K$ instructions from the original $N$ for each $K$ from $1$ to $N$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

In this example, there are six ways Bessie can select the instructions:

(-2,0) (3,0) (4,0) (0,10) (0,-10) (0,10) (1 2 3 5 6 7)
(-2,0) (3,0) (4,0) (0,10) (1 2 3 5)
(-2,0) (3,0) (4,0) (0,10) (1 2 3 7)
(5,0) (0,10) (0,-10) (0,10) (4 5 6 7)
(5,0) (0,10) (4 5)
(5,0) (0,10) (4 7)

For the first way, the robot's path looks as follows:

(0,0) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10)

SCORING:

Test cases 2-4 satisfy $N \leq 20$ .
Test cases 5-16 satisfy no additional constraints.

Problem credits: Alex Liang

USACO 2022 February Contest, Silver Problem 2. Robot Instructions 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Nick Wu)

The first observation we make in this problem is that the order in which operations happen in does not matter, it only matters which operations we do. This means there are $2^{N}$ different sets of operations to consider. To solve the subtask, we can manually consider each set.

Below is my Python 3 code that solves the subtask where $N \leq 20$ .

def solve():
    n = int(input())
    wantx, wanty = (int(z) for z in input().split())
    cand = [(0, 0, 0)] # [(x, y, number of instructions used)]
    for _ in range(n):
        x, y = (int(z) for z in input().split())
        now = len(cand)
        for i in range(now):
            cand.append((cand[i][0] + x, cand[i][1] + y, cand[i][2] + 1))
    ret = [0] * n
    for x, y, z in cand:
        if (x, y) == (wantx, wanty):
            ret[z-1] += 1
    for x in ret:
        print(x)

solve()

We note that the original bounds on the problem have $N \leq 40$ , which is only twice as big. This suggests cutting the given operations into two halves of roughly equal sizes and running the above algorithm on both halves. If we iterate over one of the given lists, we know exactly how far we need to move from the other half of the instructions.

This technique is sometimes known as meet-in-the-middle. To motivate this, imagine that half of the instructions are actually instructions to move the goal location in some direction. Note that in this variant of the problem, even though we are effectively brute-forcing all possible ways to move the robot and all possible ways to move the goal, we can quickly check when the goal and robot are in the same place. The time complexity for each of the solutions below is $O (N \cdot 2^{N / 2})$ .

Benjamin Qi's C++ code:

#include <bits/stdc++.h>

using namespace std;

using P = pair<long long, long long>;
P operator+(P a, P b) { return {a.first + b.first, a.second + b.second}; }
P operator-(P a, P b) { return {a.first - b.first, a.second - b.second}; }

vector<pair<P, int>> all_subsets(const vector<P> &dirs) {
	vector<pair<P, int>> v{{}};
	for (const P &d : dirs) {
		v.resize(2 * v.size());
		for (int i = 0; i < v.size() / 2; i++) {
			v[i + v.size() / 2] = {v[i].first + d, v[i].second + 1};
		}
	}
	sort(v.begin(), v.end());
	return v;
}

int main() {
	int N;
	cin >> N;
	P goal;
	cin >> goal.first >> goal.second;
	vector<P> dirs(N);
	for (auto &d : dirs) {
		cin >> d.first >> d.second;
	}
	vector<pair<P, int>> a =
		all_subsets(vector<P>(begin(dirs), begin(dirs) + N / 2));
	vector<pair<P, int>> b =
		all_subsets(vector<P>(begin(dirs) + N / 2, end(dirs)));
	reverse(b.begin(), b.end());
	vector<long long> ans(N + 1);
	vector<int> with_num;
	P rest_prev{1e18, 1e18};
	int ib = 0;
	for (const auto &[offset, num] : a) {
		const P rest = goal - offset;
		if (rest != rest_prev) {
			rest_prev = rest;
			with_num = vector<int>(N - N / 2 + 1);
			for (; ib < b.size() && b.at(ib).first > rest; ++ib);
			for (; ib < b.size() && b.at(ib).first == rest; ++ib) {
				++with_num.at(b.at(ib).second);
			}
		}
		for (int i = 0; i < with_num.size(); i++) {
			ans[i + num] += with_num[i];
		}
	}
	for (int i = 1; i <= N; i++) {
		cout << ans[i] << "\n";
	}
}

Alternatively, a hashmap can be used instead of sorting, though the constant factor is somewhat worse:

#include <bits/stdc++.h>

using namespace std;

using P = pair<long long, long long>;
P operator+(P a, P b) { return {a.first + b.first, a.second + b.second}; }
P operator-(P a, P b) { return {a.first - b.first, a.second - b.second}; }

vector<pair<P, int>> all_subsets(const vector<P> &dirs) {
	vector<pair<P, int>> v{{}};
	for (const P &d : dirs) {
		v.resize(2 * v.size());
		for (int i = 0; i < v.size() / 2; i++) {
			v[i + v.size() / 2] = {v[i].first + d, v[i].second + 1};
		}
	}
	return v;
}

struct hsh {
	size_t operator()(const P &p) const {
		return p.first * 239 + p.second;
	}
};

int main() {
	int N;
	cin >> N;
	P goal;
	cin >> goal.first >> goal.second;
	vector<P> dirs(N);
	for (auto &d : dirs) {
		cin >> d.first >> d.second;
	}
	vector<pair<P, int>> a =
		all_subsets(vector<P>(begin(dirs), begin(dirs) + N / 2));
	vector<pair<P, int>> b =
		all_subsets(vector<P>(begin(dirs) + N / 2, end(dirs)));
	unordered_map<P, map<int, int>, hsh> first_half;
	for (const auto &[offset, num] : a) {
		++first_half[offset][num];
	}
	vector<long long> ans(N + 1);
	for (const auto &[offset, num] : b) {
		auto it = first_half.find(goal - offset);
		if (it != end(first_half)) {
			for (const auto &[num2, ways] : it->second) {
				ans[num + num2] += ways;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		cout << ans[i] << "\n";
	}
}

Danny Mittal's Java code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class RobotInstructionsSort {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        long xGoal = Long.parseLong(tokenizer.nextToken());
        long yGoal = Long.parseLong(tokenizer.nextToken());
        long[] instructionsX = new long[n];
        long[] instructionsY = new long[n];
        for (int j = 0; j < n; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            instructionsX[j] = Long.parseLong(tokenizer.nextToken());
            instructionsY[j] = Long.parseLong(tokenizer.nextToken());
        }
        InstructionChoice[] choicesLeft = new InstructionChoice[1 << (n / 2)];
        for (int mask = 0; mask < 1 << (n / 2); mask++) {
            long x = 0;
            long y = 0;
            for (int j = 0; j < n / 2; j++) {
                if ((mask & (1 << j)) != 0) {
                    x += instructionsX[j];
                    y += instructionsY[j];
                }
            }
            choicesLeft[mask] = new InstructionChoice(x, y, Integer.bitCount(mask));
        }
        Arrays.sort(choicesLeft);
        InstructionChoice[] choicesRight = new InstructionChoice[1 << ((n + 1) / 2)];
        for (int mask = 0; mask < 1 << ((n + 1) / 2); mask++) {
            long x = 0;
            long y = 0;
            for (int j = n / 2; j < n; j++) {
                if ((mask & (1 << (j - (n / 2)))) != 0) {
                    x += instructionsX[j];
                    y += instructionsY[j];
                }
            }
            choicesRight[mask] = new InstructionChoice(xGoal - x, yGoal - y, Integer.bitCount(mask));
        }
        Arrays.sort(choicesRight);
        long[] answer = new long[n + 1];
        long[] amounts = new long[(n / 2) + 1];
        int j = 0;
        int k = 0;
        for (InstructionChoice choice : choicesRight) {
            while (j < choicesLeft.length && choicesLeft[j].compareTo(choice) <= 0) {
                amounts[choicesLeft[j].instructions]++;
                j++;
            }
            while (k < choicesLeft.length && choicesLeft[k].compareTo(choice) < 0) {
                amounts[choicesLeft[k].instructions]--;
                k++;
            }
            for (int instructions = 0; instructions <= n / 2; instructions++) {
                answer[instructions + choice.instructions] += amounts[instructions];
            }
        }
        StringBuilder out = new StringBuilder();
        for (int instructionsUsed = 1; instructionsUsed <= n; instructionsUsed++) {
            out.append(answer[instructionsUsed]).append('\n');
        }
        System.out.print(out);
    }
 
    static class InstructionChoice implements Comparable<InstructionChoice> {
        final long x;
        final long y;
        final int instructions;
 
        InstructionChoice(long x, long y, int instructions) {
            this.x = x;
            this.y = y;
            this.instructions = instructions;
        }
 
        @Override
        public int compareTo(InstructionChoice other) {
            if (y != other.y) {
                return Long.compare(y, other.y);
            } else {
                return Long.compare(x, other.x);
            }
        }
    }
}

[/hide]