Sort by

recency

|

7 Discussions

|

  • + 0 comments

    Is Python able to pass this? Even after I put in place a min-heap and utilized it for dijkstra pathfinding, I still crash on all tests but the initial one.

  • + 0 comments

    This is my python Solution

    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    # returns d, x, y so that gcd(a, b) = d and ax + by = d
    def extended_euclidean_alg(a,b):
        # starts out as p[0] = P_{-1}, p[1] = P_0 and same for q
        # in general it's the previous 2 terms, P_{i-1}, P_{i-2}
        p = [0, 1]
        q = [1, 0]
        counter = 1
        while b != 0:
            quo = a//b
            rem = a % b
            newP = quo*p[1] + p[0]
            newQ = quo*q[1] + q[0]
            p[0] = p[1]
            p[1] = newP
            q[0] = q[1]
            q[1] = newQ
            a = b
            b = rem
            counter = (counter + 1) % 2
        minusOne = (counter-1) % 2
        return a, q[0]*((-1)**minusOne), p[0]*((-1)**(counter))
    
    def leastSigBit(num):
        return (num & -num)
    
    # implementation of a Fenwick tree
    class PrefixSumTree(object):
        def __init__(self,array):
            l = len(array)
            self.sums = [0] * l
            for i in range(1,l):
                cl = i - leastSigBit(i)
                for j in range(cl+1,i+1):
                    self.sums[i] = (self.sums[i] + array[j]) % p
    
        def sum(self,i):
            sum = 0
            while i > 0:
                sum = (sum + self.sums[i]) % p
                i -= leastSigBit(i)
            return sum
    
        # adds toAdd to the ith element of array
        def add(self,i,toAdd):
            while i <= len(self.sums)-1:
                self.sums[i] = (self.sums[i] + toAdd) % p
                i += leastSigBit(i)
    
    p = 10**9 + 7
    
    def polynomialDivision(a, b, c, queries):
        res = []
        a_inv = extended_euclidean_alg(p, a)[2]
        x = -b*a_inv % p
        # if x != 0 then we have to build the sum tree
        if x != 0:
            l = len(c)
            # polyArray[i+1] = c[i]*x^i % p and polyArray[0] = 0
            polyArray = [0] * (l+1)
            polyArray[1] = c[0]
            # powsOfX[i] = x^i % p
            powsOfX = [1] * l
            for i in range(1,l):
                newPow = (powsOfX[i-1]*x) % p
                powsOfX[i] = newPow
                polyArray[i+1] = (c[i]*newPow) % p
            sumTree = PrefixSumTree(polyArray)
        for q in queries:
            if q[0] == 1:
                # compute how much we need to add for the sum
                toAdd = q[2]-c[q[1]]
                # update the array c with our new entry q[2]
                c[q[1]] = q[2]
                if x != 0:
                    # then we add the appropriate amount to our prefix sums.
                    # since sumTree keeps track of sum c_i * x^i we multiply by the 
                    # appropriate power of x
                    sumTree.add(q[1]+1,(toAdd*(powsOfX[q[1]])) % p)
            else:
                # remember c is zero indexed but sumTree is one indexed
                # so we do sum(q[2]+1) - sum(q[1]) instead of sum(q[2]) - sum(q[1]-1)
                pOfX = c[q[1]] if x == 0 else (sumTree.sum(q[2]+1) - sumTree.sum(q[1])) % p
                if pOfX == 0:
                    res.append("Yes")
                else:
                    res.append("No")
        return res
    
    
    if __name__ == '__main__':
        fptr = open(os.environ['OUTPUT_PATH'], 'w')
    
        nabq = input().split()
    
        n = int(nabq[0])
    
        a = int(nabq[1])
    
        b = int(nabq[2])
    
        q = int(nabq[3])
    
        c = [int(t) for t in input().rstrip().split()]
    
        queries = []
    
        for _ in range(q):
            queries.append([int(t) for t in input().rstrip().split()])
    
        result = polynomialDivision(a, b, c, queries)
    
        fptr.write('\n'.join(result))
        fptr.write('\n')
    
        fptr.close()
    
  • + 0 comments

    the method is easy, but the debugging took me forever. O(n + qlog(n)) using fenwick trees

    long long mod = 1000000007;
    
    long long extended_gcd(long long a, long long b, long long& x, long long& y) {
        if (a == 0) {
            x = 0;
            y = 1;
            return b;
        }
        long long x1, y1;
        long long gcd = extended_gcd(b % a, a, x1, y1);
        x = y1 - (b / a) * x1;
        y = x1;
        return gcd;
    }
    
    long long inverse(long long a, long long p) {
        long long x, y;
        long long g = extended_gcd(a, p, x, y);
        if (g != 1) {
            std::cout << "Inverse doesn't exist";
            return -666;
        } else {
            long long res = (x % p + p) % p;
            return res;
        }
    }
    
    void update(vector<long long>& fenwick, int i, long long value) {
        while (i < fenwick.size()) {
            fenwick[i] = (fenwick[i] + value) % mod;
            i = i + (i & -i);
        }
    }
    
    long long access(const vector<long long>& fenwick, int i) {
        long long sum = 0;
        while (i > 0) {
            sum = (sum + fenwick[i]) % mod;
            i = i - (i & -i);
        }
        return sum;
    }
    
    int main()
    {
        long long n, a, b, q, c, h, k, l;
        vector<long long> C;
        vector<long long> Xpower;
        vector<long long> fenwick = {0};
        cin >> n >> a >> b >> q;
        long long x = (mod - ((inverse(a, mod) * b) % mod)) % mod, temp = 1;
    
        for (int i=0; i < n; i++) {
            cin >> c;
            C.push_back(c);
            Xpower.push_back(temp);
            fenwick.push_back((c*temp) % mod);
            temp = (temp * x) % mod;
        }
        
        for (int i = 1; i < n + 1; i++) {
            int J = i + (i & -i);
            if (J < n + 1) fenwick[J] = (fenwick[J] + fenwick[i]) % mod;
        }
        
        for (int i=1; i <= q; i++) {
            cin >> h >> k >> l;
            if (h == 1) {
                update(fenwick, k + 1, (l*Xpower[k]) % mod - (C[k]*Xpower[k]) % mod );
                C[k] = l;
            }
            else if (h == 2) {
                long long partialSum = (access(fenwick, l + 1) - access(fenwick, k)) % mod;
                if (partialSum != 0 or (x == 0 and C[k] != 0)) cout << "No" << '\n';
                else cout << "Yes" << '\n';
            }
        }
    }
    
  • + 0 comments

    I worked sythentic division (very slow), reaching a point of root check -b/a and brute force computing sub polynomials (still too slow), then precomputing polynomial with possible root -b/a as a basis for root checking sub polynomials, and then integrating binary search tree on coefficient index updated values (per query) which is still too slow. Fenwick tree is a key prefix data structure for mutating polynomial coefficients and pertinent sub polynomials on query set. Recall summation difference between front and tail of sub polynomial, once polynomial array (including query updates) is computed and allows for rapid computation on subpolynomial summation series. Also worth noting this is computed (per large integers) on modulus p, so rationals on the set of reals need to be converted to integers mod p. That is computing for a/b compute b^-1 to compute a*b^-1%p.

  • + 0 comments

    here is hackerrank polynomial division solution