10592 - Freedom Fighter

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

Moderator: Board moderators

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

10592 - Freedom Fighter

Post by windows2k » Sat Dec 27, 2003 10:25 am

Could someone give some tricky inputs or outputs?
"It is granted that a freedom fighter group can fight only one opponent group at a time."
Means that we should calc how many freedom fighter connected to oppoent?
Am I right?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sat Dec 27, 2003 11:40 am

I calculated the number of groups of freedom fighters that are connected to the enemies. Then simply I multiply that amout by 2 to get the total.

I think the judge data does not contain severely technical inputs. And any general approach should get AC.

Try this

................................
.............B.................
........BBBB................
***..***P..................
................................
................................
................................

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Sat Dec 27, 2003 4:59 pm

sohel wrote:I calculated the number of groups of freedom fighters that are connected to the enemies. Then simply I multiply that amout by 2 to get the total.
Yes, I thought my method is the same as yours.
I think the judge data does not contain severely technical inputs. And any general approach should get AC.

Try this

................................
.............B.................
........BBBB................
***..***P..................
................................
................................
................................
The graph should be n*n, the input looks strange.
Have another tricky input/output? Thx :D

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Sat Dec 27, 2003 5:27 pm

8)

I don't whether tricks exist or not.

But I consider if freedom A and B connect to oppenent C at the same time.

Like this:

BBB
PPP
BBB

I still count that only once.

(Maybe it is the trick. Good Luck)

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Sat Dec 27, 2003 5:40 pm

Ghost77 dimen wrote:8)
BBB
PPP
BBB
My Output:
Sector #1: contain 2 freedom fighter group(s) & 1 enemy group(s)
Total 2 group(s) are in fighting position.
Am I right?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sat Dec 27, 2003 5:55 pm

it should be 3 groups in fighting position :)
that is :
- the 1st row 'B'
- 'P'
- the 3rd row 'B'

the B in the 1st row and B in the 3rd row are considered different group.
good luck!

-titid-
Kalo mau kaya, buat apa sekolah?

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Sat Dec 27, 2003 6:00 pm

8)
Sorry, I find my program have some bugs.

3
BBB
PPP
BBB

3
PPP
BBB
PPP

the last answer of mine are also equal to 4

(I don't know why I still got Accepted, maybe only simple connection will

occur.)

Some other sample

4
BB..
.PP.
B..P
BBBB
Sector #1: contain 1 freedom fighter group(s) & 1 enemy group(s)
Sector #2: contain 1 freedom fighter group(s) & 1 enemy group(s)
Total 4 group(s) are in fighting position.

5
B.B..
.P.P.
.PP.B
BB.P.
B...P
Sector #1: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #2: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #3: contain 1 freedom fighter group(s) & 1 enemy group(s)
Sector #4: contain 0 freedom fighter group(s) & 1 enemy group(s)
Sector #5: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #6: contain 0 freedom fighter group(s) & 1 enemy group(s)
Sector #7: contain 0 freedom fighter group(s) & 1 enemy group(s)
Total 2 group(s) are in fighting position.

Good Luck

Kamirr
New poster
Posts: 1
Joined: Sun Jan 18, 2004 9:15 pm

Post by Kamirr » Sun Jan 18, 2004 9:31 pm

I check all Yours tests, and i had correct answers. I dont't know what's wrong with my code. Can You look at source, or give more inputs?
Thanks in advance.

[pascal]

type
flist=record
a,b:integer;
end;
var
se,t:array[0..115,0..155]of char;
fft,ent:array[1..2501]of integer;
out:array[1..5221,1..5541]of integer;
fl:array[1..5500]of flist;
spr:array[1..5500]of boolean;
spr2:array[1..5500]of integer;
bb,aa,zz,qq,f,reg,enc,ffc,n,m,bi,bk,z,i,j,d,s,k:longint;
label start;

procedure region(x,y:longint); forward;
procedure freef(x,y,z:longint);forward;
procedure ocup(x,y,z:longint);
begin
t[x,y]:='.';
if (t[x+1,y]='P') then ocup(x+1,y,0);
if (t[x-1,y]='P') then ocup(x-1,y,0);
if (t[x,y+1]='P') then ocup(x,y+1,0);
if (t[x,y-1]='P') then ocup(x,y-1,0);

