Just stopped by quickly to say that may not be able to post during this week… finishing projects at work, so, that means long hours and a tight schedule. But I’ll be fine. I sincerely hope there’s pizza for dinner. ðŸ™‚ baba

# Monthly Archives: September 2013

# Difficult CodeJam problem and Free Software Documentary

Well, it’s been a tough weekend. Many new things were installed at home, lots of drilling and weightlifting (oh my arms…) but feels nicer after all. ðŸ™‚ More places for the kittens to hide.

That said, I’m evolving on Africa 2010 CodeJam D problem, but as soon as I get closer to solving, another challenge appears. This time, I’m having trouble finding an heuristic to determine the right choice to make, of all the results. Perhaps I’m still getting many results and not comparing correctly to the “solved group” list. I’ll for sure find out eventually.

Also, watched InProprietario, a brazilian documentary on free software (lots of Stallman) and, beside being very crude on effects, they used some nice movie references to cleverly show some software concepts. If you can understand portuguese and would like to know more about Free Software, I highly recommend it. ðŸ™‚

# Code Jam 2010 Africa â€“ Problem C

Whoa, that was a tough problem. Ironically it’s called Qualification Round:

You’ve just advancedfrom the Qualification Round of Google Code Jam Africa 2010, and youwant to know how many of your fellow contestants advancedwith you. To give yourself a challenge, you’ve decided only tolook at how many people solved each problem.The Qualification Round consisted ofÂ

PÂ problems; the i^{th}Â problem was fully solved byÂScontestants. Contestants_{iÂ }had to solveÂ CÂ problems in order to advanceto the next round. Your job is tofigure out, using only that information,the maximum number of contestants who could have advanced.

Well, at first it seems pretty simple, but there is quite some math involved. The first case of the example input is easy to solve, but the second will most likely get you scratching your head thinking “where the #$%* that number came from” (at least I did). ðŸ™‚ Well the secret is that you should not look at the inputs as they are, but instead, find the maximum amount of solved problem combinations there are.

I studied a bit but still could not solve it, and surrendered by checking the contest analysis. It was quite complicated to understand, until they wrote about a clever solution from the winning candidate: it consisted in lowering the possible scores to max at the division of the scores by the amount of needed problems. Just do it (don’t ask why) until there are no scores over the result of that division. That same result will be the answer. Creepy! Python code time:

for case in range(1,int(raw_input())+1): # For all test cases info = map(int, raw_input().split(" ")) # Get test case information problems = info[0] # Fetch number of problems needed = info[1] # Fetch number of needed problems to pass results = info[2:] # Fetch results for each problem qualified = 0 # Initialize our results if (problems == needed): # For this case, we can expect results.sort() # as many contestants as the qualified = results[len(results)-needed] # least solved problem else: # For this case, we use a solution out = False # similar to the winning one while not out: out = True qualified = sum(results)/needed # Reduce the number of possible qualifiers for i in range(len(results)): # And for all results if results[i] > qualified: # Limit their values to the current qualifiers results[i] = qualified out = False # Until they all "match" the qualifiers number print "Case #%d: %s" % (case, str(qualified)) # Report results

Interestingly enough, this code is smaller than the last, and solves a more complicated problem (at least in my opinion). I don’t think I could have done a better job on this one. ðŸ™‚ That’s the beauty in learning!

# CodeJam Quickie: 2010 Africa â€“ Problem B

Howdy! This time, problems started getting more and more complex, and that’s good, because I like the challenge! The next problem is Get to Work:

You work for a company that hasÂ

EÂ employees working in townÂ T. There areÂNÂ towns in the areawhere the employees live. You want to ensure that everyone will be able to make it to work.Some of the employees are driversand can driveÂPÂ passengers. Acapacity ofÂto work. You want to`P == 1`

Â indicates that the driver can only transport themselvesensure that everyone will be able to make itto work and you would like tominimize the number of carson the road.You want to calculate the number of cars on the road, with these requirements:

- Every employee can get to townÂ
T.- The only way an employee may travel between towns is in a car belonging to an employee.
- Employees can only take rides from other employees that live in the same town.
- The minimum number of cars is used.
Find whether it is possible for everyone to make it to work, and if it is, how many cars will end up driving to the office.

Whoa, that’s way more complex than the other problems, but still, not that hard! What we need to do is: check who are drivers and passengers for each town (since they can only help same town buddies), if the total capacity of cars from a town is inferior to the number of passengers, the problem cannot be solved and so, reported as “IMPOSSIBLE”. If we can carry everyone, start filling the cars from the “minivan” (can carry more passengers) to the “mini cooper”. ðŸ˜€ That way we can make sure there are fewer cars on the road.

Some rough, but commented, and validated (!) python code follows:

for case in range(1,int(raw_input())+1): # For all test cases town_len, office = map(int, raw_input().split(" ")) # Get amount of towns and office carriers = [[] for x in xrange(town_len)] # Create new lists for every town capacities = town_len * [0] # Initialize "capacity of transportation" payload = town_len * [0] # Initialize "cargo" for each town for i in range(int(raw_input())): # Get and go through employee list town, capacity = map(int, raw_input().split(" ")) # Get the current employee info if town == office: # If employee is from office town continue # No need to commute, ignore town -= 1 # Adjust "town" to zero-based index payload[town] += 1 # Employee needs to commute, count if capacity != 0: # If employee has a car capacities[town] += capacity # Add to our capacities for the town carriers[town].append(capacity) # Append its car capacity resultStr = "" # Create our result string for i in range(town_len): # For all towns if capacities[i] < payload[i]: # If we can't carry everyone resultStr = "IMPOSSIBLE " # declare it impossible, give up break; cars = 0 # We can carry, start with 0 cars carriers[i].sort() # Sort and reverse the car list carriers[i].reverse() for car in carriers[i]: # So we can start from the bigger ones if (payload[i] <= 0): # If we're carrying everybody already break # we're done for this town payload[i] -= car # Else, fill a car, report as being used cars += 1 resultStr += str(cars)+" " # Add this town filled vehicles print "Case #%d: %s" % (case, resultStr[:-1]) # Report results, remove last space

