Help me with this Dynamic Programming Question kind of stuck on this

general
1

There are N buildings in a locality each building must be painted with a type of paint. InitiaIly, some buildings are painted with some type of paint. The building that is painted cannot be painted again. You are given M types a paints, 1 to M inclusive. The specialty 0f the locality is defined as the number of contiguous buildings that are painted with the same type of paint. For example, if six buildings apartment are painted from left to right are {1, 2, 1, 1, 3, 3}, then the likelihood of the apartment is 4 { {1}, {2}, {1,1}, and {3,3}}. You are given an N x M matrix, where the ith row and jth column denote the painting cost of the ith building with the jth the type of paint.

You are required to determine the minimum cost to paint all the buildings such that the specialty of the appartment is exactly K. If it is not possible to paint all building such that the likelihood of the apartment is exactly K, then print -1.

Input Format : --> The first line contains T denoting the number of test cases.

-> For each test case:

–> The next line contains N, M, and K where N is the number of buildings in a locality , M is the number of types of paints, and K is the specialty of the locality respectively.

–> The next line contains N space-separated integers where the ith integer is either 0 or the type of paint from which the ith building is already painted. Here, 0 means that the building is not painted.

–> The next N lines contain M space-separated integers where the ith row and jth column denote the painting cost (cost i,j of the ith building with the jth type of paint.

OUTPUT FORMAT :

Print the minimum cost to paint all buildings such that the specialty of the apartment is exactly K. If it is not possible to paint all building such that the likelihood of the apartment is exactly K, then print -1.

CONSTRAINTS :

1 ≤ T ≤ 10
1 ≤ K ≤ N ≤ 100 
1 ≤ M ≤ 100
1 ≤ cost(i,j) ≤ 10 power 9

SAMPLE INPUT :

1

4 2 1

0 0 0 2

100 20

30 59

71 81

9 200

SAMPLE OUTPUT :

1 Like
2

Do you have a link to the problem?

And why did you flag this as DP? What’s the approach you currently have that isn’t working?

2 Likes
3

it was test i couldn’t complete it but still stuck at it how can it can be solved
i thought it dp cause we have to find minimun cost while taking of the specality so i got succeed in generating minimun cost but wasn’t able to fulful the speciality criteria

4

I don’t want your source, I want the link so I’m sure it’s not from some ongoing contest.

1 Like
5

it was PayPal hiring test on HackerEarth you can check it test duration was 2:30 hours only I wasn’t able to finish it and this question kind of stuck in mind from yesterday evening

7

There are a lot of PayPal contests. Can you just give me the link so I know which one you’re talking about?

I do have a solution for you, by the way, and I will share it with you as soon as I know you’re not trying to cheat on something.

3 Likes
9

@galencolin @everule1 help?

10

You can’t participate but any others can…so wait or solve on your own.

3 Likes
11

Okay i got that so will you help with solution after that challenge gets ends it’s like i tried everything and still stuck?

12

@iamnobbie Hi. i couldnt solve the first question related to Alice and Bob. could you ping me privately since i dont want anyone to post answers online while the test is going on. I have completed my challenge btw. Thank you

13

@aditya_kumar_b thanks for replying i solved the first one but got stuck on this one where i can contact you?

18

@iamnobbie COuld you please share the answer of first problem privately

19

If anyone has any solution or approach for the 2nd question, please message me privately.
I have completed the test and tried all the approaches. But nothing seems to work.

20

Could anyone solve this?

21

Kindly ping me on telegram . User name : NightKing1123

23

Those who feel they have tried everything for this question and want to discuss about it, then message me on Telegram.
@AsciiVal

24

Hi friends, can anyone pls share the solution for this, did anyone able to solve this ? is it really into DP?

25

Hello, does anyone know how to do this problem?

Try to write a program to check if a generalized sudoku board is completed correctly or not.

It is considered that a table is correctly completed if there are no duplicate values ​​on rows, columns or groups (squares).

Input data:
Unfortunately, the size of the board is not always the same, it being read from the keyboard at the beginning of the program, in the format:

line_number number_columns no_groups

Then enter from the keyboard the contents of each cell of the sudoku board, in the format:

line_number_column column_group number effective_value

Output data:
1 will be displayed if the board is correct, or 0 if not.

mentions:

The groups cannot overlap and are all the same size.
The value is just a natural number.
It is guaranteed that there are at least 2 rows, 2 columns, 2 groups.
The number of the row, column, group, starts from 0.

Example:
(comments are for clarity, they are not entered at the entrance)

4 4 4
0 0 0 1
0 1 0 2
1 0 0 3
1 1 0 4
// so far it was the first square
0 2 1 3
0 3 1 4
1 2 1 5
1 3 1 6
// so far the 2nd square
2 2 3 7
2 0 2 5
3 1 2 0
2 3 3 8
3 2 3 1
2 1 2 6
3 0 2 9
3 3 3 2
// last 2 mixed squares

the sudoku matrix would be: (4x4 with 4 groups)

1 2 | 3 4
3 4 | 5 6

5 6 | 7 8
9 0 | 1 2

this table is correct, having no duplicates either on the line, or on the column, or on the group.

Example of incorrect table:

1 1 | 3 4
3 4 | 5 6

5 6 | 7 8
9 0 | 1 2

line 0 has “1” doubled

1 2 | 3 4
1 4 | 5 6

5 6 | 7 8
9 0 | 1 2

column 0 has “1” doubled

1 2 | 3 4
3 4 | 5 6

5 6 | 7 8
9 0 | 1 7

group 3 has “7” doubled.

26

Contest is over now so,@galencolin can you share your approach now??

28

Just a confusion bro…In the attempt of reducing complexity in second transition shouldn’t we use min(pre[i-1][j-1][k-1], suf[i-1][j-1][k+1]) + c[i][k] since we would like to reduce the cost of painting.
Also how we will calculate the suf[][][] , I am no able to visualize it
Thanks in Advance