 # ZCO 2014 Smartphone

Why is my code not getting accepted even when i have tested all selfmade testcases to be running correctly

You are overcomplicating the things.
Do this :
Sort the array.
let the 0-indexed array be arr[i]
You know that for each element , the elements after it will have the budget >= arr[i] . So, traverse backwards. For each i, if we choose arr[i] as the price for app, we will get arr[i]*(n-i) rupees (Becase all the people after the current person will at least arr[i] money so they will buy this.)

Here’s the code if you have any doubts but seriously first understand and try it yourself :
https://www.codechef.com/viewsolution/8716059

``````#include<bits/stdc++.h>
using namespace std;
// Input macros
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%lld",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)

// Useful hardware instructions
#define bitcount                    __builtin_popcount
#define gcd                         __gcd

// Useful container manipulation / traversal macros
#define forall(i,a,b)               for(int i=a;i<b;i++)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair

//Lengthy data types
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
// code starts here
int main(){
long long int n;
cin >> n;
long long int cap[n];
for(int i=0;i<n;i++)cin >> cap[i];
sort(cap,cap+n);
long long int currmax=0;
long long int prev=-1;
for(long long int i=n-1;i>=0;i--){
//if(cap[i]==prev)continue;
currmax=max(currmax,((n-i))*cap[i]);
prev=cap[i];
}
cout << currmax << endl;
return 0;
}``````

+theweblover007

Why doesn’t my code work for the second test case,because I think my solution is similar to yours.

https://www.codechef.com/viewsolution/8729874

nvm got it,thanks for your answer though I was trying to sort using merge sort like the OP but the built in sort function is way easier and I guess quicker.

Lines 24-33 is where the problem is.
In this problem, if we sort the array in increasing order, then the revenue generated for a given price in the array will be generated by all customers after that in the array as they will have higher prices to offer. As reference, you might want to look at this short and simple code.

``````#include <bits/stdc++.h>
using namespace std;
struct _ { ios_base::Init i; _() { cin.sync_with_stdio(0); cin.tie(0); } } _;

///////////////////////////////////////////////////////////////////////////////
#define endl '\n'
#define ll long long
#define ld long double
#define pb push_back
#define mt make_tuple
#define in(a) for (auto& i: a)
#define tbeg clock_t _t=clock();
#define test ll t; cin >> t; for (ll tc=1; tc<=t; tc++) {
#define tend cout << "\n\nTime: " << (double)(clock()-_t)/CLOCKS_PER_SEC;
///////////////////////////////////////////////////////////////////////////////

int main()
{

ll n, ans=INT_MIN;
cin >> n;
ll a[n];
in(a) cin >> i;
sort(a, a+n);
for (ll i=0; i<n; i++) ans=max(ans, a[i]*(n-i));
cout << ans << endl;

}``````

Hi everyone.

Can past year ZCO participants explain how is the whole procedure of submitting the answers in the competition. Suppose if I submit a wrong answer, will I get another chance?

https://www.codechef.com/viewsolution/8714051

or

http://pastebin.com/27HEgwr4

You can check out here if you have any doubt the post---------

First I also made a O(n^2) solution but that will obviously not pass the second subtask. What you need to do is simply sort the array in descending order and start from the biggest element. Keep going to the smaller element and in the loop find out the product of a[i]*(n-i). The biggest element after processing this is your answer. Apart from the sorting this is o(n) and with O(n log n) so a pretty good improvement I would say. I got 100.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define e ‘\n’

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
ll n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
ll ma=0,tmp=0;
for(int i=n-1;i>=0;i–){
tmp=a[i]*(n-i);
ma=max(tmp,ma);
}
cout<<ma;
return 0;
}

Here’s my solution to the problem.

Also could you please upvote my answer as I need karma points to ask a question related to the olympiad, I’m having problems with little red riding hood

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
long long n;
cin >> n;
vector<long long> ns(n);

long long i =0;
for(i=0;i<n;i++)
{
cin >> ns[i];
}
long long max = 0;
sort(ns.begin(), ns.end());
for(long long i =0;i<n;i++)
{
max = max > (n-i) * ns[i] ? max : (n-i) * ns[i] ;
}
cout << max;
return 0;
}``````
3 Likes

What’s wrong with my code (excluding the slow sorting algorithm)?

@owneriekno1 , Why the hell are you not sorting using inbuilt sort function, its way easier and way faster.
just write :
sort(arr,arr+n);
#include<bits/stdc++.h>
and remove every other includes file. Makes the coding easier. Also, a hint : Look for corner cases.

import java.util.*;
class Smartphone
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println(“Enter the data in the given format”);
int N=sc.nextInt(); //Stores number of potential customers
int budg[]=new int[N]; //Array to store budget of customers
for(int i=0;i<N;i++)
budg[i]=sc.nextInt();

``````    //Sorting the array
for(int i=0;i<N-1;i++)
{
int pmin=i;
for(int j=i+1;j<N;j++)
{
if(budg[j]<budg[pmin])
pmin=j;
}
int temp=budg[i];
budg[i]=budg[pmin];
budg[pmin]=temp;
}

//Checking for maximum revenue
int rev=0,maxRev=0;
for(int i=0;i<N;i++)
{
if(budg[i]*(N-i)>maxRev)
{maxRev=budg[i]*(N-i);rev=budg[i];}
}

System.out.println("Revenue : "+rev+"\nMaximum Revenue : "+maxRev);
}
``````

}

1 Like

Try this… It’s simple …It’s Working

``````
include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n,maxR=0;
cin>>n;//geting number  of customers.
long long int arr[n+9];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);//sort the aray in acending order
for(long long int i=0;i<n;++i)
{
if( (arr[i]* (n-i) ) >maxR)
{
maxR = (arr[i]* (n-i) );
}
}
cout<<maxR<<"\n";
return 0;
}

``````

yes, you will. and ur best solution will be taken for evaluation.

But your sorting method is not efficient,you can use Arrays.sort(which uses quick sort(more efficient then this).
Thanks upvote if you like my amswer,and accept my gift(10 points)

can you please check what’s wrong with my code?
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
ll t,n;
cin>>t;
vector vect(t);
for(ll i=0;i<t;i++)
{
cin>>vect[i];
}
sort(vect.begin(),vect.end());
int max=-1;
for(ll i=0;i<t;i++)
{
if(vect[i](t-i)>=max)
{
max=vect[i]
(t-i);
}
}
cout<<max<<endl;
return 0;
}

hey i did the same my code is showing right ans for custom input while on submission it’s showing wrong ans
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
ll t,n;
cin>>t;
vector vect(t);
for(ll i=0;i<t;i++)
{
cin>>vect[i];
}
sort(vect.begin(),vect.end());
int max=-1;
for(ll i=0;i<t;i++)
{
if(vect[i](t-i)>=max)
{
max=vect[i]
(t-i);
}
}
cout<<max<<endl;
return 0;
}

``````/* package codechef; // don't place package name! */
``````

import java.util.;
import java.lang.
;
import java.io.*;[quote=“vedant2080, post:1, topic:11855, full:true”]
Why is my code not getting accepted even when i have tested all selfmade testcases to be running correctly

[/quote]

``````indent preformatted text by 4 spaces
``````

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner (System.in);

``````	    int n =sc.nextInt();

long arr[]= new long[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextLong();
Arrays.sort(arr);
long max = 0;
for(int i = n-1;i>=0;i--)
{
//System.out.println(i);
if((arr[i]*(n-i))>max)
{
//System.out.println(max);
max=arr[i]*(n-i);
}
}
System.out.println(max);

}
``````

}