Explaining codejam 1C

This round, 1C, is by far the easiest among the 3 rounds. I tried the questions and could figure out the general answer without having to refer to the analysis.

Problem A

This is a problem that has an obvious greedy solution. “Trying to remove everyone from the room without having more than half the people being in the same party”.

One of the first solution is to remove a guy from the party with the most people. And it makes sense, since we are removing from the party with the most member, there wouldn’t be a chance of other parties having a majority.

But what if there is only 2 parties left? Yes, this is one of the edge cases that the competition conviniently highlighted in their test case 2. If there is only 2 party left, then we must evacuate such that the two parties always have the same number of people.

Taking all that into consideration, here is the following code for the problem.

Problem B

At first glance, this problem looks like a typical graph question. I recalled the only graph algorithm I know – Dijkstra’s algorithm. That algorithms helps you count the shortest, or longest (if you want), path from one node to another.

Generating the vectors such that there is only a certain number of ways to get there. Sounds like reverse djistrak to me. I got to my drawing board and started to figure out how the counting would work.

Simplifying the question

First, lets take a look at what kind of criteria will result in a “IMPOSSIBLE” solution. And the hint is kindly stated in the test cases.

“It is possible to find a sequence with infinite ways, but its impossible to get EXACTLY 20 ways”. And how do you get infinite ways? Create a loop of course. So conclusion, there cannot be any loops.

If there cannot be any loops, there must be some kind of maximum M for each B. So what’s the maximum number for M?

To find that, we first have to figure out how to count the number of ways from 1 to B.

Figuring out the counting

So I started from test case 1, where there is 5 buildings (B==5), and we need exactly 4 methods (M==4).

And I started from the answer. So building 1 is connected to building 2 and 5. This means the total ways from 1 to 5 will be the (1 + ).

So we have something that looks like this:

building paths total
1 1, (2)
2 (3), (4)
3 1
4 1, (3)
5

And if we filled in from building 3 onwards, a little like Dijkstra, we get the following values (representing ways from that building to building 5):

building paths total
1 1, (2) 4
2 (3), (4) 3
3 1 1
4 1, (3) 2
5

And there it works, exactly 4 ways from building 1 to building 5.

Finding the maximum value

So using this method there must be some way I can generate the highest number of ways from 1 to 5.

Using the greedy approach, I created a configuration that promises maximum number of ways:

building paths total
1 1, (2), (3), (4)
2 1, (3), (4)
3 1, (4)
4 1
5

And filling up from building 4 to 1, we have the following values:

building paths total
1 1, (2), (3), (4) 8
2 1, (3), (4) 4
3 1, (4) 2
4 1 1
5

Eureka

Oh look, binary values. And yes, that’s the key to the solution.

Let’s rewrite the paths for building one a little, so instead of “1+++”, it becomes “1+4+2+1”.

And can be we get all the values by taking out certain bridges? As proof, I have compiled the list below:

value count sequence
1 1+0+0+0 00001
2 1+0+0+1 00011
3 1+0+2+0 00101
4 1+0+2+1 00111
5 1+4+0+0 01001
6 1+4+0+1 01011
7 1+4+2+0 01101
8 1+4+2+1 01111

There we have it. This solution means that the bridges of building 2, 3 and 4 will never need to change. But what about the configuration for building 1?

As inferred from the table above, the pattern for building 1 will follow this certain pattern: 0{binary format of (M-1)}1

And the maximum value of M? The last piece of the puzzle 2^(M-2).

Problem C

This problem is a permutation problem, so has to be some pattern to it. Intially, I used a greedy approach to generate the permutations, but it failed. After reading the analysis, I learnt that I found the “maximal” value, and not the “maximum”, kind of like a “local maxima”.

After pouring through all the math in the analysis, here I have a simplified and easy to understand version of the solution.

Before we start, we have to keep a very important limitation that they have given in mind – “J <= P <= S". This statement helps us avoid many problems as you can see later on.

Key to solution

Assuming the only restriction is that there is no repeat of full outfits (all 3 the same).

How many times have a certain jacket (j) and a certain pants (p) appeared together? Exactly S times. What about a certain pants (p) and certain shirt (s)? Exactly J times.

So which appears more times? The jacket-pants combo, or the pants-shirt combo? Of course the jacket-pants combo, since "J <= P <= S".

And this is conclusion 2, we only needs to care about the jacket-pants combo, because that will appear the most number of times.

Solving the simpler question

Let's return to the question with all the rules.

If there is a case where "SK”, it means that the jacket-pants combo can only appear only K times.

