Problem Code: ZCO14003

I have a solution for the problem:https://www.codechef.com/ZCOPRAC/submit/ZCO14003 it runs well in code chef ide but it appears to be wrong after the submit.It passes few test cases but not all. can anyone help me!
here’s my code:

#include <stdio.h>

int main(void) {
    long long int n,list[100000000],temp,values[50000],i,j,arr[500000],size;
    scanf("%11d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%11d",&list[i]);
    }
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-1;j++)
        {
            if(list[j]>list[j+1])
            {
                temp=list[j];
                list[j]=list[j+1];
                list[j+1]=temp;
            }
        }
    }
    temp=0;
    size=n;
    while(size>=0)
    {
        values[temp]=size;
        size--;
        temp++;
    }
    for(i=0;i<n;i++)
    {
        arr[i]=list[i]*values[i];
    }
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-1;j++)
        {
            if(arr[j]>arr[j+1])
            {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp; 
            }            
        }        
    }
    printf("%d",arr[n-1]);
    return 0;
}

Your logic is right. Just change “%11d” to “%lld” in all scanf and printf statements and your code will get accepted on the first subtask.

You’re getting a TLE on the second subtask because it seems you’re using bubble sort which has a time complexity of \mathcal{O}(n^2), which is too slow to run in the time limit for n = 5\times10^5. If you’re not familiar with the \mathcal{O}-notation, learn it here.

You should use faster sorting algorithms like merge sort and quicksort, which are \mathcal{O}(n\log_2 n) algorithms. Also, I think there’s a qsort() function in C.

@pratik_2003

The only problem you are having is with sorting the array.

I would prefer that you would refer to these two links for merge sort:

  1. https://www.youtube.com/watch?v=TzeBrDU-JaY

  2. https://www.youtube.com/watch?v=mB5HXBb_HY8

I prefer that you shouldn’t use quicksort as it will give you a TLE if it runs in the Worst Case (which we consider the most). It has a time complexity of O(n ^ 2).

Secondly, make the limit for ‘values’ array 500001.

This is because n is 5 * (10 ^ 5) for the second test case. It will give you a RTE (run-time error). This is because you are storing 50001 values in the worst test case (when n is 50000).

I hope this helps you :slight_smile:

Thanks for it!

Could you suggest me the perfect code for it! It’s an request, merge sort isn’t working.

The size of the “values” array should be 500,000 instead of 50,000. It’s funny how C doesn’t give a runtime error on accessing an out of bound array index.

If it still doesn’t work, post your code here, you might be doing some mistake.

@aryan12 Quicksort is actually faster than merge sort by a constant factor. Agreed, its time complexity is \mathcal{O}(n^2), but the probability that this case arises is extremely low. In fact, for n > 10, the worst case almost never arises if you’re choosing a random pivot.

About the size of the values array, even I thought that the code will give a run-time error. It’s surprising how there was no error when I submitted a code in C which certainly accessed an illegal array index.

import java.util.;
import java.io.
;
class smartphonecc
{
public static void main(String args[])throws IOException
{
try{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s=br.readLine();
int n=Integer.parseInt(s);
ArrayList al=new ArrayList(n);
ArrayList al1=new ArrayList();
//long[] al1=new long[n];
for(int i=0;i<n;i++)
{
al.add(Integer.parseInt(br.readLine()));
}
Collections.sort(al);
//Collections.reverse(al);
//System.out.println(al);
//int temp=0;
int n1=al.size();
double max=0;
for(int i=0;i<n1;i++)
{
al1.add((double)(al.get(i)*(n1-i)));
max=Math.max(al1.get(i),max);
}
System.out.println((int)max);
}catch(Exception e){}
}
}

Getting wrong answer.can anyone help to get out this