if (t[x+1,y]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x+1,y,1); end;
if (t[x-1,y]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end; freef(x-1,y,1); end;
if (t[x,y+1]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x,y+1,1); end;
if (t[x,y-1]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x,y-1,1); end;

if (t[x+1,y]='*') then begin inc(aa); fl[aa].a:=x+1; fl[aa].b:=y; end;
if (t[x-1,y]='*') then begin inc(aa); fl[aa].a:=x-1; fl[aa].b:=y; end;
if (t[x,y+1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y+1; end;
if (t[x,y-1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y-1; end;

end;

procedure freef;
begin
t[x,y]:='.';
if (t[x+1,y]='B') then freef(x+1,y,0);
if (t[x-1,y]='B') then freef(x-1,y,0);
if (t[x,y+1]='B') then freef(x,y+1,0);
if (t[x,y-1]='B') then freef(x,y-1,0);


if (t[x+1,y]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]); end; ocup(x+1,y,1); end;
if (t[x-1,y]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x-1,y,1); end;
if (t[x,y+1]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x,y+1,1); end;
if (t[x,y-1]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x,y-1,1); end;
if (t[x+1,y]='*') then begin inc(aa); fl[aa].a:=x+1; fl[aa].b:=y; end;
if (t[x-1,y]='*') then begin inc(aa); fl[aa].a:=x-1; fl[aa].b:=y; end;
if (t[x,y+1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y+1; end;
if (t[x,y-1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y-1; end;

end;

procedure region;
begin
if t[x,y]= 'B' then
begin
inc(ffc);
freef(x,y,0);
end
else if t[x,y]= 'P' then
begin
inc(enc);
ocup(x,y,0);
end
else
begin
t[x,y]:='.';
if t[x+1,y]<>'.' then region(x+1,y);
if t[x-1,y]<>'.' then region(x-1,y);
if t[x,y+1]<>'.' then region(x,y+1);
if t[x,y-1]<>'.' then region(x,y-1);

end;

end;

begin
start:
{}{}{}{}{}{}{}{}{}{ read & clean }{}{}{}{}{}{}
for i:=0 to 51 do
for j:=0 to 51 do
begin
t[i,j]:='.';
se[i,j]:='.';
end;
k:=0;
n:=0;
m:=0;

readln(d);
if d=0 then exit;
for i:=1 to d do
begin
for j:=1 to d do
begin
read(t[i,j]);
end;
readln;
end;
m:=1;
{}{}{}{}{}{}{}{}{}{}{}{}{}{}{ EOF read }{}{}{}{}{}{}{}{}

{}{}{}{}{}{}{}{}{}{}{ seek }{}{}{}{}{}{}{}
for i:=1 to d do
begin
for j:=1 to d do
begin
if (t[i,j]='*')or (t[i,j]='B')or (t[i,j]='P') then
begin
inc(reg);
region(i,j);
for bb:=1 to aa do
begin
if t[fl[bb].a,fl[bb].b]<>'.' then region(fl[bb].a,fl[bb].a);
end;
for qq:=1 to 100 do
begin
if spr2[qq]<>0 then
begin
f:=1+f+spr2[qq];
spr2[qq]:=0;
end;

end;
for qq:=1 to ffc do
begin
spr[qq]:=false;
end;
f:=f+zz;
fft[reg]:=ffc;
ent[reg]:=enc;
ffc:=0;
enc:=0;
aa:=0;
bb:=0;
end;
end;
end;

{}{}{}{}{}{}{}{}{}{}{ EOF seek }{}{}{}{}{}{}{}



{}{}{}{}{}{}{}{}{}{}{ output }{}{}{}{}{}{}{}
for i:=1 to reg do
begin
writeln('Sector #',i,': contain ', fft ,' freedom fighter group(s) & ', ent ,' enemy group(s)');
end;
writeln('Total ', f,' group(s) are in fighting position.');
Writeln('');

reg:=0;
f:=0;

{}{}{}{}{}{}{}{}{}{}{ output }{}{}{}{}{}{}{}

goto start;

end.


[/pascal]

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

About The Judge Input Data Set

Post by Mahmud776 » Sat Jan 31, 2004 9:03 pm

In the judge input data set of this problem, it is clear that there is no such an input set that contain the data of four connected groups. Like..
PPPP
BBBB
PPPP
BBBB
Or,
BBBB
PPPP
BBBB
PPPP
You can consider that highest three groups are connected or in fighting
position.
Here I gave a sample input and output:

Input:
10
......****
.***.*BBBB
PPPP*.BPPP
BBBB*..BBB
PPPP*.***B
******....
B**BB*....
B**BB**..*
***BB**..P
P**BBBB..P

Output:
Sector #1: contain 2 freedom fighter group(s) & 1 enemy group(s)
Sector #2: contain 3 freedom fighter group(s) & 3 enemy group(s)
Sector #3: contain 0 freedom fighter group(s) & 1 enemy group(s)
Total 5 group(s) are in fighting position
.

I think this will remove all confusions.

Mahmud

Faisal_Bd
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am
Location: Bangladesh

10592(Freedom Fighter): WA

Post by Faisal_Bd » Wed Sep 01, 2004 10:26 am

When I got WA for the first time in this problem, I visited the previous discussions on this one. Some tricky input-output were given there and my solution code was right for them. But I still can't understand what wrong is with my code. I couldn't find out the bug in my code though I tried couple of hours. Anyone can help me please? Or give some other tricky input-output? Here's my code:

Code: Select all

deleted later......
Last edited by Faisal_Bd on Sat Sep 04, 2004 10:45 am, edited 1 time in total.

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Wed Sep 01, 2004 4:56 pm

What is your answer for the following cases ?

5
.B...
.....
.....
...P.

1
.

1
B

1
P

2
BP
PB

2
PP
BB

2
BP
BP

3
B.B
.P.
B.B

Faisal_Bd
New poster
Posts: 13
Joined: Wed Sep 01, 2004 10:00 am
Location: Bangladesh

Post by Faisal_Bd » Sat Sep 04, 2004 10:39 am

Thanks a lot, Raiyan Kamal. I managed to handle the error and fixed the code and got AC :) .
The answers for your test cases follow:
  • Sector #1: contain 1 freedom fighter group(s) & 0 enemy group(s)
    Sector #2: contain 0 freedom fighter group(s) & 1 enemy group(s)
    Total 0 group(s) are in fighting position.


    Sector #1: contain 1 freedom fighter group(s) & 0 enemy group(s)
    Total 0 group(s) are in fighting position.

    Sector #1: contain 0 freedom fighter group(s) & 1 enemy group(s)
    Total 0 group(s) are in fighting position.

    Sector #1: contain 2 freedom fighter group(s) & 2 enemy group(s)
    Total 4 group(s) are in fighting position.

    Sector #1: contain 1 freedom fighter group(s) & 1 enemy group(s)
    Total 2 group(s) are in fighting position.

    Sector #1: contain 1 freedom fighter group(s) & 1 enemy group(s)
    Total 2 group(s) are in fighting position.

    Sector #1: contain 1 freedom fighter group(s) & 0 enemy group(s)
    Sector #2: contain 1 freedom fighter group(s) & 0 enemy group(s)
    Sector #3: contain 0 freedom fighter group(s) & 1 enemy group(s)
    Sector #4: contain 1 freedom fighter group(s) & 0 enemy group(s)
    Sector #5: contain 1 freedom fighter group(s) & 0 enemy group(s)
    Total 0 group(s) are in fighting position.
However, I assumed that a Bangladeshi group can fight against more than one enemy group which is not valid according to the problem description. I think in the input data, there is no test case like this:

PPP
BBB
PPP
In this case, total 2 groups are fighting according to the problem description and my code gives wrong solution(3 groups). However, I shall try to fix it.

Another point, it is stated:
It is granted that a freedom fighter group can fight only one opponent group at a time.
Does it mean that there will not be any case given above? I don't think so. :-?

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Tue Sep 07, 2004 1:50 pm

Dear Faisal,

for the line
It is granted that a freedom fighter group can fight only one opponent group at a time.
I think it means that there will be no such cases where there is a Freedom Fighter group adjacent to more than on enemy groups. But what about enemy groups ? Can they fight more than one Freedom Fighter groups simultaneously ? Its confusing!!

If you assume that a Freedom Fighter group can fight only one Enemy group at a time and vice versa, then there will be no cases like

PPP
BBB
PPP

then you can solve the problem easily ( like you have already done ). But, if that line in the statement bears some special meaning which we have failed to understand, ( i.e. Enemies can fight more than one Freedom Fighter groups simultaneously ) then that code will surely get rejected if they add any case like

BBB
PPP
BBB

and then rejudge it.

Anyways, since a lot of programmers got AC assuming the same, therefore, we can also feel safe to assume this.

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Fri Dec 17, 2004 7:32 pm

hi everybody.
can anybody who got a.c. explain his algo.
i got stuck to solve this problem.
plz........

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Sat Dec 18, 2004 3:51 pm

Simple DFS or BFS with a little bit of caution for the special cases. That's all.

Post Reply

Return to “Volume 105 (10500-10599)”