Hello Codeforces!
I have a programming problem form Iranian Olympiad in Informatics in type of Project Euler problems and I want you to help me for solving this problem:
Suppose that we have a $$$m \times n$$$ table that every cell of this table has filled with an integer, so that the sum of the numbers in $$$i$$$'th row of the table is $$$a_i$$$ and the sum of numbers in $$$i$$$'th column of the table is $$$b_i$$$. We say the sequence below key sequence:
$$$[a_1,a_2,\ldots,a_m,b_1,b_2,\ldots,b_n]$$$
Suppose again we write down all of the ways of filling a $$$5 \times 5$$$ table with numbers 0,1,2 so that at least one number 2 exists in the table, and calcute their key sequences. If the number of distinic sequences is $$$M_3$$$, What is the $$$M_3 mod \Delta$$$?($$$\Delta=10039$$$)
If you have a sulotion that solves this problem in less than 15 minutes, your sulotion is useful!
And like my other blog entry, sorry for my bad English!
Do you by any chance have the solution so i can see if my method works well?
Try back track but before running it optimize it az much az you can.
how ever a friend told me it has a faster solution with matching!
Ok so here is my idea, but i'm not at all sure its correct. Since there are less ways to choose the key sequences than to choose the board we will do that. (The maximum values of an element can be 10). Notice that we can swap any two rows/columns in the board and by doing so swap the value in any two elements ai,aj or bi,bj. Look at all the key sequences such that they have the first 5 element and the last 5 elements sorted. There are not that many of them (3003*3003) (i think) so we can check all the combinations. For each combination, we can see if there is a board that is good for that key sequence with a greedy algorithm.
Now if a key sequence is good, we add it to the answer but we also add all the sequences we can get by swapping the first/last 5 elements.
Edit: by running this appoach, i got that the answer is 1018871059 or 2910 under modulo This too a little over 1 second to complete in codeforces
Thanks for thinking about this problem! But, unfortunately, your answer (8197) is incorrect :( (I submited it in a persian judge) Mybe your code has bug!
Actually I had this idea too but I didn't know how can see if there is a board that is good for that key sequence in a good time!
Can you express your greedy algorithm?
EDIT, new greedy:
First of all, since we need to place a two somewhere, i think its always the best to place it at the intersection of the row with the maximum sum and the column with the maximum sum and fill the rest of the matrix with this algorithm.
I will store in a priority queue, the values for each column and the number of times i took something form that column in this row. We will always choose the column with the highest value from which i didn't already take two values, subtract the values for that column and the current row, and also increase the counter of how many times i took that value.
If you want it you can find the code here
I think your greedy algorithm is incorect
You can see this sample: <5,5,5,5,6,5,5,5,5,6>
there is a table like below:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 2
But you can check that your algorithm (If I didn't take mistake) says this sequence is not good!
Yea, as i said in the edit. The greedy is incorrect. And all the other greedy's i have tried so far have also been incorrect. I will tell you if i figure something out.
Edit: I think i figures something out and i edited my comment above with the new approach.
.