| ENG RUS | Timus Online Judge |
Discussion of Problem 1486. Equal SquaresArtem Khizha [DNU] WA#10 [4] // Problem 1486. Equal Squares 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. Kenny_HORROR Re: WA#10 [1] // Problem 1486. Equal Squares 28 Jan 2011 21:17 You have a collisions with hash. (I've got this problem also because second number x was to small and close to first one). Artem Khizha [DNU] Re: WA#10 // Problem 1486. Equal Squares 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 Anwar binary search [1] // Problem 1486. Equal Squares 17 Sep 2018 18:51 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? InstouT94 Re: binary search // Problem 1486. Equal Squares 11 Dec 2024 16:38 We run a binary search on the length of the square's side. For a fixed length of the square's side, we calculate the hash of all squares with that side length, and look for a pair of squares with the same hash. 👑TIMOFEY👑 TLE 10 // Problem 1486. Equal Squares 26 Aug 2023 08:45 use sort instead of map or unordered_map, its around 10 times faster Tianyi Any solution other than hashing? [2] // Problem 1486. Equal Squares 20 Aug 2019 14:42 Anti-hash testcases are added, so I guess intended solution isn't hashing. However I can't think of any. sziiza Re: Any solution other than hashing? [1] // Problem 1486. Equal Squares 20 Apr 2023 17:25 There is a determined solution - the one i've got AC with. Idea from this post https://codeforces.com/blog/entry/92092 can be applied to 2D case. Edited by author 20.04.2023 17:25 Viper Re: Any solution other than hashing? // Problem 1486. Equal Squares 30 Apr 2023 23:48 hi Zeardoe Warning // Problem 1486. Equal Squares 14 Jul 2022 13:16 Anti-hash tests are added. Please choose mod = 2^64 and strange p in case of being hacked. Eray WA7 [1] // Problem 1486. Equal Squares 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 Eray Re: WA7 // Problem 1486. Equal Squares 13 Jul 2022 06:56 by the way, use 123 and 1789 in hashing will pass. Vedernikoff Sergey Weak tests [1] // Problem 1486. Equal Squares 7 Feb 2007 23:47 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... Rodion Re: Weak tests // Problem 1486. Equal Squares 20 Dec 2021 12:32 why don't you share your strong tests with us then? Pascal or C++ WA test #11 [4] // Problem 1486. Equal Squares 24 Oct 2006 08:17 Can you help me? I WA test #11 Bumba Re: WA test #11 [1] // Problem 1486. Equal Squares 26 Jan 2007 14:13 Pascal or C++ wrote 24 October 2006 08:17 Can you help me? I WA test #11 Sorry. I can't.Dmitry Re: WA test #11 // Problem 1486. Equal Squares 26 Jan 2007 14:14 Oh! I can't help you too. ძამაანთ [Tbilisi SU] Re: WA test #11 [1] // Problem 1486. Equal Squares 30 Sep 2013 22:38 Me neither. Rodion Re: WA test #11 // Problem 1486. Equal Squares 20 Dec 2021 12:32 I can help you, but I won't Rachel going craaaaaaazy! [1] // Problem 1486. Equal Squares 12 Mar 2008 17:19 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 Rodion Re: going craaaaaaazy! // Problem 1486. Equal Squares 20 Dec 2021 12:10 Chill out Otrebus WA 7 = mind the coordinate order in the output [1] // Problem 1486. Equal Squares 2 Jul 2016 22:01 foxlup Re: WA 7 = mind the coordinate order in the output // Problem 1486. Equal Squares 26 Nov 2021 19:00 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. Anwar binary search [1] // Problem 1486. Equal Squares 17 Sep 2018 19:02 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... Alikhan Zimanov Re: binary search // Problem 1486. Equal Squares 5 Jun 2020 16:06 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. Sandro (USU) Problem 1486 "Equal Squares" has been rejudged (+) [1] // Problem 1486. Equal Squares 4 Mar 2017 11:47 New anti-hash test was added. 141 author lost AC. Mahilewets Re: Problem 1486 "Equal Squares" has been rejudged (+) // Problem 1486. Equal Squares 11 May 2017 19:55 Nice! I just checked the discussion before writing hash solution... Lion give me some hints please [1] // Problem 1486. Equal Squares 6 Jan 2007 13:03 please give me some hints how to solve the problem fast Mahilewets Re: give me some hints please // Problem 1486. Equal Squares 11 May 2017 16:54 Probably the problem can be solved using two-dimensional hashing Rabin-Carp algorithm. hoan what's the best order? [1] // Problem 1486. Equal Squares 18 Feb 2011 12:02 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 kun368 Re: what's the best order? // Problem 1486. Equal Squares 7 Sep 2016 18:45 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 Ilya Filippov (Petrozavodsk SU) give me the ideas of solution please [1] // Problem 1486. Equal Squares 12 Jul 2009 05:09 only_nicety Re: give me the ideas of solution please // Problem 1486. Equal Squares 28 Nov 2010 08:30 if you are a chinese , you can read the article —— Hash在信息学竞赛中的一类应用 Alexander Sokolov [MAI] 1x1 squares [2] // Problem 1486. Equal Squares 9 Oct 2006 14:24 Should I output squares 1x1? sqybi Re: 1x1 squares // Problem 1486. Equal Squares 1 Dec 2007 15:08 you should output "0". Peter Ivanov Re: 1x1 squares // Problem 1486. Equal Squares 16 Apr 2008 13:43 yes. you should output "0" iff no 1x1 squares match. tantian Could you give me some tests?I WA on test 8 // Problem 1486. Equal Squares 14 Jun 2007 11:30 Could you give me some tests?I WA on test 8 PSV TLE10 [5] // Problem 1486. Equal Squares 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? Kit Re: TLE10 [2] // Problem 1486. Equal Squares 15 Feb 2007 22:40 Only thing you need is z = O(1). Edited by author 15.02.2007 22:43 Vedernikoff Sergey Re: TLE10 [1] // Problem 1486. Equal Squares 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... Kit Re: TLE10 // Problem 1486. Equal Squares 19 Feb 2007 16:44 What 'not very good' hash you mean? Can you describe it? R13 Re: TLE10 // Problem 1486. Equal Squares 28 Apr 2007 21:06 Pasha, if you accept this ... help me to do this too! Good Luck! Chobit'my jiji, chobit'my!!! R13 Re: TLE10 // Problem 1486. Equal Squares 28 Apr 2007 22:14 I have f..ed this problem! I did this problem the same as you did. my Modulo in hash table = 999983.
|