ENCJMAY6 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Shekhar Srivastava
Testers: Sandeep Singh, Arnab Chanda

DIFFICULTY:

EASY

PREREQUISITES:

Sorting, hash-map

PROBLEM:

Some people ordered t-shirts of desired sizes to a factory but when t-shirts were received some of them were not of the same size as ordered. If N people have ordered t-shirts you will be given the details of orders in the following manner:

the value of N; N rows follow
[person’s ID] [the t-shirt they wanted] [the t-shirt they received]

Note: ID is an integer starting from 0(so last ID is N-1), t-shirt size is a character(uppercase A to Z) and the input is sorted by the value of ID.

you have to check if the issue can be solved if people exchange their t-shirts in some order. If the issue can be solved for all the people print “YES” else solve the issue for some people giving higher priority to people with smaller ID numbers and print the IDs of all the people who could not get their t-shirts in increasing order. And perform this task per test case.

EXPLANATION:

It is possible to solve the issue completely by performing exchanges if the total t-shirts ordered is the same as the t-shirts received. We can check this by making arrays of t-shirts ordered and t-shirts received if these arrays are equal then the answer is YES.

It would be better if we maintain two maps, the first map has size as keys and a list of IDs of people who ordered a t-shirt of that size, another map has size as keys, and a list of IDs of people who received t-shirt of that size. We iterate through all the keys in the first map, for every key/size if the list of people who ordered that t-shirt is larger than the list of people who received that t-shirt then the issue cannot be solved completely.

Suppose the size of the list of people who ordered a t-shirt of size X is A and size of the list of people who received t-shirt of size X is B and A>B then the issue is solved for B people with smallest IDs in the ordered list and we keep rest of the IDs in an array Fails. In the end, if the array Fails is not empty then we print its size and its elements in sorted order otherwise the answer is YES.

SOLUTIONS:

Setter's Solution
from collections import defaultdict as dd
for tc in range(int(input())):
    n = int(input())
    ordered = dd(list)
    received = dd(list)
 
    for i in range(n):
        i,o,r=input().split()
        ordered[o].append(int(i))
        received[r].append(int(i))
 
    fails = []
    for size in ordered.keys():
        if len(ordered[size])>len(received[size]):
            fails.extend(ordered[size][len(received[size]):])
 
    if len(fails)==0: print('YES') 
    else: 
        print(len(fails))
        print(*sorted(fails)) 
Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for( i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for( i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define MAX 100005
using namespace std;
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////
 
void solve(){
 
    unordered_map<char, int> cnt;
 
    unordered_map<int, char> sz;
 
    int i, n, id;
    char a, b;
    cin >> n;
    vector <int> ans;
 
    for(i = 0; i < n; ++i){
        
        cin >> id >> a >> b;
        sz[id] = a;
        ++cnt[b];
    }
 
    for(i = 0; i < n; ++i){
        if(cnt[sz[i]])
            --cnt[sz[i]];
        else
            ans.push_back(i);
    }
    if(ans.empty())
        cout<<"YES"<<endl;
    else{
        cout<<ans.size()<<endl;
        for(int x : ans)
            cout << x <<" ";
        ln;
    }
 
 
    
 
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif
    int t;
    cin>>t;
    while(t--)
        solve();
} 
2 Likes