I am not a big fan of programming competions, but i do love good challenges and interesting problems. Google Code Jam (https://code.google.com/codejam/) is comming soon and i decide to participate in a normal way. I am not that hardcore programmer 24/7.
- File Fix-It: The problem consisted on on telling the minimum number of mkdirs (it creates folders one by one) to create the given directories. In each case was given the already done directories and the ones we needed to create. Creating directories can be viewed as building a tree. I simulated that using a dictonary.
#!/usr/bin/python # -*- coding: utf-8 -*- from sys import stdin def add_directory(directory_hash, path, done): directory = '' created_directories = 0 for node in path.split('/')[1:]: directory += '/' + node if not directory_hash.has_key(directory): directory_hash[directory] = True created_directories += 1 return 0 if done else created_directories if __name__ == "__main__": ncases = int(stdin.readline()) for ncase in xrange(ncases): case = stdin.readline() done_nodes, left_nodes = map(int, case.split(' ')) directory_hash = dict() for done_node in xrange(done_nodes): add_directory(directory_hash, stdin.readline().replace('\n',''), True) created_directories = 0 for left_node in xrange(left_nodes): created_directories += add_directory(directory_hash, stdin.readline().replace('\n',''), False) print 'Case #' + str(ncase + 1) + ': ' + str(created_directories)
- All Your Base: A little more complicated problem. The input was an alphanumeric string and the output a mapping each symbol of it to de minimum number, in any base, expresed as a decimal. The minimum base was 2 and the first symbol can’t be 0. The solution was quite simple, map the first symbol to 1, after that, map from left to right each diferent symbol to 0, then 2, then 3 and so on. Finally change the number to base 10.
#!/usr/bin/python # -*- coding: utf-8 -*- from sys import stdin if __name__ == "__main__": ncases = int(stdin.readline()) for ncase in xrange(ncases): case = stdin.readline() mapped_number = 0 symbol_number = dict() symbol_number[case] = 1 for symbol in case[1:-1]: if not symbol_number.has_key(symbol): symbol_number[symbol] = mapped_number mapped_number = 2 if mapped_number == 0 else mapped_number + 1 if mapped_number == 0: symbol_number[case] = 1 case.replace(case, '1') mapped_number = 2 to_pow = len(case) - 3 result_decimal = 1 * pow(mapped_number, to_pow + 1) for symbol in case[1:-1]: result_decimal += (pow(mapped_number, to_pow) * symbol_number[symbol]) to_pow -= 1 print 'Case #' + str(ncase + 1) + ': ' + str(result_decimal)
Both handled the large inputs and are quite efficient. The teaching here is that before doing any code is important to reason how to solve the problem.
Lets see how i perform in the Code Jam :3.