You are not logged in. Please login at www.codechef.com to post your questions!

×

CONNECT - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

My solution for this problem is a random method with dynamic programming.

The first step is to get the dynamic programming method when there are only k different numbers in the matrix.
Let f[i][j][s] state that you are at (i,j) and you have the numbers in the set s.
You can find that the best answer should be a tree shape. That gives us a way to DP.
there are two types of transition:
1.|s| increases.
2.|s| does not change.
we can implement the second one by Shortest Path algorithms.
Thus, we get a perfect algorithm to solve this reduced problem.

The second step is the most creative step.
If you map all the numbers into 1..k, what is the probability you can get the correct answer using the above algorithm on the new matrix?
It is clear that is (k!)/(k^k).
Since k<=7, the probability is >=7!/7^7. So if you repeat this progress much more time, you can almost sure your answer is the best one.

In all submissions in this contest, some of them are accepted by this random method and others seem accept by other method like searching and so on.
However, this problem is a very interesting problem that can be solved by many solutions. I hope you have fun in thinking and solving this problem.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 12 Nov '12, 13:56

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,359
×10
×1

question asked: 12 Nov '12, 13:56

question was seen: 1,352 times

last updated: 12 Nov '12, 13:56