RRCOPY - editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Roman Rubanenko
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa

DIFFICULTY:

Cakewalk

PREREQUISITES:

Simple Array.

PROBLEM:

For a given array, you can copy one segment of the array and paste it anywhere.
You are given the final array A after copy paste operations, find the minimum size of initial array.

Explanation

It looks like answer of the problem is number of distinct number in the array.

Yes, you are right. Let us prove it.

If the initial array is containing all the distinct numbers, we can generate our
the array A by applying copy paste operations.
We will simply iterate over each distinct numbers and place it in its correct positions. You can see
its resemblance with insertion sort.

Can you take some example?
Yes, take the example. Let A = [3 1 2 1 2 3].
Let assume that our initial array is a: Initially it will contain all the distinct elements ie. a = [1 2 3].
Now let us iterate over each distinct numbers.
Start with 1.
Add 1 between 1 and 2.
a = [1 1 2 3]
Now we go to 2.
Add 2 between 1 and 1.
a = [1 2 1 2 3]
Now we go to 3.
Add 3 in the beginning.
a = [3 1 2 1 2 3]
Now we notice that we have generated the array we wanted to generate ie. a is same as A.

Got it, How to find number of distinct numbers in the array?

Finding number of distinct numbers in array can be done by following ways.

  • As the range of integers in A is small (1 <= A[i] <= 10^5). So we can create a lookup array and update the information of numbers in a single pass of the
    array. Let us say lookup array is denoted by cnt. We will iterate over the array and update the cnt of the numbers. Finally number of distinct numbers will be
    equal to positions having their cnt values positive.
  • Using set in C++. We can use HashSet, TreeSet etc in Java.

Pseudo Code 1


	// create the lookup array and initialize it with value 0;
	int cnt[100001] = {0}
	for (int i = 0; i < n; i++)
	{
		// update the cnt array
		cnt[A[i]]++;
	}
	int ans = 0;
	for (int i = 1; i <= 100000; i++)
		if (cnt[i] > 0)
			ans++;

Pseudo Code 2


	set<int> s;
	for (int i = 0; i < n; i++)
		st.insert(A[i]);
	int ans = st.size();

Few Small Points

  • Array of size cnt should be 10^5 + 1, not 10^5.

Complexity:
In case of using set, Each insertion option takes O(log n) times, So overall time complexity for n insertions will be O(n log n).

In case of using lookup array, We just need a single pass over the array A and then we need to check for 10^6 values whether they cnt value is positive
or not. So overall time complexity will be O(max(n, 10^5)).

AUTHOR’S and TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

4 Likes
2

I think you mixed up the Problem Links. RRSUM Editorial links to RRCOPY and vv. Same with solution links i think.

1 Like
3

changed, ty for notifying :slight_smile:

4

why this not accepted

#include <bits/stdc++.h>
#define max  100015
using namespace std;
int main () {
int t,d,n;
//vector<int>v;

scanf("%d", &t);
while(t --) {
long int arr[max] ={0};  
scanf("%d", &n);
for (int i = 0;i < n;i ++) {

	scanf("%d", &d);
	arr[d]++;

}
long int ans = 0;
for(int i = 0;i <= max ;i++) {
//	printf(" %d ",arr[i]);
    if(arr[i]>= 1)
      ans += 1;
    
 }
printf("%d\n", ans);
//v.clear();

}

return 0;
}
5

array size should be 10^6+1, not of the order of 10^5

6

I think its still not changed.

7

Sorry for the extra work. I would have changed it myself but thought it would be better if you did it as you would know everything properly.

8

The array size is fine. I think the problem is in the statement long int arr[max] ={0}; Try initializing to zero using a for loop and see. It should work. @dpraveen In the question range of A is given upto 10^5 and not 10^6.

9

i did not understand why should size of array be 10^5 + 1, not 10^5 in pseudo code 1?
since, 1 <= A[i] <= 10^5 shouldn’t it be 10^5 …

10

it will cause a memory leak…an array starts with element 0, so either u subtract 1 from every calculation or just increase the size by 1 so that A[10^5] element can be accessed!

1 Like
11

thanks bro, i got it :slight_smile:

12

problem is in this line
for(int i = 0;i <= max ;i++)

13

why is this not accepted?

#include<stdio.h>
void quicksort(long long int a[],long long int f,long long int l)

{

long long int i,j,pivot,temp;

if(f<l)

{

	i=f;

	j=l;

	pivot=f+2;

	while(i<j)
	{

		while((a[i]<=a[pivot])&&(i<=l))
		i++;

		while((a[j]>a[pivot]))
		j--;

		if(i<j)
		{
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}

	}
	temp=a[j];
	a[j]=a[pivot];
	a[pivot]=temp;
	quicksort(a,f,j-1);
	quicksort(a,j+1,l);

}

}

main()
{

long long int t,n,i,j,c;
scanf("%lld",&t);
for(i=0;i<t;i++)
{
	c=0;
	scanf("%lld",&n);
	long long int a[n];
	for(j=0;j<n;j++)
	scanf("%lld",&a[j]);
	quicksort(a,0,n-1);
	j=0;

	while(j<n)
	{
		if((i==n-1)||(a[j]!=a[j+1]))
		c++;
		j++;
	}

	printf("%d\n",c);
}
return 0;

}

14

Hi my code gives a wrong answer, although I can’t find any error :-

    #include <iostream>

using namespace std;

int a[100000], seen[100001];

void initSeen()

{

    for (int i = 0; i <= 100000; ++i)

        seen[i] = 0;

}

int main()

{

int t, n, ctr;

    cin >> t;

    while (t--)
    {
        cin >> n;

        initSeen();
        ctr = 0;

        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];

            if (!seen[a[i]])
            {
                ++ctr;
                seen[a[i]] = 1;
            }

        }

    cout << ctr << '\0';
    }

    return 0;

}
15

You did a very silly mistake. Your code is absolutely correct .You are getting a wrong answer because in your cout statement you should replace ‘\0’ with ‘\n’. Since the output of the question expects you a newline after every output.

16

Rather than running for loop again we can simply update number of distinct elements at each input, like this:-

while(t--)
{
    scanf("%d",&n);
    int c[100001]={0};
    sum=0;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        if(c[a]==0)
        c[a]=1;
        else
        sum++;
    }
    printf("%d\n",(n-sum));
}
17

I am getting NZEC error for many problems.please anyone can help here

18

Is there any way that this is accepted in GO language. Always stuck in TLE even if the logic is straightforward.
https://www.codechef.com/viewsolution/23228017