As the last problem, the same can be told about this code. There are many ways to improve its performance, but this way it can already solve the large inputs in an instant. Bitbangers apart, it solves the problem and everybody gets happy. Also, I think it is quite clear to understand, even more with the comments. ðŸ™‚ Bye!

# CodeJam Quickie: 2010 Africa â€“ Problem A

Hey there! So, another day, another problem! This time, it is calledÂ Odd Man Out, and it is quite simple to “get”:

You are hosting a party withÂ

and notice that`G`

Â gueststhere is an odd numberof guests! When planning the party you deliberately invitedonly couplesand gave each couple a unique numberÂ`C`

Â on their invitation. You would like tosingle out whoever came aloneby asking all of the guests for their invitation numbers.

Well, just get the number that’s not duplicated! There are many ways to do this, be it counting the occurrences of every member of the list and finding the “odd man”, or the way I did, which is basically some push and pop into a new list. Python code follows:

for case in range(1,int(raw_input())+1): # For all test cases raw_input() # Discard the guest list size guests = raw_input().split(" ") # Get the list of guest IDs guestList = [] # Create an empty guest list for guest in guests: # For all guests if guestList.count(guest) > 0: # If it's already on the final list guestList.remove(guest) # if is a couple, remove else: # If it's not in the list yet guestList.append(guest) # Add its ID print "Case #%d: %s" % (case, guestList[0]) # Reports results

Needless to say, I bet there are many ways to improve this algorithm, but for this problem it performs decently, so no worries (unless you’re a hardcore bit banger). ðŸ™‚ See you tomorrow!

# CodeJam Quickie: 2010 Africa â€“ Qualification C

Whoa! Keeping up with the Africa 2010 contest, enter the Qualification C problem:Â T9 Spelling! It was a very fun problem and says:

The Latin alphabet contains

26 characters and telephones only have ten digitson the keypad. We would like to make it easier towrite a messageto your friendusing a sequence of keypressesto indicate the desired characters. Theletters are mapped onto the digitsas shown below. To insert the characterÂ`B`

Â for instance, the program would pressÂ`22`

. In order to inserttwo characters in sequence from the same key, the usermust pausebefore pressing the key a second time. The space characterÂ. For example,Â`' '`

Â should be printed to indicate a pause`2 2`

Â indicatesÂ`AA`

Â whereasÂ`22`

Â indicatesÂ`B`

.

Reminds me of those days of texting through that old indestructible Nokias! Anyway, it’s not hard to do, but requires some data disposition. I chose to create a map to lists containing keys and the amount of keystrokes for every letter (including space, which would be 0), in order to simply match letters and print the sequence right along. Also, to know when to pause, I would check the last printed character before, so I can print a space and then the sequence.

Python code followsas usual:

# Build a map with the number to write and its repetition count t9 = { "a" : ["2", 1], "b" : ["2", 2], "c": ["2", 3], "d" : ["3", 1], "e" : ["3", 2], "f": ["3", 3], "g" : ["4", 1], "h" : ["4", 2], "i": ["4", 3], "j" : ["5", 1], "k" : ["5", 2], "l": ["5", 3], "m" : ["6", 1], "n" : ["6", 2], "o": ["6", 3], "p" : ["7", 1], "q" : ["7", 2], "r": ["7", 3], "s": ["7", 4], "t" : ["8", 1], "u" : ["8", 2], "v": ["8", 3], "w" : ["9", 1], "x" : ["9", 2], "y": ["9", 3], "z": ["9", 4], " " : ["0", 1], } for case in range(1,int(raw_input())+1): # For all test cases message = raw_input() # Get the list of words attr = t9[message[0]] # Start with the first character t9str = attr[0]*attr[1] # Initialize t9str with first T9 "word" for i in range(1,len(message)): # From the second character on attr = t9[message[i]] # Get the map values if t9str[-1] == attr[0]: # If it's the same number as the last t9str += " " # Add a space t9str = t9str+attr[0]*attr[1] # Append the new T9 "word" print "Case #%d: %s" % (case, t9str) # Reports results

It was the hardest of the Qualification problems, but still very easy to develop. ðŸ™‚ Fun! See ya tomorrow!

# CodeJam Real Quickie: 2010 Africa â€“ Qualification B

Hello there! Well, I can’t say anything about this problem other than it’s just super easy. Allow me to show you:

Given a list of space separated words, reverse the order of the words.

If that first sentence didn’t kill it for you, I don’t know what will. Anyway, the python code (validated, of course):Â

for case in range(1,int(raw_input())+1): # For all test cases words = raw_input().split(" ") # Get the list of words words.reverse() # Reverse word list print "Case #%d: %s" % (case, " ".join(words)) # Reports results, add spaces

Can’t get easier than that. And I actually had to learn that reverse() does not return the reversed list… in a perfect world, it could be solved within the print line, with:

" ".join(raw_input().split(" ").reverse())

But, maybe next time… ðŸ˜€ See ya, warned you it was real quick!