839 - Not so Mobile

[broderic]

Hello...besides the sample input being wrong, is there something else
tricky with this question? Somebody in the ranklist said to use pascal
if it doesn't work, but people did solve it using c++.

I'll post my code since it's so short (in case I did something really
dumb), but I'll only keep it up till somebody helps me.

[Adrian Kuegel]

With your code you don't consider the case, that the mobile is in equilibrium in the highest level, but not in equilibrium in a lower level. Use a flag to indicate if anywhere was a level where the mobile wasn't in equilibrium.
The problem, which made people like me use Pascal instead of C/C++, is already fixed.

[broderic]

hmm,
wouldn't one of the "if (!mobile()) return 0;" catch the case where
a subsequent mobile is not in equilibrium?

[Adrian Kuegel]

What about rd = ld = 0?

[htl]

How about this code? It got WA. Is anything I didn't consider yet?
[c]
#include<stdio.h>
#define YES 1
#define NO 0
int error;
int mobile(int);
void main(void)
{
int count,x;
scanf("%d",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
error=NO;
mobile(0);
if(error)
printf("NO\n");
else
printf("YES\n");
}
}
int mobile(int depth)
{
int wl,dl,wr,dr;
scanf("%d %d %d %d",&wl,&dl,&wr,&dr);
if(wl==0)
wl=mobile(depth+1);
if(error)
return;
if(wr==0)
wr=mobile(depth+1);
if(error)
return;
if(wl*dl==wr*dr)
return wl+wr;
else
{
error=YES;
return;
}
}
[/c]

BTW, I think the data might be wrong:

0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 2 3 -> I think it's 1 6 3 2

[xenon]

Read the complete input, even if you know there is an error at an early stage. Your function mobile() returns if it encounters an error in the left branch and leaves the right branch unread.

[htl]

I still don't understand why I have to read the complete input.
If I got error in reading left branch, do I have to read the
right branch? Is it necessary?

[WhiteShadow]

I still don't understand why I have to read the complete input.
If I got error in reading left branch, do I have to read the
right branch? Is it necessary?

Well, don't forget that this problem has multiple input, ie, more than one mobile may be present in the input. Therefore, it is necessary to read a single mobile completely in order to correctly read the start of the next mobile....

[..]

Can anyone tell me, why is the following case should give "No"?

1

0 2 0 2
1 3 1 1
1 1 1 3

From the problem specification, I can't find a clear statement stating that all the sub-mobiles are also required to be in equilibrium.......
But it seems that "checking equilibrium of sub-mobile" is the key to accepted.........

[Daredevil]

Equilibrium in this problem is defined as a condition where the product of the left distance with the TOTAL left mobile weight (although there may be a sub mobile in the left mobile not equilibrium) equals to that of the right.
Example:

Input =
0 12 96 1
1 2 3 2
2 4 2 4

Left - mobile : 0 left distance : 12

sub 1 : 1 2 3 2 (not equilibrium)

sub 2 : 2 4 2 4 (equilibrium)

Total weight of left - mobile is 8

Right - mobile : 96 right distance : 1

so the math : left weight * left distance = 12 * 8 = 96
right weight * right distance = 96 * 1 = 96

So this system, according to me is equilibrium. Is this correct?
If false, what's the right definition of 'equilibrium' ?

[ashutoshkorde]

you need to have equilibrium in each and every sub moblie branch..
its not mentioned in the problem but that's the case...

[lowai]

i got wa with the code following...
can anyone help me to check it/
[pascal]
var
kase : integer;
equ : boolean;

function balance : double;
var w1, d1, w2, d2 : longint;
l, r : double;
begin
readln(w1, d1, w2, d2);
if not equ then exit;

if w1 > 0 then l := w1 else l := balance;
if w2 > 0 then r := w2 else r := balance;
if abs(l * d1 - r * d2) > 1e-7 then begin equ := false; exit; end;
balance := r * (d1 + d2) / d1;
end;

begin
readln(kase);
while kase > 0 do
begin
equ := true;
balance;
if equ then
writeln('YES')
else
writeln('NO');
dec(kase);
if kase > 0 then writeln;
end;
end.
[/pascal]

[Sanghack]

You wrote that
0 12 96 1
1 2 3 2
2 4 2 4

But how this input could be...
0 12 96 1 shows that this root mobile needs only one left sub - mobile.

and
1 2 3 2 sub-mobile's total weight is 2 + 2 = 4 , not 1*2 + 3*2...

the right definition of 'equilibrium' ?
-> All sub-mobile's left-weight and right weight is equal.

[Sanghack]

Hi.
Thanks for reading my question.

I solved ( not yet ) this problem with

stack ( to make mobile - as tree data type ),
and
dfs ( to traverse all the sub-mobiles ).

I tested some kinds of input with several test cases.
I thought my code would work well... But I got WA.

(My code is so complex)

typedefinition...
pushStack.. (also links the mobile and pop from stack list..)
traverse ( easy to see... DFS method.)
and...
main...

[cpp]#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>

typedef struct mobile MOB;
struct mobile{
int leftWeight,leftLength,rightWeight,rightLength;
int totalWeight;
MOB* l_Mob;
MOB* r_Mob;
MOB* stack;
};
MOB* stackLast;
MOB* root;

MOB* newMobile(int lw,int ll,int rw,int rl){
MOB* result=(MOB*)malloc(sizeof(MOB));
result->leftWeight=lw;
result->l_Mob=NULL;
result->leftLength=ll;

result->rightWeight=rw;
result->r_Mob=NULL;
result->rightLength=rl;

result->totalWeight=0;
return result;
}


void pushStack(MOB* pushed){
if(stackLast==NULL){
//stackStart=pushed;
stackLast=pushed;
pushed->stack=NULL;
}
else{
if(stackLast->leftWeight==0 && stackLast->l_Mob==NULL){
stackLast->l_Mob=pushed;
// all mobile hanged.
if(stackLast->rightWeight!=0 || stackLast->r_Mob!=NULL){
// new mobile should be pushed
if(pushed->leftWeight==0 || pushed->rightWeight==0){
pushed->stack=stackLast->stack;
stackLast=pushed;
}
// don't have to
else{
stackLast=stackLast->stack;
}
}
// wait right sub mobile.
else{
// & push current
if(pushed->leftWeight==0 || pushed->rightWeight==0){
pushed->stack=stackLast;
stackLast=pushed;
}
}
}
else if(stackLast->rightWeight==0 && stackLast->r_Mob==NULL){
stackLast->r_Mob=pushed;
// all mobile hanged.
// new mobile should be pushed
if(pushed->leftWeight==0 || pushed->rightWeight==0){
pushed->stack=stackLast->stack;
stackLast=pushed;
}
// don't have to
else{
stackLast=stackLast->stack;
}
}
}
}

bool traverse(MOB* at){
if(at->leftWeight!=0 && at->rightWeight!=0){
if(at->leftWeight*at->leftLength == at->rightWeight*at->rightLength){
at->totalWeight=at->leftWeight+at->rightWeight;
return true;
}
else
return false;
}
else{
bool balance;
int lw,rw;
if(at->leftWeight==0){
balance=traverse(at->l_Mob);
if(balance==false)
return false;
lw=at->l_Mob->totalWeight;
}
else
lw=at->leftWeight;
if(at->rightWeight==0){
balance=(balance && traverse(at->r_Mob));
if(balance==false)
return false;
rw=at->r_Mob->totalWeight;
}
else
rw=at->rightWeight;
if(lw*at->leftLength == rw*at->rightLength){
at->totalWeight=lw+rw;
return true;
}
else
return false;
}
}

void main(){
freopen("839.txt","r+",stdin);
int testCase;
int lw,ll,rw,rl;
cin >> testCase;
while(testCase--){
root=NULL;
stackLast=NULL;
bool readMore=false;
cin >> lw >> ll >> rw >> rl;
root=newMobile(lw,ll,rw,rl);
if(lw==0)
readMore=true;
if(rw==0)
readMore=true;
if(readMore){
pushStack(root);
}
while(stackLast){
cin >> lw >> ll >> rw >> rl;
MOB* subMobile=newMobile(lw,ll,rw,rl);
pushStack(subMobile);
}
if(traverse(root)){
printf("YES\n");
}
else{
printf("NO\n");
}
if(testCase){
printf("\n");
}
}
}[/cpp]


Sample Input
11

0 2 6 5
0 2 6 3
1 8 0 1
0 5 0 3
1 2 2 1
2 3 3 2

0 2 6 6
0 2 6 3
1 8 0 1
0 5 0 3
1 2 2 1
2 3 3 2

0 2 0 4
0 3 0 2
1 1 1 1
2 4 4 2
1 6 3 2

0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

1 6 3 1

2 4 4 2

0 4 8 1
1 1 1 3

1 1 1 1

2 100 100 2

2 100 2 100

0 3 0 3
0 2 0 2
1 1 1 1
1 1 1 1
0 2 0 2
1 1 1 1
1 1 1 1

Sample Output

YES

NO

NO

YES

NO

YES

NO

YES

YES

YES

YES

It seems like 'delegating my responsibility'. But I can't do it more without your help...

Any help appreciated-
(sorry to read my poor English)

[Sarmento]

Can anyone help me out? I dunno why I get WA. I tried out all the input I could find/create and the answer is accurate. Maybe I'm missing something.

Code: Select all

[c]
#include <stdio.h>

int balanced;

void mobile(int *weight){
	int w1, d1, w2, d2;
	scanf("%d %d %d %d",&w1,&d1,&w2,&d2);
	if (balanced == 1){
		if (w1 == 0)
			mobile(&w1);
		if (w2 == 0)
			mobile(&w2);
		if (w1*d1 != w2*d2)
			balanced = 0;
		*weight = w1 + w2;
	}
}

int main(){
	int n;
	int weight;
	scanf("%d",&n);
	for(; n>0; n--){
		weight = 0;
		balanced = 1;
		mobile(&weight);
		if (balanced)
			printf("\nYES\n");
		else
			printf("\nNO\n");
	}
	return 0;
}
[/c]