PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Daanish Mahajan
Tester & Editorialist: Aman Dwivedi
DIFFICULTY:
Simple
PREREQUISITES:
Hashing
PROBLEM:
Each color has an integer ID from 1 to N. There are M lists where each color belongs to exactly one list. Batman can distinguish colors belonging to different lists, but he cannot distinguish colors belonging to the same list.
Given a strip of L colors, find the different number of segments Batman will see as a result of his disability. Two positions of the strip are said to belong to the same segment if they are adjacent on the strip and Batman cannot distinguish their colors.
QUICK EXPLANATION:
-
In the given strip, replace the Color ID with the List ID to which the color belongs.
-
Remove the adjacent duplicates in the strip.
-
Output the count of the elements that are remaining in the strip.
EXPLANATION:
We need to find out the number of segments that Batman would be able to see in the given strip. Let us try to find out the starting point of each of the segments. It is quite clear that the number of starting points will be equal to the number of segments in the strip since each segment will have a unique starting point.
A segment will begin from index i of the strip if the colors present at indices i and i-1 belong to different lists. Because if they come from the same list, then they are considered to be part of the same segment and then i can’t be the starting point of a new segment.
So we are left with finding out the number of starting points possible. To do so, for every index i \in [2, L] we need to find out the list IDs for the colors present at the index i and at index i-1. One way is to check every list and find out which one this color belongs to. But this is slow enough to give us a TLE verdict.
We can improve our solution by using hashing. We can simply hash the Color ID with the List ID it belongs to. And then we can easily find out the List ID in constant time for any color. Then when we find the starting point we can simply increment our answer.
Note that the value of number of starting points (i.e. the variable that holds our answer) is initialized from 1, because the first color on the strip will always be the starting point of the first segment that batman can see.
TIME COMPLEXITY:
O(N+L) per test case.
SOLUTIONS:
Setter
#include<bits/stdc++.h>
using namespace std;
const int maxl = 1e5, maxn = 1e5, maxm = 1e5, maxt = 10;
int main()
{
int t; cin >> t;
while(t--){
int n, m, l; cin >> n >> m >> l;
int id[n + 1]; memset(id, 0, sizeof(id));
int tot = n;
for(int i = 0; i < m; i++){
int k; cin >> k; tot -= k;
int x;
for(int j = 0; j < k; j++){
cin >> x;
id[x] = i + 1;
}
}
assert(tot == 0);
for(int i = 1; i <= n; i++)assert(id[i] != 0);
int pid = 0, ans = 0, s;
for(int i = 0; i < l; i++){
cin >> s;
int nid = id[s];
if(nid != pid){
ans++;
}
pid = nid;
}
cout << ans << endl;
}
}
Tester
#include<bits/stdc++.h>
using namespace std;
#define int long long
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
void solve()
{
int n,m,l;
n=readIntSp(1,100000);
m=readIntSp(1,100000);
l=readIntLn(1,100000);
unordered_map <int,int> m1;
int sum=0;
for(int i=0;i<m;i++)
{
int k;
k=readIntSp(1,n);
sum+=k;
for(int j=0;j<k;j++)
{
if(j!=k-1)
{
int x;
x=readIntSp(1,n);
assert(m1[x]==0);
m1[x]=i;
}
else
{
int x;
x=readIntLn(1,n);
assert(m1[x]==0);
m1[x]=i;
}
}
}
assert(sum==n);
int a[l];
for(int i=0;i<l;i++)
{
if(i!=l-1)
a[i]=readIntSp(1,n);
else
a[i]=readIntLn(1,n);
}
int ans=1;
for(int i=1;i<l;i++)
{
if(m1[a[i]]!=m1[a[i-1]])
ans++;
}
cout<<ans<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
t=readIntLn(1,10);
while(t--)
solve();
assert(getchar()==EOF);
return 0;
}