| Show all threads Hide all threads Show all messages Hide all messages |
| TLE 10 | 👑TIMOFEY👑 | 1486. Equal Squares | 26 Aug 2023 08:45 | 1 |
TLE 10 👑TIMOFEY👑 26 Aug 2023 08:45 use sort instead of map or unordered_map, its around 10 times faster |
| Any solution other than hashing? | Tianyi | 1486. Equal Squares | 30 Apr 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. Equal Squares | 14 Jul 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. Equal Squares | 13 Jul 2022 06:56 | 2 |
WA7 Eray 13 Jul 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. Equal Squares | 20 Dec 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. Equal Squares | 20 Dec 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. Equal Squares | 20 Dec 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. Equal Squares | 26 Nov 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. Equal Squares | 5 Jun 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. Equal Squares | 17 Sep 2018 18:51 | 4 |
WA#10 Artem Khizha [DNU] 26 Jan 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 Jul 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. Equal Squares | 11 May 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. Equal Squares | 11 May 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. Equal Squares | 7 Sep 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. Equal Squares | 28 Nov 2010 08:30 | 2 |
if you are a chinese ,
you can read the article —— Hash在信息学竞赛中的一类应用 |
| 1x1 squares | Alexander Sokolov [MAI] | 1486. Equal Squares | 16 Apr 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. Equal Squares | 14 Jun 2007 11:30 | 1 |
Could you give me some tests?I WA on test 8 |
| TLE10 | PSV | 1486. Equal Squares | 28 Apr 2007 22:14 | 6 |
TLE10 PSV 26 Dec 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 Feb 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. |
