OVGDEL - Good Elements Editorial or Solution SPOJ - UCS - Unleash-Coding-Skills

Thursday, 26 July 2018

OVGDEL - Good Elements Editorial or Solution SPOJ - UCS




OVGDEL - Good Elements


The link for the problem OVGDEL - Good Elements is:


Note:

In the given problem it is given as aj=aik and  k>=0. and i≠j.

This is the corner case where your code give wrong answer.

So consider the following test case:
If there are 6 elements in the sequence as an example like:

Example 1:
1 2 4 5 3 5

Output for the above example-1 testcase will be: 5


Suppose consider another example of 6 elements:
Example 2:
1 1 2 5 3 5

The output for the above example-2 is : 6




Explanation for example 1:

Since the condition is aj=aik  and  k>=0. and i≠j.


So for 1 there is no combination available like aj=aik  

For 2 => 2 power (0) or 2^0 = 1

Similarly for 4 , 5 ,3 ,5 also powers of 0 are same like x power 0 =1 

Here x is anything or anynumber.



So for this example the output is 'n-1' where 'n' no of elements in the given sequence.


Example 2:


The example 2 output is also like example-1 but one exception for '1' since the rule is:



aj=aik and k>=0. and i≠j.



So the index of 1st '1' is zero and the index of 2nd '1' is '1'



So the condition i≠j is valid now.



1 power (0) or 1^0 =1 which is another one available in the sequence so the output is 'n'. where 'n' is number of elements in given input.


Terminology used while designing my solution:


I have filled the array of character with 3 different letter and my index value of the array is considered as the value given by the sequence elements.



'f' : Represent the corresponding index of array is not present in the sequence.'t' : Represent the corresponding index of array is present once.'m' : Represent the corresponding index of array is present more than once. 

Variables used in code:


count -> output is stored i.e. no of good elements.


onescount -> no of ones in given sequence.


Be carefull will printing the output format



The CPP solution for the problem OVGDEL - Good Elements :


#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
  char a[1000001];
long long int i,j,k,t,n,count,p,maxi,onescount;
//taking no of test cases input
cin>>t;
    for(int ii=1;ii<=t;ii++)
    {
    memset(a,'f',sizeof(a));
    count=0;
    onescount =0;
    maxi =0;
    cin>>n;
    for(i=0;i<n;i++)
    {
    cin>>p;
    if(p==1){
        onescount++;
    }
    if(p>maxi)
    maxi = p;
    if(a[p]=='f')
    a[p]='t';
    else{
//I have adding to count if is more than one.
//suppose there are 4 twos in sequence I have added 3 to count and remaining 1 in 4  is added //later  in logic
    a[p]='m';
    count++;
        }
        }
        //if there is atleast one 1 in sequence case and in else block more than 1 one case
    if(onescount==1)
        {
        cout<<"Case "<<ii<<": "<< n-1<<endl;
        continue;
        }
    else if(onescount>1)
        {
        cout<<"Case "<<ii<<": "<< n<<endl;
        continue;
        }
          //we have said that extra 1 will be adding count here incase of 'm'
        for(i=2;i<=maxi;i++)
        {
            if(a[i]=='m')
                count++;
        }
        //only  counting upto square root of maximum element in sequence is enough
        for(i=2;i<=sqrt(maxi);i++)
        {
             if(a[i]=='t'){
                long long r = i;
                r=r*i;
            while(r<=maxi)
            {
                if(a[r]=='m'||a[r]=='t')
                {
                    //if I found element like a power(k) I will increment count and break
                    count++;
                    
                    break;
                }
                r=r*i;
            }
            }
        }
            cout<<"Case "<<ii<<": "<< count<<endl;
    }
    return 0;
}

Happy Coding........

Tags:

OVGDEL , OVGDEL - Good Elements Editorial ,OVGDEL - Good Elements solution,
OVGDEL - Good Elements answer ,OVGDEL - Good Elements Editorial  SPOJ , SPOJ, ovgdel,
ovgdel good elements editorial spoj

2 comments:

  1. As the setter of this problem, I'm pleased to see this good editorial. Thanks.. :)

    ReplyDelete
    Replies
    1. You are welcome Hafiz Al Masud.We will try to make more quality editorials and help the coding community and technical stuff.I am feeling good to receive appreciation from problem setter.

      Delete