10745 - Dominant Strings

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:

Re: Bah

Post by dispanser » Wed Oct 20, 2004 5:47 pm

Michael Goldshteyn wrote: P.S. for those that still do not understand the problem statement, here is a simplified version:

Given strings A and B. B dominates A if BOTH conditions below are satisfied:

- Every distinct character in A also appears in B
- Any character that appears multiple times in A must appear at least that many times in B

So, a simple way of saying this is that a string B dominates a string A if A can be constructed using some or all of the characters from B.

Here are examples where the first string is dominated by the second:

abc bac (in fact, each dominates the other, so neither is a dominant string)
the problem statement says something different:
Given two strings s1 and s2, we say that s1 dominates s2 if the (multi)set of characters in s1 is a proper superset of the (multi)set of characters in s2.
according to http://mathworld.wolfram.com/ProperSuperset.html abc is no proper superset of bac (cause they are equal).

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Oct 20, 2004 6:28 pm

Yeah, that would be the correct interpretation. And if Michael got AC with the other interpretation, it seems I wasn't careful enough when constructing the data.

Michael Goldshteyn
New poster
Posts: 14
Joined: Tue Oct 19, 2004 2:01 am

Post by Michael Goldshteyn » Wed Oct 20, 2004 10:05 pm

Not only that, but I'm not sure if an implementation that checked for a truly proper superset would even pass the test. But, I presume the test data and test are constant, correct? Or will the test data be changed, now? In any case, the performance penalty of proper superset vs. superset is negligible, because all you need to do is to compare string lengths to distinguish a proper superset from a permutation of a string. That is, if a string you think dominates is longer than the string you are comparing with, it is definitely a proper superset. This is a trivial O(N) operation, especially considering that the number of permutations in the input, especially for longer string lengths which are more difficult to dominate, is most likely negligible.

Michael Goldshteyn
(10745 - 0.061)

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:

Post by dispanser » Thu Oct 21, 2004 8:40 pm

i can assure you that the solution only considering proper supersets gets accepted; my running time is appr. 100x slower than yours, though :evil: .

fennec
New poster
Posts: 4
Joined: Thu Jul 29, 2004 12:18 pm

another way

Post by fennec » Mon Nov 08, 2004 5:34 am

I just give each char with a prim,eg: a(2) b(3) c(5)...
so you can change each string to a long long int ,and use % to check!
so without any cut you will get ac, and if you improve it, I think you will get a better time:)

Michael Goldshteyn
New poster
Posts: 14
Joined: Tue Oct 19, 2004 2:01 am

Re: another way

Post by Michael Goldshteyn » Thu Nov 11, 2004 6:17 pm

fennec wrote:I just give each char with a prim,eg: a(2) b(3) c(5)...
so you can change each string to a long long int ,and use % to check!
so without any cut you will get ac, and if you improve it, I think you will get a better time:)
That sounds like a horribly inefficient way of doing this. Mod (%) is very expensive.

Michael Goldshteyn

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

I/O

Post by _.B._ » Sat Jan 08, 2005 7:54 am

Greetings!
Will any of you please post a critical Input/Output to illustrate all the rules you mention here? :o
Thanks in advance!

Keep posting!
_.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Re: another way

Post by Christian Schuster » Sat Jan 29, 2005 6:40 pm

fennec wrote:I just give each char with a prim,eg: a(2) b(3) c(5)...
so you can change each string to a long long int ,and use % to check!
This is not (completely) correct, since the 26th prime is 101, and "zzzzzzzzzz" would be 101^10, which is a bit too large for 63 or even 64 bits. However, I split the characters into a..w (maximum 83^10) and x..z (maximum 5^10) and did the modulo checks for these two products. This got AC, but ran 9 seconds. Sorting by length reduced it to 3.3 seconds.

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

What's wrong with my algorithm

Post by ranjit » Sun Jan 30, 2005 7:46 pm

I keep getting WA in 5sec with the foll. algorithm
Can somebody point out the mistake.

Code: Select all

1.mat[i][j]  stores the number of  occurrences of "j+'a' " character in string i.
2.loop overall i
2a.      if i not marked dominated
3.        loop overall j
3a.               if j not marked
                           if mat[i][k]!=mat[j][k]
                                              if i dominates j
                                                              mark j dominated
                                              if j dominated i
                                                              mark i dominated
                                                              break out of j loop
4 loop overall i
      if i not marked as dominated print string i.
Thanks in advance.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Re: What's wrong with my algorithm

Post by Christian Schuster » Sun Jan 30, 2005 8:52 pm

Do you do the inner check (that with mat[i][k]) for all k? i dominates j iff mat[i][k] >= mat[j][k] for all k from 0 to 25. Theoretically, there must also be at least one k with mat[i][k] > mat[j][k], but since all strings are different, there is no need to check this. Remember to skip string i in the inner loop. I assume you sort the strings, since otherwise you wouldn't get the sample output right.

HTH,
Christian

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

sorry

Post by ranjit » Mon Jan 31, 2005 1:13 pm

my j loop runs from i+1 to n. So no conflicts.

Also i just find out whether my mat[k]>mat[j][k]
or otherwise when i check for inequality.

Also, I didnt not sort the strings anywhere in my code.
That was the mistake.

Thanks to Christian for finding it out.

Thanks anyway.
ranjit

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Mon Feb 14, 2005 10:45 am

I've solved it in a little different way. At first I have sorted all strings (index-sorting for speed) ascendingly on:
1) length
2) num of 'a'
3) num of 'b'
4) num of 'c'
etc...

In that order of priority.

Than recursively I created a forest based on this sorting. First level nodes united strings with same length, then for each same-length subset of strings I grouped them by same amount of character 'a' on the 2nd level, on the 3rd level strings of same length and same amount for character 'a' were grouped on amount of character 'b', and so on until some segment representing subset ends up with the only string (dupes were eliminated before building the forest).

I guess this way it creates graph like O(N). Per-character graph can be blown off with a suitable test. This way it can't. 1024^2 nodes were enough, perhaps much less. I think it's something like 26*N*C.

Then, to test a string for being dominated, I check all root nodes with L>l, then for each sub-level of those nodes with NUM('a') >= num('a'), etc... where big letters stand for node properties, and small letters stand for string properties. Whenever I faced terminating segment (that is, referring to just one string), I checked the rest of it. I.e. if we end at level corresponding to letter 'e', do check for 'e'...'z' and see if it's dominated. Later this was optimized using the fact length-is-at-most-10.

This way it worked at about 4.6 sec. With optimizations based on strings length it worked under contests' 2 sec (namely 1.699 sec).

NightFir
New poster
Posts: 5
Joined: Thu Feb 17, 2005 2:01 pm

10745 ?What does it me

Post by NightFir » Thu Feb 17, 2005 2:08 pm

What does "Restricted Function" mean?
I'm rookie,please tell me.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Thu Feb 17, 2005 2:31 pm

U have used some functions which r not allowed such as fopen(), fclose().
U must read from standard input and not from a file.

NightFir
New poster
Posts: 5
Joined: Thu Feb 17, 2005 2:01 pm

Post by NightFir » Thu Feb 17, 2005 2:47 pm

I used "seekeof",it gets that.
I try to use "eof",it's OK,and acceptd.
I think both "seekeof" and "eof" should be right.
Do you think so?

Post Reply

Return to “Volume 107 (10700-10799)”