Hii Everyone, I just needed help in understanding what went wrong in my solution to the given question: 1922D - Berserk Monsters
The submission fails for the second test case and is long enough not to be able to see the difference: 242453785
The Code:
The Code with added comments for understanding:
static void solve(IO io) throws IOException {
int[] params = io.readIntArray();
int n = params[0];
// int k = params[1];
long[] attack = io.readLongArray();
long[] defence = io.readLongArray();
TreeSet<Integer> alive = new TreeSet<>();
// Using ordered set for left closest and right closest alive member
for (int i = 0; i < n; i++) {
alive.add(i);
}
HashSet<Integer> active = new HashSet<>();
// Active members are different from alive members
//We should not traverse each monster repeatedly if we know the neighbours do not kill them and do not change either.
//This reduces redundancy and complexity
active.addAll(alive);
for (int i = 0; i < n; i++) {
HashSet<Integer> dead = new HashSet<>();
// Dying members of each round
HashMap<Integer, Long> damage = new HashMap<>();
// Damage dealt on every person each round
for (Integer j : active) {
// Logic for dealing damage to the closest left and right
Integer prev = alive.lower(j);
Integer next = alive.higher(j);
damage.put(next, damage.getOrDefault(next, 0l) + attack[j]);
damage.put(prev, damage.getOrDefault(prev, 0l) + attack[j]);
}
for (Integer j : damage.keySet()){
// if damage surpasses defence, kill the monster
if(j != null && damage.get(j) > defence[j]){
dead.add(j);
}
}
for(Integer j: dead){
// removing the dead monsters from the alive list
alive.remove(j);
}
active.clear();
// checking active members for the next round
// active members are members who are alive and with different neighbours in the next round than the previous round
for (Integer j : dead) {
if(alive.lower(j) != null){
active.add(alive.lower(j));
}
if(alive.higher(j) != null){
active.add(alive.higher(j));
}
}
io.append(dead.size());
}
io.newLine();
}