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.
Could anyone solve this?
Kindly ping me on telegram . User name : NightKing1123
Those who feel they have tried everything for this question and want to discuss about it, then message me on Telegram.
@AsciiVal
Hi friends, can anyone pls share the solution for this, did anyone able to solve this ? is it really into DP?
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.
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
Yes, you’re right about the minimums, and they should in fact be everywhere (sorry, I’ll edit the comment to fix the mistakes).
To compute suf[i][j][k], use the values you already have: suf[i][j][k] = min(dp[i][j][k], suf[i][j][k + 1]). This is because in suf[i][j][k + 1] you’ve already processed dp[i][j][(k + 1) \dots M], and the only difference is the single value dp[i][j][k]. The same goes for pre, except it’s based on k - 1.
So After complete iteration of DP[i][j][i…M] we will update the suf[i][j][1…M] and pre[i][j][1…M] for the next use ??
I’m not exactly sure what you mean, but I would find it easiest to compute them after finishing all values of k for a fixed i, j pair (because you won’t need these values until you get to computing i + 1, j + 1).
Actually you just gave a green tick to my above approach…I meant exactly the same what you are saying.
Nice talking to you 
1 Like
How to do the looping to find dp[i][j][k]
They extended it? What the hell? That’s the stupidest move I’ve ever seen, ofc people would talk about solutions after it ends. That being said, I’ll still remove it of course and repost it when it re-ends.
Hi @galencolin, the contest will end today can you share the solution, I tried dp but was not sure how I will find minimum value while making recursive calls as there can be n types of paints.
Tell me when the thing actually ends, I’ll just re-paste it in
1 Like
(Reposted):
Denote c[i][j] to be the cost of painting the i-th building as color j. Also, assume 1-indexing for everything as it makes the math easier.
Let dp[i][j][k] be the minimum cost to paint the first i buildings with j as the specialty of the first i buildings, such that the last color used was k (as in, the color of the i-th building is k). If the color of the i-th building is fixed, then all dp[i][j][k] for that i are \infty except for when k is the fixed color. Then when computing dp[i][j][k], there are two possibilities:
-
The color k is the same as the previous color. Then, when placing this color, the specialty does not change. So the value of this transition is dp[i - 1][j][k] + c[i][k]. This takes O(1) time.
-
The color k is different from the previous color. In this case, the specialty increases by 1, so the previous specialty must be 1 less than j. So the value of this transition is the minimum value of dp[i - 1][j - 1][p] + c[i][k], where p is any valid color not equal to k. This takes O(M) time.
The answer is the minimum over dp[N][K][c] over all 1 \leq c \leq M.
Naively, there are O(NMK) states and transitions are O(M). This will probably not pass if all tests in a file are maxtests. But we can speed the second type of transition up. Let pre[i][j][k] be the prefix minimum of dp[i][j][1 \dots k], and suf[i][j][k] be the suffix minimum of dp[i][j][k \dots M]. Then the entire second transition can be computed as min(pre[i - 1][j - 1][k - 1], suf[i - 1][j - 1][k + 1]) + c[i][k] (be careful with edge cases). Now this is O(NMK), which should pass easily.
2 Likes