PROBLEM LINK:
Setter: priyansh2802
Tester: debrc
Editorialist: priyansh2802
DIFFICULTY:
Easy
PREREQUISITES:
Basic observation
PROBLEM:
Tanushree and her friends are organizing her college’s fest and she has invited none other than The local train to perform in her college, she is raising money by selling concert passes to people, now the problem is people are counterfeiting the passes and they are trying to enter the auditorium.
There are M seats present in the concert auditorium and there are N numbered people from 1 to N who are outside the auditorium.
Tanushree is given Q events of the following form:
- +i denotes that i enters the auditorium
- -i denotes that i leaves the auditorium
It is guaranteed in the input that each person from 1 to N enters at most once as well as leaves the auditorium at most once.
- There may be inconsistency when a person tries to enter with a pass that was already recorded (i.e a person with numbered pass already exists inside the auditorium)
- There may be inconsistency when a person tries to leave with a pass that was never recorded entering the auditorium
- There may be inconsistency if after q-queries the number of people entered the auditorium is greater than the number of seats
EXPLANATION
The answer is “Inconsistent” when one of the following happens
- When a person with id i wants to enter the auditorium (i.e +i) but a person with the same Id is already sitting inside
- When a person with Id i wants to leave (i.e -i) but that person never went inside acccording to Tanushree
-When the number of persons trying to enter the auditorium are greater than the capacity of the Auditorium
TIME COMPLEXITY
Time complexity is O(q) for traversing the number of queries.
SOLUTIONS:
Setter's Solution
C++
#include<iostream>
#include<bits/stdc++.h>
#define int long long int
using namespace std;
void solve();
int32_t main(void)
{
int t;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
int n,m,q;
cin>>n>>m>>q;
vector<pair<char,int>>quer;
int counter=0;
for(int i=0;i<q;i++)
{
char a;
int t;
cin>>a>>t;
quer.push_back(make_pair(a,t));
}
int res=0;
unordered_map<int,int>mp;
unordered_map<int,int>::iterator it;
for(int i=0;i<quer.size();i++)
{
if(quer[i].first=='+')
{
if(mp.find(quer[i].second)==mp.end())
{
counter++;
mp[quer[i].second]++;
}
else
{
res=1;
cout<<"Inconsistent"<<endl;
return;
}
}
else if(quer[i].first=='-')
{
if(mp.find(quer[i].second)==mp.end())
{
res=1;
cout<<"Inconsistent"<<endl;
return;
}
else
{
counter--;
// cout<<quer[i].second<<endl;
it=mp.find(quer[i].second);
mp.erase(it);
}
}
if(counter>m)
{
res=1;
cout<<"Inconsistent"<<endl;
return;
}
}
cout<<"Consistent"<<endl;
}
Tester's Solution
PYTHON 3.6
#import modules here
import math,sys,os
#from itertools import permutations, combinations
# from collections import defaultdict,deque,OrderedDict,Counter
# import bisect as bi
#import heapq
from io import BytesIO, IOBase
mod=10**9+7
# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
#input functions
def minp(): return map(int, sys.stdin.readline().rstrip().split())
def linp(): return list(map(int, sys.stdin.readline().rstrip().split()))
def inp(): return int(input())
def print_list(l):
print(' '.join(map(str,l)))
def yes():
print("YES")
def no():
print("NO")
# functions
# def BinarySearch(a,x):
# i=bi.bisect_left(a, x)
# if i != len(a) and a[i] == x:
# return i
# else:
# return -1
# def gcd(a,b):
# return math.gcd(a,b)
# def is_prime(n):
# """returns True if n is prime else False"""
# if n < 5 or n & 1 == 0 or n % 3 == 0:
# return 2 <= n <= 3
# s = ((n - 1) & (1 - n)).bit_length() - 1
# d = n >> s
# for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
# p = pow(a, d, n)
# if p == 1 or p == n - 1 or a % n == 0:
# continue
# for _ in range(s):
# p = (p * p) % n
# if p == n - 1:
# break
# else:
# return False
# return True
# def mulinverse(a):
# return pow(a,mod-2,mod)
####################Let's Go Baby########################
for _ in range(inp()):
n,m,q=minp()
queries=[]
for i in range(q):
queries.append(input().split())
queries[-1][1]=int(queries[-1][1])
count=0
d={}
flag=1
for i in queries:
if i[0]=="+":
if i[1] not in d:
d[i[1]]=1
else:
if d[i[1]]==0:
d[i[1]]=1
else:
break
count+=1
else:
if i[1] not in d:
break
else:
if d[i[1]]==0:
break
else:
d[i[1]]=0
count-=1
if count>m:
break
if count<0:
break
else:
flag=0
if flag:
print('Inconsistent')
else:
print('Consistent')