JOHNY - Editorial

cakewalk
editorial
johny
nov13

#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

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*<x cnt++
if a[j]<x cnt++
i++,j–
print(cnt+1)

Hope am correct


#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*);
		scanf("%d",&k);
		x=a[k-1];
		qsort(a,n,sizeof(int),cmp);
		j=search(a,0,n-1,x);
		printf("%d

",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*);
    scanf("%d",&K);
    song=0;
    for(i=1;i<=N;i++)
    {
        if (A*<A[K]) song++;
    }
    printf("%d

",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*;
        }
        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<<"

";
}
}
}
return 0;
}


#8

The majority of students think that doing their homework is boring. They do everything accept their homework. If you are one of such students, struggling with the study overload and burden of assignment.
Dissertation writing service


#9

The Class Clown

Easily identifiable, it is the student who is bored and tries to boycott the class by interrupting constantly with questions away from the topic that develops at that moment. Your goal is to get the attention of the class with your comments and jokes so that everyone laughs. He does not allow his classmates to get involved with the lessons or that someone actively participates in the class as he talks to the students coming to his site.

Uk Dissertation Writing Services


#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	",p[j]);    //sorted
     }
    //  printf("

“);
fst=0;
lst=s-1;
mid=(fst+lst)/2;
// printf(”%d %d %d %d
“,fst,lst,mid,p1);
while(fst<=lst)
{
if(p[mid]<p1)
fst=mid+1;
else if(p[mid]==p1)
{
printf(”%d
",(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?


#13

The lion’s share of understudies believe that getting their work done is exhausting. They do everything acknowledge their homework. Get dissertation help UK On the off chance that you are one of such understudies, battling with the examination over-burden and weight of task.


#14

Dont stress long challenge are implied for learning that is the reason they give 10 days to take care of issues and since as u portrayed u were not ready to do first q of the current month’s long this implies despite everything you need to concentrate on your execution abilities so Dissertation Service alongside critical thinking attempt to center usage aptitudes also Happy coding.


#15

We have a wide range of assignment help writers that are experts on a gigantic variety of topics that come under the Assignment help Services in Australia.

Assignment Help Australia


#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*);
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*)
{
printf("%d
",i+1);
break;
}
}
return 0;
}


#17

If you use the phrase that work was a cakewalk or that mission was a cakewalk that means the work was a piece of cake. UK dissertation help Simply accomplished with little or no effort. You six guys! Go carry that Ping-Pong table to the other side of the room = cakewalk. Yo, Fred! Carry the slate pool table up those stairs = not a cakewalk.


#18

You looking for Dentist in Jaipur. We have become a symbol of quality and Endeavour Our self to provide high standards of dental treatment to our patients. We have high standards of sterilization with International sterilization protocols followed . We follow three Phase Sterilization as recommended by American Dental Association. Ekdantam Dental clinic


#19

We provide the best jaipur sightseeing taxi with Facilities and healthy Relations for Future Bookings.kdcab is here to provide the best experience of traveling of your trip with reliable and affordable cab service in Jaipur.


#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

",binary_search(vec,1,n,val));
}
return 0;
}