Interview Question
Country: United States
#include<iostream>
#include<vector>
using namespace std;
int main(){
int x,y;
cin>>x>>y;
vector<int> gv(x+1);
vector<int> rv(y+1);
int ans = 0;
int slibings = y + 1;
int mxKid = 0;
for (int g=1 ; g<=x ; ++g) {
cin>>gv[g];
ans+=(gv[g]* slibings);
mxKid+=gv[g];
}
bool isOk= true;
for (int k=1 ; k<=y ; ++k){
cin>>rv[k];
if(rv[k] > mxKid) {
isOk = false;
}
}
Looks like Integer linear programming problem to me. I guess the interviewer expects you to use DP here. However an alternative and more fun approach would be to use a specialized tool like z3 in Python where this kind of problems are easy to express:
from z3 import *
X = 3
Y = 2
G = [1,2,1]
K = [3,4]
a = [[Int('a_{}_{}'.format(i,j)) for j in range(Y)] for i in range(X)]
s = Optimize()
s.add(And([a[i][j] >= G[i] for i in range(X) for j in range(Y)]))
s.add(And([a[i][j] <= K[j] for i in range(X) for j in range(Y)]))
for j in range(Y):
s.add(Or([a[i][j] == K[j] for i in range(X)]))
for i in range(X):
s.add(Or([a[i][j] == G[i] for j in range(Y)]))
s.minimize(Sum([a[i][j] for i in range(X) for j in range(Y)]))
if s.check() == unsat:
print (-1)
else:
print (simplify(sum([s.model()[a[i][j]] for j in range(Y) for i in range(X)])))
print ([[s.model()[a[i][j]] for j in range(Y)] for i in range(X)])
Output:
12
[[3, 1], [2, 4], [1, 1]]
#include<iostream>
- Anonymous September 06, 2019#include<vector>
using namespace std;
int main(){
int x,y;
cin>>x>>y;
vector<int> gv(x+1);
vector<int> rv(y+1);
int ans = 0;
int slibings = y + 1;
int mxKid = 0;
for (int g=1 ; g<=x ; ++g) {
cin>>gv[g];
ans+=(gv[g]* slibings);
mxKid+=gv[g];
}
bool isOk= true;
for (int k=1 ; k<=y ; ++k){
cin>>rv[k];
if(rv[k] > mxKid) {
isOk = false;
}
}
if (isOk) cout<<ans<<endl; else cout<<-1<<endl;
return 0; }