You are not logged in. Please login at www.codechef.com to post your questions!

×

JOHNY - Editorial

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

This question is marked "community wiki".

asked 11 Nov '13, 15:03

shaleen's gravatar image

4★shaleen ♦♦
616913
accept rate: 0%

edited 11 Nov '13, 22:17


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

link

answered 11 Nov '13, 22:08

tijoforyou's gravatar image

3★tijoforyou
4.2k52364
accept rate: 15%

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

link

answered 12 Nov '13, 07:09

okekeau's gravatar image

3★okekeau
161
accept rate: 0%

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.

(12 Nov '13, 17:39) kostya_by ♦♦6★

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.

(14 Nov '13, 02:48) okekeau3★

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

(09 Dec '13, 20:33) sanjay513★

I can't figure out why doesn't it work? https://ideone.com/ftTHzI Seems correct to me.

PS: Nicely formatted, readable code.

link

answered 02 Jun '16, 10:19

jarpit96's gravatar image

2★jarpit96
1
accept rate: 0%

Why is this code giving wrong answer ?

include<cstdio>

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;

}

link
This answer is marked "community wiki".

answered 27 Jul '16, 14:09

adarsh1021's gravatar image

2★adarsh1021
1
accept rate: 0%

edited 27 Jul '16, 14:10

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;
}
link

answered 26 Aug '16, 08:17

pratiktsingh17's gravatar image

1★pratiktsingh17
1
accept rate: 0%

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

link

answered 26 Aug '16, 11:22

adam0702's gravatar image

0★adam0702
1
accept rate: 0%

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

link

answered 23 Feb, 14:21

aanish's gravatar image

0★aanish
-1
accept rate: 0%

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.

link

answered 25 Apr, 01:40

fiery_phoenix0's gravatar image

0★fiery_phoenix0
1
accept rate: 0%

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

link

answered 13 Jun, 00:10

subham_1999's gravatar image

2★subham_1999
1
accept rate: 0%

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?

link

answered 22 Jul, 16:49

knightcube's gravatar image

2★knightcube
11
accept rate: 0%

edited 22 Jul, 16:56

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.

link

answered 09 Aug, 12:06

brucebrennan's gravatar image

0★brucebrennan
1
accept rate: 0%

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.

link

answered 09 Aug, 13:07

brucebrennan's gravatar image

0★brucebrennan
1
accept rate: 0%

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

link

answered 13 Nov, 11:17

vincymol's gravatar image

0★vincymol
1
accept rate: 0%

    #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;
}
link

answered 06 Dec, 21:07

sumanmichael01's gravatar image

0★sumanmichael01
11
accept rate: 0%

edited 06 Dec, 21:11

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.

(06 Dec, 21:11) ashutosh4505★
-1

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;
}
link

answered 13 Nov '13, 11:54

sanki's gravatar image

1★sanki
0
accept rate: 0%

edited 04 Nov '14, 18:11

tech_boy's gravatar image

3★tech_boy
1.2k41931

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..:) All the best..

(13 Nov '13, 18:57) bipin23★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,344
×1,155
×15
×2

question asked: 11 Nov '13, 15:03

question was seen: 5,272 times

last updated: 06 Dec, 21:13