MohamedHamada_'s blog

Need help in CF 313C

By MohamedHamada_, history, 6 years ago, In English

in the 313C i tried to solve it recursively. then i got WA (i expected either AC or TLE Due to the recursion complexity )

i tried this test :

16

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

following the problem description , i have 2^2 * 2^2 matrix so i pick the max number = 16 and then divide the matrix to 4 2*2-matrices

next, for each 2*2 matrix i choose the max number and then divide each sub-matrix to another 4 submatrices of size 1*1

this the base case so the answer so far ( due to my solution ! )

= 16 + 6 + (1+2+5+6) +8 +(3+4+7+8) +14 + (9+10+13+14) +16+(11+12+15+16) = 196 [Wrong answer !]

i cloned an accepted code and tested my above test case and the answer = 210 (not 196 )

this is my Submission

any help appreciated , Thanks in advance :)

UDP :

i wasn't Sort the numbers in such way that maximize the answer , the right matrix for the above input :

and the answer = 16 +(16 + ( 11+12+8+16) + 15+(9+10+6+15) + 14+(3+4+7+14) + 13+(1+2+5+13)) = 210

thanks for you help.

Regards.

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In your code, I didn't see any procedure that deal with arranging the input array in an optimal way. You just put the elements in the order of inputting them.

As we can see from the problem statement, we are required (or allowed) to put each element of the input array in a single individual cell of a 2^n * 2^n matrix so that the beauty of the matrix is maximal.

Actually, I haven't yet got the way that should be followed to write hints for this problem or to explain the solution of it, but the point above is necessary to be considered.

Hope you will get the solution early :D

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't want to spoil this problem too much for you, but observe how many times each value is counted, and why.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Each of the largest 4 elements in the array ( 13, 14, 15 and 16 in your example ) should be placed in a different quadrant partition of the matrix so as to maximize the overall beauty of the matrix. In your suggested solution, these four elements are placed in two quadrants only.

→ Reply