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

×

ZCO 2014, Can anyone tell me the algorithm for this problem? Mine is working wrong.

The problem statement is: http://www.iarcs.org.in/inoi/2014/zco2014/zco2014-2a.php

Here is my code: My logic is that if we sort the budgets and find the maximum value of i-th budget times (n-i). (0-based index). n-i means the number of people having budget greater than or equal to ith-budget.

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<stack>
#include<cmath>
#include<utility>
using namespace std;

int main() {
           int n;
           cin >> n;
           int a[n];
           for(int i = 0;i < n;i++) cin >> a[i];
           sort(a,a+n);
           long long int ans = 0;
           for(int i = 0;i < n;i++) {
                   ans = (ans> ((n-i)*a[i]) )?ans:(n-i)*a[i];
           }
           cout << ans;
           return 0;
}

asked 28 Nov '14, 16:46

ketanhwr's gravatar image

6★ketanhwr
1.9k31844
accept rate: 15%

edited 28 Nov '14, 16:47

1

ooooooooooooooooooooo...i was also hvin the same prob

(20 Jan '15, 19:47) arpanb83★

Your logic is correct use long long instead of int in everything except main().

link

answered 28 Nov '14, 17:12

neo1tech9_7's gravatar image

6★neo1tech9_7
8.5k51538
accept rate: 19%

even in the loops

(28 Nov '14, 17:42) neo1tech9_76★
1

This is also written as a note and the end of problem!

(28 Nov '14, 17:51) yash_155★

Thanks but why didn't this code work? int < 10^9 and I think it should suffice the constraints. Maybe there's something wrong in their judge.

(29 Nov '14, 10:57) ketanhwr6★
2

The code doesn't work because your multiplication in (n-i)a[i] is a multiplication of 2 integers and will overflow int since, (n-i)a[i] can be larger than 10^9.

(29 Nov '14, 18:51) akulsareen4★

Here's my idea on how to find the highest revenue, although I'm not sure if it is correct.

I think the best price would be the median of the array. For the odd length arrays, you can use the middle element and calculate the revenue generated. For even length arrays, you can calculate the revenues for both the elements in the middle and use the greater one.

link

answered 28 Nov '14, 17:10

sampritipanda's gravatar image

5★sampritipanda
3621315
accept rate: 31%

You declare ans as an array of size n and store (n-i)*a[i] in ans[i]. Eventually sort the array (ans) and it's last element is the answer. (I used this logic and had scored 100 upon 100 in the ZCO online practice server).

Hope it helps!

link

answered 20 Jan '15, 23:06

anupam_datta's gravatar image

4★anupam_datta
469630
accept rate: 7%

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:

×2,738
×427
×399
×195
×24

question asked: 28 Nov '14, 16:46

question was seen: 3,116 times

last updated: 20 Jan '15, 23:06