664 - Single-Player Games

[zac.friggstad]

I'm getting WA on 664 "Single-Player Games" and I'm pretty sure it's not due to precision. I'm trying to solve it by constructing a system of linear equations for the expected values of each variable and then solving this system with Gaussian elimination.

I'm confident that this is the right approach, but I have obviously done something wrong in my implementation. Does anybody have sample I/O for this problem that they would be willing to share? Thanks in advance.

[rio]

I'm also getting WA.
Could some one verify my io test ? Also, any tricky case may help me too.

input:

Code: Select all

3
a = (b (a 2))
b = 1
c = (a a 1)
3
a = a
b = (1 2 a b)
c = (c c c c c c c 1)
8
a = ((1 7) 6 ((b 3) c))
b = (4 a)
c = (1 (1 1 (2 c)) f a (a a))
d = ((b a) 3 e f (2 (b c) 2))
e = (1 e h)
f = (a b c d e e f)
g = (1 1 (a (b (c e (f 1)))))
h = (h (a b 2 -1) -3 0 f (f e -9))
0

output:

Code: Select all

Game 1
Expected score for a = 1.333
Expected score for b = 1.000
Expected score for c = 1.222

Game 2
Expected score for a undefined
Expected score for b undefined
Expected score for c = 1.000

Game 3
Expected score for a = 4.390
Expected score for b = 4.195
Expected score for c = 2.742
Expected score for d = 2.548
Expected score for e = 0.486
Expected score for f = 2.475
Expected score for g = 1.886
Expected score for h = -0.028

Thanks in advance.
----
Rio

[mf]

My accepted program produces the same output.

Your input is not strictly correct. "b = 1" and "a = a" are not valid definitions, according to the grammar.

[little joey]

Your input is not strictly correct. "b = 1" and "a = a" are not valid definitions, according to the grammar.

So that's why my program couldn't solve these cases. Anyway, here's some I/O I found on the internet (and might even be the judges I/O ):

input:

Code: Select all

1
a = ((1 7) 6 ((8 3) 4))
2
a = (1 b)
b = (4 a)
1
a = (a a a)
3
a = (1 b c)
b = (a 2 c)
c = (a b 3)
5
a = (e (15 d (57 a) (45 (75 c))) b 189)
b = (d (a -29 30) ((b c)) ((51 a) (a 67) (e 79) (e a)))
c = (((d)))
d = (-1 (-98) ((a) c) (d e e (-81) ((a))) 58 (b))
e = (a b c d a b c d a b c d a b c d a b c d a b c d)
2
a = (1 (2 (3 (4 (5 (6 (7 (8 (9 (10 (11 (12 (13 (14 (15 b)))))))))))))))
b = (b b)
5
a = ((((((((((((((a))))))))))))))
b = (13 17 18 b d)
c = (a b c d)
d = (b 8 (d 7))
e = ((e) ((7)) (((((e))))))
7
a = ((4 5) 2 ((1 3) 7))
b = (9)
c = ((((((((((((((((((((((((((((((((((((99))))))))))))))))))))))))))))))))))))
d = ((1)(1)(1))
e = (1 (2 (3 (4 (5 (6 (7 (8 (9 (10 20))))))))))
f = (-1 1)
g = (-1 -2 -3 -4 -5 -6 1998 -1111)
2
a    =   (    17    (    18     b  ))                
b  =           (      -19            a       (    8  a   )    ( 4   9))   
26
a = ((-17 a) (z (z 3)))
b = (b 8 c g i h j)
c = ((a c m) (p r o g r a m m i n g) (c o n t e s t))
d = (1 6 (1 6 (1 6 (1 6 d d))))
e = ((((f)) g) h)
f = (17 18 19 (20 21))
g = (((((7 (n) 8))) 9 b d))
h = (((((((1 2 3 4 5 6 7 8) (8 7 6 5 4 3 2 1)))))))
i = (((((h a c)))))
j = ((1) (11) (1998))
k = ((((((((k l))))))))
l = (l k)
m = (1 9 2 0 -1)
n = (0 e)
o = (o h n o (8))
p = (0 0 0 0 0 0 0 0 0 0 0 0 0 0 p p p p p p p p p p p p p p)
q = ((((((((w))))))))
r = (m c m)
s = (1 p 1 p 1 p 1 p s s s s s s s o m)
t = (a d f e g t s r p)
u = (u v w x y z)
v = (a a a a v v v v)
w = ( w y w y )
x = ((2) m o r e)
y = (q)
z = (1 -9 9 -8)
0

output:

Code: Select all

Game 1
Expected score for a = 4.917

Game 2
Expected score for a = 2.000
Expected score for b = 3.000

Game 3
Expected score for a undefined

Game 4
Expected score for a = 1.750
Expected score for b = 2.000
Expected score for c = 2.250

Game 5
Expected score for a = 67.521
Expected score for b = 24.617
Expected score for c = 4.685
Expected score for d = 4.685
Expected score for e = 25.377

Game 6
Expected score for a undefined
Expected score for b undefined

Game 7
Expected score for a undefined
Expected score for b = 14.611
Expected score for c undefined
Expected score for d = 10.444
Expected score for e = 7.000

Game 8
Expected score for a = 3.667
Expected score for b = 9.000
Expected score for c = 99.000
Expected score for d = 1.000
Expected score for e = 2.008
Expected score for f = 0.000
Expected score for g = 108.250

Game 9
Expected score for a = 13.759
Expected score for b = 3.034

Game 10
Expected score for a = -6.042
Expected score for b = 120.778
Expected score for c = 5.593
Expected score for d = 3.500
Expected score for e = 15.712
Expected score for f = 18.625
Expected score for g = 35.224
Expected score for h = 4.500
Expected score for i = 1.350
Expected score for j = 670.000
Expected score for k undefined
Expected score for l undefined
Expected score for m = 2.200
Expected score for n = 7.856
Expected score for o = 6.785
Expected score for p = 0.000
Expected score for q undefined
Expected score for r = 3.331
Expected score for s = 1.299
Expected score for t = 8.956
Expected score for u undefined
Expected score for v = -6.042
Expected score for w undefined
Expected score for x = 6.006
Expected score for y undefined
Expected score for z = -1.750

[rio]

Thanks for reply, mf and joey. Finally got AC.
The bug was caused by round-off error. (I didn't take the approach using Gaussian elimination)

our input is not strictly correct. "b = 1" and "a = a" are not valid definitions, according to the grammar.

Sorry for my bad input
----
Rio

[Fly]

hm... It seems even the long doubles are not quite enough for this problem, isn't it?

Code: Select all

1
a = (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a 1))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
1
a = (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a 1))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
1
a = (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a (a 1))))))))))))))))))))))))))))))))
0

Code: Select all

Game 1
Expected score for a = 1.000

Game 2
Expected score for a = 1.000

Game 3
Expected score for a = 1.000

[mf]

I've used double with epsilon 1e-9, standard Gauss-Jordan algorithm with pivoting, and didn't have any problems with precision at all.

For all three of your test cases my program prints "undefined".

[Fly]

Hurray!!! I have solved it by the long fraction arithmetics!!!I'm crazy. %)