HackerRank Number Theory – Ants – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Challenge: Ants

Subdomeniu: Number Theory (number-theory)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464755529

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/ants/problem

Cerinta

N ants are in a circular race. The length of the race is 1000 meters and ant number i is initially Vi meters far from starting point (point 0) of the race in clockwise order. All the ants walk with a speed of 0.1 meters per second, some of them walk in clockwise order, some in counter clockwise order. When two ants meet at a point, they say "Hi" to each other and both of them change their direction of walking to the opposite direction. This process is timeless, meaning they say "Hi" and change their direction in 0 seconds.

You are given the initial position of ants, you don't know their initial directions but you want to know how many times do they say "Hi" to each other after 1000000006 ( 10^9+6 seconds ). You need to find the initial walking direction of ants such that, c1+c2+c3+...+cn is maximized, where ci is the number of times ant number i say "Hi". Print this maximum value.

**Input:**  
The first line of the input contains an integer N, the number of ants. N is not greater than 100.  
Next line contains n numbers V1 , V2 , ... , VN. All Vi are non negative integers less than 1000. All Vi are distinct.

**Output:**  
On the only line of the output print an integer being the answer to the test.

**Sample Input**  
2  
0 500

**Sample Output**  
400000

**Explanation**  
In the example there are two ants, In case their direction is the same, they will never say hi to each other, in the other case they will say "Hi" to each other in times 2500, 7500,12500, ... , 999999750. so the result for an Ant would be (999997500 - 2500)/5000+1 = 200000. Hence the answer is 200000\*2 = 400000.

Cod sursa

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];

    // Constants from statement.
    const long long T = 1000000006LL;
    const long long baseMeetPerOppositePair = T / 5000LL; // 200000

    // Bonus +1 happens only when clockwise distance from CW ant to CCW ant is 1 meter.
    // Build directed edge i -> j if v[j] == (v[i] + 1) mod 1000.
    unordered_map<int, int> idx;
    idx.reserve(n * 2 + 1);
    for (int i = 0; i < n; ++i) idx[v[i]] = i;

    vector<int> out(n, -1), indeg(n, 0);
    for (int i = 0; i < n; ++i) {
        int want = (v[i] + 1) % 1000;
        auto it = idx.find(want);
        if (it != idx.end()) {
            int j = it->second;
            out[i] = j;
            indeg[j]++;
        }
    }

    // Decompose into directed paths (no cycle possible since n <= 100 < 1000 and step is +1 mod 1000).
    vector<char> vis(n, 0);
    vector<vector<int>> comps;

    for (int s = 0; s < n; ++s) {
        if (indeg[s] == 0 && !vis[s]) {
            vector<int> path;
            int x = s;
            while (x != -1 && !vis[x]) {
                vis[x] = 1;
                path.push_back(x);
                x = out[x];
            }
            comps.push_back(move(path));
        }
    }
    for (int s = 0; s < n; ++s) {
        if (!vis[s]) {
            vector<int> path;
            int x = s;
            while (x != -1 && !vis[x]) {
                vis[x] = 1;
                path.push_back(x);
                x = out[x];
            }
            comps.push_back(move(path));
        }
    }

    const long long NEG = -(1LL << 60);

    // Global knapsack over components: best bonus for exact number of CW ants.
    vector<long long> global(n + 1, NEG), nextGlobal(n + 1, NEG);
    global[0] = 0;
    int done = 0;

    for (const auto& path : comps) {
        int k = (int)path.size();

        // DP along a path: dpMinus[c], dpPlus[c]
        vector<long long> dpMinus(k + 1, NEG), dpPlus(k + 1, NEG);
        dpMinus[0] = 0; // first node is CCW
        dpPlus[1] = 0;  // first node is CW

        for (int i = 2; i <= k; ++i) {
            vector<long long> ndpMinus(k + 1, NEG), ndpPlus(k + 1, NEG);
            int prevLen = i - 1;
            for (int c = 0; c <= prevLen; ++c) {
                if (dpMinus[c] != NEG) {
                    // prev = CCW, current = CCW (no bonus)
                    ndpMinus[c] = max(ndpMinus[c], dpMinus[c]);
                    // prev = CCW, current = CW (no bonus)
                    ndpPlus[c + 1] = max(ndpPlus[c + 1], dpMinus[c]);
                }
                if (dpPlus[c] != NEG) {
                    // prev = CW, current = CCW => bonus +1 on this edge
                    ndpMinus[c] = max(ndpMinus[c], dpPlus[c] + 1);
                    // prev = CW, current = CW (no bonus)
                    ndpPlus[c + 1] = max(ndpPlus[c + 1], dpPlus[c]);
                }
            }
            dpMinus.swap(ndpMinus);
            dpPlus.swap(ndpPlus);
        }

        vector<long long> best(k + 1, NEG);
        for (int c = 0; c <= k; ++c) best[c] = max(dpMinus[c], dpPlus[c]);

        fill(nextGlobal.begin(), nextGlobal.end(), NEG);
        for (int g = 0; g <= done; ++g) {
            if (global[g] == NEG) continue;
            for (int c = 0; c <= k; ++c) {
                if (best[c] == NEG) continue;
                nextGlobal[g + c] = max(nextGlobal[g + c], global[g] + best[c]);
            }
        }
        global.swap(nextGlobal);
        done += k;
    }

    auto totalSumCi = [&](int cw) -> long long {
        int ccw = n - cw;
        long long oppositePairs = 1LL * cw * ccw;
        long long bonus = global[cw];
        if (bonus < 0) return NEG;
        long long pairMeetings = oppositePairs * baseMeetPerOppositePair + bonus;
        return pairMeetings * 2LL;
    };

    long long ans = 0;
    if (n % 2 == 0) {
        ans = totalSumCi(n / 2);
    } else {
        ans = max(totalSumCi(n / 2), totalSumCi(n / 2 + 1));
    }

    cout << ans << '\n';
    return 0;
}

HackerRank Number Theory – Ants