CFRTEST - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Utkarsh Lath
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are n people and the i_{th} of them wants a party on the d_i^{th} day. Devu can give at most one party in a day. What is the maximum number of people who can take parties from Devu?

SHORT EXPLANATION

  • Answer will be the number of distinct days.

EXPLANATION:

Since Devu can give only one party each day. So if more than one people want a party on a day, then he can give party to only one of them. Also, if nobody wants a party on a particular day, then Devu won’t give a party on that day. So it means that number of parties given by Devu will be number of days on which people are asking parties. In other words, it is equal to number of distinct elements in the array d.

Finding number of distinct elements in an array
There are a lot of ways of finding number of distinct elements in an array. The most basic idea is to maintain number of occurrences of of each element in the array and then our answer will be number of elements having non zero number of occurrences.

For maintaining count of elements in the array, we can make an look up array whose i-th element denotes number of occurrences of element i.

Pseudo Code

int cnt[101]; // (since 1 <= d_i <= 100)
// fill the cnt array.
for (int i = 1; i <= n; i++) {
	cnt[d[i]]++;
}
// Now check number of elements having non zero count.
int ans = 0;
for (int i = 1; i <= 100; i++) {
	if (cnt[i] > 0) {
		ans++;
	}
}

Time complexity of the above algorithm is \mathcal{O}(100 + n) which is \mathcal{O}(n).

Another way of finding number of distinct elements in the array
First let us sort the array d. Now, we can notice that all equal elements will appear continuously in the array. So, we will go from left to right in the sorted order and will count only first occurrence of each element.

Time complexity of this method will be \mathcal{O} (n log n)

Yet another way of finding number of distinct elements in the array
You can use STL (standard template library) data structure set which maintains only unique elements in the sorted order. So all we need to do is add all the numbers in the set and finally find the size of the set.

Pseudo Code

set st;
// insert all the array elements into the set
for (int i = 1; i <= n; i++) {
	st.insert(d[i]);
}
// Size of set can be found using .size() function
int ans = st.size();

Time complexity of each insertion in set is \mathcal{O}(log n). As we are inserting n elements in the array, so overall time will be \mathcal{O}(n log n)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

1 Like
2

An interesting modification of the problem would be:

Devu can give at most K parties every day, what is the maximum number of parties that Devu can give?

P.S. - I solved this problem by maximal bipartite matching (quite an overkill, I guess), so I happened to think of the above modification.

2 Likes
3

Short python code using set. I’m sure quite a few people must have used this though. So much for input. Else the logic is a 1 liner really :stuck_out_tongue:

tc=eval(input())
for j in range(tc):
    n=eval(input())
    s=input().split(' ')
    a=set() 
    for i in range(n): a.add(eval(s[i])) #Keep adding elements to set and print the size in the end
    print(len(a))
1 Like
4

Anyways, i see it’s been added to the editorial

5

Can somebody please tell me my mistake?
http://www.codechef.com/viewsolution/7019550

6

python 1 liner :

print(len(set(input().split())))

:smiley: