10513 - Bangladesh Sequences

[pingus]

plz, what is the ouput for:

Code: Select all

7
?
?
?
?
?
?
?
0

[Per]

823543.

Such short sequences are not very interesting. But for the same input with 10 as length instead of 7, the answer is 9999999996.

[Ghost77 dimen]

As per said, you'll find the rule is worked when the length is more than

10. By the way, make sure your algorithm is efficient.

[pingus]

Thank you, Per

Your are right Ghost77 dimen , my code is not very efficient (TLE).

only the worst case {15,?,?,...,?} take 7s with output :

Code: Select all

437893890380826859 

is at least correct ?

[PdR]

Only the worst case { 15, ?, ?, ..., ? } take 7s with output:

Code: Select all

437893890380826859 

is at least correct ?

Yes

[chancp]

I have tried several times, but always get WA. I use the following test data:

Code: Select all

1
A
1
?
2
?
?
2
B
?
2
A
B
10
C
F
I
A
D
G
J
B
E
H
10
AC
F
I
A
D
G
J
B
E
H
10
?
?
?
?
?
?
?
?
?
?
15
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
15
ABCDEFGHJKLMN
ABCDEFGHIJKMN
ABCDEGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
15
ABCDEFGHJKLMN
ABCDEFGHIJKMN
ABCDEGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
ABCDEFGHIJKLMN
?
ABCDN
14
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
?
?
ABCDEFGHIJKLMN
14
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
?
?
?
15
B
B
B
B
B
B
B
B
?
?
?
?
?
?
?
14
ABCDEFGHIJKLMN
ABCDEFGHIJKLMN
ABCEFGHIJKLMN
ABCDEFGHIJKLMN
ABCDEGHIJKLMN
ABCDEFGHIJKLMN
ABCDEFGHIJLMN
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
BCDEFGHIJKLMN
ABCD
MN
?
13
ABCDEFGHJ
ABCDEFGHI
BCDEFGHIJ
ABCDEFGHIJ
ABCEFGHIJ
ACDEFGHIJ
?
?
?
?
BCDEFGHIJ
ABCEFGHIJ
ACDEFGHIJ
4
AB
?
CD
?
8
ABCEFG
CDEF
ABCD
EFGH
FGAB
DDCC
ABCD
?
0

And the output from my program:

Code: Select all

Case 1: 0
Case 2: 0
Case 3: 4
Case 4: 2
Case 5: 1
Case 6: 0
Case 7: 1
Case 8: 9999999996
Case 9: 107398228610003968
Case 10: 85989033621056384
Case 11: 32903966946832653
Case 12: 7671302043568244
Case 13: 7671302043568244
Case 14: 170859375
Case 15: 313114369125235
Case 16: 12294573984810
Case 17: 64
Case 18: 98304

Is there anything wrong?

Thanks.

[PdR]

Only the last one differs.
It should be

Code: Select all

Case 18: 196608

[chancp]

The last input case has a tricky thing, there is a line "DDCC".
So the correct answer should not be 196608

[chancp]

Finally AC
My problem is that I write my high precision function wrongly.

From my testing, I can see that in the test data of online judge, there are no spaces, and should be no repeated letters on the same line.

Thanks for your help PdR.

[Der-Johng Sun]

Strangely, Case 6, should be 1? that match rule 4.

10
C
F
I
A
D
G
J
B
E
H

[Maniac]

I keep getting an unfortunate TLE Can somebody give me some advice?

This is my approach:
- store the number of possible letters for position i
- store the possible letters for position i
- start counting all possible non-bangla-sequences
- search complete tree of possible non-bangla-sequences
- when a new position has to be filled (cause sequence not complete) always fill the position with minimal number of possible letters (to keep fan-out low)
- update stored data when filling a position
- stop searching branch whenever the number of possible letters for some position is zero.

The requested number of bangla-sequeces is then of course easily obtained from the number of non-bangla-sequences.

Although for n=15 and 15 times a '?' there are only 32516 possibilities, it takes my pc about 10 secs to find them Can somebody help me?

Thanks, Erik

[Observer]

Well, don't know if this helps, but since you know the number of possible non-bangla seqs, you may branch your search like this:

Code: Select all

if (num_of_seqs_found == 32516) /* or whatever */
  break;

That's what I've tried for 10663 Non-Powerful Subsets and it's working good~ (though this sounds a bit like cheating)

Ah yeah. Have you ever thought about why all the accepted programs for this task use so much memory?
http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:10513

[Maniac]

I'll give it a try

I have thought about that but I don't have a good idea of a sensible and useful thing to store. Any ideas?

[Per]

My solution doesn't use "much" (depending on what you consider that to be, of course) memory, and the fastest solution even less.
But anyway, one good start is to precalculate all non-bangla sequences when every position is a wildcard, and then answer queries by doing pattern matching among those precalced sequences.

And a hint for speeding up the search: exploit symmetries.

[Hackson]

Hi, I know one way tackling this task is to calculate the non bangladesh sequences, which do not fufil all the 4 requirements. But I 've got WA all the time while I passed all the test data provided in this board... it's driving me insane

Here comes my code:

Code: Select all

const
 lim : array[1..15] of char = ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O');

var
 canuse : array[1..15, 'A'..'O'] of boolean;
 seq : array[-1..15] of char;
 used : array['A'..'O'] of boolean;
 i, j, k, n, m : longint;
 c : string;
 p : char;
 tans, kAns, ans : Qword;

procedure Find(lv : longint);
var x : char;
    t : longint;
   ok : boolean;
begin
 if lv = n+1 then
 begin
  inc(kAns);
  exit;
 end;
 for x := 'A' to lim[n] do
  if not used[x] then
   if canuse[lv][x] then
    if abs(ord(seq[lv-1]) - ord(x)) <> 2 then
     if abs(ord(seq[lv-2]) - ord(x)) <> 1 then
     begin
      ok := true;
      for t := 1 to lv-1 do
      if abs(lv - t) = abs(ord(x) - ord(seq[t])) then
      begin
       ok := false;
       break;
      end;
      if ok then
      begin
       used[x] := true;
       seq[lv] := x;
       find(lv+1);
       if kAns = 32516 then exit;
       used[x] := false;
      end;
     end;
end;

begin

 seq[-1] := chr(1);
 seq[0] := chr(2);

 m := 0;

 while true do
 begin
 for i := 1 to 15 do
  for p := 'A' to 'O' do canuse[i][p] := false;
 readln(n);
 inc(m);
 if n = 0 then break;
 write('Case ', m, ': ');
 ans := 0;
 tans := 1;
 for i := 1 to n do
 begin
  readln(c);
  if c = '?' then
  begin
   tans := tans * n;
   for p := 'A' to lim[n] do
    canuse[i][p] := true;
  end
  else
  begin
   k := 0;
   for j := 1 to length(c) do
    if not canuse[i][C[j]] then
    begin
     canuse[i][c[j]] := true;
     inc(k);
    end;
   tans := tans * k;
  end;  
 end;
 kAns := 0;
 Find(1);
 ans := tans  - kAns;
 if n < 0 then ans := 0;
 writeln(ans);
 end;
end.

Maybe this is so naive that it may got TLE... would there be any better approach? Someone said using exploit symmetry would help, but what does it mean? I know nothing about it.

I need help, thanks