QUIZPLAG - Editorial

editorial
, ,
1

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Daanish Mahajan
Tester: Manan Grover
Editorialist: Aman Dwivedi

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are an administrator of a popular quiz website. Every day, you hold a quiz on the website. Each user is allowed to attempt a quiz at most once. Each user has a unique id from [1, N]. Also, there are M admins for the contest having a unique id from [N+1, N+M]. Sometimes admins too attempt the quizzes for testing purposes. Thus, they may attempt a quiz multiple times

Given a list L of ids for the K total submissions, count the number of users who attempted the quiz more than once to disqualify them and return a list of their ids in ascending order.

EXPLANATION:

The problem is straightforward, it wants us to find the count of users who attempted the quiz more than once and return a list of their ids in ascending order.

Since we are given the list L of ids for the K total submissions, we can easily find the number of times the user had attempted the quiz. This can be done by creating the frequency array of size N where i^{th} element of array denotes the user which has id i.

Now, we can traverse the list L, and If the id of the submission is less than N (since id above than N are admins), we will increment the number of submissions for this id in our frequency array by 1.

Pseudo code for same 
// frequency array each intialized to 0
int freq[n+1]={};

// Traverse the list L
for(int i=0;i<k;i++)
{
  if(l[i]<=n)
    freq[l[i]]++;
}

Finally, traverse the frequency array, and if we find any id having more than 1 submission, then we need to disqualify this user and hence put this user id in our answer. At last, we output the number of users who were disqualified and their ids.

TIME COMPLEXITY:

O(K) per test case

SOLUTIONS:

Setter 
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
 
using namespace std;
 
int main()
{   
    int t; cin >> t;
    int n, m, k;
    while(t--){
        cin >> n >> m >> k;
        int f[n + m + 1]; memset(f, 0, sizeof(f));
        int x;
        for(int i = 1; i <= k; i++){
            cin >> x;
            f[x]++;
        }
        vector<int> ans;
        for(int i = 1; i <= n; i++){
            if(f[i] > 1)ans.pb(i);
        }
        int sz = ans.size();
        cout << sz;
        for(int i = 0; i < sz; i++){
            cout << " " << ans[i];
        }
        cout << endl;
    }
}
Tester 
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int> ans;
    int a[n+1] = {};
    for(int i = 0; i < k; i++){
      int temp;
      cin>>temp;
      if(temp > n){
        continue;
      }
      if(a[temp] == 1){
        ans.push_back(temp);
      }
      a[temp]++;
    }
    sort(ans.begin(), ans.end());
    cout<<ans.size()<<" ";
    for(int i = 0; i < ans.size(); i++){
      cout<<ans[i]<<" ";
    }
    cout<<"\n";
  }
  return 0;
}
Editorialist 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve()
{
  int n,m,k;
  cin>>n>>m>>k;
 
  map<int,int> m1;
 
  vector <int> ans;
 
  for(int i=0;i<k;i++)
  {
    int x;
    cin>>x;
 
    if(x<=n && m1[x]==1)
      ans.push_back(x);
 
    m1[x]++;
  }
 
  cout<<ans.size()<<" ";
  sort(ans.begin(),ans.end());
  for(auto itr: ans)
    cout<<itr<<" ";
  cout<<"\n";
}
 
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin>>t;
 
  while(t--)
    solve();
 
return 0;
}
4 Likes
2

#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n, m, k,count=0;
cin >> t;
int a[k];
while (t–)
{
cin >> n >> m >> k;
for (int i = 0; i < k; i++)
{
cin >> a[i];
}
map<int, int> mp;
for (int i = 0; i < k; i++)
{
mp[a[i]]++;
}
int j = 0;
vector arr;
for (auto i = mp.begin(); i != mp.end(); i++)
{
if(i->first<=n && i->second>1){
count++;
arr.push_back(i->first);
}
}
cout<<count<<" “;
for(auto& i:arr)
cout<<i<<” ";
count =0;
cout<<endl;
}
return 0;
};

Can someone tell why this code is showing segmentation fault?

3

It might be because of vector arr ,I think so it should be vectorarr

4

