Show all threads Hide all threads Show all messages Hide all messages |
Solved with hashes XD | FaNato4kA_TiMoFeYa | 1590. Bacon’s Cipher | 12 Mar 2024 23:47 | 1 |
|
WA 3 | Cat36 | 1590. Bacon’s Cipher | 22 Jul 2023 18:05 | 5 |
WA 3 Cat36 11 Nov 2008 23:42 Give me some tests, please Edited by author 11.11.2008 23:43 Re: WA 3 Aleksandr Shvarkunov (Pskov SPI team #1) 2 Feb 2009 20:14 abab answer - 7 It helped me with WA3 (Z-function O(N^2) solution) rthfdffdfdfffffdddffdgdfdfdg answer - 349 hshhflgseiuajsliouew answer - 202 gggfffgggghhhhghh answer - 126 aaaabbbbfghjjlltrgttcdssdbnpoiuyewtdarsuorprpooeuyywdgfxsdkkvcjbidfryieiue answer - 2713 Edited by author 02.02.2009 20:14 Edited by author 02.02.2009 20:21 Re: WA 3 [RSU_Tash]Nodirbek_Kuklamov 12 Nov 2011 23:53 If you use Z-function don't forget re-initialize z-array before each iteration!!! z[0]..z[i] = {0} hm... This are tests successful, but error on 1 test try bbbabbbababb answer is 51 |
WA2 | farmer.26 | 1590. Bacon’s Cipher | 20 Aug 2021 16:26 | 1 |
WA2 farmer.26 20 Aug 2021 16:26 Please give me some tests! |
TL test 2. Why?????????????? | DimaLahtin`~ | 1590. Bacon’s Cipher | 5 Nov 2019 21:36 | 1 |
#include <bits/stdc++.h> using namespace std; int main() { map<string, int> d; string s; cin >> s; string c = ""; int n = s.size(); for (int i = 0; i < n; i++) { c = s[i]; d[c]++; for (int j = i + 1; j < n; j++) { c += s[j]; d[c]++; } } cout << d.size(); } |
To admins | basuki | 1590. Bacon’s Cipher | 17 May 2019 00:16 | 1 |
|
Actually hashes work | ARK (***AESC_USU***) | 1590. Bacon’s Cipher | 27 Jan 2018 02:09 | 3 |
There were rumors that it is hard to get AC with hashes. Got AC in 0.031 using standard N log^2 N suffix array. Hashes modulo 2^64 (so there is no explicit divisions in code). There are couple of tricks, but they all are very easy to code. 1) gethash(i + l, i + mid) == gethash(j + l, j + mid) && memcmp(s + i + l, s + j + l, mid - l) == 0 instead of just gethash(i, i + mid) == gethash(j, j + mid) in binary search (lcp computing) 2) std::::stable_sort is preferable over std::sort when comparisons are heavy. std::stable_sort makes more assignments in average, but much less comparisons. 0.031 sec, 62 lines of code (including 10 empty, "return 0", 4 includes and so on). The rumors said that it was hard to get AC with hashes in O(n^2): to calculate hashes of all substrings and output the number of different ones :) I got AC by output number of different hashes in O(n^2). Took some tries though. Ended up using double hash, one which uses long long overflow and one modulo some big prime. I think test 27 is anti-hash test. Edited by author 27.01.2018 02:09 |
with a basic LCP and using not a fast prefix sort you might solve 1590 in 0.45 seconds on java 1.8 | esbybb | 1590. Bacon’s Cipher | 15 Sep 2015 15:25 | 2 |
String s = scanner.next(); TreeSet<String> c = new TreeSet<String>(); for (int i=0; i<s.length(); i++) { c.add(s.substring(i)); } int L = c.size() + 1; long total = L - c.first().length(); while(c.size()>1) { String first = c.pollFirst(); String second = c.first(); int lcp = LCP(first, second); total+= L - second.length() - LCP(first, second);; } System.out.println(total); static int LCP(String s1, String s2) { int l = 0; int j = Math.min(s1.length(), s2.length()); for (int i=0; i<j; i++) { if (s1.charAt(i)!=s2.charAt(i)) break; else l++; } return l; } |
I use Suffix array and Z-function. Both of them get me Accepted | Adhambek | 1590. Bacon’s Cipher | 3 Dec 2014 15:28 | 1 |
TIME Memory Suffix array - 0.031 s 534 kb Z-function - 0.187 s 132 kb Edited by author 03.12.2014 15:29 |
A simple solution using suffix arrays | 吕蒙子明 | 1590. Bacon’s Cipher | 20 Jun 2014 20:54 | 3 |
Well, the N is rather small that we can construct the suffix array for O(N^2logN) for example, we get all the suffix and sort it: a aa aaa then calculate the longest common prefix(LCP) between two neighbour string we get : 1 2 it means that: the substring "a" occurs 3 times (in string 1,2, LCP is "a",in string 2,3, LCP is "aa", which also contains "a") , and should be counted as once the substring "aa" occurs twice and it's also should be counted as once then the answer should be : 3 * (3 + 1) / 2 - 1 - 2 = 3 i found the DC3 algorithm much easier to understand (and implement). and it is fast enough (even in scala) |
WA3 | I.Smirn0ff | 1590. Bacon’s Cipher | 26 Mar 2014 22:13 | 2 |
WA3 I.Smirn0ff 26 Mar 2014 20:48 Please give me some tests. Re: WA3 I.Smirn0ff 26 Mar 2014 22:13 I found a bug in the code, i wrote wrong z-function. Test aaabaaaab correct answer is 29 |
Solution with prefix-function, but without KMP | adamant | 1590. Bacon’s Cipher | 22 Feb 2014 01:28 | 1 |
Well, it's crazy one =) Let's solve this problem just like classical prefix-function solution, but let's get prefix-func from Z-function instead of using KMP. Here is a part of my code. z[0]=0; l=r=m=0; for(int i=1;i<n;i++) { if(i<r) z[i]=min(z[i-l],r-i+1); else z[i]=0; while(i+z[i]<n && t[i+z[i]]==t[z[i]])z[i]++; if(i+z[i]-1>r) l=i,r=i+z[i]-1; } fill(p,p+n,0); for(int i=0;i<n;i++) for(int j=0;j<z[i] && !p[i-j];j++) p[i-j]=z[i]-j; |
Why N*N TL??? | Furious Wolf | 1590. Bacon’s Cipher | 20 Jul 2012 21:34 | 8 |
Help me... I really don't know, why 25000000 TL? I think 25000000 not many time...and must get AC in 1 sec. Edited by author 17.04.2008 08:16 Try to change the order of FOR cycles. For example, for (i=0;i<n;i++) for (j=0;j<n;j++) p[i][j]=1; works faster than for (j=0;j<n;j++) for (i=0;i<n;i++) p[i][j]=1; Why??? But I use first variant and get TL... 25000000 operation : compare of char and value assignment of integer. And 12500000 operation works 0.953! Why this work too many time???? Edited by author 18.04.2008 09:58 My O(N^2) solution works 0.171. My O(N^2) solution works 0.171. Can you write your code as pseudo or explain your algo in details, please? Not in forum ... Mail to me. (I send to u my code only) naxart@yandex.ru May be because of "mod operation"? |
Finally got accepted | JAVATAR | 1590. Bacon’s Cipher | 20 Jul 2012 21:32 | 2 |
|
Problem 1590 "Bacon’s Cipher" was rejudged | ...†.†.†... Stigius ...†.†.†... | 1590. Bacon’s Cipher | 20 Jul 2012 12:30 | 4 |
Some new tricky tests were added. 53 authors lost their AC. someone have AC with hash? what base u used? Read this: http://codeforces.ru/blog/entry/4898Now it's VERY difficult to get AC with hashes. Double hashes fail on TLE, single hashes fail on collisions at most cases. You must be really lucky to solve it with hashes now. I did it :D On Java. Edited by author 20.07.2012 12:30 |
Accepted | Suckerfur | 1590. Bacon’s Cipher | 6 May 2012 12:54 | 1 |
I got AC with prefix function. Edited by author 06.05.2012 12:56 |
Can we use hashes? | Khamitbekov Madi | 1590. Bacon’s Cipher | 9 Feb 2012 07:10 | 3 |
Can we solve this problems with hashes? It takes TLE #3 with hash table... Who solved with hashes, comment please =) I tried, but i didn't use tables. Just calculated the number of different hashes. But I have WA3. And it seems quite interesting to me. I tried, but i didn't use tables. Just calculated the number of different hashes. But I have WA3. And it seems quite interesting to me. Why do you think that you could avoid hash collisions? There could be 5000*5000/2 different substrings and if your hash size (modulo you are using) is less than that, some two will DEFINITELY be in the same section and they could be unequal. Even if your number is greater, you still can get WA because of a collision ... |
Can solve with hash? | vanla | 1590. Bacon’s Cipher | 1 Nov 2011 23:46 | 2 |
Can anyone solve this task with hash? I solved it with hash. But I wrote my own hashset. |
No subject | Aybek | 1590. Bacon’s Cipher | 6 Jul 2011 01:41 | 2 |
Edited by author 06.07.2011 10:45 Edited by author 06.07.2011 10:45 |
About the solving approach(+) | SPIRiT | 1590. Bacon’s Cipher | 24 Jun 2011 01:17 | 9 |
I know that suffix trees can be used for such problem. How about using a large hash table for storing codes of substrings that we already have? Anyone got AC in that way? I trying during a long time O(n) suffix tree of Ekkonen but could'n catch all details. I think that you question has the same nature. If you think about yourself as good coder you should catch O(n) suffix tree. I tried double-hash of about 30000 elements each but WA. Nevertheless, some people claim the problem may be solved with hash. How do you calculate hash for n^2 substrings? I calculate hash seperately for each lenth os substring by: hashcode = prime^n*c1 + prime^(n-1)*c2 + prime^(n-2)*c1... string movement is by 1 char: newhashcode = (oldhashcode - prime^n*removedchar)*prime + prime*addedchar This gets TLE 3. I use 'poganyi hash'. And it works very good. Yeah, baby! to Lomir: you should not use sorting. Without sorting this approach gives AC in 0.454 sec. Finally managed to implement the Ukkonen algo correctly - worked from the first try and is much faster now, than with O(N^2) implementation. Here is my status board to examine: http://acm.timus.ru/status.aspx?space=1&num=1590&author=33910 Edited by author 06.08.2009 00:47 Edited by author 06.08.2009 00:48Calculation of hash for each substring will take O(N^2). Then you need to check non-equal of string with same hash. For example for test 'aaaaaaaaaaaaa' (and longer) every substring of same length will have same hash code Can it be done using ternary search tree |
What is s "substring" here? | Vedernikoff Sergey | 1590. Bacon’s Cipher | 27 Oct 2010 16:20 | 6 |
Is empty string is a substring of the whole string? Is whole string is a substring of the whole string? You can see example: "aaba": a b aa ab ba aab aba aaba Totaly 8 substrings. So, empty string is not substring. Where is baa? "baa" is not subsequnce of "aaba" |