JOHNY - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

Given an unsorted array of unique elements, find the position of a specified elements in array’s sorted form.

QUICK EXPLANATION:

Count the number of elements in an unsorted array which are smaller than the given element.

EXPLANATION:

Since the length of all songs is unique, if we count the number of songs which have length less than the length of “Uncle Johny”, we know its position in sorted array.

Constraint on the value of N in this problem is very low so many contestants sorted the array and then did binary search for the length of “Uncle Johny” song in the sorted array. This approach also passes well within time limit.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be uploaded soon
Tester’s solution can be found here and here

2 Likes
2

Links to author’s and tester’s solutions not working.

3

You can also use two pointers at both ends to get a faster time

a—is the array of numbers
x— is the number we are trying to find its position after sorting

i=0;j=n-1
while(i<=j)
if a[i]<x cnt++
if a[j]<x cnt++
i++,j–
print(cnt+1)

Hope am correct

1 Like
4

Why this code not working ?

#include <stdio.h>
#include<stdlib.h>
int cmp(const void* a, const void* b)
{
	return ( *(int*)a - *(int*)b );
}
int search(int a[], int low, int high, int x)
{
	while(low<high)
	{
		int mid=(low+high)/2;
		if(a[mid]==x)
		return mid;
		else if(a[mid]>x)
		return search(a,low,mid-1,x);
		else
		return search(a,mid+1,high,x);
	}
	//return 0;
}
int main(void) {
	// your code goes here
	int t,n,i,k,x,j;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int a[n];
		for(i=0;i<n;i++)
		scanf("%d",&a[i]);
		scanf("%d",&k);
		x=a[k-1];
		qsort(a,n,sizeof(int),cmp);
		j=search(a,0,n-1,x);
		printf("%d\n",j+1);
	}
	return 0;
}
5

I can’t figure out why doesn’t it work?

Seems correct to me.

PS: Nicely formatted, readable code.

6

Why is this code giving wrong answer ?

#include

using namespace std;

int main()
{

int T,N,K,i,song;
long long A[102];
scanf("%d",&T);
while(T--)
{
    scanf("%d",&N);
    for(i=1;i<=N;i++) scanf("%lld",&A[i]);
    scanf("%d",&K);
    song=0;
    for(i=1;i<=N;i++)
    {
        if (A[i]<A[K]) song++;
    }
    printf("%d\n",song);
}
return 0;

}

7

Why this code returns wrong answer??

#include <iostream>

using namespace std;

int main()
{
    int T,N,a[100],K,fav,temp=0;
    cin>>T;
    for(int k=0;k<T;k++){
        cin>>N;
        for(int i=0;i<N;i++){
            cin>>a[i];
        }
        cin>>K;
        fav=a[K-1];
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
             if(a[k]>a[k+1]){
                temp=a[k];
                a[k]=a[k+1];
                a[k+1]=temp;
             }
            }
        }
        for(int m=0;m<N;m++){
            if(fav==a[m]){
                cout<<m+1<<"\n";
            }
        }
    }
    return 0;
}
10

Vlad enjoys listening to music. He lives in Sam’s Town. A few days ago he had a birthday, so his parents gave him a gift: MP3-player! Vlad was the happiest man in the world! Now he can listen his favorite songs whenever he wants!

Vlad built up his own playlist. The playlist consists of N songs, each has a unique positive integer length. Vlad likes all the songs from his playlist, but there is a song, which he likes more than the others. It’s named “Uncle Johny”.

After creation of the playlist, Vlad decided to sort the songs in increasing order of their lengths. For example, if the lengths of the songs in playlist was {1, 3, 5, 2, 4} after sorting it becomes {1, 2, 3, 4, 5}. Before the sorting, “Uncle Johny” was on K-th position (1-indexing is assumed for the playlist) in the playlist.

Vlad needs your help! He gives you all the information of his playlist. Your task is to find the position of “Uncle Johny” in the sorted playlist.

11

#include <stdio.h>
int main(void)
{
int t,s,p[100],p1,i,j,k,b,u1,lst,fst,mid;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&s);
for(j=0;j<s;j++)
{
scanf("%d",&p[j]);
}
scanf("%d",&u1);
p1=p[u1-1];

      for(k=0;k<s-1;k++)
      {
           for(j=0;j<=s-k-1;j++)
          {
               if(p[j]>p[j+1])
               {
                 b=p[j];
                 p[j]=p[j+1];
                 p[j+1]=b;
               }
           }
      }
        for(j=0;j<s;j++)
     {
       //  printf("%d\t",p[j]);    //sorted
     }
    //  printf("\n");             
      fst=0;
      lst=s-1;
      mid=(fst+lst)/2;
     // printf("%d %d %d %d\n",fst,lst,mid,p1);
      while(fst<=lst)
     {
           if(p[mid]<p1)
              fst=mid+1;
           else if(p[mid]==p1)
           {
               printf("%d\n",(mid+1));
               break;
           }
           else
               lst=mid-1;
           mid=(fst+lst)/2;
      }
      
}
return 0;

}

