Determine if matrix exists or not [closed]

any help with optimizing following code to make it run faster.

Tried making function inline, tried cin.TIE(NULL), tried ios_base::sync_with_stdio(false);

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class gfg
{
public:
bool satisfiable(std::vector<int> a, std::vector<int> b) {
while (!a.empty()) {
std::sort(b.begin(), b.end(), std::greater<int>());
int k = a.back();
a.pop_back();
if (k > b.size()) return false;
if (k == 0) continue;
if (b[k - 1] == 0) return false;
for (int i = 0; i < k; i++)
b[i]--;
}
for (std::vector<int>::iterator i = b.begin(); i != b.end(); i++)
if (*i != 0)
return false;
return true;
}

};

int main()
{
gfg g;
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int r,c,n,cnt=0;
cin >> n;
while(cnt<n){
cnt++;
cin >> r >> c;
int x;
vector<int> a;
vector<int> b;
for(int i=0;i<r;i++){
cin >> x;
a.push_back(x);
}

for(int j=0;j<c;j++){
cin >> x;
b.push_back(x);
}

if(g.satisfiable(a,b)) cout << "YES\n";
else cout << "NO\n";
}

return 0;
}


Expected : Average 1s or less processing time per test case Actual : Average 2s to 2.5s processing time per test case

• Welcome to Code Review. This question is currently a "code dump". Please explain what task this code accomplishes. See How to Ask. – 200_success Jun 1 '19 at 5:15
• Did you try using a profiler? What did it say was taking up the time? Also, it would help to see an example of the input data. – user673679 Jun 1 '19 at 6:35
• As is typical with any performance related question, are you compiling with optimizations enabled? – 1201ProgramAlarm Jun 1 '19 at 18:38

General points:

• We need to include <functional> for std::greater<>.

• The gfg class has no state, so we can use a free function for satisfiable.

• Variables should be declared as close as possible to their point of use. If possible they should also be initialized to a valid value, and not a placeholder "invalid value". e.g. r, and c should be declared inside the outer while loop.

• Reading input can be made much neater by factoring it into a separate function. We should also check for errors by testing cin.fail().

Performance:

• There is no need to modify the vector a. We are just iterating through it in reverse, which can be done with... reverse iterators:

for (auto r = a.rbegin(); r != a.rend(); ++r) { int k = *r; ... }

• This means that satisfiable can take a by const reference and avoid copying it:

bool satisfiable(std::vector<int> const& a, std::vector<int> b) { ... }

• The vector b is modified inside the function, so we should still accept the parameter by value. However, since we don't use the vector in main afterwards we can still avoid copying it:

satisfiable(a, std::move(b))


Modified code:

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>

bool satisfiable(std::vector<int> const& a, std::vector<int> b) {

for (auto r = a.rbegin(); r != a.rend(); ++r) {

std::sort(b.begin(), b.end(), std::greater<int>());

int k = *r;

if (k > b.size()) return false;
if (k == 0) continue;
if (b[k - 1] == 0) return false;

for (int i = 0; i != k; ++i)
b[i]--;
}

auto is_zero = [] (int x) { return x == 0; };
return std::all_of(b.begin(), b.end(), is_zero);
}

{
int x = 0;
std::cin >> x;

if (std::cin.fail()) {
std::cout << "invalid input!\n";
exit(1);
}

return x;
}

int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);

int n = read_int();

for (int cnt = 0; cnt != n; ++cnt) {

int r = read_int();
int c = read_int();

std::vector<int> a;
for (int i = 0; i != r; ++i)

std::vector<int> b;
for (int j = 0; j != c; ++j)

std::cout << (satisfiable(a, std::move(b)) ? "YES" : "NO") << "\n";
}
}


These changes may not fix your performance issues. I suspect that with large inputs, most of the time will be taken up by std::sort (you should profile it and find out!). Without more details on what the algorithm does, or what the input looks like, it's hard to make further suggestions.

However, it looks like we don't need to sort the entire b vector with every iteration:

• If the item at k-1 is greater than the item at k before the decrement, it will be equal to the item at k after the decrement (i.e. the b vector is still sorted correctly).

• If the item at k-1 is equal to the item at k before the decrement, it will be less than the item at k after the decrement (i.e. the b vector is no longer ordered).

However, we still don't need to sort the whole vector, we can just move any equal items from k onwards to the correct point (perhaps using std::rotate). In this case you may also find the std::lower_bound and std::upper_bound algorithms useful.

• The Idea behind the program is to tell whether a matrix exists or not (yes or no) given list of values in each row and column For ex. 3 2 - dimensions 2 1 0 - row values 1 2 - col values YES (Matrix Exists) 3 3 - dimensions 3 2 1 - row values 1 2 2 - col values NO(Matrix wont Exists) – user202018 Jun 1 '19 at 11:29
• I tried above modified code by you ( with all suggested improvements by you however i was not able to get performance below 2s average, seems like the sort is bottelneck). maybe i am trying the wrong approach while sorting or doing it in wrong way can you please show the kind of sorting you are takling about. – user202018 Jun 1 '19 at 16:46