| Show all threads Hide all threads Show all messages Hide all messages |
| My best time is 0.078 s. I'm interested if there are quicker solutions. | UXMRI: Sergey Baskakov, Raphail Akhmedisheff and Denis Nikonorov | 1035. Cross-stitch | 23 Dec 2015 15:07 | 6 |
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. Thank you! (-) UXMRI: Sergey Baskakov, Raphail Akhmedisheff and Denis Nikonorov 12 Jun 2005 16:12 |
| How to create a graph in this problem | Karolis Kusas | 1035. Cross-stitch | 1 Jul 2011 18:00 | 1 |
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? |
| Why it returns wrong and said my solution is stack overflow | zhuaiyaa | 1035. Cross-stitch | 26 Nov 2010 11:37 | 3 |
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 |
| Good problem =) | Erop [USU] | 1035. Cross-stitch | 27 Mar 2010 02:43 | 2 |
True... And kind of crazy... at first sight! =) |
| statement | Tbilisi SU: Giorgi Saghinadze (GVS) | 1035. Cross-stitch | 2 Dec 2009 17:50 | 2 |
statement Tbilisi SU: Giorgi Saghinadze (GVS) 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 Sorry,it's hard to say in English. |
| Help wanted on 1035!! | Ivan Georgiev | 1035. Cross-stitch | 3 Jan 2009 17:47 | 4 |
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 some test for you~ | sherry | 1035. Cross-stitch | 10 Aug 2008 11:53 | 1 |
give you some test~~
5 4
..\/
\/..
/X..
..X/
..X.
..X.
\/\/
\/..
\/..
\/..
ans:13
3 3
..\
/\X
...
..\
///
...
ans:2 |
| WA on #17 | barty | 1035. Cross-stitch | 31 Oct 2007 07:52 | 1 |
Who can help me?
my email address:yby.barty@163.com |
| What's the answer of this input? | davidsun | 1035. Cross-stitch | 4 Aug 2006 23:39 | 4 |
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! |
| WA#9. Can anyone help me? | Gene JHZ | 1035. Cross-stitch | 20 Jul 2006 12:55 | 2 |
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! |
| Is there a mistake in format of input? | VC15 (Orel STU) | 1035. Cross-stitch | 25 Sep 2005 16:32 | 3 |
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 there a mistake in format of input? | VC15 (Orel STU) | 1035. Cross-stitch | 23 Sep 2005 21:13 | 1 |
|
| Why wrong answer on test#9 | JIM | 1035. Cross-stitch | 18 Jul 2004 13:41 | 1 |
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? |
| Any more hints ? | Costel::icerapper@k.ro | 1035. Cross-stitch | 27 Feb 2002 22:15 | 1 |
|
