If you are trying to flip signs on rectangles consider of using 1 request instead of many. :) Could someone tell me what's the meaning of this problem?my english is noot good.The google translation is bad. let: 2D array[N][N], and transversal is a cells of N , which for each row and each column has one cell in the transversal. for example: 2D array: 1) 2) 3) ============= 1)| 1 2 3 2)| 4 5 6 3)| 7 8 9 transversal-1: { (1;1) , (2;2) , (3;3) } // (row, col) -- coordinate of a cell, . transversal-2: { (1;1) , (2;3) , (3;2) } transversal-3: { (1;2) , (2;1) , (3;3) } transversal-4: { (1;2) , (2;3) , (3;1) } transversal-5: { (1;3) , (2;1) , (3;2) } transversal-6: { (1;3) , (2;2) , (3;1) } Note that, there 1*2*3...*N = N! different transversals exist. Now, about problem: 2D array with 2N+1 x 2N+1 size , elements '+' or '-'. And allowed operation: can change sign to opposite in all cells in a transversal. You are asked to determine if it is possible to obtain a table containing not more than 2N cells with the sign "+" by a sequence of such operations Good Luck!
Someone said that it can be solved by Greedy. Just use net flow to catch the largest number of "+". And then so. But they all said that it is a wrong arithmetic. Could you tell me your way to solve it? > Someone said that it can be solved by Greedy. Just use net > flow to catch the largest number of "+". And then so. But > they all said that it is a wrong arithmetic. Could you tell > me your way to solve it? > > Someone said that it can be solved by Greedy. Just use net > > flow to catch the largest number of "+". And then so. But > > they all said that it is a wrong arithmetic. Could you > tell > > me your way to solve it? You can't prove it, because there is a counter-eaxample: 2 +---- +---- +---- +---- +---- Could you tell me what's the meaning of this problem?my english is noot good.The google translation is bad. I solved this problem with a non-greedy solution. Basically there are only one of the following 4 cases: 1. total number of '+' is <= 2N, problem solved; 2. There exists one column without any '+', and there also exists one column with more than 2 '+'(i.e. at least three), in this case you can "move" that two '+'s to the empty column (through two permutations); 3. Similar condition for case 2, move the row; 4. None of above is satisfied, using Hungarian Algorithm to find a best traversal. Repeat above process until case 1 is reached. This is not greedy and we can prove that it is correct: Both case 2 and 3 guarantees that 1) the total number of '+'s does not change, and 2) cannot continue infinitely, i.e. it must reach case 4 at some point. Then case 4 guarantees the total number of '+'s will be reduced at least by 1 (due to the fact that 2N + 1 is odd, and neither case 2 and case 3 is satisfied, can be easily proved) Good solution! A great fix to the greedy algorithm Edited by author 08.02.2011 19:51 I founded some non-greedy solution :) O(N^4) As far as I remember I solved it by math. My algo is likely to be O(N^3). can you briefly describe what you did? i could solve it only with greedy approach... Put all + signs onto main diagonal (except for the last row). Then you have to (optionally) flip main diagonal and reduce double + in columns towards single + in the last column. Even after anti-greedy tests were added, it is possibly to solve the problem with greedy algo. Just randomize directions in which you make "greedy walk" of the incidence matrix. The best thing is that it is impossible to kill such an algo with any anti-greesy tests! =) I have proven greedy solution (with O(N^3) output size) RT. TXs. I had WA when I output non-permutation for the sample test Could someone tell me what is the answer for this test? 2 ----+ ----+ ----+ ----+ ----+ I haven't got AC yet, but possible answer is: 5 4 3 2 1 4 5 3 2 1 4 3 5 2 1 3 4 2 5 1 3 4 2 1 5 Do you know what is test 7 ? Or maybe I made a mistake in my program. I use hungary algo, but OLE. It is right to use this algo? Or what should I improve in my prog? Any hint? Plz The problem is under investigation yet. Some new "anti-greedy" tests were added, many submits have lost AC verdict. You can check that greedy algorithm really does not solve this problem. I used Greedy(Hungary Algorithm) and Randomization in my Program and Got ACed. First Time, ACed at 1.000s; While Second, Failed because TLE. Third Time, ACed again at 0.015s!!! Forth Time to Ninth Time, Either OLE or TLE... Tenth Time, ACed at 0.564s...... What a 'Strange' Program I've Created! After you do max_match, when you change the un-matched rows' state, there maybe many orders, but some of them are wrong, and will get OLE, so you can use randomization (I think this method is very good! ^_^). But in this problem, you just change the un-matched rows' state in increasing order, then you will get AC. (At the first time, I used decreasing order, but I got OLE :( ,then I used increasing order and got AC with 0.015s :) ). I'm sorry my English is so poor... :( Edited by author 10.05.2005 14:46 Is there somebody has a correct idea? Please write it down. Thanks! could somebody tell me what is this problem mean?thank you very much. Well, but the description contains: <The first line of the output should contain the words "No solution" if a necessary sequence of operations does not exist.> So, we should write "No solution".... Are you an author of the problem? If yes, what EXACTLY should we output Can anyone tell me how to do it , Please say it clearly , Thanks !!! |
|