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

×

PNTNG - Editorial

PROBLEM LINK:

Practice
Contest

Author: Konstantin Sokol
Tester: Tasnim Imran Sunny
Editorialist: Praveen Dhinwa

DIFFICULTY:

EASY

PREREQUISITES:

sorting, greedy

PROBLEM:

Given a three dimensional table of dimensions N * M * H. N * M is the dimension of the base of the table. H is the number of layers of the table. You can paint at most T k cells in k th layer with cost of painting a cell in the level being C k .

Find out the minimum cost needed to paint such that there is no vertical column which is unpainted on every layer.

QUICK EXPLANATION

  • You can select exactly N * M cells to paint such that the condition of no vertical column being unpainted is satisfied.

  • Use greedy algorithm for painting the cells. Paint the least cost N * M cells.

  • If there are not enough cells available for painting, then answer will be impossible.

EXPLANATION

As said earlier, as cost of each painting each cell is positive, we will not select more than N * M cells. So we will select N * M cells having least painting cost.

It can be done by using a simple greedy algorithm. We will sort the layers in increasing order of cost and will take the least costly N * M element.

If there are not enough cells available for painting, then the answer will be impossible. In other words, we can say that if the number of cells available for painting are less than N * M, then the answer is impossible.

Number of cells which can be painted will be T 1 + T 2 + .. T k .

Pseudo Code:

    Sort the layers in increasing order of C_k.
    toPaint = N * M;
    // toPaint number of cells to be painted.
    ans = 0
    // ans denotes the cost of the operations.
    for i = 1 to H:
        canPaint = min(toPaint, T_k);
        ans += canPaint * C_k
        toPaint -= canPaint
    if (toPaint > 0):
        // it means that you can not paint N * M cells, the answer will be impossible.
        print "impossible".
    else:
        print ans;

Complexity
O(H log H) : We need sorting + another O(H) loop. So time complexity will be O(H log H).

Possible reasons of getting wrong answers
You should make n and m long long rather than int, because n = 10^12 and m = 1 and vice versa.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution
Tester's solution

This question is marked "community wiki".

asked 23 Jun '14, 00:47

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 23 Jun '14, 20:05

admin's gravatar image

0★admin ♦♦
19.8k350498541

provide the strong test cases as many of us have failed....

