We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. Salary Blues
  5. Discussions

Salary Blues

Sort by

recency

|

30 Discussions

|

  • xavi_aclm
     + 0 comments

    1) The salaries after normalization are actually just the gcd - note the process is reminiscent of the naïve euclidean algorithm, or that it preserves divisors + reduces numbers until everything is equal => everything ends up at an equal number which is divided by every divisor of the original set, which is the gcd

    2) gcd(a1+k, a2+k, ..., an+k) = gcd(a1+k, (a2+k)-(a1+k), ..., (an+k)-(a1+k)) = gcd(a1+k, a2-a1, ..., an-a1) = gcd(a1+k, gcd(a2-a1, an-a1)). You can precompute the second bit of the gcd and then you only have to do a gcd with two elements for each of the queries, which is fast enough to pass.

  • CS_2212256_T
     + 0 comments
    import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int Q = sc.nextInt();

		long[] A = new long[N];
		for (int i = 0; i < A.length; i++) {
			A[i] = sc.nextLong();
		}

		long diffsGCD = computeDiffsGCD(A);

		for (int tc = 0; tc < Q; tc++) {
			int K = sc.nextInt();
			System.out.println(gcd(diffsGCD, A[0] + K));
		}

		sc.close();
	}

	static long computeDiffsGCD(long[] A) {
		long diffsGCD = Math.abs(A[1] - A[0]);
		for (int i = 2; i < A.length; i++) {
			diffsGCD = gcd(diffsGCD, Math.abs(A[i] - A[i - 1]));
		}
		return diffsGCD;
	}

	static long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a % b);
	}
}

  • acnoidcommunity
     + 0 comments

    Actors' salaries are often a topic of debate. Like in HackerX, equalizing salaries may avoid disputes. However, industry norms and individual agreements must be considered to ensure fairness.

  • chjames655
     + 0 comments

    I appreciate the detailed explanation and the use of the gcd identities. However, could you elaborate on how the constant time update is achieved in practical scenarios? Are there specific applications or examples where this approach is particularly advantageous? I'm curious to understand the real-world implications of applying these identities to reduce computation time.

  • ks6831084
     + 0 comments

    // C++ 20........solution

    const int N = 100000; long long arr[N];

    long long gcd(long long a, long long b) { if(a < 0){ a = -a; }

    if(b < 0){
    b = -b;
} 

if(b>0){
      return gcd(b, a % b);

}
else{
    return a;
}

    }

    int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 

    int n, q; 
    cin >> n;
    cin>> q;
long long int  x;


for(int i = 0; i < n; ++i) {
  cin >> x;
  arr[i] = x;
}


long long int  d = 0;

for(int i = 0; i < n; ++i)
    d = gcd(d, arr[i] - arr[0]);

while(q>0)
{
    int k; cin >> k;
    cout << gcd(d, arr[0] + k) << '\n';
            q--;
}

    return 0;
    }



return 0;

    }