| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| My story , wa11 and test cases | 👑TIMOFEY👑 | 1628. Белые полосы | 5 сен 2022 08:58 | 1 |
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! |
| Что за тесты???? | Dekado | 1628. Белые полосы | 3 сен 2022 23:16 | 8 |
Каким образом во втором тесте(примере) получаем 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 |
| WA#15 | hduads2022_20321227 | 1628. Белые полосы | 24 апр 2022 11:34 | 1 |
WA#15 hduads2022_20321227 24 апр 2022 11:34 please give me some tips!
Edited by author 24.04.2022 16:19 |
| WA8 | vtalgo21_RKhuzin | 1628. Белые полосы | 29 апр 2021 19:30 | 1 |
WA8 vtalgo21_RKhuzin 29 апр 2021 19:30 Try this:
3 3 6
1 1
1 2
1 3
2 1
2 2
2 3
Should be:
1 |
| give some tests | {AESC MSU}Vadim Kaushanskiy | 1628. Белые полосы | 8 май 2020 10:58 | 4 |
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 |
| Incomplete tests | vtalgo20_NAkatyev | 1628. Белые полосы | 19 апр 2020 23:55 | 1 |
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 |
| If you have WA 7 | Toshpulatov (MSU Tashkent) | 1628. Белые полосы | 31 мар 2020 16:40 | 1 |
|
| Give 13 test please | vtalgo20_egurin | 1628. Белые полосы | 29 мар 2020 01:52 | 1 |
I failed on 13 test and I can't found error. Please give a 13 test. |
| OFFER YOU SOME CLARIFICATION | scidylanpno | 1628. Белые полосы | 7 май 2019 12:14 | 1 |
The problem is to find how many l*1 or 1*l while rectangles that do not *included* by each others. |
| What is Test 1? | Norbert Nolte | 1628. Белые полосы | 14 апр 2014 14:05 | 3 |
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. |
| some explain about sample#1 & some test | hoan | 1628. Белые полосы | 28 дек 2013 03:41 | 3 |
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 |
| Clarification | Vedernikoff Sergey (HSE: EconomicsForever!) | 1628. Белые полосы | 25 янв 2012 19:40 | 15 |
Clarification Vedernikoff Sergey (HSE: EconomicsForever!) 11 окт 2008 13:22 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 !!!!!!!!!!!!!! Да правда фигня какая-то. в первом тесте хз почему 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] [ ]
^ ^ 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 |
| Why this problem is classified as Data Structure? | ahyangyi(newer id) | 1628. Белые полосы | 11 дек 2011 10:44 | 3 |
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). |
| Funny tests! QSort must die =) | Pavel Khaustov [Tomsk PU] | 1628. Белые полосы | 12 янв 2009 00:36 | 1 |
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! |
| What a strange thing!!! | Genesis | 1628. Белые полосы | 19 окт 2008 23:43 | 1 |
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 |
| If Graph | Nikolai Besschetnov | 1628. Белые полосы | 17 окт 2008 21:32 | 2 |
If Graph Nikolai Besschetnov 17 окт 2008 21:25 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 got TLE #21 | SerailHydra | 1628. Белые полосы | 17 окт 2008 08:43 | 1 |
|
| I can't understand problem statement | Ali | 1628. Белые полосы | 15 окт 2008 18:15 | 2 |
I can't understand problem statement. can anybody explain it more clear ?
Edited by author 11.10.2008 16:19 |
| No subject | hess | 1628. Белые полосы | 12 окт 2008 03:27 | 3 |
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. |
| 60000 not very large but... | svr | 1628. Белые полосы | 12 окт 2008 03:17 | 2 |
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 |
