|
|
I used a little different approach from the one mentioned on this board. It was based on weighted quick-union described by Sedgewick... I made a stupid logical mistake which caused my program to work the longest time possible, so first I got TLE#10 (solutionID=861144). Then I optimized my code with path compression (see Sedgewick once again) and got AC in 0.125 sec (solutionID=861147). Then I realized my error, removed path compression and got AC in 0.078 s (solutionID=861151). Adding path compression back slowed my solution a bit (0.109 s, solutionID=861153). All my solutions consume 449 KB of memory. I'm interested in time and memory requirements of other possible algorithms. I haven't got their implementations, so I cann't submit them myself. If somebody feels interested about my approach to this problem, just let me know - I'll explain. Hello, I tried to create a graph for this problem in this way: Vertices correspond to intersections of the board (left upper (0; 0) and right lower (n; m)). I will denote the vertice by [i][j][l]. If i = 0, then we have face of the cloath, else if i = 1, we have the rear of the cloth. j means the row, and l - column. For the example test, graph edges: [0][1][1] <-> [1][2][2] [0][2][2] <-> [1][1][1] [0][2][2] <-> [1][3][3] [0][3][3] <-> [1][2][2] [1][2][1] <-> [0][3][2] [1][2][2] <-> [0][3][3] [1][2][3] <-> [0][3][2] [1][2][5] <-> [0][1][4] [1][3][2] <-> [0][2][1] [1][3][2] <-> [0][2][3] [1][3][3] <-> [0][2][2] I can not count degrees correctly with this graph even for the example test. Is there a better graph representation? If no, how to solve the problem with this one? I was completely mad of it! (By the way ,my English is poor.) And what is the 16th test? Can anyone give me a test? Apreciated much. I finally AC,I use BFS at last,DFS will return stack overflow True... And kind of crazy... at first sight! =) I cant understand problem statement , I'm reading it for 1 hour and can't understand what they want ;( please explain it to me... thanks Sorry,it's hard to say in English. As far as I can see the problem has relatively small percent of the difficulty, but I can't think of the way I should walk the pattern by means of minimal number of threads.. Is the problem only a DFS (and if it is how should it be done) or there is something else? Thank you. You need some graph theory and common sense to solve it. Basically after you do the logic the problem breaks down to simple bfs/dfs and counting degrees. The idea comes from the problem of decompossing graph to a minimum amount of paths which is solved by some simple logic - you should be able to prove it yourself. Hint - it has something to do with Euler ... Helpfull to have math invariant(which right for every algo) I think that answer=Nc+Ndb/2 where Ndb- sum of disbalances of vertices of grid's graph. and Nc- number of alternating loops which unreached from disbalanced vertices by alternating pathes. But can't go far then test 8. AC 0.031 now.Idea is right. It taken 3 days to convert idea in quick algo. Edited by author 04.01.2009 10:13 give you some test~~ 5 4 ..\/ \/.. /X.. ..X/ ..X. ..X. \/\/ \/.. \/.. \/.. ans:13 3 3 ..\ /\X ... ..\ /// ... ans:2 Who can help me? my email address:yby.barty@163.com What's the answer of this input, why? 2 2 \/ /\ \/ /\ I think it should be 2. Edited by author 04.08.2006 11:09 Ask again: 3 3 \\\ \\\ \\\ /// /// /// I think it should be 3. Edited by author 04.08.2006 20:41 It is enough 2 threads: 1 \ \ \ \ \ / / / / 2 \ \ \ \ / / / / / Try to write cout << ans-1 << endl;) GoodLuck! I got WA#9. Does any one know anything about #9. Or can any one offer me some tests? 3Q. I found my algo wrong. And I changed it. But I got WA#7. What a pity! Can any one offer me some tests? I need help! It is said in the input "...The symbols used are “.”, “/”, “” and “X”...". Looks like it should be "\" instead of "". Am I right? Or it is necessary to check every possible position of "\" character? Thank you for you have found this misprint. Now it is fixed. You forgot to fix this bug ih the sample input. Is the algorithm that DFS all the vertices and count the number of threads? But why wrong answer on test#9? Is there any tricky input available? |
|
|