Google Code Jam Round 2 2022 Record

Contents

• Info
• Problems
  • Spiraling Into Control
  • Pixelated Circle
  • Saving the Jelly
  • I, O Bot

Info

• Practice Link
• Code Repo Link
• Score: 22
• Rank: 1680

Problems

Spiraling Into Control

题意：

给出一个 的蛇形矩阵。

从 能够到达 ，当且仅当 和 相邻，并且在蛇形矩阵上 上对应的数字大于 上对应的数字。

现在要求从 走到 ，并且恰好用 步，问是否可能，可能的话，给出中间跳跃的步骤。

思路：

猜想了一下，当前这一步是否选择跳跃，取决于跳跃后剩余的最大步数是否大于等于可用步数，是的话，就跳跃。

但是大 case TLE 了。

Small Case Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <utility>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

// #ifdef LOCAL
// #include <debug.hpp>
// #else
// #define dbg(...)
// #endif
// head
const int N = 1e4 + 10;
int n, k;
int f[N][N];

int mv[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void genG() {
    int ix = 1;
    int mx = 0;
    int x = 1, y = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = -1;
        }
    }

    const auto ok = [](int x, int y) {
        if (x < 1 || x > n || y < 1 || y > n) {
            return false;
        }

        if (f[x][y] != -1) {
            return false;
        }

        return true;
    };

    f[1][1] = 1;

    while (ix < n * n) {
        ++ix;
        int nx = x + mv[mx][0];
        int ny = y + mv[mx][1];

        if (!ok(nx, ny)) {
            mx = (mx + 1) % 4;
        }

        nx = x + mv[mx][0];
        ny = y + mv[mx][1];

        x = nx;
        y = ny;

        f[x][y] = ix;
    }
}

void printG() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << f[i][j] << " \n"[j == n];
        }
    }
}

struct node {
    int x, y, v;
    bool operator<(const node &other) const {
        return v > other.v;
    }
};

vector<pair<int, int>> gao() {
    auto res = vector<pair<int, int>>();

    const auto ok = [](int x, int y) {
        if (x < 1 || x > n || y < 1 || y > n) {
            return false;
        }

        return true;
    };

    node cur = {
            .x = 1,
            .y = 1,
            .v = 1,
    };

    int _k = k;
    int target = n * n;
    while (_k > 0) {
        vector<node> t;

        // cout << cur.x << " " << cur.y << " " << cur.v << " " << _k << " " << res.size() << endl;

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + mv[i][0];
            int ny = cur.y + mv[i][1];
            if (ok(nx, ny) && f[nx][ny] > cur.v) {
                t.emplace_back(node{
                        .x = nx,
                        .y = ny,
                        .v = f[nx][ny],
                });
            }
        }

        sort(t.begin(), t.end());

        int ok = 0;

        for (const auto &nx : t) {
            if (_k - 1 <= target - nx.v) {
                if (nx.v - cur.v > 1) {
                    res.push_back(make_pair(cur.v, nx.v));
                }

                cur = nx;
                ok = 1;

                break;
            }
        }

        if (ok == 0) {
            return vector<pair<int, int>>();
        }

        --_k;
    }

    if (cur.v != target) {
        return vector<pair<int, int>>();
    }

    return res;
}

