Actually, the DP is all good, I think. Your better function is what's wrong.
public bool better( ArrayList a, ArrayList b ) { int N = Math.Min( a.Count, b.Count );
for ( int i = 0; i < N; i++ ) if ( (string) a[i] != (string) b[i] ) return ((string) a[i]).CompareTo((string) b[i]) < 0;
return a.Count < b.Count; } Shorter arraylists are better than longer ones. You are just looking at the lexicographical ordering, so you will favor splitting "aab" into "a" "a" "b" instead of "a" "ab".
Ya, you're looking at my submitted code, which for some reason passes the silly tests, and also it didn't register in my mind. (Hence the really stupid mistake part)
But ya, there is a bug in the code I posted - it's subtle, and it's actually the second time I've done something similar in a TC contest.. I spent about 10-15 minutes finding and correcting this bug that I get the "now it works!" and submit without double checking some stuff, which led to overlooking the really stupid mistake..
Comments 2
public bool better( ArrayList a, ArrayList b ) {
int N = Math.Min( a.Count, b.Count );
for ( int i = 0; i < N; i++ )
if ( (string) a[i] != (string) b[i] )
return ((string) a[i]).CompareTo((string) b[i]) < 0;
return a.Count < b.Count;
}
Shorter arraylists are better than longer ones. You are just looking at the lexicographical ordering, so you will favor splitting "aab" into "a" "a" "b" instead of "a" "ab".
Reply
But ya, there is a bug in the code I posted - it's subtle, and it's actually the second time I've done something similar in a TC contest.. I spent about 10-15 minutes finding and correcting this bug that I get the "now it works!" and submit without double checking some stuff, which led to overlooking the really stupid mistake..
Reply
Leave a comment