| Show all threads Hide all threads Show all messages Hide all messages |
| I have some test datas | zzyzzy12 | 1158. Censored! | 7 Jan 2024 21:09 | 2 |
50 50 10
qwertyuiop[]\asdfghjkl;'zxcvbnm,./ QWERTYUIOP{}|AS
aegaegu
etoijqt
tquqi
witowwt
zxcjnc
oeit
potieq
iojge
nvoq
piqper
ans=8881647922834867244791415981705771412427494861672253136057167374729235842468240763290
1 1 1
a
a
ans=0
5 10 3
abcde
abc
bc
c
ans=1048576
Edited by author 05.04.2012 20:51 -
Edited by author 07.01.2024 21:19 |
| Don't panic! | Otrebus | 1158. Censored! | 6 Aug 2019 12:47 | 2 |
Some have claimed that this is a very difficult problem. Not true! There is a reasonably simple and very fast DP-solution to this problem. No string algorithms are required beyond the naive ones that every non-programmer knows.
Hint: Store the solution for sentences of length k in A[k], and store the number of strings that end with some forbidden word i (0 < i < P), but does not contain any other forbidden words as substrings in F[i][k]. Then construct the solution from A[k] to A[k+1], updating F[i][k+1] as well for each i. For each new character that you tuck onto the end of a valid string of length k, you get A[k] more valid strings, except those that end with a forbidden word, so those strings need to be removed. But make sure you don't remove stuff that you've assumed that you already removed earlier in the string - that's where F[i][k] comes in handy. |
| Does one need BigInteger to solve this? | dull_jester | 1158. Censored! | 25 May 2017 01:45 | 2 |
Since n^m can be very large (n,m <= 50), does one need BigInteger? I would not want to do it, since I've already started coding the whole thing in C++... Never mind, yes -- one does need BigInteger. Had to recode the whole thing in Java to get Accepted. Excellent problem! |
| some test | ProgBeat | 1158. Censored! | 31 Jul 2015 22:46 | 3 |
2 5 3
01
0
11
10001
ans: 0
Edited by author 26.06.2007 18:43 OH
it's a good test.
i'm writing DFA th e first time, and i don't know what's wrong with my program.
this test helped me. Thank you very much! This test really helped me. |
| Any test?I WA #9. | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1158. Censored! | 30 Mar 2015 09:25 | 5 |
What's test 9.
I've got WA too. Try these tests:
3 3 2
ABC
AB
BC
the answer is 16.
2 6 1
AB
ABAB
the answer is 53. I had WA#9 as well. My DFA was too primitive. Think about cases, when some word's prefix is contained in other word. For example, "dabc" and "abd" -- "ab" is prefix of "abd" and is contained in "dabc". It would be nice, if automaton can recognize words like "dabd".
Regards,
Denis Firsov tests:
2 4 3
ab
abab
abb
baa
answ:7
6 6 2
abcdef
dabcab
abdef
answ:46643
Edited by author 30.03.2015 09:25
Edited by author 31.03.2015 06:18 |
| WA 11 | IvanShafran | 1158. Censored! | 14 Oct 2014 20:30 | 1 |
WA 11 IvanShafran 14 Oct 2014 20:30 If you use Aho-Korasik+DP you should delete forbidden words which contain other forbidden words.
Example:
alphabet = "01"
forbidden words = ["100", "10", "11"] -> forbidden words = ["10", "11"] |
| Underrated problem | raggzy | 1158. Censored! | 3 Jul 2014 20:40 | 1 |
1. If you read some discussion, you may have found out, that there is `simple` algo solution, which just does A^M, and sums all final states counts (here A - is transition matrix of automaton built by `bad words`)
Yes, it is cool, algorithmic, etc.
But personally I've completely forgotten the 1st year of university, and after reading that I felt little shame, which results in not willing to implement that.
2. DP
This is one of hardest DP I've ever thought about.
It took me for almost 3 weeks of `background-thinking`.
Although, when you came to the function, which is `DP-able` - code looks small, etc.
But still, the function is hard to come to.
Personally, i felt pure happiness after got my DP ACed.
Actually I'm writing this post affected by this happiness :) Like in school :)
Wish u the same when u solve it!
I'd rate it as `one of the hardest problem` in this volume, if there was only DP solution and no automaton analogy.
If someone can invent similar problem, but without automaton solution - would be very cool! |
| How to solve this problem(1158)? It's too hard.... | Sa Lang Hae | 1158. Censored! | 14 Feb 2014 00:35 | 10 |
I have been working on it for a week.... Why extreme difficulty? My DP is about 30 lines. Idea is very simple. But it's hard to discover as well :) I mean no true DP solution is really large, but this very DP is rather difficult to find and understand. would you please tell me your method? I think only a big-number code will use more than 30 lines... ALGO IS HERE:
1. Remove all words which contain some other word as a substring. They do not affect anything, but make further things more difficult.
2. Build characters tree from forbidden words. E.g. for set "aabc, abd, bcd" it will be like that:
root(a(a(b(c)),b(d)),b(c(d)))
positions in this tree will represent history (recent placed letters) and its size will be <= 100 (total amount of letters in all forbidden words)
A path from root to node is safe if it does not end in a leaf (otherwise you're in jail for 10 years). Any sub-paths of a safe path are also safe because we removed all words which could lead to such paths. So, we have a good test for path safety - it shouldn't be a leaf, and that's enough.
While we place letters, we are allowed to make only safe steps - we can't step into a leaf.
If we attempt to perform a step outside of the tree, we should apply 1st postfix of history to that tree to find where will we get after forgetting that least recent placed letter. For example, if the string 'aabce' falls out from the tree after 'aab' (i.e. there is no forbidden word starting with 'aabc'), then we will search for 'abce' (1st postfix of 'aabce') in the same manner, recursively. All this information can be precalculated (which state leads where after adding some particular letter). It's like prebuilding automaton for multi-substring search and then calculate number of programs which do not lead to terminal states.
This gave me AC in 0.031 sec and final understanding of KMP which I used blindly before :)
Edited by author 05.08.2008 04:24 The limits are not very strict. I did not perform precalculation and did not build automata. |
| Does anybody has the Data of #8? | xkszltl | 1158. Censored! | 17 Dec 2011 14:30 | 3 |
I'm WA #8.Who can tell me why?Need HELP!!! |
| Why the hell would you use ascii greater than 127??? | HeypaBHoBeceH | 1158. Censored! | 30 Oct 2011 15:08 | 2 |
My program is correct, but I can't pass test 23 because of specific input characters! Couldn't you just use A...Z and a...z instead? That's even 52 characters! I thought the point is to generate a right solution, rather than fight implementation language's specifics! |
| test #16 hint | jlcastrillon | 1158. Censored! | 30 Oct 2011 11:19 | 1 |
answer overflows long long type....in test # 16....
hope this helps
Edited by author 31.10.2011 04:43 |
| If you got WA 23 on Java | Pavel Kovalenko | 1158. Censored! | 17 Apr 2011 01:02 | 2 |
use it:
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in, "ISO-8859-1")); Thanks a lot, I would never find it out by myself. |
| Hash | Zhandos | 1158. Censored! | 12 Apr 2011 23:54 | 1 |
Hash Zhandos 12 Apr 2011 23:54 Can I solve this problem using hash method? |
| My code AC at POJ , but WA 3 here | Peng Kejing | 1158. Censored! | 5 Feb 2009 21:43 | 4 |
How funny. I really can not find what had gone wrong in my code.
I have already test all the data in the discuss founm. I got AC at POJ, but WA 23 here T_T 3xian is an ACMER from GDUT? Isn't it? haha
OH, I know.
While reading data, dealing with string, must use:
for(i = 0; i < strlen(str); i++)
{
XXXXXXX
}
if use:
i = 0;
while(str[i])
{
i++;
}
will WA 32
It takes me two days to find this fault.
Edited by author 05.02.2009 21:26
Edited by author 05.02.2009 21:26
Edited by author 05.02.2009 21:28 I know what had happened~
When we convert 'char' that ASCII larger than 127 into 'int', we will get negative integer but not the original number.
Edited by author 05.02.2009 21:51 |
| To Rybak Michael. Why I get WA? (+) | Nazarov Denis (nsc2001@rambler.ru) | 1158. Censored! | 29 Dec 2008 22:32 | 5 |
You give the test:
50 8 2
QWERTYUI
QWERT
ERTYU
What the answer for this test?
My Program get WA? But why?
[deleted by moderator]
Edited by moderator 11.04.2004 02:00 >
> [deleted by moderator]
Edited by moderator 11.04.2004 02:00 are you joking?
39215086890725
is greater than
50^8 = 39062500000000
I got WA on test 11 , could you help me? My output is
39062499000100 |
| Help!!! I got WA at 23 | updog | 1158. Censored! | 17 Sep 2008 21:04 | 2 |
I have past every test case I can find. I even got AC at another OJ. Please help me!!!! Check if you consider words which contain some other word as a substring (my AC solution strips them off). |
| what is the trap on test 23? | Crusader | 1158. Censored! | 17 Sep 2008 02:04 | 1 |
what is the trap on test 23?
i refer to the discuss by updog, but i don't know what is wrong with my code?
can anyone help me? |
| 1158- Dp-classica | svr | 1158. Censored! | 5 Aug 2008 02:25 | 2 |
Best problem in 1100-1199
Very many combinatorial problems lay in it’s framework.
Dp and recurrences are natural for the problem
and it’s wrong to abuse it for some complexness
because of it’s very generality.
Also interesting that preprocessing part
help very much in avoiding TLE |
| Warning!!! | updog | 1158. Censored! | 5 Aug 2008 02:24 | 4 |
I'm SURE test #23 contains some strange characters that can't be read in by scanf("%s") and gets(). While I can read them by getline() and cin>> . ASCII code 255 is dangerous because EOF constant returned by 'getc' is -1.
Edited by author 05.08.2008 02:25 |
| how about the test 16 | zfy0701 | 1158. Censored! | 21 May 2008 15:27 | 1 |
i wa on that, i don't know why
could anybody give the testdata |
