Hello,
The following code passes all the test cases for the exercice Transmutation
<https://codingcompetitions.withgoogle.com/codejam/round/0000000000007764/000000000003675c>
.
Can you confirm the complexity is O(M^2)? I did a lot of tests and I did
not quite understand why I need to check if quantity equals 0.
I changed it with an assert(quantity == 0) and it fails.
Another remark, when using a map inside the loop, I get a Compilation Time
Limit Exceeded whereas locally it's fine, is there any reason for that?
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <time.h>
#include <vector>
#define INF 1E9
#define INF64 1E18
using namespace std;
template<typename T> int remin(T& a,const T& b){if(b<a){a=b;return true;}
return false;}
template<typename T> int remax(T& a,const T& b){if(b>a){a=b;return true;}
return false;}
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
int T, M;
vector<ll> stocks;
vii r;
ll calc() {
vector<ll> needs(M+1);
needs[1] = 1;
int tries = 0;
ll ans = 0;
vector<ii> missings;
while (tries <= M) {
missings.clear();
for (int i = 1; i <= M; ++i) {
if (needs[i] > stocks[i]) {
missings.push_back(ii(i, needs[i] - stocks[i]));
}
}
if (missings.empty()) {
tries = 0;
ll quantity = INF64;
for (int i = 1; i <= M; ++i) {
if (needs[i] != 0) {
remin(quantity, stocks[i] / needs[i]);
}
}
for (int i = 1; i <= M; ++i) {
stocks[i] -= quantity * needs[i];
}
if (quantity == 0) return ans;
ans += quantity;
} else {
tries++;
for (auto p: missings) {
needs[p.first] -= p.second;
needs[r[p.first].first] += p.second;
needs[r[p.first].second] += p.second;
}
}
}
return ans;
}
int main(int argc, const char **argv) {
scanf("%d", &T);
for (int tt = 1; tt <= T; ++tt) {
scanf("%d", &M);
stocks.resize(M+1); r.resize(M+1);
for (int i = 1; i <= M; ++i) {
scanf("%d%d", &r[i].first, &r[i].second);
}
for (int i = 1; i <= M; ++i) {
scanf("%lld", &stocks[i]);
}
printf("Case #%d: %lld\n", tt, calc());
}
return 0;
}
Compilation Time Limit Exceeded
...
while (tries <= M) {
map<int, ll> missing;
...
Romain.
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/3dc0dd98-1ae8-4105-bc1a-4ea2a46b1a10%40googlegroups.com.
