Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Another easy approach | andreyDagger | 1229. Прочная кладка | 24 ноя 2021 10:53 | 1 |
You can always fill 2 * m area |
Why WA1? | Peshkov [57 lyceum tlt] | 1229. Прочная кладка | 24 ноя 2021 10:50 | 2 |
Why WA1? Peshkov [57 lyceum tlt] 13 июл 2020 12:15 My program got WA1 with answer 1 2 3 4 1 2 3 4 on example test Why? |
[Hint] Very easy problem | hadooken | 1229. Прочная кладка | 10 дек 2019 14:13 | 1 |
Check all 2x2 squares A[i][j] A[i][j+1] A[i+1][j] A[i+1][j+1] Make sure you always can cover this square at least one of the methods x x y y or x y x y Edited by author 10.12.2019 14:13 Edited by author 10.12.2019 14:15 |
AC with maximum bipartie, guys! | SmnTin | 1229. Прочная кладка | 25 сен 2019 14:15 | 1 |
|
What's wrong with my algo? | Akaishuichi | 1229. Прочная кладка | 23 окт 2017 22:08 | 3 |
Finally ACed by changing to a direct approch. But I still don't understand what's wrong with my previous algo(which results to WA5) It's something like this: For example, for such a input: 4 6 1 1 2 3 3 7 4 5 2 6 6 7 4 5 8 9 12 11 10 10 8 9 12 11 1.Construct a n*m graph G, every vertices connected with all it's neighbors(up, down, left, right) (for layout reasons here I use hex to number the vertices) (the graph left is only a illustration to explain the things happening to the former graph. the graph right shows the result we get in every stage.) 1-1-2-3-3-7 o-o-o-o-o-o | | | | | | | | | | | | 4-5-2-6-6-7 o-o-o-o-o-o | | | | | | | | | | | | 4-5-8-9-C-B o-o-o-o-o-o | | | | | | | | | | | | A-A-8-9-C-B o-o-o-o-o-o 2.Remove an edge whose endpoints have the same number. Repeat this operation until no such pairs connected. finally we get something like this 1 1-2-3 3-7 o o-o-o o-o | | | | | | | | 4-5-2-6 6-7 o-o-o-o o-o | | | | | | | | 4-5-8-9-C-B o-o-o-o-o-o | | | | A A-8-9-C-B o o-o-o-o-o 3.Pick a vertex v, which has a minimum degree(non-zero), and w, an arbitrary neighbor of v. Assign a incremental number to both v and w, and remove all the edges who cover v or w. Repeat this operation until Δ(G) == 0. For the input the process will be: (STEP1) 1 1-2-3 3-7 1 o-o-o o-o | | | | | | | 4-5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4-5-8-9-C-B o-o-o-o-o-o | | | | A A-8-9-C-B o o-o-o-o-o (STEP2) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4-5-8-9-C-B o-o-o-o-o-o | | | | A A-8-9-C-B o o-o-o-o-o (STEP3) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5-8-9-C-B 3 o-o-o-o-o | | A A-8-9-C-B 3 o-o-o-o-o (STEP4) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5-8-9-C-B 3 o-o-o-o-o | | A A-8-9 C B 3 o-o-o 4 4 (STEP5) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5-8-9-C-B 3 o-o-o-o-o | | A A 8 9 C B 3 o 5 5 4 4 (STEP6) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5 8-9-C-B 3 6 o-o-o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP7) 1 1 2 3 3 7 1 7 7 o 2 2 | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5 8-9-C-B 3 6 o-o-o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP8) 1 1 2 3 3 7 1 7 7 o 2 2 | | 4 5 2 6 6-7 1 8 8 o o-o | | | | | | 4 5 8-9-C-B 3 6 o-o-o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP9) 1 1 2 3 3 7 1 7 7 9 2 2
4 5 2 6 6-7 1 8 8 9 o-o | | | | 4 5 8-9-C-B 3 6 o-o-o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP10) 1 1 2 3 3 7 1 7 7 9 2 2
4 5 2 6 6-7 1 8 8 9 o-o | | | | 4 5 8 9 C-B 3 6 A A o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP11) 1 1 2 3 3 7 1 7 7 9 2 2
4 5 2 6 6 7 1 8 8 9 B B
4 5 8 9 C-B 3 6 A A o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP12) 1 1 2 3 3 7 1 7 7 9 2 2
4 5 2 6 6 7 1 8 8 9 B B
4 5 8 9 C B 3 6 A A C C
A A 8 9 C B 3 6 5 5 4 4 4.Finally we got a valid output: 1 7 7 9 2 2 1 8 8 9 B B 3 6 A A C C 3 6 5 5 4 4 I know I must mistaked something, but I can't find the mistake. Please tell me where is wrong, or give me some tests to beat this algo. Thanks in advance. Edited by author 31.05.2009 00:28 Sorry Akaishuichi 31 май 2009 00:32 I'm sorry the layout turned out to be totally unreadable. Please copy the text to the notepad for viewing the graph edges. It was a very good question. What's wrong with the algo? "3. Pick a vertex v, which has a minimum degree (non-zero)..." If there are several (not one) such vertices, we must do a choice. Let choose the vertix (with a minimum degree) that is placed in the least row. If the row has several vertices with a minimum degree, let choose the vertix that is placed in the least column. The next choice is the choice of w (see the algo). Let choose right neighbor of v if v is connected with it. Otherwise let choose bottom neighbor of v as w. So we have input data that breaks the algo: 6 6 1 1 2 2 3 4 5 5 6 7 3 4 8 9 6 7 10 11 8 9 12 12 10 11 13 14 15 15 16 17 13 14 18 18 16 17 STEP 12 1 9 9 3 2 2 1 10 10 3 11 11 4 4 o - o 12 12 | | o - o - o o - o - o | | | | o - o 6 8 o - o 5 5 6 8 7 7 STEP 13 (it is not good) 1 9 9 3 2 2 1 10 10 3 11 11 4 4 13 13 12 12
o - o - o o - o - o | | | | o - o 6 8 o - o 5 5 6 8 7 7 I'm sure we can build input data that makes the algo invalid if we would choose the v and w in other way. Edited by author 23.10.2017 22:15 |
WA5 | Programmer | 1229. Прочная кладка | 24 сен 2015 11:25 | 1 |
WA5 Programmer 24 сен 2015 11:25 I passed 5 test, when change method is_inside: from return (0<=i&&i<=n&&0<=j&&j<=m) to return (0<=i&&i<n&&0<=j&&j<m) what test failed me? |
When soultion does not exist? | Georgiy Savchenko | 1229. Прочная кладка | 17 мар 2014 15:02 | 3 |
Could someone publish such testcase with the answer = -1? Edited by author 25.07.2008 18:11 If m and n are even, there is always a solution. |
WA5 | pmartynov | 1229. Прочная кладка | 2 фев 2013 21:32 | 2 |
WA5 pmartynov 2 фев 2013 20:13 Could someone provide me with a testcase that returns -1? paul.martynov@gmail.com I've written a random test case generator for the problem and created more than 200 tests but still can't find any that results in -1. What's the trick? |
Need help??? | Lebedev_Nicolay[Ivanovo SPU] | 1229. Прочная кладка | 9 май 2009 23:01 | 1 |
How to construct bipartite graph there? |
More interesting (+) | Alexander Kouprin | 1229. Прочная кладка | 16 авг 2008 03:20 | 4 |
This problem is very simple. I think it can be more interesting if one of dimensions can be odd. For example: 4 5 1 1 2 2 3 4 5 5 6 3 4 7 7 6 10 8 8 9 9 10 Another example: 2 3 1 2 3 1 2 3 Anyway, bipartie algo does not depend on that :) That tests aren't correct. "M and N are EVEN numbers not exceeding 100" |
I've got test #3. Maybe it will help somebody. | TECTOBOP | 1229. Прочная кладка | 25 июл 2008 19:02 | 2 |
Just 122 submissions. He-he... 10 10 1 1 3 5 7 9 11 11 13 13 15 15 3 5 7 9 17 17 19 21 23 25 25 27 29 29 31 33 19 21 23 35 37 27 39 39 31 33 41 41 49 35 37 43 43 45 45 47 47 50 49 36 38 44 44 46 46 48 48 50 24 36 38 28 40 40 32 34 42 42 24 26 26 28 30 30 32 34 20 22 16 16 4 6 8 10 18 18 20 22 2 2 4 6 8 10 12 12 14 14 I had crash at test3 when I forgot to reset size of BFS array. |
help | @ntiFreeze | 1229. Прочная кладка | 25 июл 2008 18:11 | 3 |
help @ntiFreeze 11 мар 2007 19:42 please explain me what is meaning of this problem? I think I don't understood problem statement well and I have WA 1 :( Help Please Re: help Giorgi Saghinadze (Tbilisi SU) 11 мар 2007 21:51 As I understand if there is such test: 11 22 answers may be: 12 12 or 21 21 22 11 is incorrect im my opinion. but I am not sure can anybody tell me am I correct or not? Re: help Denis Koshman 25 июл 2008 18:11 |
test 4 is wrong, or wrong checker | stdio | 1229. Прочная кладка | 27 май 2008 11:49 | 5 |
before output I check arrays: for(i = 0; i < n; i++) for(j = 1; j < m; j++) if( a[i][j-1] == a[i][j] && b[i][j-1] == b[i][j] ) while(1);
for(i = 1; i < n; i++) for(j = 0; j < m; j++) if( a[i-1][j] == a[i][j] && b[i-1][j] == b[i][j] ) while(1); and I have wa4, not TL Did you number the bricks correctly? I numbered bricks by squares: xx yy
or xy xy Maybe it wrong? Use int instead of char. There can be numbers up to 5000 in the answer. |
Help me! | Alex Stoff | 1229. Прочная кладка | 22 фев 2006 16:39 | 1 |
Please, give me some tests to check my programm... I have WA |
Hint | BFL | 1229. Прочная кладка | 9 дек 2005 22:12 | 1 |
Hint BFL 9 дек 2005 22:12 bipartite perfect matching |
Can sample output be... | Danica Porobic | 1229. Прочная кладка | 6 сен 2004 01:54 | 5 |
1 2 3 4 1 2 3 4 And what sentence "that no brick in it rests on a brick from the first layer" mean? That whole brick in second row cannot rest on whole brick in first row, or ...? And what's output for this input: 4 2 1 1 2 2 3 3 4 4 And what's output for this input: 4 2 1 1 2 2 3 3 4 4 This is incorrect input for this task. Sorry, my this my mistake. Correct answer for this simple is : 1 2 1 2 3 4 3 4 And what's output for this input: 4 2 1 1 2 2 3 3 4 4 This is incorrect input for this task. Sorry, this is my mistake. Correct answer for this simple is : 1 2 1 2 3 4 3 4 Edited by author 06.09.2004 01:55 |
why i get WA?? who can help me?? | Zhang Ruiwen | 1229. Прочная кладка | 20 ноя 2002 15:21 | 1 |
var a,b:array[1..100,1..100] of char; ans:array[1..100,1..100] of integer; m,n,i,j,top:integer; procedure init; var aa:array[1..100,1..100] of integer; begin fillchar(a,sizeof(a),' '); readln(n,m); for i:=1 to n do for j:=1 to m do read(aa[i,j]); for i:=1 to n do for j:=1 to m do if a[i,j]=' ' then begin if a[i,j+1]=a[i,j] then begin a[i,j]:='l'; a[i,j+1]:='r'; end else begin a[i,j]:='u'; a[i+1,j]:='b'; end; end; top:=0; fillchar(b,sizeof(b),' '); end; procedure print; var i,j:integer; begin for i:=1 to n do begin for j:=1 to m do write(ans[i,j],' '); writeln; end; end; function can(u,v,i:integer):boolean; begin if i=1 then begin if (a[u,v]<>'l')and(v+1<=m) then can:=true else can:=false; end else begin if (a[u,v]<>'u')and(u+1<=n) then can:=true else can:=false; end; end; procedure work(u,v:integer); var i:integer; begin if (u=n+1)and(v=1) then begin print; halt; end; if b[u,v]=' ' then begin for i:=1 to 2 do if can(u,v,i) then begin inc(top); if i=1 then begin b[u,v]:='l'; b[u,v+1]:='r'; ans[u,v]:=top; ans[u,v+1]:=top; end else begin b[u,v]:='u'; b[u+1,v]:='b'; ans[u,v]:=top; ans[u+1,v]:=top; end; if v+1<=m then work(u,v+1) else work(u+1,1); if i=1 then begin b[u,v]:=' '; b[u,v+1]:=' '; end else begin b[u,v]:=' '; b[u+1,v]:=' '; end; end; end else if v+1<=m then work(u,v+1) else work(u+1,1); end; begin init; work(1,1); writeln(-1); end. |
Help!!!!!!!!!Please send some hit to me if you have got AC in this problem.Thanks! | Tony | 1229. Прочная кладка | 18 ноя 2002 14:44 | 4 |
|