Header Ad

HackerEarth Number Recovery problem solution

In this HackerEarth Number Recovery problem solution A positive integer X has been stolen. But luckily, N hints are available, each described by two integers ai and di, meaning that |X - ai| = di. The hints are numbered 1 through N. While some of those hints are helpful, some might be just a lie. Therefore, we are going to investigate the number X under different possible scenarios.

Initially, we neither trust nor distrust any hint. That is, each hint may be either true or false. Then, in each of the Q stages, we will either:

1 id
Entrust the -th hint (1 <= id <= N). That is, from now on, the -th hint must be true, unless declared otherwise in the future.
2 id
Distrust the -th hint (1 <= id <= N). That is, from now on, the -th hint must be false, unless declared otherwise in the future.
3 id
Neutralize the -th hint (1 <= id <= N). That is, from now on, the -th hint may be either true or false, unless declared otherwise in the future.
After each stage, you should determine the number of possible positive values X and report such values in increasing order. If there are infinitely many such values, print -1 instead.


HackerEarth Number Recovery problem solution


HackerEarth Number Recovery problem solution.

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <assert.h>
#include <iostream>
using namespace std;

map<int, int> ok;
map<int, int> ban;

queue<int> q;

int main(){
int M, K;
scanf("%d%d", &M, &K);
vector<int> x(M+1), d(M+1);
vector<int> status(M+1, 0);
for(int i=1; i<=M; i++) scanf("%d%d", &x[i], &d[i]);
int entrusted = 0;
for(int i=0; i<K; i++){
int t, id;
scanf("%d%d", &t, &id);
int a = x[id]-d[id], b = x[id]+d[id];
if(status[id] == 1){
ok[a]--;
if(a != b) ok[b]--;
entrusted--;
} else if(status[id] == 2){
ban[a]--;
ban[b]--;
}
status[id] = (t == 3 ? 0 : t);
if(t == 1){
ok[a]++;
if(a != b) ok[b]++;
entrusted++;
q.push(id);
} else if(t == 2){
ban[a]++;
ban[b]++;
}
// get the answer
int idx = -1;
while(!q.empty()){
int x = q.front();
if(status[x] == 1){
idx = x;
break;
}
q.pop();
}
if(idx == -1) printf("-1\n");
else{
int a = x[idx]-d[idx];
int b = x[idx]+d[idx];
vector<int> res;
if(a > 0 && ok[a] == entrusted && ban[a] == 0) res.push_back(a);
if(b > a && ok[b] == entrusted && ban[b] == 0) res.push_back(b);
printf("%d", (int)res.size());
for(int i=0; i<res.size(); i++){
printf(" %d", res[i]);
}
printf("\n");
}
}
return 0;
}

Second solution

#include "bits/stdc++.h"
using namespace std;

map<int,int> bad, good;
multiset<vector<int>> good_pairs;

int main() {
int n, q;
scanf("%d%d", &n, &q);
vector<vector<int>> info(n);
for(int i = 0; i < n; ++i) {
int x, d;
scanf("%d%d", &x, &d);
info[i] = {x - d, x + d};
if(x - d == x + d) {
info[i].pop_back();
}
}
vector<int> state(n);
// bad: -1
// neutral: 0
// trusted: 1
while(q--) {
int type, i;
scanf("%d%d", &type, &i);
--i;
// 1) erase the current state
if(state[i] == -1) {
for(int a : info[i]) {
--bad[a];
}
}
if(state[i] == 1) {
for(int a : info[i]) {
--good[a];
}
good_pairs.erase(good_pairs.find(info[i]));
}
// 2) add a new state
if(type == 1) state[i] = 1;
else if(type == 2) state[i] = -1;
else if(type == 3) state[i] = 0;
else assert(false);
if(state[i] == -1) {
for(int a : info[i]) {
++bad[a];
}
}
if(state[i] == 1) {
for(int a : info[i]) {
++good[a];
}
good_pairs.insert(info[i]);
}
if(good_pairs.empty()) {
puts("-1");
continue;
}
set<int> answer; // set doesn't count twice
for(int a : *good_pairs.begin()) {
if(!bad[a] && a > 0 && good[a] == (int) good_pairs.size()) {
answer.insert(a);
}
}
printf("%d", (int) answer.size());
for(int a : answer) {
printf(" %d", a);
}
puts("");
}
}

Post a Comment

0 Comments