I've been trying to solve this problem for so long, I've had a lot of errors, more than 150 lines of clean code, I've tried to do a little dirty debug, but I think it's not fair. I got wa11, I didn't know what it was, it just turns out I forgot to sort the array correctly, it was in the second part when I'm looking for vertical stripes that I forgot to sort and got wa 11, while I was looking for it, I did a lot of tests and can show them to you. I can give advice on what to count, count all vertical rectangles 1*l where l>=2 and horizontal rectangles l*1 where l>=2, add them up and add all single cells. tests: 4 4 10 1 2 1 3 2 1 2 4 3 2 3 3 4 1 4 2 4 3 4 4 5
4 4 5 1 2 2 1 2 4 3 3 4 2 9 4 4 8 2 1 2 2 2 3 2 4 3 1 3 4 4 2 4 3 4 4 4 8 1 2 1 3 2 1 2 3 3 1 3 3 3 4 4 2 5 4 4 4 2 2 2 3 3 2 3 3 4 4 4 3 2 3 3 2 3 3 6 5 5 2 4 3 3 4 12 5 5 5 1 3 3 1 4 1 3 4 4 3 12 5 5 6 1 3 3 1 4 1 4 2 4 3 3 4 12 5 5 12 1 2 1 4 2 1 2 3 2 5 3 2 3 4 4 1 4 3 4 5 5 2 5 4 13 5 5 11 1 2 1 4 2 1 2 3 2 5 3 2 3 4 4 1 4 5 5 2 5 4 11 5 5 9 1 2 2 4 3 1 3 3 3 4 4 2 4 5 5 2 5 5 11 5 5 9 1 5 2 5 2 4 3 3 3 4 4 2 4 3 5 1 5 2 10 5 5 12 1 2 1 3 1 4 2 1 3 1 4 1 2 5 3 5 4 5 5 2 5 3 5 4 10 6 6 12 2 1 2 2 2 3 2 4 2 5 3 5 4 5 5 5 5 4 5 3 5 2 4 2 8 7 4 14 1 1 2 1 3 1 4 1 5 1 6 1 7 1 1 4 2 4 3 4 4 4 5 4 6 4 7 4 9 7 4 18 1 1 2 1 3 1 4 1 5 1 6 1 7 1 1 4 2 4 3 4 4 4 5 4 6 4 7 4 1 2 1 3 7 2 7 3 7 7 4 20 1 1 2 1 3 1 4 1 5 1 6 1 7 1 1 4 2 4 3 4 4 4 5 4 6 4 7 4 1 2 1 3 7 2 7 3 4 2 4 3 8 7 4 28 1 1 2 1 3 1 4 1 5 1 6 1 7 1 1 4 2 4 3 4 4 4 5 4 6 4 7 4 1 2 1 3 7 2 7 3 4 2 4 3 3 2 3 3 2 2 2 3 5 2 5 3 6 2 6 3 0 7 4 27 1 1 2 1 3 1 4 1 5 1 6 1 7 1 1 4 2 4 3 4 4 4 5 4 6 4 7 4 1 2 1 3 7 2 4 2 4 3 3 2 3 3 2 2 2 3 5 2 5 3 6 2 6 3 1 7 4 7 1 2 2 3 3 2 4 3 5 2 6 3 7 2 9 7 4 1 3 2 12 7 5 1 2 3 13 7 5 2 3 3 4 3 15 7 5 10 1 2 2 2 5 2 6 2 7 2 1 4 2 4 5 4 6 4 7 4 7 7 4 14 1 1 3 1 5 1 7 1 2 2 4 2 6 2 1 3 3 3 5 3 7 3 2 4 4 4 6 4 14 5 1 4 1 1 3 1 4 1 5 1 2 WRONG!!! on this test i have eror, right ans is 1 good luck, don't give up it's not such a difficult problem! Каким образом во втором тесте(примере) получаем 2 полосы??? если даже когда вручную нарисовав таблицу 1х5, получаем максимум 1 полоску????каким образом вторая получается??? п.с.или белая полоса может состоять из одного дня???? How in the second test(example) does get 2 bars??? if even when by hand drawing a table 1x5, get a 1 strip maksimum???? how does the second turn out??? p.s. or can a white bar consist of one day???? Kakim obrazom vo vtorom teste(primere) poluchaem 2 polosy??? esli dazhe kogda vruchnuju narisovav tablicu 1h5, poluchaem maksimum 1 polosku????kakim obrazom vtoraja poluchaetsja??? p.s.ili belaja polosa mozhet sostojat' iz odnogo dnja???? Без комментариев No comments Bez kommentariev Исправьте тесты! Неправильные примеры. It is all right. Even 1 square is the bar (if it not contains in other bars). So it must be added. ti cho otvet 0, poloska dlinoi odin ne mojet bit, a test is inkarekt please give me some tips! Edited by author 24.04.2022 16:19 Try this: 3 3 6 1 1 1 2 1 3 2 1 2 2 2 3 Should be: 1 Input #1: 1 1 0 Output #1: 1 Input #2: 1 1 1 1 1 Output #2: 0 Input #3: 30000 1 0 Output #3: 1 Input #4: 30000 30000 0 Output #4: 60000 Input #5: 3 3 1 2 2 Output #5: 4 Input #6: 3 3 4 1 2 2 1 2 3 3 2 Output #6: 5 Input #7: 3 3 2 2 1 2 2 Output #7: 3 Input #4: 30000 30000 0 Output #4: 60000 why? I think the answer should be 2 Got AC with a program that had a 100% wrong answer on this test: 1 5 2 1 2 1 4 _ _ _ _ _ | |X| |X| | Definitely should be 3 (as we got 3 1x1 stripes separated by black cells), my prog got 2 and got AC. Dont know if adm reads this but why not - good to know for everyone Also hi to all ITMO vtalgo dudes <3 I failed on 13 test and I can't found error. Please give a 13 test. The problem is to find how many l*1 or 1*l while rectangles that do not *included* by each others. My codes solves all the samples from all Topics but i always get wrong answer #1. If I'm not mistaken, test 1 is the first sample. Do you have the right output format? It´s only an integer, so what to Format? It´s a C# program, i tested Console.WriteLine and also Console.Write. I have absolutely no idea what to. this is a shape of sample#1: ('B'=Black, '.'=white) B...B .B... ..B.. you must count all the streak which not belong to the streak with size more than current streak, therefor the cell's (1,2) & (2,1) & (3,2) must'nt count because they are belong to streak (1,2)->(1,4) & (2,1)->(2,2) & (3,1)->(3,2). here some test for problem: ////////////////////////// input: 5 5 2 1 2 3 3 output: 12 ////////////////////////// input: 5 5 4 1 2 5 3 3 1 4 4 output: 12 ////////////////////////// input: 1 1 0 output: 1 ////////////////////////// input: 1 1 1 1 1 output: 0 ///////////////////////// input: 5 5 12 1 2 1 4 2 1 2 3 2 5 3 2 3 4 4 1 4 3 4 5 5 2 5 4 output: 13 ////////////////////////////// I hope can help you. GOOD LUCK! I don't understand this is a shape of sample#1: ('B'=Black, '.'=white) B...B .B... ..B.. I see 7 sreaks: 1) (2,1)->(3,1) 2) (3,1)->(3,2) 3) (1,2)->(1,4) 4) (2,3)->(2,5) 5) (1,4)->(3,4) 6) (3,4)->(3,5) 7) (2,5)->(3,5) why 8!? +(1,3)-->(2,3) i think... Edited by author 28.12.2013 04:11 Edited by author 28.12.2013 04:55 Is just one white square counted as rectangle? If no, explain me please sample #1. Am I right that output to the sample 1 3 1 1 2 is 0? Please, explain me sample output #1. I can't understand the problem statement. I also can't understand why answer is 8. if 1*1 isn't a white streaks,why the sample#2 is 2 Yes, i have this problem TOO, please answer !!!!!!!!!!!!!! No comments Да правда фигня какая-то. в первом тесте хз почему 8 когда там надо 11. Иначе во 2м должно быть 1 PLZ post in english , I don't under stand the problem too!! Почему во втором тесте 2, а не 4? Или l>1? No you are wrong. 2 is correct [ ] [X] [ ] ^ ^ WHY??? I think because we dont count white stripes two times... Segments 1x1 are counted. But not if they are a part of larger segments. For example: 0 0 X 0 X 0 0 X 0 0 X X 1x1 segment (1,6) is counted. But 1x1 segment (1,2) isn't because it's not maximal. It's part of segment from (1,1) to (1,2). Segment (1,6) is maximal. There is no larger segment containing it. if "NO COMMENTS" why you write this? information - Zero I feel this is somewhat misleading as Data Structure isn't necessary for this problem. Agree. Solves with sort only. Sorting is good, yes. But it can be solved with data stuctures too. I used map<int,set<int> > and it gave slow AC (0.75 sec). I used QSort with M=(l+r)/2 and I got TLE26 many times, but after randomizing of M i've got AC with 0.1 sec! In my code, I declared two vector like this vector<int> row[maxn], col[maxn]; and got TLE but if I declared them like this vector<int> col[maxn], row[maxn] and got AC in 0.671s anyone can explain this? Edited by author 19.10.2008 23:43 What algorythm we ought to use? It may be sorting of black positions on each row and each column. Case 1*1 must be considered separetely , for example with help of find position in sorted arrays. I can't understand problem statement. can anybody explain it more clear ? Edited by author 11.10.2008 16:19 I cant undrestand how to count rectangles? pleaze explain it. Let me describe 2nd example of the task. 5 1 2 2 1 3 1 --- We will got this: [ ] [X] [X] [ ] [ ] There is 2 bars 'cause 1 square as well is bar. And it should be counted if it not contents into others longer bars. For example: ---------- 3 4 4 1 2 2 1 3 2 3 3 ----------- [ ][X][ ][ ] [X][ ][ ][ ] [ ][X][X][ ] The right answer will be horizontal: 1+1 = 2 vertical : 1+1 = 2 single blocks: 1+1 = 2 Answer is 6. How to build program? Dont allocate all matrix into memory as i did :))) Sorry for this idiotizm :( So u need to find out the optimal way. The program can be runed and exited with success with 300Kb of mem. I know this way, so i try to put the code here as fast as possible. The problem statement is very ambigous and tricky. Don't like such problems... Program is very easy, but undestanding what is requested by the authors- isn't. Thanks to Nikolai Besschetnov. Your sample saves me. Right math idea was having TLE for using set and vector after set. The same idea has AC 0.125 with malloc function for dynamic arrays. First , I used map < pair< int , int > , int > for finding lines of length 1 , but gave TLE too, then I did it in O(k) and got AC :) Edited by author 12.10.2008 03:27 |
|