| ENG RUS | Timus Online Judge |
Discussion of Problem 1035. Cross-stitchUXMRI: Sergey Baskakov, Raphail Akhmedisheff and Denis Nikonorov My best time is 0.078 s. I'm interested if there are quicker solutions. [5] // Problem 1035. Cross-stitch 12 Jun 2005 04:06 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. qwerty Mine is 0.046. (+) [2] // Problem 1035. Cross-stitch 12 Jun 2005 05:34 UXMRI: Sergey Baskakov, Raphail Akhmedisheff and Denis Nikonorov Thank you! (-) // Problem 1035. Cross-stitch 12 Jun 2005 16:12 zslwyuan Re: Mine is 0.046. (+) // Problem 1035. Cross-stitch 1 Dec 2011 16:01 Mine is 0.031 uuu Re: My best time is 0.078 s. I'm interested if there are quicker solutions. // Problem 1035. Cross-stitch 8 Apr 2010 14:00 I'm 0.015s Demenev Dmitriy Re: My best time is 0.078 s. I'm interested if there are quicker solutions. // Problem 1035. Cross-stitch 23 Dec 2015 15:07 ddfwf Karolis Kusas How to create a graph in this problem // Problem 1035. Cross-stitch 1 Jul 2011 18:00 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? zhuaiyaa Why it returns wrong and said my solution is stack overflow [2] // Problem 1035. Cross-stitch 25 Nov 2010 16:39 I was completely mad of it! (By the way ,my English is poor.) zhuaiyaa Re: Why it returns wrong and said my solution is stack overflow [1] // Problem 1035. Cross-stitch 25 Nov 2010 16:44 And what is the 16th test? Can anyone give me a test? Apreciated much. zhuaiyaa Re: Why it returns wrong and said my solution is stack overflow // Problem 1035. Cross-stitch 26 Nov 2010 11:37 I finally AC,I use BFS at last,DFS will return stack overflow Erop [USU] Good problem =) [1] // Problem 1035. Cross-stitch 16 Mar 2010 00:30 ile Re: Good problem =) // Problem 1035. Cross-stitch 27 Mar 2010 02:43 True... And kind of crazy... at first sight! =) Tbilisi SU: Giorgi Saghinadze (GVS) statement [1] // Problem 1035. Cross-stitch 22 May 2009 19:05 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 Despise_Me Re: statement // Problem 1035. Cross-stitch 2 Dec 2009 17:50 Sorry,it's hard to say in English. Ivan Georgiev Help wanted on 1035!! [3] // Problem 1035. Cross-stitch 24 Sep 2001 01:34 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. Jivko Ganev Re: Help wanted on 1035!! [1] // Problem 1035. Cross-stitch 24 Sep 2001 03:36 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 ... Ivan Georgiev Re: Thanks. Got AC (at last!!!!) Very tricky problem. // Problem 1035. Cross-stitch 28 Sep 2001 19:36 svr Re: Help wanted on 1035!! // Problem 1035. Cross-stitch 3 Jan 2009 17:47 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 sherry give some test for you~ // Problem 1035. Cross-stitch 10 Aug 2008 11:53 give you some test~~ 5 4 ..\/ \/.. /X.. ..X/ ..X. ..X. \/\/ \/.. \/.. \/.. ans:13 3 3 ..\ /\X ... ..\ /// ... ans:2 barty WA on #17 // Problem 1035. Cross-stitch 31 Oct 2007 07:52 Who can help me? my email address:yby.barty@163.com davidsun What's the answer of this input? [3] // Problem 1035. Cross-stitch 4 Aug 2006 10:59 What's the answer of this input, why? 2 2 \/ /\ \/ /\ I think it should be 2. Edited by author 04.08.2006 11:09 anus (USU) Re: What's the answer of this input? // Problem 1035. Cross-stitch 4 Aug 2006 12:38 No, right answer is 1. davidsun Re: What's the answer of this input? [1] // Problem 1035. Cross-stitch 4 Aug 2006 20:37 Ask again: 3 3 \\\ \\\ \\\ /// /// /// I think it should be 3. Edited by author 04.08.2006 20:41 anus (USU) Re: What's the answer of this input? // Problem 1035. Cross-stitch 4 Aug 2006 23:39 It is enough 2 threads: 1 \ \ \ \ \ / / / / 2 \ \ \ \ / / / / / Try to write cout << ans-1 << endl;) GoodLuck! Gene JHZ WA#9. Can anyone help me? [1] // Problem 1035. Cross-stitch 18 Jul 2006 20:27 I got WA#9. Does any one know anything about #9. Or can any one offer me some tests? 3Q. Gene JHZ Re: WA#9. Can anyone help me? // Problem 1035. Cross-stitch 20 Jul 2006 12:55 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! VC15 (Orel STU) Is there a mistake in format of input? [2] // Problem 1035. Cross-stitch 23 Sep 2005 21:16 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? Aleksandr Klepinin Re: Is there a mistake in format of input? [1] // Problem 1035. Cross-stitch 24 Sep 2005 12:37 Thank you for you have found this misprint. Now it is fixed. VC15 (Orel STU) Re: Is there a mistake in format of input? // Problem 1035. Cross-stitch 25 Sep 2005 16:32 You forgot to fix this bug ih the sample input. VC15 (Orel STU) Is there a mistake in format of input? // Problem 1035. Cross-stitch 23 Sep 2005 21:13 JIM Why wrong answer on test#9 // Problem 1035. Cross-stitch 18 Jul 2004 13:41 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? Costel::icerapper@k.ro Any more hints ? // Problem 1035. Cross-stitch 27 Feb 2002 22:15
|