why the answer is coming wrong although i am getting correct answer in online ide

12

https://www.codechef.com/viewsolution/14638375
Why is this working in c99strict compiler but not in c compiler??? What is the difference between the two?

16

#include<stdio.h>
int main()
{
int i,j,t,n,k;
long long int a[101],e,temp;
scanf("%d",&t);
while(t–)
{
scanf("%d",&n);
for(i=0; i<n; i++)
scanf("%lld",&a[i]);
scanf("%d",&k);
e=a[k-1];
for(i=0; i<n; i++)
for(j=0; j<n-i; j++)
if (a[j]<a[j-1])
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
for(i=0;i<n;i++)
if(e==a[i])
{
printf("%d\n",i+1);
break;
}
}
return 0;
}

20

hello why don’t you give if the editorial says you can accept within time with a binary search???
#include
#include
#include

using namespace std;
#define MAX 101
int medio;

int binary_search(int *vec,int i,int j,int m){
if(i>j)return -1;
medio = (i+j)/2;
if(m>vec[medio])return binary_search(vec,medio+1,j,m);
else if(m<vec[medio])return binary_search(vec,i,j-1,m);
else medio;
}
int main(int argc,char *argv[],char **env){
int t,n,k,val;
scanf("%d",&t);

while(t--){
    scanf("%d",&n);
    int vec[MAX]{};
    for(int i=1;i<=n;i++)
        scanf("%d",(vec+i));
    scanf("%d",&k);
    val = vec[k];
    sort(vec+1,vec+n+1);
    printf("%d\n",binary_search(vec,1,n,val));
}
return 0;

}

21

Why is thi code giving wrong answer??

#include<stdio.h>
int main()
{
int t,n,m,k,i,j;
long long int a[100],b,temp;
scanf("%d",&t);
while (t–)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
scanf("%d",&k);
b = a[k-1];
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<n;i++)
{
if(a[i]== b)
printf("%d",i+1);
}
}
return 0;

}

22

#include
#include
using namespace std;
void fastscan(int &number)
{
//variable to indicate sign of input number
bool negative = false;
register int c;

number = 0; 


c = getchar(); 
if (c=='-') 
{ 
    // number is negative 
    negative = true; 


    c = getchar(); 
} 


for (; (c>47 && c<58); c=getchar()) 
    number = number *10 + c - 48; 

if (negative) 
    number *= -1;

}
int main()
{
int a;
fastscan(a);
while(a–)
{
int b;
fastscan(b);
int l[b];
for(int i=0;i<b;i++)
{
fastscan(l[i]);
}
int y;
fastscan(y);
int u=l[y-1];int o=0;
for(int i=0;i<b;i++)
{
if(u>=l[i])
{
o++;
}
}
cout<<o+1<<endl;
}
}

23

#include
#include
using namespace std;
void fastscan(int &number)
{
//variable to indicate sign of input number
bool negative = false;
register int c;

number = 0; 


c = getchar(); 
if (c=='-') 
{ 
    // number is negative 
    negative = true; 


    c = getchar(); 
} 


for (; (c>47 && c<58); c=getchar()) 
    number = number *10 + c - 48; 

if (negative) 
    number *= -1;

}
int main()
{
int a;
fastscan(a);
while(a–)
{
int b;
fastscan(b);
int l[b];
for(int i=0;i<b;i++)
{
fastscan(l[i]);
}
int y;
fastscan(y);
int u=l[y-1];int o=0;
for(int i=0;i<b;i++)
{
if(u>=l[i])
{
o++;
}
}
cout<<o+1<<endl;
}
}

25

Your algorithm is right, but i don’t understand why it works faster. Your solution consider every element of the array, so author’s solution do. So, i guess it works as fast as author’s one.

26

Firstly i cant read your code…Then why do you need to go with binary search?
Make the code as simple as that-make linear search.
I am sorry i cant read it completly…
If you provide the proper indentation then i shall try…:slight_smile: All the best…

27

Yes you are correct by saying that it considers every element in the array but notice that it considers it 2 at a time while the authors own considers it 1 at a time leading my own to an O(n/2) algorithm which will be faster asymptotically speaking.

28

… dude, believe me, n = (1/2)(n + n), if you know what I mean.

29

It would be better if you format and use proper indentation while posting codes. Posting the code in a paragraph makes it unreadable and impossible to debug.