i have done the code on python can someone point out my mistake
def checking(n, m, k, listof):
listof.sort()

indexfind = 0

for i in range(0, len(listof)):
    if listof[i] >= n + 1:
        indexfind = i
        break



if indexfind== 0 :
    listofplayer =listof[:]
else :
    indexfind = indexfind + 1

    listofplayer = listof[0:indexfind]
map= {}
listinascending = []
removecount = 0

for i in listofplayer:
    if (len(map.keys()) == 0):
        f = 1
        map[i] = f
    else:
        if map.get(i):
            freq = map.pop(i)
            map[i] = freq + 1



        else:
            f = 1
            map[i] = f

for i in map.keys():
    if map.get(i) > 1:
        removecount = removecount + 1
        listinascending.append(i)
return removecount, listinascending

if name == “main”:

testcase = (int)(input())
while testcase > 0:
    n, m, k = [int(x) for x in input().split()]
    input_string = input()
    listof = input_string.split()
    for i in range(len(listof)):
        listof[i] = int(listof[i])
    if len(listof) == k:
        nofdisqualify, list2 = checking(n, m, k, listof)
        print(nofdisqualify, end=" ")
        for i in  list2:
            print(i, end=" ")

    testcase = testcase - 1
8

Anyone, please help me with this, I tried to debug this for like hours but still can’t figure out why its not working

 #include
 using namespace std;

 int main() {
 int t,n,m,k;
 cin >>t;
 while(t–){
 cin >> n >> m >> k;
 int count[n+1] = {0};
 int cm,num;


    for(int i=0;i<k;k++){

        cin >> num;

        if(num <= n){

            count[num]+=1; 

        }

    }

    for(int i=1;i<=n;i++){

        if(count[i] >1){

            cm++;

        }

    }

    cout << cm << " ";

    for(int i=1;i<=n;i++){

        if(count[i] >1){

            cout << i << " ";

            

        }

    }

    cout << endl;

}

return 0;


}
9

Simple and easy solution :slight_smile:

int t;
cin>>t;
while (t–) {
int n, m, k;
cin >> n >> m >> k;
int arr[k];
set s;
for (int i = 0; i < k; i++) {
cin >> arr[i];
}
sort(arr, arr + k);
for (int i = 0; i < k; i++) {
if (arr[i] <= n + m && arr[i] >= n + 1) {
continue;
} else {
if (arr[i] == arr[i + 1]) {
s.insert(arr[i]);
}
}
}
cout << s.size() << " ";
for (auto it : s) {
cout << it << " ";
}
cout << “\n”;
}

2 Likes
10

this is python3 code this is giving a TLE
can anyone help

import sys
def get_arr(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())

t=int(input())
for _ in range(t):
    N,M,k=get_ints()
    attempts=get_arr()
    user=[]
    attempt=[]
    for i in range(1,N+1):
        count=attempts.count(i)
        if count>1:
            attempt.append(i)
    print(len(set(attempt)),*attempt)
11

as mentioned in question, the series of input has a large constraint, so iterating over it using forloop for changing into int, counting separately will give TLE, so i suggest you to use listof=list(map(int,input().split())), this will map the input to integers while taking input and again while iterating for the frequency of occurrence, store them in dictionary data structure and you can simultaneously count the frequency as value and number as key.
Counting the frequencies in a list using dictionary in Python - GeeksforGeeks refer this website for how to store value and frequency of occurrence in single iteration

12

Why does this give TLE

#include
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int count =0,n,m,k,num;
string result = “”;
cin>>n>>m>>k;
int attempt[n+m+1] = {0};

while(k--)
{
    cin>>num;
    attempt[num]++;
  
    
}

for(int i =1;i <=n ; i++)
{
   
  if(attempt[i] > 1) 
  {
     result = result + " " + to_string(i);
      count++;
  }
}
cout<<count<<result<<endl;

}
int main() {

 int t;
 cin>>t;
while(t--)
{
solve();

}

return 0;

}

13

Amazing logic…short n crisp…i was making some mistakes but after finding ur logic I have made the corrections appropriately…i was just making my code more lengthy and complicated. Thank you. :blush: