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

×

CHEFWORK- Editorial

PROBLEM LINKS:

Div2
Practice

Setter- Adlet Zeineken
Tester- Misha Chorniy
Editorialist- ????

DIFFICULTY:

CAKEWALK

PRE-REQUISITES:

Array, Looping, Sorting (optional).

PROBLEM:

There are $3$ type of workers, where the first type only translates, second type only writes and third type does both, we are to find minimum cost to write $and$ translate a piece of text. We are given the information of type of worker, and how many coins he will charge for his service.

QUICK EXPLANATION:

We clearly see that the answer will be ${min} (C_3,C_1+C_2)$ where ${C}_{i}$ denotes the cost of cheapest worker of type $i$. With that, we just have to take care of cases where -

  1. There are no workers of type $C_1$ or $C_2$ .
  2. No worker of type ${C}_{3}$.

EXPLANATION :

This editorial will describe two approaches, one which is easy and intended one, and another which is followed by me (a bit complex- but its intended to expose you guys to data structures).

Easy Approach #1
This is a fairly simple problem. What we must focus on, is finding the minimum cost of workers of all three types.

There can be multiple ways to do so. One way is to iterate over the array thrice, each time finding minimum cost of worker of the required type. If no worker of that type exists, we simply put ${C}_{i}=INF$ where INF can be some large number, more than $2*{10}^{5}$ (preferably INTMAX).

With this data, we can simply find answer as $min(C_3,C_1+C_2)$, which was stated above.

My Approach (Medium)-

My approach intends to introduce you people to data types, and this time it is vectors (in C++) and any equivalent data structure in other languages. In context to editorial, you can think like, vector is an array where you can insert and delete elements from end in $O(1)$ time. (although its much more than that!)

What I did was, I created an array of vectors, of size $4$ (just to follow 1-based indexing). In my solution, $worker[i][j]$ represents a worker of type $i$ take $j$ coins to do his work. I sorted the vectors of all $3$ types, took care of conditions when worker of a specific type are absent, and simply printed the answer (because after sorting, the first element is the minimum).

Dont worry if this seems complex to you now, but do make sure to understand this at some point of time :).

SOLUTION:

Setter
Tester - He essentially did the same as in approach 1 we discussed. His array $F[i]$ is equivalent to our $C_i$.
Editorialist

CHEF VIJJU'S CORNER :D

1.Make it a point to learn vectors. A proper command over data structures are needed to master algorithms. Vectors are very commonly used in Graph Algorithms. You can refer to here for more on vectors :)

2.Any other approaches are welcomed :)

This question is marked "community wiki".

asked 06 Apr '18, 17:34

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 17 Apr '18, 15:52

admin's gravatar image

0★admin ♦♦
19.8k350498541

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:

×1,688
×862
×311
×191
×35
×1

question asked: 06 Apr '18, 17:34

question was seen: 974 times

last updated: 17 Apr '18, 15:52