USACO 2022 February Contest, Silver Problem 2. Robot Instructions

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)(0,0) on the coordinate plane and Bessie wants the robot to end at point (xg,yg)(xg,yg). Bessie initially has a list of NN (1N401≤N≤40) instructions to give to the robot, the ii-th of which will move the robot xixi units right and yiyi units up (or left or down when xixi and yiyi are negative, respectively).

For each KK from 11 to NN, help Bessie count the number of ways she can select KK instructions from the original NN such that after the KK instructions are executed, the robot will end at point (xg,yg)(xg,yg).

**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 NN. The next line contains xgxg and ygyg, each in the range 109109−109…109. The final NN lines describe the instructions. Each line has two integers xixi and yiyi, also in the range 109109−109…109.It is guaranteed that (xg,yg)(0,0)(xg,yg)≠(0,0) and (xi,yi)(0,0)(xi,yi)≠(0,0) for all ii.

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

Print NN lines, the number of ways Bessie can select KK instructions from the original NN for each KK from 11 to NN.

SAMPLE INPUT:

7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10

SAMPLE OUTPUT:

0
2
0
3
0
1
0

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 N20N≤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 2N2N 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 N20N≤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 N40N≤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(N2N/2)O(N⋅2N/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]

翰林国际教育资讯二维码