Algorithms

Viktor Grabarchuk wrote:

I just want to find some people who might solve this task earlier.

Bastard Programmer from Hell
If you can't read my code, try converting it here[^]

Chaitanya Pai wrote:

I have tried a lot to arrive at the solution.

1. [Preparation] Sort the strings representing the first ticket in each book in ascending order:
   a. zero-pad any short strings (e.g. "ABC1" should be padded to "00ABC1"
   b. sort the strings using a case-insensitive sort
   c. pad the list with a dummy ending value (e.g. "ZZZZZZ").
   d. pad the list with a dummy starting value (e.g. "000000").
2. [Eliminate low values] Use a binary search to find the location of largest value less than or equal to the target string. If the result points to the starting dummy value, then no such value exists.
3. [Eliminate high values] Use a binary search to find the location of the smallest value larger than the target string. If the result points to the ending dummy value, then no such value exists.

   IsInBetween( "A0ZWS0A" );
   IsInBetween( "A0ZWS0P" );
   IsInBetween( "A0ZWS7P" );
   IsInBetween( "A0ZWSAP" );

private static void IsInBetween( string value ) {

   string s1 = "A0ZWS0P";
   string s2 = "A0ZWS9P";

   bool isInbetween =
      value.CompareTo( s1 ) == 0 ||
      value.CompareTo( s2 ) == 0 ||
      ( value.CompareTo( s1 ) > 0 && value.CompareTo( s2 ) < 0 );

   Console.WriteLine( "Is {0} between {1} {2}? {3}", value, s1, s2, isInbetween );
}

bool isInbetween = ( value.CompareTo( s1 ) >= 0 && value.CompareTo( s2 ) <= 0 );

long long GenRadVal(char *str, int base)
{
	if (base<2 || base>36)
		return 0LL;

	long long val = 0;

	for (int i = 0; str[i]; i++)
	{
		int c = toupper(str[i]);
		if ((c < 0) || ((c > '9') && (c < 'A')) || (c > 'Z'))
			break;
		c =  c > '9' ? c - 'A' + 10 : c - '0';
		if (c >= base)
			break;
		val *= base;
		val +=  c;
	}
	return val;
}

static long Parse36(string s)
{
  long v = 0;
  foreach(char c in s)
  {
    char uc = char.ToUpper(c);
    bool isDigit = ('0' <= uc && uc <= '9');
    if (!(isDigit || ('A' <= uc && uc <= 'Z')))
      throw new FormatException();
    int d = uc - (isDigit ? '0' : ('A' - 10));
    v = v * 36 + d;
  }
  return v;
}