void run() {
    cin >> n >> k;
    genG();
    // printG();

    auto res = gao();

    if (res.empty()) {
        cout << "IMPOSSIBLE\n";
    } else {
        cout << res.size() << "\n";
        for (const auto &it : res) {
            cout << it.first << " " << it.second << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);

    int _T = 0;
    cin >> _T;
    for (int i = 1; i <= _T; ++i) {
        cout << "Case #" << i << ": ";
        run();
    }

    return 0;
}

Pixelated Circle

题意：

给出两种在矩阵上「画圆」的函数，求两种方式画出来的「黑点」的数量差异。

思路：

小 case 就将题面中的伪代码翻译一下，然后跑一遍，求个数量的 diff。

Small Case Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

// head
const int N = 1e4 + 10;
int r;
int f[N][N];

int get_pixel(int x, int y) {
    return f[x + 100][y + 100];
}

void set_pixel(int x, int y, int v = 0) {
    f[x + 100][y + 100] = v;
}

void set_pixel_to_black(int x, int y) {
    set_pixel(x, y, 1);
}

int get_all_pixel() {
    int res = 0;

    for (int i = -r; i <= r; i++) {
        for (int j = -r; j <= r; j++) {
            res += get_pixel(i, j);
        }
    }

    return res;
}

void init() {
    for (int i = -r; i <= r; i++) {
        for (int j = -r; j <= r; j++) {
            set_pixel(i, j, 0);
        }
    }
}

void draw_circle_perimeter(int r) {
    for (int x = -r; x <= r; x++) {
        int y = static_cast<int>(round(sqrt(r * r - x * x)));

        set_pixel_to_black(x, y);
        set_pixel_to_black(x, -y);
        set_pixel_to_black(y, x);
        set_pixel_to_black(-y, x);
    }
}

void draw_circle_filled_wrong(int r) {
    for (int i = 0; i <= r; i++) {
        draw_circle_perimeter(i);
    }
}

void draw_circle_filled(int r) {
    for (int i = -r; i <= r; i++) {
        for (int j = -r; j <= r; j++) {
            int x = static_cast<int>(round(sqrt(i * i + j * j)));
            if (x <= r) {
                set_pixel_to_black(i, j);
            }
        }
    }
}

void run() {
    cin >> r;

    init();
    draw_circle_filled(r);
    int a = get_all_pixel();

    init();
    draw_circle_filled_wrong(r);
    int b = get_all_pixel();

    cout << abs(a - b) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);

    int _T = 0;
    cin >> _T;
    for (int i = 1; i <= _T; ++i) {
        cout << "Case #" << i << ": ";
        run();
    }

    return 0;
}

Saving the Jelly

题意：

在一个足球场上，有 个人， 个糖果。

第 个人的位置是 。

第 个糖果的位置是 。

现在有个教练，每次可以指定第 个人去拿糖果，这个人只能选择离自己最近的一颗糖果，如果有多颗糖果离自己最近，那么由教练指定他拿取哪一颗。

问，有没有方案，使得标号为 的糖果，最后不被拿走？

思路：

针对小 case：

全排列枚举人拿的顺序，然后暴力 check。

check 的时候，如果某个人在轮到时有多个候选糖果，怎么办？

只要不取 ，其它随便取。

因为如果存在这个人一定得取某一颗糖果，那么最后方案才能跑通的话，那么肯定有另一种排列使得优先级更高的人在前面取走他所需的糖果。

Small Case Code

#include <bits/stdc++.h>
#include <algorithm>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <limits>
#include <utility>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

// head

int n, vis[12];

long long calcDis(int x, int y, int nx, int ny) {
    return 1ll * (x - nx) * (x - nx) + 1ll * (y - ny) * (y - ny);
}

ll dis[30][30];

struct node {
    int ix;
    long long dis;

    bool operator<(const node &other) const {
        if (dis == other.dis) {
            return ix > other.ix;
        }

        return dis < other.dis;
    }
};

vector<node> disVec[15];

