Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
TLE 10 | 👑TIMOFEY👑 | 1486. Одинаковые квадраты | 26 авг 2023 08:45 | 1 |
TLE 10 👑TIMOFEY👑 26 авг 2023 08:45 use sort instead of map or unordered_map, its around 10 times faster |
Any solution other than hashing? | Tianyi | 1486. Одинаковые квадраты | 30 апр 2023 23:48 | 3 |
Anti-hash testcases are added, so I guess intended solution isn't hashing. However I can't think of any. |
Warning | Zeardoe | 1486. Одинаковые квадраты | 14 июл 2022 13:16 | 1 |
Anti-hash tests are added. Please choose mod = 2^64 and strange p in case of being hacked. |
WA7 | Eray | 1486. Одинаковые квадраты | 13 июл 2022 06:56 | 2 |
WA7 Eray 13 июл 2022 06:54 Maybe you can find out why you are wrong in this test if you WA on 7. 3 4 aaaa aaaa aaaa answer: 3 1 1 1 2 (or other correct coordinates) sorry for my bad English by the way, use 123 and 1789 in hashing will pass. |
Weak tests | Vedernikoff Sergey | 1486. Одинаковые квадраты | 20 дек 2021 12:32 | 2 |
Testset for this problem is very weak. Program, that works ~5 secs. on my tests got AC in less than 1 sec. on jury tests... why don't you share your strong tests with us then? |
WA test #11 | Pascal or C++ | 1486. Одинаковые квадраты | 20 дек 2021 12:32 | 5 |
Can you help me? I WA test #11 Can you help me? I WA test #11 Sorry. I can't. Oh! I can't help you too. I can help you, but I won't |
going craaaaaaazy! | Rachel | 1486. Одинаковые квадраты | 20 дек 2021 12:10 | 2 |
WA on the 5th test! It passed all random tests on my computer. got no idea! Please help me! Edited by author 12.03.2008 17:48 |
WA 7 = mind the coordinate order in the output | Otrebus | 1486. Одинаковые квадраты | 26 ноя 2021 19:00 | 2 |
Could you be more specific? Because I try: 1. Point (row, col) closest to point (1,1) first (distance formula). 2. Row closest to row 1 first. 3. Other variations And I still get WA7. |
binary search | Anwar | 1486. Одинаковые квадраты | 5 июн 2020 16:06 | 2 |
Why use a binary search. How can we say that the value of the hash of 4x4 > 3x3 > 2x2 > 1x1? I don`t understand why to use binary search. plz, help me... Let's call a number k "good" if there are two same squares with side length k in the matrix. I claim that if k is good, then k - 1 is good. Indeed, let's look at any pair of same squares with side length k. Now, let's take the left-upper square with side k - 1 in each of them. Note that they will be equal, but still won't be in the same place in the matrix, so they will be a good pair of squares with side length k - 1. We've just proved that if K is the side length of the optimal pair of squares, then k = 1, 2, ... , K are all good, while k = K + 1, K + 2, ... , min(n, m) are all bad. Hence, we can do binary search to find K. The only thing left is how to check for a given k whether there are two equal squares with side length k or not. This part can be done by using hashing. |
WA#10 | Artem Khizha [DNU] | 1486. Одинаковые квадраты | 17 сен 2018 18:51 | 4 |
WA#10 Artem Khizha [DNU] 26 янв 2011 03:53 At the moment my way is to look through all the squares of length LEN (using binary search) and to check, whether a hash of a square was met before. It is of O(N*M*log(min{N, M})) complexity. But I get WA#10 again and again. Please, if someone had a problem with this test, share your impressions, 'cause I'm going slightly mad. You have a collisions with hash. (I've got this problem also because second number x was to small and close to first one). Re: WA#10 Artem Khizha [DNU] 5 июл 2012 16:29 Thank you, it really had to do with collisions. Actually, my self-made hashset implementation was fantastically awful. :-) Edited by author 06.07.2012 15:48 Why you have used binary search? How we can say that the sq. matrix 2x2 has less value than 3x3. and 3x3 has less than 4x4. how can we justify? |
Problem 1486 "Equal Squares" has been rejudged (+) | Sandro (USU) | 1486. Одинаковые квадраты | 11 май 2017 19:55 | 2 |
New anti-hash test was added. 141 author lost AC. Nice! I just checked the discussion before writing hash solution... |
give me some hints please | Lion | 1486. Одинаковые квадраты | 11 май 2017 16:54 | 2 |
please give me some hints how to solve the problem fast Probably the problem can be solved using two-dimensional hashing Rabin-Carp algorithm. |
what's the best order? | hoan | 1486. Одинаковые квадраты | 7 сен 2016 18:45 | 2 |
I use Hash and binary-search and got Ac in 0.828 s. my algo has order O(n^2 * (lg n)^2). but some person can Ac in 0.109 s what this algo? sorry for my poor english. Edited by author 18.02.2011 12:03 You can change map/set into unordered_map/set get faster, reduce time O(lg n) O(∩_∩)O Edited by author 07.09.2016 18:47 |
give me the ideas of solution please | Ilya Filippov (Petrozavodsk SU) | 1486. Одинаковые квадраты | 28 ноя 2010 08:30 | 2 |
if you are a chinese , you can read the article —— Hash在信息学竞赛中的一类应用 |
1x1 squares | Alexander Sokolov [MAI] | 1486. Одинаковые квадраты | 16 апр 2008 13:43 | 3 |
Should I output squares 1x1? yes. you should output "0" iff no 1x1 squares match. |
Could you give me some tests?I WA on test 8 | tantian | 1486. Одинаковые квадраты | 14 июн 2007 11:30 | 1 |
Could you give me some tests?I WA on test 8 |
TLE10 | PSV | 1486. Одинаковые квадраты | 28 апр 2007 22:14 | 6 |
TLE10 PSV 26 дек 2006 06:00 I make O(n^2*z) (z - time for updating hash table) algo to check if exist equal squares of some k-size. Then I make binary search by k. So complecity in worth case is O(n^3*log n) - so that is bad... But what to do - some ideas?.. Maybe goodhash function or doublize it, or there is much different approach? Only thing you need is z = O(1). Edited by author 15.02.2007 22:43 Re: TLE10 Vedernikoff Sergey 19 фев 2007 15:21 Hash-based solution can be applied easily in O(N^2*logN). Even not very good hash can get AC because of weak tests for this problem... What 'not very good' hash you mean? Can you describe it? Pasha, if you accept this ... help me to do this too! Good Luck! Chobit'my jiji, chobit'my!!! I have f..ed this problem! I did this problem the same as you did. my Modulo in hash table = 999983. |