Hello everybody,
I can't manage to solve the Chain Reactions problem. My solution seems to
work locally, passes the sample tests on site, but when it comes to the
real tests, I always get a runtime error.
I decided to build a graph for every test case, then generate all the
permutations of the chain reaction initiators and traverse the graph in
order relevant for each permutation.
I used a similar general code structure for other problems and it worked,
so I guess it is a problem with the solution's logic.
Below is my code in JS.
Any suggestions would be greately appreciated!
'use strict';
var readline = require('readline');
var rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
class NodeF {
constructor(f) {
this.back = false;
this.used = false;
this.f = f;
}
}
class Input {
constructor(strings) {
this.stringsInd = 0;
this.strings = strings;
}
getString() {
return this.strings[this.stringsInd++];
}
getStringArray(sep) {
return this.getString().split(sep);
}
getNumber() {
return parseInt(this.getString());
}
getNumberArray(sep) {
return this.getStringArray(sep).map(a => parseInt(a));
}
}
let permutatorMethod = (inpArr) => {
let res = [];
let doPermute = (array, g) => {
if (array.length === 0) {
res.push(g);
}
else {
for (let x = 0; x < array.length; x++) {
let current = array.slice();
let next = current.splice(x, 1);
doPermute(current.slice(), g.concat(next));
}
}
};
doPermute(inpArr, []);
return res;
};
let clearTree = (nodes) => {
nodes.forEach((node) => {
node.used = false;
});
};
let solve = (input) => {
let n = input.getNumber();
let fss = input.getNumberArray(' ');
let pss = input.getNumberArray(' ');
let nodes = [];
for (let i = 0; i < fss.length; i++) {
nodes.push(new NodeF(fss[i]));
}
for (let i = 0; i < pss.length; i++) {
if (pss[i] === 0) {
nodes[i].next = null;
}
else {
nodes[i].next = nodes[pss[i] - 1];
nodes[pss[i] - 1].back = true;
}
}
let nodeInitiators = nodes.filter(x => x.back === false);
let nodeInitiatorsPerms = permutatorMethod(nodeInitiators);
let permsMaxes = [];
nodeInitiatorsPerms.forEach((perm) => {
clearTree(nodes);
let maxSum = 0;
perm.forEach((ni) => {
let max = 0;
while (ni !== null && ni.used !== true) {
max = Math.max(ni.f, max);
ni.used = true;
ni = ni.next;
}
maxSum += max;
});
permsMaxes.push(maxSum);
});
return Math.max(...permsMaxes);
};
let main = (input) => {
let _numTests = input.getNumber();
for (let _id = 1; _id <= _numTests; ++_id) {
console.log('Case #' + _id + ': ' + solve(input));
}
};
function init() {
let strings = [];
rl.on('line', function (line) {
strings.push(line);
}).on('close', function () {
main(new Input(strings));
process.exit(0);
});
}
if (!module.parent) {
init();
}
//# sourceMappingURL=index.js.map
--
-- You received this message because you are subscribed to the Google Groups
Code Jam group. To post to this group, send email to
google-code@googlegroups.com. To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com. For more options, visit this group at
https://groups.google.com/d/forum/google-code?hl=en
---
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 google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/bbff8533-ad73-4b9d-8a72-6794831df987n%40googlegroups.com.
