OJ Board

I can't understand why my program gets WA I use backtracking. I try all posssibilitis for all steps. But if I have a two steps like:

<a1 b1>, <a2 b2> and noone didn't fill a triangle, then <a2 b2>, <a1 b1> take the same result as previous.

or

<a1 b1>, <a2 b2> and one player filled a triangle in each step, then <a2 b2>, <a1 b1> take the same result as previous.

But I get WA on 6.0 seconds. Is there any trick? Please, help me!

[cpp]/* Problem 751 Triangle War */

#include <stdio.h>

#define SWAP(a,b) {unsigned c=a;a=b;b=c;}

const unsigned Lines[18][2] = {{1,2},{1,3},{2,3},{2,4},{2,5},{3,5},{3,6},
{4,5},{5,6},{4,7},{4,8},{5,8},{5,9},{6,9},{6,10},{7,8},{8,9},{9,10}} ;

const unsigned Triangles[9][3] = {{0,1,2},{2,4,5},{3,4,7},{5,6,8},
{7,10,11},{8,12,13},{9,10,15},{11,12,16},{13,14,17}};

unsigned A,B,astep,bstep;
unsigned game[18],cc[18],aa[18];

unsigned AddLine(unsigned NLine)
{
unsigned i,j=0,k=0;
for (i=0;i<9;i++)
if (game[Triangles[0]] && game[Triangles[1]] && game[Triangles[2]])
j++;
game[NLine]=1;
for (i=0;i<9;i++)
if (game[Triangles[0]] && game[Triangles[1]] && game[Triangles[2]])
{
k++ ;
if (astep) A++;
if (bstep) B++;
}
if (!(k-j)) SWAP(astep,bstep);
return k-j;
}

unsigned FAddLine(unsigned NLine)
{
unsigned i,j=0,k=0;
for (i=0;i<9;i++)
if (game[Triangles[0]] && game[Triangles[1]] && game[Triangles[2]])
j++ ;
game[NLine]=1;
for (i=0;i<9;i++)
if (game[Triangles[0]] && game[Triangles[i][1]] && game[Triangles[i][2]])
k++ ;
return k-j;
}

void MakeForB(unsigned &A, unsigned &B, unsigned C, unsigned D);

void MakeForA(unsigned &A, unsigned &B, unsigned C, unsigned D)
{
unsigned AA,i,f=1,at,bt,kk[20];
A=B=0;
AA=0;
for (i=0;i<18;i++)
if (game[i]==0)
{
kk[i] = FAddLine(i);
game[i]=0;
if (kk[i]>AA) AA=kk[i];
}
for (int U=AA;U>=0;U--)
{
for (i=0;i<18;i++)
if (game[i]==0)
if (unsigned(U)==kk[i] && ((U && (i>=C)) || ((!U) && (cc[D-1] || (i>=aa[D-1])))))
{
game[i]=1;
cc[D]=U;
aa[D]=i;
if (U) MakeForA(at,bt,i,D+1);
if (!U) MakeForB(at,bt,0,D+1);
at+=U;
if (f || (at>A)) {A=at;B=bt;f=0;}
game[i]=0;
if (!B) break;
}
if (!B) break;
}
}

void MakeForB(unsigned &A, unsigned &B, unsigned C, unsigned D)
{
unsigned BB,i,f=1,at,bt,kk[20];
A=B=0;
BB=0;
for (i=0;i<18;i++)
if (game[i]==0)
{
kk[i] = FAddLine(i);
game[i]=0;
if (kk[i]>BB) BB=kk[i];
}
for (int U=BB;U>=0;U--)
{
for (i=0;i<18;i++)
if (game[i]==0)
if (unsigned(U)==kk[i] && ((U && (i>=C)) || ((!U) && (cc[D-1] || (i>=aa[D-1])))))
{
game[i]=1;
cc[D]=U;
aa[D]=U;
if (U) MakeForB(at,bt,i,D+1);
if (!U) MakeForA(at,bt,0,D+1);
bt+=U;
if (f || (bt>B)) {A=at;B=bt;f=0;}
game[i]=0;
if (!A) break;
}
if (!A) break;
}
}

void main()
{
unsigned t,tt,t2,tt2,f=0;
scanf("%u",&t2);
for (tt2=1;tt2<=t2;tt2++)
{
if (f) printf("\n"); else f=1;
scanf("%u",&t);
for (tt=1;tt<=t;tt++)
{
unsigned n,i,j,x,y;
scanf("%u",&n);
A=B=bstep=0;
astep=1;
for (i=0;i<18;i++) game[i]=0;
unsigned b[18];
for (i=0;i<n;i++)
{
scanf("%u%u",&x,&y);
for (j=0;j<18;j++)
if (Lines[j][0]==x && Lines[j][1]==y)
{
cc[i]=AddLine(j);
if (cc[i]) b[i]=j; else b[i]=0;
aa[i]=j;
break;
}
}
unsigned AA,BB;
if (astep) MakeForA(AA,BB,b[n-1],n); else MakeForB(AA,BB,b[n-1],n);
A+=AA;
B+=BB;
printf("Game %u: ",tt);
if (A>B) printf("A wins.\n"); else printf("B wins.\n");
}
}
}[/cpp]

As topic

[cpp]#include <stdio.h>
#include <string.h>

