CHEFWORK- Editorial

general
, , , , ,
1

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 :smiley:

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 :slight_smile:

2.Any other approaches are welcomed :slight_smile: