12 days ago

Rohit • 40

Hyderabad

Question: Reorder It

Problem Statement:

You are given two arrays A, B of length N and an integer denoting P which will be used for hashing.

An array C is formed as follows: c_i = (a_i + b_i) mod N. It is given that the length of C will be min(N, P). You can reorder one of the arrays A or B but not both.

You want the array C to be lexicographically smallest.

Your task is to print the hash of the resulting array C.

Note:

• Let C be 0-indexed, print the hash = Sum of (c[i]* P^i) mod{10^9+7}.

Input Format for Debugging:

• The first line contains an integer, N, denoting the number of elements in A.
• The next line contains an integer, P, denoting the base of the hash.
• Each line i of the N subsequent lines (where 0 <= i < N) contains an integer describing A[i].
• Each line i of the N subsequent lines (where 0<= i < N) contains an integer describing B[i].

13 hours ago

admin 1.9k

Sehore

Problem1 Solution -:

Reorder It Solution

Topics Involved / Prerequisites

• Greedy Algorithms
• Set / Multiset Data Structures
• Lexicographical Comparisons
• Modular Arithmetic and Polynomial Hashing

Overview

To make the resulting array C lexicographically smallest, we must greedily minimize C_0, then C_1, and so on. We are given the choice to either keep A fixed and reorder B, or keep B fixed and reorder A. Because the order of the fixed array determines the "priority" of which elements get optimized first, the two choices can yield different sequences for C.

Our approach is to simulate both scenarios:

1. Fix A, dynamically pick the best available elements from B.
2. Fix B, dynamically pick the best available elements from A.

To efficiently "pick the best available element", we can store the elements of the permuted array inside a balanced Binary Search Tree (like a std::multiset). For any fixed element X, the optimal element Y to pair it with such that (X + Y) \bmod N is minimized would be Y = (N - X) \bmod N. We can use lower_bound on the multiset to find the closest available element \ge Y. If no such element exists, we wrap around and pick the absolute smallest available element.

After generating both possible arrays for C, we compare them lexicographically up to length min(N, P) and compute the polynomial hash of the smaller one.

.Code Implementation (C++)

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

// Helper function to greedily find the best array C given a fixed array and a permutable array
vector<long long> get_best_C(const vector<long long>& fixed_arr, const vector<long long>& perm_arr, long long N) {
    multiset<long long> ms;
    for (long long val : perm_arr) {
        ms.insert((val % N + N) % N); // Ensure purely positive modulo
    }
    
    vector<long long> C(N);
    for (int i = 0; i < N; i++) {
        long long X = (fixed_arr[i] % N + N) % N;
        long long target = (N - X) % N;
        
        // Find the smallest element Y >= target
        auto it = ms.lower_bound(target);
        
        // If no such element exists, wrap around to the absolute smallest available element
        if (it == ms.end()) {
            it = ms.begin();
        }
        
        long long Y = *it;
        C[i] = (X + Y) % N;
        ms.erase(it);
    }
    
    return C;
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long N, P;
    if (!(cin >> N >> P)) return 0;

    vector<long long> A(N);
    vector<long long> B(N);

    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];

    // Scenario 1: Fix A, reorder B
    vector<long long> C1 = get_best_C(A, B, N);
    
    // Scenario 2: Fix B, reorder A
    vector<long long> C2 = get_best_C(B, A, N);

  
    long long L = min(N, P);
    
    vector<long long> best_C(L);
    bool use_c1 = true;
    
    for (int i = 0; i < L; i++) {
        if (C1[i] < C2[i]) {
            use_c1 = true;
            break;
        } else if (C2[i] < C1[i]) {
            use_c1 = false;
            break;
        }
    }

    if (use_c1) {
        for (int i = 0; i < L; i++) best_C[i] = C1[i];
    } else {
        for (int i = 0; i < L; i++) best_C[i] = C2[i];
    }

    // Compute the polynomial hash of the best_C
    long long MOD = 1000000007;
    long long hash_val = 0;
    long long p_pow = 1;
    long long P_mod = P % MOD;

    for (int i = 0; i < L; i++) {
        long long term = (best_C[i] % MOD * p_pow) % MOD;
        hash_val = (hash_val + term) % MOD;
        p_pow = (p_pow * P_mod) % MOD;
    }

    cout << hash_val << "\n";

    return 0;
}

Time and Space Complexity

• Time Complexity-:O(N log N) — We iterate through the fixed arrays of length N, and at each step, querying and erasing from the multiset takes {O(log N) time.
• Space Complexity: O(N) — We need O(N) memory to store the sequences and the multiset