Show all threads Hide all threads Show all messages Hide all messages |
OLE (probably 9) | kirdmiv | 1092. Transversal | 28 Oct 2020 20:49 | 1 |
If you are trying to flip signs on rectangles consider of using 1 request instead of many. :) |
I cant understand the problems!!!! | Xudong_LI | 1092. Transversal | 2 Jan 2017 23:36 | 2 |
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!
|
Hello. Could anybody tell me how to solve this problem? (See in) | Safe Bird (USU) | 1092. Transversal | 4 Jun 2016 12:46 | 8 |
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. |
A non-greedy solution | ucs6 | 1092. Transversal | 28 Nov 2015 18:07 | 2 |
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 |
Can't pass test number 1 | Maximus | 1092. Transversal | 8 Feb 2011 19:43 | 1 |
Edited by author 08.02.2011 19:51 |
Is there non-greedy solution? | VNTU Vitaly(Traning) | 1092. Transversal | 17 Jun 2010 03:59 | 4 |
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... |
Can anybody please tell me how to greedy this prob? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1092. Transversal | 19 Aug 2008 02:50 | 3 |
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. |
Possibly to solve with greedy algo even now | Vedernikoff Sergey | 1092. Transversal | 19 Aug 2008 02:48 | 2 |
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) |
I got wa#1..Do anybody has some tests? | double | 1092. Transversal | 19 Aug 2008 02:47 | 2 |
I had WA when I output non-permutation for the sample test |
Test | IGOR_Lviv NU | 1092. Transversal | 1 Apr 2008 12:32 | 2 |
Test IGOR_Lviv NU 5 Feb 2008 03:19 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 |
I used Greedy (with maximum flow) and I get WA on test 7 | Alexandru Popa | 1092. Transversal | 14 Sep 2007 01:40 | 2 |
Do you know what is test 7 ? Or maybe I made a mistake in my program. |
OLE 11 help! | mj256 | 1092. Transversal | 7 Sep 2007 20:45 | 1 |
I use hungary algo, but OLE. It is right to use this algo? Or what should I improve in my prog? Any hint? Plz |
Problem 1092 "Transversal" has been rejudged (+) | Sandro (USU) | 1092. Transversal | 16 Dec 2006 19:50 | 1 |
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. |
You can Feel the Power of 'Random'. | 198808xc | 1092. Transversal | 10 May 2005 14:46 | 2 |
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 |
I used Greedy and got AC.But I found that my algorithm isn't right for all case and the tests seem to be always have a solution. | Yu YuanMing | 1092. Transversal | 30 Jun 2004 22:57 | 2 |
Is there somebody has a correct idea? Please write it down. Thanks! |
could somebody tell me what is this problem mean? | anson | 1092. Transversal | 11 Apr 2004 07:13 | 1 |
could somebody tell me what is this problem mean?thank you very much. |
What is the output if there are already less then 2*n '+' signs in the input itself? | Petko Minkov | 1092. Transversal | 20 Jun 2003 13:26 | 4 |
Re: Say Pete Lupherenko 25 Oct 2001 22:20 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 , Thanks !!! | XueMao | 1092. Transversal | 31 May 2003 14:13 | 1 |
Can anyone tell me how to do it , Please say it clearly , Thanks !!! |