Assuming there is 4 kinds of shirts (S==4) and each combo can only appear 3 times (K==3).

And let’s set the number of pants as 3 (P==3). For the jacket, we just need to work on the pattern on 1 jacket, then copy the pattern for the rest of the jackets.

This is because when the jacket changes, everything resets, and all the jacket-pants combo will be different. What about the combo with the shirts? As discussed in conclusion 2, we don’t need to care about it. (Still don’t get it? Try out the steps below for “2 3 3 2” and “2 3 3 1” and see for yourselves).

What about the shirts? We need to generate the shirts for the jacket-pants combo. And this is a formula we use to ensure that the shirts are equally spread out.

For the k-th number of a certain jacket-pants combo, we allocated it to the shirt number which corresponds to ([j+p+k] % S)+1. The “%” (modulo) is to wrap the numbers, the “+1” is to align the shirt number back to the “start from 1” counting system.

Below is are the steps to generate the maximum pattern of outfits for “1 3 4 3” (J P S K).

jacket-pants combo shirt shirt calculation
J1 P1 S4 ((1+1+1)%4)+1
J1 P1 S1 ((1+1+2)%4)+1
J1 P1 S2 ((1+1+3)%4)+1
J1 P2 S1 ((2+1+1)%4)+1
J1 P2 S2 ((2+1+2)%4)+1
J1 P2 S3 ((2+1+3)%4)+1
J1 P3 S2 ((3+1+1)%4)+1
J1 P3 S3 ((3+1+2)%4)+1
J1 P3 S4 ((3+1+3)%4)+1

Let’s have a check, each jacket-pants combo (“J1 P1”, “J1 P2”, “J1 P3”) only appeared K (3) times.

And we are done, an algorithm to generate the maximum sets of outfit that doesn’t offend the fashion police.

Explaining codejam 1B

The problems for 1B were harder, I felt. I only got a rough idea of how to go about solving it, it took some time to really iron out the details.

As mentioned in the analysis, the questions were deceptively easy. There were many edges cases that were not immediately apparent. I didn’t manage to come to a full solution until after I read the analysis.

Problem A

This was no doubt the easiest among the 3 questions. The key to solving this realizing that there are unique letters in the spelling of the numbers.

After identifying the unique letters, we just have to remove the letters, number by number, store down the digits, then arrange them in ascending order (stated in question) to get our answer.

So how do we know which number goes first? We first determine the set of letters needed to spell the numbers. Then we fill in the blanks and delete accordingly.

Table with the letters

success

def rm(S, word):
    for c in word:
        S.remove(c)
    return S

T = input()
for t in range(T):
    S = list(raw_input().strip())
    nums = []

    while S.count('Z'):
        S = rm(S, 'ZERO')
        nums.append(0)
    while S.count('X'):
        S = rm(S, 'SIX')
        nums.append(6)
    while S.count('S'):
        S = rm(S, 'SEVEN')
        nums.append(7)
    while S.count('W'):
        S = rm(S, 'TWO')
        nums.append(2)
    while S.count('V'):
        S = rm(S, 'FIVE')
        nums.append(5)
    while S.count('F'):
        S = rm(S, 'FOUR')
        nums.append(4)
    while S.count('R'):
        S = rm(S, 'THREE')
        nums.append(3)
    while S.count('T'):
        S = rm(S, 'EIGHT')
        nums.append(8)
    while S.count('O'):
        S = rm(S, 'ONE')
        nums.append(1)
    while S.count('N'):
        S = rm(S, 'NINE')
        nums.append(9)

    s = ''.join(map(str, sorted(nums)))

    print 'Case #%d: %s'%(t+1, s)

Problem B

The second problem is the one about finding the lowest score. On the surface, it looks as though a greedy approach can be used, generating the values one by one from left to right.

But it took some time for me to realize that it is more of a “generate all possible values and find the best answer” kind of question.

To start off, all questions can be categorized into 3 main kinds.

Both same values
Problems in this category generally ends up with the answer where both values are the same. One such example will be “?6? ??9”, where the answer will end up to be “069 069”

One big one small
One way to minimize the difference is to maximize the smaller value by replacing all the “?” with “9” and minimize the larger value by replacing all “?” with “0”. Such as example will be “7?? 6
??”, which will give us the values “700 699”.

Transferring to a higher placing
The last method of minimizing the difference is to introduce a point of difference in the previous placing , this is done by making the next placing larger. One such example is “?0? ?9?”, which will give us the values “100 099”, where we introduced a value difference in the hundreds place.

The solution
So how do we go about generating the values? We will go through the string position by position, trying to implement one of the three methods of solving the problem.