const int lines[18][2] = {
{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {4, 7},
{4, 8}, {5, 6}, {5, 8}, {5, 9}, {6, 9}, {6, 10}, {7, 8}, {8, 9}, {9, 10}
};
const int tri[9][3] = {
{0, 1, 2}, {2, 4, 5}, {3, 4, 7}, {5, 6, 10}, {7, 9, 11},
{10, 12, 13}, {8, 9, 15}, {11, 12, 16}, {13, 14, 17}
};
bool moved[18], formed[9];
int ntri[2], cur;

void init() {
memset(moved, 0, sizeof(moved));
memset(formed, 0, sizeof(formed));
memset(ntri, 0, sizeof(ntri));
cur = 0;
}

int search(int v1, int v2) {
int i;

for (i = 0; i < 18; i++)
if (lines[0] == v1 && lines[1] == v2)
return i;
}

void checktri() {
bool isformed;
int i;

isformed = false;
for (i = 0; i < 9; i++)
if (!formed && moved[tri[0]] && moved[tri[1]] && moved[tri[2]]) {
ntri[cur]++;
formed = true;
isformed = true;
}
if (!isformed)
cur = 1 - cur;
}

void input() {
int nmoved, v1, v2;

scanf("%d", &nmoved);
while (nmoved-- > 0) {
scanf("%d%d", &v1, &v2);
moved[search(v1, v2)] = true;
checktri();
}
}

int bestmove() {
bool moved2[18], formed2[18], isformed;
int sides, last, forms, min, minp;
int i, j, k;

// try to form triangle
for (i = 0; i < 9; i++)
if (!formed) {
sides = 0;
for (j = 0; j < 3; j++) {
if (moved[tri[j]])
sides++;
else
last = tri[j];
}
if (sides == 2)
return last;
}

// minimize triangles that opponent can form
min = 10;
for (i = 0; i < 18; i++)
if (!moved[i]) {
memcpy(moved2, moved, sizeof(moved2));
memcpy(formed2, formed, sizeof(formed2));
moved2[i] = true;

forms = 0;
do {
isformed = false;
for (j = 0; j < 9; j++)
if (!formed2[j]) {
sides = 0;
for (k = 0; k < 3; k++) {
if (moved2[tri[j][k]])
sides++;
else
last = tri[j][k];
}
if (sides >= 2) {
isformed = true;
formed2[j] = true;
forms++;
if (sides == 2)
moved2[last] = true;
break;
}
}
}
while (isformed);

if (forms < min) {
min = forms;
minp = i;
}
}

return minp;
}

void process() {
int ngame, g;

scanf("%d", &ngame);
for (g = 1; g <= ngame; g++) {
init();
input();

while (ntri[0] < 5 && ntri[1] < 5) {
moved[bestmove()] = true;
checktri();
}

if (ntri[0] >= 5)
printf("Game %d: A wins.\n", g);
else
printf("Game %d: B wins.\n", g);
}
printf("\n");
}

int main() {
int ncase;

#ifndef ONLINE_JUDGE
freopen("input.dat", "r", stdin);
freopen("output.dat", "w", stdout);
#endif

scanf("%d", &ncase);
while (ncase-- > 0)
process();

return 0;
}[/cpp]

It seems you are using greedy for this problem. That is wrong, because it is not necessarily the best move to build a triangle in a move when it is possible. I can't give you an example here, but I can tell you I got only accepted using brute force.

It seems you are using greedy for this problem. That is wrong, because it is not necessarily the best move to build a triangle in a move when it is possible. I can't give you an example here, but I can tell you I got only accepted using brute force.

But wouldn't a brute-force algorithm take exponential time?

Still worth a try though.

Since the problen says that
"Each game starts with an integer m, 6 <= m <= 18, indicating the moves have been made"
We can found a solution with worse case in 2^(18-m) steps.
(each edge is chosen by A or B)

ps: I got AC in 1.468 sec.
You can also try a DP solution My friend use a DP solution to get AC in less than 0.5 sec!

The first time I read this problem I thought that triangles could be of any size. For example I thought that if you connect the points in this order then you'd get a triangle:

1-2-4-5-6-3-1

But it seems that only triangles with sides of length one count.

gives me SIGFPE.
The input specification for the problem states 6<=m<=18;

The question has a blue tick(multiple input).Also the number of test cases is given.
I am confused.So is it that each set will have the number of test cases first and then the test cases.

Plz Enlighten
Thanx in advance.
ranjit

hi.

Although I haven't read probelm 751 yet, there is a clear bug.
[cpp]
int y=0;
int z=6/y;
[/cpp]
This code always set Y for 0.
You cannot divide by 0 anytime.
So, you recieved SIGFPE, I think so.

If I'm wrong, so sry.

Ok, this is kind of confusing, but here is what's happening.

The problem is multiple input, so you should first read the number of data sets.

Each data set involves a number of cases. The sample input only shows the number of cases, it doesn't show the number of data sets. So you need to read another integer at the start.

this means 6/0, witch would give u FPE, but i guess u did this to find out if there will be test cases for m < 6
Also u are declaring int y in two places, in main() , and localy for if(m < 6) ...
And i think that if u have both multiiple input problem and number of test cases, u should do something like this:

Thanx for the help.
I figured out the multiple input.

Now I am getting WA

Can anyone prvide me sample i/o;

Thanx in advance.
ranjit

why does the judge still have multiple i/ps ?

For problem 751(Triangle War) I definitely know that my solution is right but i get wa at the judge.I know it has got to do with multiple i/p but cant find out what;'s wrong ?

Can anyone help me ??

Thanx in advance.
ranjit.

I'm trying to solve problem 751(Triangle War),

But judge always gives WA to me..

Please give me some i/o to debug.

I'm practicing debugging(because of Programming Contest), so I can't post my code

What are the correct output for these inputs?
PS.although 6<=m, I want to know these outputs.

Thanks in advance.

input: my output:

Your outputs are correct.