Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
OLE (probably 9) | kirdmiv | 1092. Трансверсаль | 28 окт 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. Трансверсаль | 2 янв 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. Трансверсаль | 4 июн 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. Трансверсаль | 28 ноя 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. Трансверсаль | 8 фев 2011 19:43 | 1 |
Edited by author 08.02.2011 19:51 |
Is there non-greedy solution? | VNTU Vitaly(Traning) | 1092. Трансверсаль | 17 июн 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. Трансверсаль | 19 авг 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. Трансверсаль | 19 авг 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. Трансверсаль | 19 авг 2008 02:47 | 2 |
I had WA when I output non-permutation for the sample test |
Test | IGOR_Lviv NU | 1092. Трансверсаль | 1 апр 2008 12:32 | 2 |
Test IGOR_Lviv NU 5 фев 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. Трансверсаль | 14 сен 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. Трансверсаль | 7 сен 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. Трансверсаль | 16 дек 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. Трансверсаль | 10 май 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. Трансверсаль | 30 июн 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. Трансверсаль | 11 апр 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. Трансверсаль | 20 июн 2003 13:26 | 4 |
Re: Say Pete Lupherenko 25 окт 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. Трансверсаль | 31 май 2003 14:13 | 1 |
Can anyone tell me how to do it , Please say it clearly , Thanks !!! |