So as we go along the string we will try to do the following:

  • make the two values the same
  • introduce a difference in the value by increasing or decreasing the value at that position
  • introduce a difference in the new placing by changing the unknown values to “0” and “1” then swapping them around.

After that we will store all the possible candidates and find the pairing with the smallest difference.

success

def fill(a, b):
    a, b = ''.join(a), ''.join(b)

    a = a.replace('?', '0' if a>b else '9')
    b = b.replace('?', '9' if a>b else '0')
    return [a, b]

T = input()
for t in range(T):
    a, b = map(list, raw_input().split())
    N = len(a)  

    f = []
    for i in range(N): 
        sub_a, sub_b = a[:i], b[:i]
        if sub_a <> sub_b: 
            f.append(fill(a, b))
            break

        if a[i]=='?' and b[i]=='?':
            a[i], b[i] = '1', '0'
            f.append(fill(a, b))

            a[i], b[i] = '0', '1'
            f.append(fill(a, b))

            a[i], b[i] = '0', '0'
        elif a[i]=='?' or b[i]=='?':
            c, d = a, b
            if b[i]=='?': c, d = b, a

            if d[i]<'9': c[i] = str(int(d[i])+1)
            f.append(fill(a, b))

            if d[i]>'0': c[i] = str(int(d[i])-1)
            f.append(fill(a, b))

            c[i] = d[i]

        if not (a+b).count('?'):
            f.append(fill(a, b))
            break

    min_val = None
    min_pair = None
    for pair in f:
        val = abs(int(pair[0])-int(pair[1]))
        pair = ' '.join(pair)

        if not min_val or val<min_val:
            min_val = val
            min_pair = pair
        elif val==min_val and (pair<min_pair or not min_pair):
            min_pair = pair

    print 'Case #%d: %s'%(t+1, min_pair)

Problem C

This last problem is the most deceptive one. I initially thought that a greedy approach would work fine, but there are far too many cases to consider.

After looking through the analysis, and seeing the bipartite graph, I have a rough idea of how to use the data structure to solve the problem.

Before I start, let’s have a short explanation of how a bipartite tree can be used to model the problem. Consider the list of these words:

  • HYDROCARBON COMBUSTION
  • BIOMASS COMBUSTION
  • QUAIL COMBUSTION
  • QUAIL BEHAVIOR
  • QUAIL CONTAMINATION
  • GROUNDWATER CONTAMINATION
  • GROUNDWATER HYDROLOGY

Treating all first words to be of a set and all the second words to be one set, we have the graph as follows, courtesy of codejam analysis.

bipartite graph of words

Flow of thinking
Ignore all the lines for the moment and take a step back. Finding the most number of fakes means to use as little titles as possible to cover all the words.

This means that we must use as little lines (or vectors, in graph terms) as possible to go through all the words (or nodes, in graph terms).

So here, we work backwards. We have a list of all the nodes that are present in both set, then eliminate them one by one as we choose the optimal vector that covers the most nodes.

We start off with the most obvious ones – the nodes with only one connection. Obviously that has to be the only word pair that can be legit.

After we run out of nodes with only one vector, we iterate through the leftovers and remove the optimal match (best if both nodes of the vector are not yet covered).

If you prefer a more technical way, you can always refer to the analysis for resources to the link to the full algorithm.

Review: The $100 Startup

This is a pretty good read for those who want to start something new. From idea generation to outlining your business, to getting your first customer, this book covers it all.

These are just of the notes that I have taken from the book. It is in no way conclusive or complete. For more information you can visit the accompanying website for more information.

Introducing tumblr pbot

Journaling can be difficult sometimes, you need to have your book with you, you are not sure where to start, you get distracted. These are problems faced by many of us.

Tumblr pBot helps you get started on your journaling in as little steps as possible. Just start typing and send it, and up or goes onto tumblr.

Want a private journal, no problem, just make your tumblr page private, and nobody will be able to access your private thoughts.

Want to review your entries? Since everything is uploaded onto tumblr, you can make use of tumblr post management system to review and read through all your entries.

Want to categorize your entries? Use tags. Tumblr’s tagging system is supported in the pBot. Simply add in the tags at the end of your posts and it will be immediately uploaded with tags attached.

Don’t know how to start? Even better. Using telecom’s text messaging interface makes it feels like you are typing to a friend, making it easier to pour out all you have to say.

Getting distracted from writing? pBot is as minimal as it gets, you can now focus on what you are writing. Since its so accessible, you can get in, pour out your thoughts, and get back to whatever you are doing.

Try it out now. Or visit the bot page.