void run() {
    cin >> n;

    vector<pair<int, int>> f, g;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        f.push_back(make_pair(x, y));
    }

    for (int i = 0; i < n + 1; i++) {
        int x, y;
        cin >> x >> y;
        g.push_back(make_pair(x, y));
    }

    for (int i = 0; i < n; i++) {
        disVec[i].clear();

        for (int j = 0; j < n + 1; j++) {
            dis[i][j] = calcDis(f[i].first, f[i].second, g[j].first, g[j].second);
            disVec[i].push_back(node{
                    .ix = j,
                    .dis = dis[i][j],
            });
        }

        sort(disVec[i].begin(), disVec[i].end());

        while (!disVec[i].empty() && disVec[i].back().ix != 0) {
            disVec[i].pop_back();
        }

        disVec[i].pop_back();
        if (disVec[i].empty()) {
            cout << "IMPOSSIBLE\n";
            return;
        }
    }

    vector<int> h;
    h.reserve(n);
    for (int i = 0; i < n; i++) {
        h.push_back(i);
    }

    vector<pair<int, int>> res;
    res.reserve(n);

    do {
        res.clear();
        memset(vis, 0, sizeof(vis[0]) * (n + 1));

        int all_ok = 1;

        for (int i = 0; i < n; i++) {
            int ok = 0;

            for (const auto &d : disVec[h[i]]) {
                if (vis[d.ix]) {
                    continue;
                }

                res.emplace_back(make_pair(h[i] + 1, d.ix + 1));
                vis[d.ix] = 1;
                ok = 1;
                break;
            }

            if (ok == 0) {
                all_ok = 0;
                break;
            }
        }

        if (all_ok) {
            cout << "POSSIBLE\n";

            for (const auto &r : res) {
                cout << r.first << " " << r.second << "\n";
            }

            return;
        }
    } while (next_permutation(h.begin(), h.end()));

    cout << "IMPOSSIBLE\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);

    int _T = 0;
    cin >> _T;
    for (int i = 1; i <= _T; ++i) {
        cout << "Case #" << i << ": ";
        run();
    }

    return 0;
}

I, O Bot

题意：

在一个一维平面上，有 个 ball，然后一辆收集车从 开始出发，移动一单位需要花费 单位的能量。

ball 有两种形状，0 形状和 1 形状。

收集车上有两个容器，其中一个容器能装 0 形状的 ball，另一个容器能装 1 形状的 ball。

但是可以花费 单位的能量将一个形状的 ball 变成另外一个形状。

收集了 ball 之后，收集车可以回到 位置储存球。

问将所有球都收集到 位置最少需要多少单位的能量？

思路：

考虑，正负坐标轴是两个独立的子问题，分开做。

在比赛时想了个错误做法。

表示处理完前 个位置， 有三种状态，分别为 。

• 表示还剩一个 0 形状的 ball 还没收集。
• 表示还剩一个 1 形状的 ball 还没收集。
• 表示前 个 ball 收集完了。

然后 dp 即可。

但是这样会发现样例中的 case2 都过不了。因为它是留了两个 0 形状的 ball，和后面两个 1 形状的 ball，分别组合一起，进行两趟回收。

问题可能出在只维护剩一个 0/1 形状的 ball 的状态可能不够。但是如果维护的数量大了，空间复杂度又顶不住。

Wrong Code

#include <bits/stdc++.h>
#include <algorithm>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <limits>
#include <utility>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

// head
const int N = 1e5 + 10;
int n, C;

struct node {
    int x;
    int v;

    bool operator<(const node &other) const {
        return x < other.x;
    }
};

ll gao(vector<node> &v) {
    int m = v.size();

    v.emplace_back(node{
            .x = -1,
            .v = 0,
    });

    sort(v.begin(), v.end());

    vector<vector<ll>> f(m + 1, vector<ll>(3, 1ll * 10000 * 1e9));

    f[0][2] = 0;

    for (int i = 1; i <= m; i++) {
        ll baseCost = 1ll * v[i].x * 2;

        for (int j = 0; j <= 2; j++) {
            f[i][j] = min(f[i][j], f[i - 1][j] + baseCost);
        }

        f[i][v[i].v] = min(f[i][v[i].v], f[i - 1][2]);

        f[i][2] = min(f[i][2], f[i - 1][v[i].v ^ 1] + baseCost);
        f[i][2] = min(f[i][2], f[i - 1][v[i].v] + baseCost + C);
    }

    return f[m][2];
}

void run() {
    cin >> n >> C;

    vector<node> f, g;
    for (int i = 0; i < n; i++) {
        int x, v;
        cin >> x >> v;

        if (x < 0) {
            f.push_back(node{
                    .x = -x,
                    .v = v,
            });
        } else {
            g.push_back(node{
                    .x = x,
                    .v = v,
            });
        }
    }

    ll ans = 0;
    ans += gao(f);
    ans += gao(g);

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);

    int _T = 0;
    cin >> _T;
    for (int i = 1; i <= _T; ++i) {
        cout << "Case #" << i << ": ";
        run();
    }

    return 0;
}

留坑。

---

Last update: May 17, 2022
Created: May 15, 2022