(23 Jun '14, 01:19) wonder2★

I have provided test cases for as much codes as I could have done, please check one other thread in the discussions too where I have given some test cases.

(23 Jun '14, 01:37) dpraveen ♦♦4★

please explain the 1st test case in detail. The problem is still unclear to me. what is meant by table should not be seen through top and no two vertical columns should be unpainted?

(23 Jun '14, 03:27) animax_lover2★

I did the same thing! WHY did I get WA?? Please help! http://www.codechef.com/viewsolution/4131658

EDIT: I figured out my problem. I was finding the maximum cost instead of minimum. -_- I think I will go kill myself now...

link

answered 23 Jun '14, 00:52

thespacedude's gravatar image

2★thespacedude
26371627
accept rate: 6%

edited 23 Jun '14, 15:35

For this testcase some accepted solutions are giving incorrect output

2 5 4

4 0

0 4

9 2

1 19

Answer should be 12 but I found one accepted solution which was giving answer as 37!

link

answered 23 Jun '14, 09:26

mtbar131's gravatar image

2★mtbar131
163
accept rate: 0%

edited 23 Jun '14, 09:26

I used quicksort , minheap, Python min function everything then also TLE. Feeling irritated.

link

answered 23 Jun '14, 00:49

filmwalams's gravatar image

5★filmwalams
1.6k113141
accept rate: 7%

http://www.codechef.com/viewsolution/4132176 plzz give test cases where my code fails??

link

answered 23 Jun '14, 00:49

wonder's gravatar image

2★wonder
361183769
accept rate: 0%

This solution gives WA: http://www.codechef.com/viewsolution/4127604

Can anyone give any case where it fails? I have tried all possible cases..

link

answered 23 Jun '14, 00:52

rishul_nsit's gravatar image

4★rishul_nsit
78351020
accept rate: 0%

n and m can not be stored in int. n * m <= 10^12

(23 Jun '14, 00:58) dpraveen ♦♦4★

hell man :\

(23 Jun '14, 01:03) rishul_nsit4★

I should have solved this question in C++, done in C, wasted time. anyways logic is simple and good question

link

answered 23 Jun '14, 00:57

brobear1995's gravatar image

2★brobear1995
1561511
accept rate: 0%

"Your task is to find the minimum cost of painting the table thus that it can't be seen thought from the top (there is no cell which is unpainted on every layer)".

Bold text is a bit misleading! Got WA...:( It meant you can't leave any layer completely unpainted.

link

answered 23 Jun '14, 01:14

sunny210's gravatar image

2★sunny210
1011512
accept rate: 0%

edited 23 Jun '14, 01:15

1

i don't think so..

(23 Jun '14, 01:26) fauzdar652★

i m getting WA..plz tell me in which cases it is failing : http://www.codechef.com/viewsolution/4130278

link

answered 23 Jun '14, 01:15

san_1512's gravatar image

3★san_1512
1
accept rate: 0%

Can be solved easily in C++ using the STL map! the index can be the cost, and the corresponding maximum tiles can be the data, i.e., map[ck]+=tk.

link

answered 23 Jun '14, 01:20

wiseboy's gravatar image

2★wiseboy
129110
accept rate: 0%

It will be better to choose std::multimap instead of std::map, for the simple reason that the cost can be same for more than one layer.

(23 Jun '14, 12:57) gargankit2★

no need of multimap.. you can add tk to the value stored along key ck in a map itself

(23 Jun '14, 13:55) rishul_nsit4★

I think using map is also correct. As we are only interested in cost and no. of tiles that can be painted with that cost.

(23 Jun '14, 13:56) shubham122★

i am getting wrong answer for http://www.codechef.com/viewsolution/4133204, can someone tell me where i am going wrong

link

answered 23 Jun '14, 07:38

harindersingh's gravatar image

3★harindersingh
112
accept rate: 0%

i am not able to get where i am wrong http://www.codechef.com/viewsolution/4135432

link

answered 23 Jun '14, 19:44

mayank95's gravatar image

3★mayank95
212
accept rate: 0%

@admin can anyone see y im getting a wrong answer for this submission.. I used bubble sort.. a tle is expected but its giving wrong answer.. Test cases and max values seem fine.. http://www.codechef.com/viewsolution/4135140

link

answered 24 Jun '14, 12:09

mln_koushik's gravatar image

2★mln_koushik
1
accept rate: 0%

(24 Jun '14, 17:31) achaitanyasai5★

@achaitanyasai i do understand them.. thats i wanted to clarify.. i used the same logic but different sorting in the below comment.. It is accepted solution..

(24 Jun '14, 18:42) mln_koushik2★

http://www.codechef.com/viewsolution/4137798 this is an accepted solution.. while http://www.codechef.com/viewsolution/4137241 shows runtime error..can admins tell me why i got an error in the second one even though code is same..

link

answered 24 Jun '14, 15:02

mln_koushik's gravatar image

2★mln_koushik
1
accept rate: 0%

I am getting wrong answer, plz tell me why.. http://www.codechef.com/viewsolution/4136227

link

answered 24 Jun '14, 17:23

vani57's gravatar image

2★vani57
12
accept rate: 0%

link

answered 24 Jun '14, 21:34

dwiraj007's gravatar image

2★dwiraj007
1111
accept rate: 0%

edited 24 Jun '14, 22:41

Can't understand , how we have to paint only n*m cells..??and what's this mean"vertical column in layer"..??

link

answered 25 Jun '14, 02:29

va1ts7_10's gravatar image

1★va1ts7_10
13
accept rate: 0%

ok.. i understood

(25 Jun '14, 03:04) va1ts7_101★

optimization : Inside the for loop add if(topaint==0)break;

link

answered 19 Dec '14, 15:13

king_of_hacker's gravatar image

3★king_of_hacker
204312
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:

×15,852
×3,820
×1,024
×801
×16

question asked: 23 Jun '14, 00:47

question was seen: 4,177 times

last updated: 19 Dec '14, 15:13