Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @MathisHammel,validated by @Eniidras,@Westicles and @_CG_Keelhaul.
If you have any issues, feel free to ping them.
Hello.
It seems quite simple with dynamic programming. (Why is the level “difficult” ?)
But I think there’s a mistake in the 5th testCase. The answer should be 11047.
All the validators are correct.
Thank you for your feedback.
Your code that finds 11047 is probably not implementing the exact statement - are you sure it’s possible to build your solution by successively splitting the initial district into two rectangles? For example, this type of split would not be possible on a 3x3 district, even though all parts are rectangular:
AAB
DEB
DCC
Otherwise, I’d be happy to look into your solution to see what’s wrong.
Hi,
sorry for asking silly question, in the example it mentioned
“The optimal solution in that case is to split the initial 5x4 district vertically into a 4x4 and a 1x4 district. Then, the resulting 4x4 district is split horizontally in two districts of size 4x2. The resulting score is then 39 + 96 + 96 = 231, which is the highest possible amount of voters in that case.”
As my understand, 39 and 96 are both in first horizontally district (size of 4x2). I don’t know how the second 96 comes from.
How do you come up with: 39 , 96 and 96?
In the vertically district (1x4) the max voters is 162
40
81
154
162
why 162 is not included in the total?
Your dimensions aren’t correct and they don’t match the input you are given. The maximum voters you gain from a district of (1x4) (width x height) is 39 and not 162.
If you split a district of (4x4) into TWO districts of (4x2) then you have TWO districts with 96 voters, thats where the second 96 comes from.
Thank you, @KNTK . I think i got it now, it missread the instruction.
The input is a table of number of voters for each possible shape.
This is a good problem–fun to solve–but I agree with the earlier remark that it’s not very hard for a “Hard” puzzle. Also, the tags seem to be driving people to recursive solutions when there’s a faster and simpler (imho, since no memoization is needed) iterative solution available. (Not “algorithmically” faster, btw, since I think O(hw(h+w)) is the best that can be done.)
I give it 5 stars for the fun factor–even though the story line is a bit of an “ouch!” with respect to US politics right now. 
1 Like
So I have read this multiple times and I still do not understand how they come up with the numbers.
The idea is to divide a rectangle into smaller rectangles if the sum of the scores of the smaller rectangles is greater than the score of the original rectangle. Your goal is to find the maximum possible score that can be reached in that way.
If you read the grid into a matrix (2D array, list of lists, or whatever your language allows) then the j-th entry in the i-th row gives the score of each i-by-j rectangle in the final division. Since most languages use 0-based indexing for arrays, you’d use grid[h-1][w-1] to get the score for a rectangle with height h and width w. Does that help?
@Forsaken_Ch1ld Yeah it’s a little bit strange…
If we look at the example:
7 8 18 39 40
10 41 60 96 81
24 54 114 87 154
39 56 140 135 162
a 1x1 area contains 7 voters, because at coordinates (1,1) is 7
a 2x1 area contains 8 voters, because at coordinates (2,1) is 8
a 1x2 area contains 10 voters, because at coordinates (1,2) is 10
a 4x4 area contains 135 voters, because at coordinates (4,4) is 135, even if it can seem awkward since a 3x4 area contains more voters (140)
1 Like
Sorry I am new to this so even doing the questions is hard because I don’t understand how to format in the text box, anyways.
I understand how those numbers are found, what ever the x,y spot is the amount of voters. I fully understand that from example given. The issue is when we start splitting the districts.
From what I gather on the first split 4x4 and a 1x4 district. Making the coordinates
District 1: (0,0) to (4,4)
District 2: (5,0) to (5,4)
Then splitting District 1 further
District 1A: (0,0) to (4,2)
District 1B: (0,3) to (4,4)
So we have districts as seen in my grid below.
District 1A: (0,0) to (4,2)
District 1B: (0,3) to (4,4)
District 2: (5,0) to (5,4)
7 8 18 39 40
10 41 60 96 81
24 54 114 87 154
39 56 140 135 162
From there, how are the votes being calculated? What I would get is 162, 135, and 96 but that is wrong. Maybe I am looking way to much into this problem.
1 Like
I agree about how hard this is to understand.
I haven’t solved it yet, but I think this is right.
@Thanh2022 said “The input is a table of number of voters for each possible shape.”
@kuremon showed a grid of numbers that may be confusing at first.
Here is what I think.
This is the initial 5x4 district:
xxxxx
xxxxx
xxxxx
xxxxx
According to the input data, a 5x4 shaped district contains 162 voters.
A vertical cut is made to create two districts from the original one, a new 1x4 district and a new 4x4 district. There are 2 ways to make this vertical cut:
the first way to do it
x xxxx
x xxxx
x xxxx
x xxxx
the second way to do it
xxxx x
xxxx x
xxxx x
xxxx x
It does not matter which way the vertical cut was made.
According to the input data, any 1x4 shaped district contains 39 voters and any 4x4 shaped district contains 135 voters.
However the vertical was made, we now have 39+135=174 voters.
This is more than the 162 voters we started with, so it is an improvement.
For the second cut we start with the 4x4 district, containing 135 voters:
xxxx
xxxx
xxxx
xxxx
and we cut it horizontally, yielding two 4x2 districts:
xxxx
xxxx
xxxx
xxxx
According to the input data, any 4x2 shaped district contains 96 voters.
Since we have two districts with this shape, our horizontal cut gives us 96+96=192 voters, an improvement over the 135 voters contained in the 4x4 shaped district.
At this point the original 5x4 district has been divided into:
one 1x4 shaped district with 39 voters; and
two 4x2 shaped districts, each with 96 voters.
The total number of voters is 39+96+96=231.
Hope this helps.
3 Likes
This was a very cool puzzle (I don’t believe a beat a hard one).
Ahhh. that is cool, but from an autodidact, non use to solve programmation “Puzzles” and not train algorithmic ( sometimes i use it but i discover i do with CG 
) it seems hard . after lot hours i have my main code and achieve 60%. I have my recursive Function in Py3 and pass 3 first test, not the two last and i do not found where is my mistake. please achieve me. I will need to command CLRS books
If it just a question of optimisation, and if i can help, do not do the same calcul twice.
You will find that on large matrix, cut after cut, you will calcul the 2x4 maximum (for example) a lot of time, when it can be easy to store it and to not cut it anymore.
usage of “Memoisation” i thinks. I store an equivalent matrix of best_score decomposition and only read it for Ui-n so normally no more cut. but still 
. maybe it is nothing.
but ratio time pass/ results is really poor. I do not like to say that but “i will leave it alone”. And wait results for trying understand and learn from the bests.
Thank you, you have made the problem more easy to approach
I’m ashamed… I should have checked my stop conditions.
It works perfectly now 
I was fooled by the fact that my code was passing all the validators, but failing one test case.
I’m pretty proud of my solution.
But seriously… “difficult” ? 
Hi there. A bit of struggle to find how to cut and evaluate the shapes, but when you get the algorithm part, the code is quite short (and i do it in C++). Thanks for the puzzle !