PROBLEM LINK:Author: Konstantin Sokol 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
EXPLANATIONAs 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:
Complexity Possible reasons of getting wrong answers AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 23 Jun '14, 00:47

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... answered 23 Jun '14, 00:52

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! answered 23 Jun '14, 09:26

I used quicksort , minheap, Python min function everything then also TLE. Feeling irritated. answered 23 Jun '14, 00:49

http://www.codechef.com/viewsolution/4132176 plzz give test cases where my code fails?? answered 23 Jun '14, 00:49

This solution gives WA: http://www.codechef.com/viewsolution/4127604 Can anyone give any case where it fails? I have tried all possible cases.. answered 23 Jun '14, 00:52
n and m can not be stored in int. n * m <= 10^12
(23 Jun '14, 00:58)
hell man :\
(23 Jun '14, 01:03)

I should have solved this question in C++, done in C, wasted time. anyways logic is simple and good question answered 23 Jun '14, 00:57

"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. answered 23 Jun '14, 01:14

i m getting WA..plz tell me in which cases it is failing : http://www.codechef.com/viewsolution/4130278 answered 23 Jun '14, 01:15

i am getting wrong answer for http://www.codechef.com/viewsolution/4133204, can someone tell me where i am going wrong answered 23 Jun '14, 07:38

i am not able to get where i am wrong http://www.codechef.com/viewsolution/4135432 answered 23 Jun '14, 19:44

@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 answered 24 Jun '14, 12:09
I think you have misunderstood.To know why refer this link :
(24 Jun '14, 17:31)
@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)

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.. answered 24 Jun '14, 15:02

I am getting wrong answer, plz tell me why.. http://www.codechef.com/viewsolution/4136227 answered 24 Jun '14, 17:23

answered 24 Jun '14, 21:34

Can't understand , how we have to paint only n*m cells..??and what's this mean"vertical column in layer"..?? answered 25 Jun '14, 02:29

optimization : Inside the for loop add if(topaint==0)break; answered 19 Dec '14, 15:13

provide the strong test cases as many of us have failed....
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.
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?