OJ Board

The Online Judge board
https://onlinejudge.org/board/

10513 - Bangladesh Sequences

https://onlinejudge.org/board/viewtopic.php?t=3915

Page 1 of 2

10513 - Bangladesh Sequences

Posted: Mon Sep 15, 2003 11:31 pm
by pingus
plz, what is the ouput for:

Code: Select all

7
?
?
?
?
?
?
?
0

Posted: Tue Sep 16, 2003 6:44 am
by 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.

Posted: Wed Sep 17, 2003 7:12 am
by 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. 8)

Posted: Wed Sep 17, 2003 12:29 pm
by 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 ?

Posted: Wed Sep 17, 2003 1:04 pm
by PdR
pingus wrote:Only the worst case { 15, ?, ?, ..., ? } take 7s with output:

Code: Select all

437893890380826859
is at least correct ?
Yes

Posted: Fri Sep 19, 2003 10:32 am
by 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.

Posted: Fri Sep 19, 2003 11:30 am
by PdR
Only the last one differs.
It should be

Code: Select all

Case 18: 196608

Posted: Fri Sep 19, 2003 12:39 pm
by chancp
The last input case has a tricky thing, there is a line "DDCC".
So the correct answer should not be 196608

Posted: Fri Sep 19, 2003 1:10 pm
by 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.

Posted: Thu Dec 11, 2003 9:35 am
by Der-Johng Sun
Strangely, Case 6, should be 1? that match rule 4.

10
C
F
I
A
D
G
J
B
E
H

TLE

Posted: Thu Sep 16, 2004 8:52 pm
by 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

Posted: Fri Sep 17, 2004 6:37 am
by 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) :wink:

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 :P

Posted: Fri Sep 17, 2004 3:25 pm
by 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?

Posted: Fri Sep 17, 2004 5:37 pm
by 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.

10513 WA and any efficient approach?

Posted: Mon May 29, 2006 5:48 pm
by 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 :o

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 :wink: :roll:
All times are UTC+02:00
Page 1 of 2

Powered by phpBB® Forum Software © phpBB Limited