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. Triple sum
  2. Discussions

Triple sum

Sort by

recency

|

220 Discussions

|

  • torexed
     + 0 comments

    Used set to remove duplicates and create order. Put data back into vectors to retrieve indices for upper bound checks.

    // Complete the triplets function below.
long triplets(vector<int> a, vector<int> b, vector<int> c) {
    long result = 0;
    std::set<int> setA{a.begin(), a.end()};
    std::set<int> setB{b.begin(), b.end()};
    std::set<int> setC{c.begin(), c.end()};
    
    std::vector<int> orderedA {setA.begin(), setA.end()};
    std::vector<int> orderedC {setC.begin(), setC.end()};
    
    for (const auto& itemB : setB)
    {
        auto idxA = std::upper_bound(orderedA.begin(), orderedA.end(), itemB);
        auto idxC = std::upper_bound(orderedC.begin(), orderedC.end(), itemB);
        auto aDiff = idxA - orderedA.begin();
        auto cDiff = idxC - orderedC.begin();
        result += aDiff * cDiff;
    }
    
    return result;
}

  • cherrymeteor
     + 0 comments

    javascript

    function triplets(a, b, c) {
  let cleanA = [...new Set(a)].sort((a, b) => a - b)
  let cleanB = [...new Set(b)].sort((a, b) => a - b)
  let cleanC = [...new Set(c)].sort((a, b) => a - b)

  let count = 0
  for (let i = 0; i < cleanB.length; i++) {
    let howManyA = cleanA.findIndex(v => v > cleanB[i])
    let howManyC = cleanC.findIndex(v => v > cleanB[i])
    if (howManyA == -1) howManyA = cleanA.length
    if (howManyC == -1) howManyC = cleanC.length
    
    count += howManyA * howManyC
  }
  return count
}

  • urossevkusic
     + 0 comments

    My algorithm works as follows:: 1. remove duplicates from all vectors (generate sets, then recreate vectors); note that the vectors are now sorted because std::set is an ordered collection 2. for all elements q in B, find the number of elements r in C such that q <= r using binary search, and store the results in vector. Also, generate a prefix sum of that vector starting from its end. 3. for all elements p in A, find the first element q in B such that p <= q. Simply add all triplets with q' >= q in B, that are now stored in the prefix sum array of B.

    long long triplets(vector<int> a, vector<int> b, vector<int> c) {
    std::set<int> ta(a.begin(), a.end());
    std::set<int> tb(b.begin(), b.end());
    std::set<int> tc(c.begin(), c.end());
    std::vector<long long> A(ta.begin(), ta.end()), B(tb.begin(), tb.end()), C(tc.begin(), tc.end());
    long long count = 0;
    std::vector<long long> pref(B.size());
    pref[B.size() - 1] = std::distance(C.begin(), std::upper_bound(C.begin(), C.end(), B[B.size() - 1]));
    for(int i = B.size() - 2; i >= 0; --i) {
        auto it = std::upper_bound(C.begin(), C.end(), B[i]);
        pref[i] = pref[i + 1] + std::distance(C.begin(), it);
    }
    
    for(int p : A) {
        auto it = std::lower_bound(B.begin(), B.end(), p);
        if(it == B.end()) continue;
        else count += pref[std::distance(B.begin(), it)];
    }
    return count;
}

  • cherrymeteor
     + 0 comments

    JS all pass

    function triplets(a, b, c) {
  let cleanA = [...new Set(a)].sort((x, y) => x - y)
  let cleanB = [...new Set(b)]
  let cleanC = [...new Set(c)].sort((x, y) => x - y)
  let count = 0

  for (let i = 0; i < cleanB.length; i++) {
    let numOfP = 0, numOfQ = 0
    for (let j = cleanA.length; j > 0; j--) {
      if (cleanA[j - 1] <= cleanB[i]) {
        numOfP = j
        break
      }
    }
    for (let j = cleanC.length; j > 0; j--) {
      if (cleanC[j - 1] <= cleanB[i]) {
        numOfQ = j
        break
      }
    }
    count += numOfP * numOfQ
  }
  return count
}

  • venom1724
     + 0 comments

    Completely unnecessary Treap implementation in C++

    This can be solved in 2 lines with python, but why do it when we can implement a binary search tree in C++ ourselves :)

    Python:

    a,c,b = sorted(set(a)), sorted(set(c)),set(b)
    return sum([bisect(a,i)*bisect(c,i) for i in b])

    C++:

    struct node{
    int v,p;
    uint64_t c;
    node* left, *right;
    node(int _v, int _p){c=1;v=_v;p=_p;left=right=nullptr;};
    inline static uint64_t getCount(node* x) {
        if(!x) return 0;
        return 1+(x->left?x->left->c:0)+(x->right?x->right->c:0); 
    }
    void update() {c=1+getCount(left)+getCount(right);}
    static void split(node* p, node*& l, node*& r, int val){
        if(!p) l=r=p;
        else if(p->v < val) split(p->right, p->right,r,val), l=p;
        else split(p->left, l, p->left, val), r=p;
        if(p) p->update();
    }
    static void insert(node*& p, node* x){
        if(!p) p=x;
        else if(x->p > p->p) split(p, x->left, x->right, x->v), p=x;
        else (p->v > x->v ? insert(p->left,x) : insert(p->right,x) );
        if(p) p->update();
    }
    static uint64_t lessThan(node* p, int val){
        if(!p) return 0;
        else if (p->v > val) return lessThan(p->left,val);
        else return 1+lessThan(p->right,val)+getCount(p->left);
    }
};

uint64_t triplets(vector<int> a, vector<int> b, vector<int> c) {
    sort(a.begin(),a.end());
    a.resize(distance(a.begin(),unique (a.begin(), a.end())));
    unordered_set<int> sa, sb, sc;
    node *ax=nullptr, *cx=nullptr;
    uint64_t ans = 0;
    for(auto x: a) node::insert(ax,new node(x,rand()));
    for(auto x: c) if(sc.insert(x).second) 
        node::insert(cx,new node(x,rand()));
    for(auto x: b) if(sb.insert(x).second) 
        ans+=node::lessThan(ax,x)*node::lessThan(cx,x);
    return ans;
}