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

×

GCAC - Editorial

PROBLEM LINK:

Practice
Contest

Author: Naksh Arora
Tester: Prateek Gupta
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

There are a total of N candidates and M companies. Each candidate has a certain minimum expectation of salary. You will be given N*M numbers, such that for each pair (candidate,company) you will be given a value (0/1) telling if this company accepts this candidate. A company will provide a fixed salary to the candidates it employs (and it's the same for any candidate it employs). Also, a company has an upper bound on the number of candidates it can employ and finally give an offer to.

Each candidate from (1,2,3,...N) (in this order) would call all companies that accepts him, and check which of them still hasn't reached its job offers limit. Among which haven't,he picks the company which provides the maximum offered salary, provided that it is at least his demanded salary. You have to find the number of the candidates that will end up with a job, the total amount of salaries that the candidates will get, and the number of companies that won't be able to employ even a single candidate.

No two companies provide the same salary.

DIFFICULTY:

simple

PREREQUISITES:

None

EXPLANATION:

According to our bolded constraint (which made the problem much simpler) you can observe that any candidate would always have one choice (only), or he may not find a company at all (if all companies that he is interested in working at (and accepting employing him) reached their offers limit).

So turning the instructions written in the problem statement into a code (a straight forward simulation) is pretty enough to solve the problem. Process candidates in order, for each one iterate through all companies and check ones that accept this candidate, provides a salary that satisfies his demand and most importantly still have vacancies. Among these, pick the one with best salary, assign our candidate to this company and decrement its remaining vacancies by one. Calculating required values would be pretty easy. Check my implementation for better understanding.

Solution runs in O(N*M)

AUTHOR'S AND TESTER'S SOLUTIONS:

AUTHOR's solution: Can be found here
TESTER's solution: Can be found here
ADMIN'S Solutions: Can be found here
EDITORIALIST's solution: Can be found here

This question is marked "community wiki".

asked 11 Aug '17, 13:37

deadwing97's gravatar image

3★deadwing97
118822
accept rate: 0%

edited 18 Aug '17, 16:11

admin's gravatar image

0★admin ♦♦
19.0k348495533


someone please explain me what is the error: https://www.codechef.com/viewsolution/16747078

link

answered 04 Jan, 02:28

parvatyadav's gravatar image

2★parvatyadav
11
accept rate: 0%

edited 04 Jan, 02:31

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:

×14,429
×1,002
×504
×193
×14

question asked: 11 Aug '17, 13:37

question was seen: 566 times

last updated: 04 Jan, 02:31