751 - Triangle War

[Revenger]

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]

[ec3_limz]

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]

[Adrian Kuegel]

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.

[ec3_limz]

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.

[InOutMoTo]

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!

[Ryan Pai]

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.

[ranjit]

Code: Select all

#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
  int t;
  scanf("%d",&t);
  int x,y;
  while(t--)
    {
      int m;
      scanf("%d",&m);
      if(m<6)
	{
	  int y=0;
	  int z=6/y;
	}
      for(int i=0;i<m;i++)
	scanf("%d%d",&x,&y);
      cout<<"Finished\n";
    }
  return 0;
}

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

[hiloshi]

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.

[Ryan Pai]

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.

[wos]

Code: Select all

int y=0;
int z=6/y; 

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:

Code: Select all

int cases;
scanf("%i", &cases);
while (cases--)
{
  int m, i, j;
  scanf("%i", &m);
  for(int k = 0; k < m; k++)
    scanf("%i %i", &i &j);
}

[ranjit]

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

[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.

[Solmon K.]

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

[hi!man!]

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

Thanks in advance.

input:

Code: Select all

5
0
1
5 6
2
4 5
5 9
4
4 5
5 9
1 2
7 8
6
1 2
3 5
3 6
5 6
8 9
9 10

my output:

Code: Select all

Game 1: B wins.
Game 2: B wins.
Game 3: B wins.
Game 4: A wins.
Game 5: B wins.

[Jan]

Your outputs are correct.