 # Extract Original Problem

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

pls share your approaches for above problem
contest is over now

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 (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) k-1 times, then the *next* smallest choice in A: that is -
//
//  the second-smallest element in s is equal to (k-1) * A + A
//
// from which we can easily deduce the next smallest item in A, A.
//
// 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, A, .... 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 + 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, A, ... 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, A, ... A[j-1], we can find A[j] by generating sortedChoices(j-2) (that is,
// all choices using only A ... 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;

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 = s.front() / K;
int numKnownElementsOfA = 1;

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

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;
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

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/gcd_above_calculated and calculate c=prodArr/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;
int y=prod;

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

}
suggest correct approach.