JOKRBTMN - Editorial

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;
}

2 Likes

https://www.codechef.com/viewsolution/48969944
Can someone please help why I got wrong answer.

Can someone explain the question in a simple way .

1 Like

i also did not understand the question…

2 Likes

Ok, here is my attempt to explain:
u are given N M and L . Now N == number of colors and L is the given list. Now there are M lists
with size K. suppose M=2 and N=2 and L= 4. Now there are two lists as M=2 now let those lists be of size 2,3 (i.e K1= 2 and K2=3) now elements of K1 are (1,2) and K2 are (2,3). Now you are given a list L which is of size 4 (namely L) which has elements (1,2,2,3).

Now you have to check how many different lists have been used to make L.
here its given 1,2,2,3 Batman has a problem that he cannot distinguish between adjacent elements of a same list. So, when he sees L. since 1,2,2 all these elements belong to K1 he considers them as a single list while 3 is of list K2 so in total he sees L is made up of 2 lists total.

another example k1=(1) k2=(2) k3=(4) L= (1,2,4); here batman sees that everything is different so its made of 3 lists

3 Likes

Nope.

Can someone tell me why this code is not working?
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner scan = new Scanner(System.in);

	int t = scan.nextInt();
	while(t-- > 0)
	{
	    int n = scan.nextInt();
	    int m = scan.nextInt();
	    int l = scan.nextInt();
	    HashMap<Integer,Integer> map = new HashMap<>();
	    for(int i=0;i<m;i++)
	    {
	        int size = scan.nextInt();
	        for(int j=0;j<size;j++)
	        {
	            int val = scan.nextInt();
	            map.put(val,i);
	        }
	        
	    }
	    int lr[] = new int[l];
	    for(int i=0;i<l;i++)
	    {
	        lr[i] = scan.nextInt();
	    }
	    int counter = 1;
	    for(int i=1;i<l;i++)
	    {
	        if(map.get(lr[i])!=map.get(lr[i-1]))
	        {
	            counter++;
	        }
	    }
	    System.out.println(counter);
	    
	}
}
for _ in range(int(input())):
    n,m,l = map(int,input().split())
    d = dict()
    for idx in range(m):
        lst= list(map(int,input().split()))
        for i in lst[1:]:
            d[i] = idx
    s = list(map(int,input().split()))
    
    strip = ""
    for i in s:
        strip += str(d[i])
    arr = []
    for i in strip:
        if len(arr)==0:
            arr.append([i,1])
        elif(arr[-1][0]==i):
            arr[-1][1] += 1
        else:
            arr.append([i,1])
    print(len(arr))

Why I am getting wrong answer please someone debug my code?

Even I have done exactly the same but in python. I got the wrong answer. Is it the same with you?

Definitely got a lot of clarity dude. Thank you so much!

Try using array instead of hashmap. I also got WA when I used hashmap, and I still don’t get why it is WA.

I am getting WA when I used hashmap instead of array. Can someone explain why we can’t use hashmap?

Can anyone tell me why this solution isn’t acceptable?

#include<iostream>
using namespace std;
int main(){
    int t; cin >> t;
    while(t--){
        int n,m,l;
        cin >> n >> m >> l;
        int id[n+1];

        for(int i=0; i<n; i++){
            int k ; cin >> k;
            for(int j=0; j<k; j++){
                int x ;
                cin >> x;
                id[x] = i;
            }
        }

        int ct =0;
        int index =-1;
        for(int i=0; i<l; i++){
            int x ; cin >> x;

            if(index!= id[x]){
                index = id[x];
                ct++;
            }
        }
        cout << ct << endl;

    }
    return 0;
}

P.S: For ‘example custom input’ it’s giving the right answer but without that output is 0 & at submission ‘RE (SIGSEGV)’ !

yes, and I’m still confused why I got wrong answer

Hi! In your code u r taking input for n lists. but it is given that there are only m lists .
for(int i=0; i<n; i++) change it to i<m that might work

1 Like

Thanks, finally code works :slight_smile:
Also, I should define variables as long ;
Applied changes → solution accepted :smile:

1 Like

:slight_smile: