Extract Original Problem

https://practice.geeksforgeeks.org/contest-problem/extract-original/0/

pls share your approaches for above problem
contest is over now

@karangreat234 @guitarlover @code_25 @ssrivastava990 @ssjgz

1 Like

At a quick glance - looks conceptually similar to Hackerrank’s Repetitive K Sums.

Have a look at my solution to that to see if it can be adapted.

Edit:

Keep forgetting people might not have a Hackerrank account XD

// Simon St James (ssjgz) - 2019-04-15 21:45
#define SUBMISSION
#ifdef SUBMISSION
#define NDEBUG
#endif
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <sstream>
#include <cassert>

using namespace std;

class Choice
{
    public:
        Choice(int numIndices)
            : m_indices(numIndices)
        {
        }
        int& operator[](int i)
        {
            return m_indices[i];
        }
        const int& operator[](int i) const
        {
            return m_indices[i];
        }
        int numIndices() const
        {
            return m_indices.size();
        }
    private:
        vector<int> m_indices;
};

void findChoices(Choice& choice, int indexToChange, int maxValueOfIndex, vector<Choice>& destChoices)
{
    if (indexToChange == -1)
    {
        destChoices.push_back(choice);
        return;
    }

    for (int indexValue = 0; indexValue <= maxValueOfIndex; indexValue++)
    {
        choice[indexToChange] = indexValue;
        findChoices(choice, indexToChange - 1, indexValue, destChoices); 
    }
}

template<typename T>
using IncreasingPriorityQueue = std::priority_queue<T, std::vector<T>, std::greater<T>>;

int main(int argc, char* argv[])
{
    // Another one that "took me ages", in that I started thinking about it years ago and
    // then recently re-tried it, and figured it out fairly quickly.  At least part of 
    // the delay was due to going down a rabbit hole and trying to find rule/ pattern behind generating
    // the sequence of choices in non-decreasing order, which is entirely unnecessary.
    //
    // Can't believe it's worth 150 points(!)
    //
    // So: how do we begin to untangle this list s of choices and get the original set A that the
    // choices were drawn from? First, note that the smallest item in s must be the choice where
    // we choose the smallest item in A, k times - from this, we can deduce A[0] (let's assume
    // for convenience that A is sorted).
    //
    // What about the *next* smallest item in s - does this tell us anything? Yes: we can't choose the
    // smallest item in A k times any more, so the next smallest choice must be choosing the smallest
    // choice in A (i.e. A[0]) k-1 times, then the *next* smallest choice in A: that is - 
    //
    //  the second-smallest element in s is equal to (k-1) * A[0] + A[1]
    //
    // from which we can easily deduce the next smallest item in A, A[1].
    //
    // There's already a strategy beginning to form: sort s into ascending order, and see if we can 
    // use successive values in this list to deduce successive values of A.  How can we formalise this?
    //
    // Assume s is sorted (sort it if it is not!).  For any j, 0 <= j <= k-1, there must be an index 
    // in our sorted list where A[j] is chosen for the first time.  Call this index first(j).
    // What can we deduce about first(j)? 
    //
    // Firstly, by definition, all the values of s before first(j) are formed by choices drawn from
    // A[0], A[1], .... A[j - 1].
    //
    // Secondly, the value first(j) is the smallest choice that can be formed using A[j] (again, by
    // definition), and so it must be of the form:
    //
    //  s[first(j)] = (k - 1) * A[0] + A[j]                (*)
    //
    // from which we can easily deduce A[j].
    //
    // But how can we find the first(j)'s? The clue comes from the first part: imagine we generated 
    // all choices using A[0], A[1], ... A[j-1], and sorted them - call this sortedChoices(j-1).  We'd be able to pair off,
    // starting from the top, items in this list vs items in our sorted s.  What would happen at 
    // first(j)? We're suddenly incorporating A[j], but why? There are only two possible reasons:
    // either we've run out of elements of sortedChoices(j-1), or the next element in sortedChoices(j-1)
    // would be greater than the first choice than can be formed using A[j], either of which is 
    // easily detectable and so we can easily find first(j).
    //
    // So to recap: if we know A[0], A[1], ... A[j-1], we can find A[j] by generating sortedChoices(j-2) (that is,
    // all choices using only A[0] ... A[j-1], in sorted order); pairing them off one by one with s; and designating
    // the first mismatch (where either we run out of sortedChoices(j-2), or the next element of sortedChoices(j-2)
    // does not match the next element of s) as first(j), then deduce A[j] using the formula (*).
    //
    // Obviously, generating all of sortedChoices(0), sortedChoices(1), etc and iterating over this and s
    // each time we want to find the next first(j) is very inefficient, but we can do it all incrementally:
    // sortedChoices(j) is just sortedChoices(j-1) plus all choices where i_k == j merged in and re-sorted.
    // We can model this with a set, but actually, since we're pairing off elements of sortedChoices(j) with
    // elements of s, a priority_queue is easier: we can discard elements of sortedChoices(j) that
    // have already been paired off elements of s, which helps with the book-keeping.
    //
    // And that's about it! In the code, the sortedChoices array(s) is referred to as expectedValuesUsingKnownElements.

    int T;
    cin >> T;

    for (int t = 0; t < T; t++)
    {
        int N;
        cin >> N;
        int K;
        cin >> K;

        // Skip to next line, so we can read in s.
        cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

        // Read in and sort s.
        string sLine;
        getline(cin, sLine);
        istringstream sStream(sLine);
        vector<int64_t> s;
        int64_t x;
        while (sStream >> x)
        {
            s.push_back(x);
        }
        sort(s.begin(), s.end());

        // Build up choicesWithLastIndexEqualTo.
        Choice choice(K);
        vector<Choice> choices;
        findChoices(choice, K - 1, N - 1, choices);
        vector<vector<Choice>> choicesWithLastIndexEqualTo(N);

        for (const auto& choice : choices)
        {
            choicesWithLastIndexEqualTo[choice[K - 1]].push_back(choice);
        }

        // Extract first element.
        assert((s.front() % K) == 0);
        vector<int64_t> a(N);
        a[0] = s.front() / K;
        int numKnownElementsOfA = 1;

        IncreasingPriorityQueue<int64_t> expectedValuesUsingKnownElements;
        expectedValuesUsingKnownElements.push(K * a[0]);

        for (const auto x : s)
        {
            if (expectedValuesUsingKnownElements.empty() || expectedValuesUsingKnownElements.top() != x)
            {
                // This element x of s is not expected: therefore, it must be using the next unknown value of a,
                // which we can now deduce.
                const int64_t nextElementOfA = x - (K - 1) * a[0];
                a[numKnownElementsOfA] = nextElementOfA;
                // We now need to ensure that expectedValuesUsingKnownElements now contains precisely the set of 
                // elements where the last chosen index (i.e. i_k) is *at most* numKnownElementsOfA.
                // It is already (from previous passes) precisely the set of elements where the last chosen index 
                // is *at most* (numKnownElementsOfA - 1), which is a subset of what we want.
                // So, to avoid re-adding duplicates of values added in previous passes, we add precisely the values
                // where the last chosen index (i.e. i_k) *is equal to* numKnownElementsOfA.
                for (const auto& choice : choicesWithLastIndexEqualTo[numKnownElementsOfA])
                {
                    int64_t newValueUsingKnownElements = 0;
                    for (int i = 0; i < K; i++)
                    {
                        assert(choice[i] <= numKnownElementsOfA);
                        newValueUsingKnownElements += a[choice[i]];
                    }
                    expectedValuesUsingKnownElements.push(newValueUsingKnownElements);
                }
                numKnownElementsOfA++;
                if (numKnownElementsOfA == N)
                    break;
            }

            // We matched this expected element against x (possibly after just adding it!): discard it.
            expectedValuesUsingKnownElements.pop();
        }
        for (const auto x : a)
        {
            cout << x << " ";
        }
        cout << endl;
    }
}
1 Like

The product array is arranged in an order so no need of this actually

Before script:wrong answer.
But my approach is to calculate gcd of the first two number in the prodArr[] i.e. gcd(ab,ac) and then to calculate b=prodArr[1]/gcd_above_calculated and calculate c=prodArr[2]/gcd_above_calculated like that calculated others…

This is my solution
#include<bits/stdc++.h>
using namespace std;
int fn(int n1,int n2){
while(n1 != n2)
{
if(n1 > n2)
n1 -= n2;
else
n2 -= n1;
}
return n1;
}
int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int prod[n];
for(int i=0;i<n;i++){
cin>>prod[i];
}
int m=0;
for(int i=2;i<=n;i++){
if(i*(i-1)==2*n){
m=i;
break;
}
}
int ans[m];
int x=prod[0];
int y=prod[1];

	ans[0]=fn(x,y);
	for(int i=1;i<m;i++){
		ans[i]=prod[i-1]/ans[0];
	}
	for(int i=0;i<m;i++){
		cout<<ans[i]<<" ";
	}
	cout<<endl;
}

}
suggest correct approach.