AMR14D - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Editorialist: Lalit Kundu

DIFFICULTY:

CAKEWALK

PRE-REQUISITES:

Sorting

PROBLEM:

Given N dolls of size A1, A2 … AN.
A Matryoshka doll refers to a set of wooden dolls of strictly decreasing size, placed one inside the other. Any doll can contain only one doll directly inside it.
Output “YES” if it is possible to nest them all and have one doll on the outside and “NO” otherwise.

EXPLANATION:

If any two dolls have same size, we can never nest them together. Otherwise, we just sort them in decreasing order and nest them.

So, we just have to check if there are any two numbers same in a list.
We can do this in many ways:

  1. sort and check adjacent elements. Complexity: O(N log N)
  2. check for each pair of i,j if Ai == Aj. Complexity: O(N * N)
  3. Mark flag[Ai], for all i and check each element of flag array. Complexity: O(MAX[Ai]).
  4. Use set from STL in C++ and keep inserting in order. If same element find already answer is NO. Complexity: O(N log N).

SOLUTIONS:

Setters’s solution

2

An alternate solution to the problem could be to hash each doll size to a hash table. A set of dolls can’t be placed inside one another if more than one doll is of the same size. Before inserting a value in the hash table we check whether it’s already present; if already present we can say the set of dolls can’t be placed inside one another.

There is no need to sort the doll sizes. This solution is O(N).

1 Like
3

yeah thats what i did, and thats what should be done

4

I did hashing. But its complexity would be dependant on the max size of the doll. The complexity will be O(MAX_DOLL_SIZE);

5

Use unordered_map for hashing. Complexity O(N)

6

#include
using namespace std;
main()
{
int t,p=1,hash[1000]={0},n,a,f,i;
cin>>t;
while(p<=t)
{f=0;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a;
hash[a]=++hash[a];
}
for(i=1;i<=100;i++)
if(hash[i]>1)
{f=1;
}
if(f==1)
cout<<“NO\n”;
else
cout<<“YES\n”;
for(i=0;i<1000;i++)
hash[i]=0;
p++;
}
}

7

what is wrong in this code .
it is giving wrong answer!!!

8

Buying through Art Gifted by God ensures the World Missions, Charities and Art Projects we support, receive 10% commission from the proceeds of the Sales. 5% will be allocated annually by the World Missions Committee of Christ Church, Cheltenham and 5% by the artists to Art Projects 2015/16. When you buy from Christian Art Gifts, your painting is packaged and delivered direct from the artist’s studio. All arranged ‘hassle free’ by ourselves.

9

you can you set, add the sizes to set and at last compare the size of set with total numbers of sizes. SET remove any duplicates items

10

i gor AC in Codechef but getting WA here

11

Python logic:

for _ in range(int(input())):
    n=int(input())
    l=[int(x) for x in input().split()]
    if n==len(set(l)):
        print("YES")
    else:
        print("NO")