SOPC009 Editorial

PROBLEM LINK:

Practice
Contest

Author: Shriram Chandran
Editorialist: Shriram Chandran

DIFFICULTY:

Medium

PREREQUISITES:

Data Structures.

PROBLEM:

Given a set of strings of size N, find the contiguous subset of size d with largest number of distinct elements.

EXPLANATION:

The problem is straightforward, the challenge just lies in the implementation.

We need a data structure that can store count of an element in O(logN) or faster, and insert and delete elements in O(logN) or faster.

For this, we use a set to store unique sorted values and a map to store frequency together. For the first d elements, we put them all in the set and store their frequency in the map. We initialise ans as the size of the set. From the next element, we add the current element at position i and increase it’s frequency, and we decrease the count of the element that was at position i-d. If the frequency is 0 on decreasing, we delete that value from the set.

At every step, we keep updating the value ans by set size if the set size is greater, since the answer is just the maximum size of set at any point.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n,d;
    cin>>n>>d;
    vector<string> e(n,"");
    map<string,int> m;
    set<string> events;
    for(int i=0;i<d;i++)
    {
        cin>>e[i];
        m[e[i]]++;
        events.insert(e[i]);
    }
    int ans=events.size();
    for(int i=d;i<n;i++)
    {
        m[e[i-d]]--;
        if(m[e[i-d]]==0)
            events.erase(e[i-d]);
        cin>>e[i];
        m[e[i]]++;
        events.insert(e[i]);
        if(events.size()>ans)
            ans=events.size();
    }
    cout<<ans<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}
1 Like

Instead of using set we can implement the solution using a single map<string,int> too . As soon as the frequency of a string becomes zero in the current window erase it from the map
Code-https://www.codechef.com/viewsolution/28393261

Yes, that will work too.

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

int main() {
long long t;
cin >> t;
while(t--) {
    long long n, k;
    cin >> n >> k;
    vector<string> v;
    map<string, int> mp;
    for(long long i = 0; i < n; i++) {
        string s;
        cin >> s;
        v.push_back(s);
    }
    for(long long i = 0; i < k; i++) {
        if(mp.count(v[i]) == 0)
            mp[v[i]] = 1;
        else
            mp[v[i]]++;
    }
    long long ans = mp.size(), siz = mp.size();
    for(long long i = k; i < n; i++) {
        if(mp.count(v[i]) == 0) {
            mp[v[i]] = 1;
            siz++;
        }
        else
            mp[v[i]]++;
        mp[v[i - k]]--;
        if(mp[v[i - k]] == 0)
            siz--;
        ans = max(ans, siz);
    }
    cout << ans << endl;
}
return 0;
}

Could anyone please tell why isn’t this solution working.

When mp[v[i-k]] becomes zero you need to erase v[i-k] from the map else it won’t be erased from the map and when you will invoke mp.count(v[i]) it will return true even if its frequency becomes zero

1 Like

Oh, yes. Forgot about that. Thanks for pointing out the mistake in my code.

1 Like

import java.util.*;
public class Main
{
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int count = 0; count < t; count++) {
int c = 1,max=1,run=0;
int n = sc.nextInt();
int d = sc.nextInt();
String[] a = new String[n];
for (int i = 0; i < n; i++) {
a[i] = sc.next();
}
for (int i = 0; i < n-1; i++)
{
if(a[i].compareTo(a[i+1])!=0)
{
c++;
run=1;
}
else
{
if(c>max)
max=c;
c=1;
run=0;
}
}
if(run==1)
{
if (c > max && max <= d) {
if (c > d)
max = d;
else
max = c;
}
System.out.println(max);
}

        else
            {

        if(max>d)
            System.out.println(d);
        else
            System.out.println(max);
         }
    }

                }
            }

please , someone look over my code and tell why they are not accepting the even after getting out all the expected outputs

I have same issues in my work prject. But I am beginner in programming. When I need to create app or get some advices I will applly to EffectiveSoft Corporation That developers helped me to make one blockchain app for android.