OJ Board

Is this issue really solved? I keep getting PE on problem 11599.

Hi, my result for (0,2) matches LayCurse's. My "wins" values are: (0,3)/(3,0): 22401389 (1,1): 11018156 (3,4)/(4,3): 24849438 (1,5)/(5,1): 9158932 (0,2)/(2,0): 13322980 (0,6)/(6,0): 21685496 (4,6)/(6,4): 20858993 Also, the problem statement is unclear about ties. Should they be considered ...

Hi there, the problem states that there are "up to 500 symbols from V and only from V" - but my parser failed on the judge's input, just because it included an "assert(0);" if it read an invalid character. Simply ignoring those invalid characters got me AC. BTW: The last sample c...

I didn't yet solve this one, but IMHO two operators with the same precedence must have the same associativity. In your input, this is not the case with * and /. Imagine the expression 2*2/3, using the precedences and associativities from your input. It could be evaluated to (2*2)/3 = 1 or to 2*(2/3)...

A hint for the C people getting TLE:

sscanf() on long input strings is extremely slow, because the glibc implementation of this function scans the string for the terminating \0 character. Using strtok() or something like that is much faster in this problem.

I just tried to solve this beast once again and came to the conclusion that the order of elimination does matter! This happens when I repeatedly try to eliminate with length=max..1, scanning from left to right: b a b a c a c b a b c b a c b a b c a c b a c b a b a c a b a>b a b a c a b a<c b b a b a...

Hello folks. This problem seemd quite simple to me: Some backtracking+memoization (or DP) should be sufficient. However, I got a bunch of WAs within times comparable to the AC solutions. My solution uses the tuple of distances to the capital as memoization key. As I don't think my calculations are p...

More than one year since the last post - let me revive that one! :D I finally got this one AC after lots of WAs. The essential point is not to write "1 0.251" when you could write "2 0.251". Personally, I think this is misleading and incorrect, as box 1 with a value of 0.2514 is ...

@Pier:

Your test if a pole is visible is wrong. A pole occludes all poles having the same angle, a greater distance and at most the same size.

HTH,
Christian

Thank you. I had alpha-beta pruning enabled in my code, but this does not work if values are changed when passing them up the game tree. Something like this is necessary for the "fast victory/slow defeat" strategy to work.

Finally, I got AC in 2.38s using "normal" minimax.

I tried to solve this problem by using a minimax search. Each game state is assigned a value recursively: 0 <= N <= 19: BLACK wins after N moves 20 <= N <= 39: WHITE wins after (39-N) moves Winning states get a 0 or 39, depending on the winner. For any other game state, BLACK uses the child state wi...

It's not allowed to put songs 1 and 3 on disk 1 and song 2 on disk 2. More formally, for every possible pair (a,b) of chosen song numbers having a>b, the relation disk(a)>=disk(b) must hold.

Ermmm... "0:00.1000" seems to be a quite strange time.

The problem can be interpreded as a three-dimensional version of the 15 Puzzle. A---D /| /| B---E | /| G/|-J C---F |/ | H-|-K |/ |/ I--- Possible exchanges are nothing but movements of letters to the (empty) "L" field. Using an IDA* search with the manhattan heuristics for the 15 Puzzle, m...

No, you may not use a grid cell twice. At least I got AC with that assumption.