Top Mobile App Design Mistakes

Note: This is a summary of an article by Kent Mundle on Toptal.

With tons of app rolling out each week, it is unlikely that your app will get any attention at all. To help your app stand out, here are some insights from seasoned app designers.

Poor first impression

Apps with no instruction, bare apps that looks like it’s designed a decade ago. Before we even figure out how the app works, we will be so annoyed we return to the appstore to look for less confusing alternatives. Here are some reasons for the frustration.

Improper Onboarding

Tailor to the needs of your users. Many “on the go” apps make the mistake of having a very tedious onboarding process. Don’t waste your users’ time. Don’t hinder them from using your app. Think progressive disclosure.

App without purpose

Many apps don’t even serve a purpose. Instead of solving problems, they are designed to follow trends. Once the novelty wears off, they are removed by your users.

Have a clear purpose for your app, and tailor the experience as so. Avoid features that do not align with the purpose. Make your app useful.

Dismissing app context

Use cases help define the purpose of your app. Have clear use cases for your app. Design all your features around these few use cases.

Example: Uber is designed to be very minimal, and excels at being used for quickly. This fits the purpose of the app — to serve the users when they are out with their friends. The unobstructive interface design helps the app fulfill its purpose without distraction.

Disregarding the development budget

After you get a rough idea of how your app will look like, approach the developers for a budget. Your developers are the one doing the work, they should be the one giving the estimates.

If you run out of budget too early, you will end up cutting critical features. Pioritize which features you need the most. Act within budget.

Cramming in features

Many apps try to do too much at a time, turning the app into an ultimate swiss army knife. The overwhelming features list makes your app difficult to learn. The best strategy is to beginning with a few features, then test out new features in the future.

Overcomplicating app design

When a designer finds themselves adding things to make the design more appealing, chances are, these choice will just result in a very cluttered design.

Instead of designing additively, design reductively. This method is directed as much towards content, concept and function as it is aesthetics.

Aim to fit the required content without cluttering the screen. Don’t let the design get into the way of your content.

Instead of designing addictively, design reductively.

Under utilizing app beta testing

All designers test their apps in some way or another. Very often, the beta testing is done in house. But you need a fresh set of eyes to review your work. Send out an ad and work with a selected group of audience to iron out the details, find out what’s missing.

Anticipate that the testing will often take 8 weeks to do properly. Give the process enough time in order to collect the quality feedback that your app design needs.

And so?

The app design market is a battleground, designing adequate products is not enough. Hook your users from the beginning – communicate and demonstrate the value your app brings.

Most of these revolves around having a clear idea of what your application is about. So, refine and refine until absolutely nothing else can be taken away without the project falling apart.

Explanation – How computers draw curves

In illustrations, lines and curves are the most basic components that will eventually form up everything that we see designed today. Well, straight lines are rather simple, get two points, and fill in whatever is in the middle.

Curves are different. Computers draw curves using the “cubic bezier curve” (yeah, its abit math-sy, I know, but it makes sense when you see it graphically). The video I found explains the bezier curve really really well. Have a look and be in awe of the wonders of maths (and computers).

Kudos to Peter Nowell for the video

There are more to bezier curves that just that. To form even more complex curves, there are curves of even higher power. It isn’t really easy to explain, and there is all these maths equations that I will have to get into and it will look really really message (plus, its not something I fully understand)

To prevent explaining it wrongly, I will just skip that part and show you the animation for generating curves of different powers. If you are really interested and looking for something to help you sleep, you can read the math parts here.

Quadratic bezier curve (simpler version of cubic)

Cubic bezier curve (we saw this just now)

Quartic bezier curve (fourth order)

Fifth order bezier curve (really really cool, but messy)

Basically, the idea is to keep connecting the different points to form different line segments, until you get the tangent to generate the points for the curve. That is as simple an explanation I can give for now. But when I eventually figure out how to explan the math formulaes in human terms, I will make another explanation post.

How I learnt basic morse in 3 days

In cheaper by the dozen, it was mentioned in one of the childhood stories that her father managed to teach morse to kids over a short span of an holiday.

Then I thought to myself, considering my age and my access to technology, I could probably be able to do it in a week, could I?

Starting with the trick

The method used in the story was to use phrases to help memorize the dots and dashes of the alphabets, using the emphasis of certain syllabus as hints.

The first few of the alphabets were given in the book, I went online and googled the rest. I settled on this list that I found on wikipedia.

I read through them a few times. It wasn’t really to memmorize it, more of trying to get the phrases in my head.

Testing it out

Armed with the knowledge, I went online to search for a morse training app. You could probably download any of them, I think it doesn’t really make much difference if the funtionalities are the same.

I downloaded the morse trainer, and tried out the transmission mode. I tried to transmit some words, I couldn’t really get the hang of it, I was too slow, the pause makes the app thinks that I am between words, I couldn’t continue.

Getting hang of tapping morse

This isn’t the way to go. I went on to the freepad mode and tried to enter some words. There was a guide in the app. Apparently, between letters the pause should be the length of a dot, and between words, the length of a dash.

I practice really hard. And after a while, I got the hang of it. The trick was to type the letters and say it out at the same time. Somehow, you will insert that pause automatically. But lets say you are pausing too long and the spaces keeps appearing, You can try saying out the letter faster. Similiarly, if your tapping are all jumbled up, you can slow down the recitation to get the right speed.

How do I push this to the extreme? When practicing in the word mode, I switched off the sound and looked away while tapping out the code. I find that this helps me grasp the momentum better as I learn not to rely on the use of audio and visual feedback.

Memorising the alphabets

It finally the main part. I still remember my first word – “elements”. When I was training the tapping, I wrote out this word in morse (with the appropriate spaces) and tried tapping it out. After trying out for really long, I found that I memorise morse best in the visual form.

What do I mean visual form? It means that I memorize the alphabets in blocks. Take “L” for example. Initially, I used the phrase method, so I have got “he LOST his lid”, which translate to “._..”.

After a while I realized that when I actually tried to recall “L”, the block of dots and dashes came to me really quickly. So when I got “L”, the image “._..” just came very quickly to me. For me that seemed like a shortcut.

This works for the more common letters such as “E”, “T”, “L”, “Y”, etc. Interesting these patterns are opposite pairs, which means that exchanging dots for dashes, you get “T” from “E” and “Y” from “L”. Maybe that’s why it was easier for me to imagine it as blocks.

For the rest, I still use the phrases. For example, “G” for “GOO GLE ad”, “V” for “vic to ry Vee”. These are the less common letters, so the phrase still prove to be a great help, especially if the phrase jumps up to you very quickly. (tip: choose a weird and memorable phrase)

But after tapping morse for a long time, I suspect that it will be very easy to imagine the letters of blocks of dots and dashes. Take “R” for example. I learnt it as “ro TA tion”, but now when I encounter it in my tapping, the block of “._.” jumps up to me immediately.

Results

After 2 days of practicing, I am proud to say that I have some basic mastery of morse code. Without refering to any sheet of information, I can type out the words with relative accuracy (except for the occasional pausing too long problems) without any form of feedback (audio or visual).

I took 10 tries to tap out 10 words
score for morse tapping

Now that I am suffuciently capable of transmitting morse, I will be moving on to receiving morse and decoding it in real time. The practice mode in the app does not really provide a very good practice (I feel), as it does not use real words. I will find another way to hone my morse receiving skills before reporting any results.

Conclusion

Over the short span of 3 days, I have learnt to transmit morse. That might be long for some people, but I feel that being able to reach such level of efficiency is rather commendable.

But to be fair, I had a lot of time to practice, and didn’t have much other things to distract me from my learning.

So, if you are wondering if you can spend a weekend learning morse, no worries, start today and you will be tapping morse in no time.

Explaining Gray Code

Introduction

I have known binary code for sometime now, the basics at least, how they are formed, what values they represent. But recently, I have came across a different kind of binary code.

Here, I am going give a brief explaination how the Gray code works, and what’s so special about it.

Basic introduction

So how you tell the value of a Gray code? Actually, there is no simple way, at least, its not as simple as a binary system, where you can count like “this is 2 to the power of 1, this is 2 to the power of 2”.

Instead, for Gray code, to get the values, you will need to have a table of values to refer to. But getting the table is really not that hard.

Understanding the values

Let me give an example of Gray code works. To do that first let me show you a table of what the Gray code values are.

Table for Gray code

Decimal Gray Code
0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 100

Seen that already? For each consecutive values, like from 0 to 1 or 1 to 2, there is only one bit flip. To make it easier to see, I have highlighted the changed bits to make it more obvious.

But what about the binary code? I have placed the Gray code and typical binary code side by side so you can see the difference in the pattern. For binary code, to jump one value, it might not just have one flipped bit. (Take 1 to 2 for example, you have to “off” the first bit and “on” the second bit)

Bold refers to changed bits

Decimal Gray Code Binary Code
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110
7 100 111

So how do I generate it?

So how do I generate Gray code for values beyond the table? Here’s an example. Let’s say the table is only has 4 values (0 to 3). So how do I go about getting the Gray code for the following values?

To understand how the system works, first follow this flow of logic – assuming that all the Gray code for the previous values are valid (meaning that it take only one bit flip to increment or decrement the value), if we reverse the whole block of code, then the rule will still apply. Let’s pause here and see what we get.

So, here is what we’ll get after the first step.

values step 1
0 00
1 01
2 11
3 10
4 10
5 11
6 01
7 00

So as you can see, the pattern here is as so, the Gray code for the numbers are reversed and placed for the the next set of values. Meaning the pattern for 0 and 7 will match, so does 1 and 6, so on, until we get to 3 and 4.

So how do we tell them apart, the 2 corresponding values? It’s all in the second step. For the actual set of values, we prepend a 0 at the front, and for the second set where we reverse the values, we prepend a 1 at the front.

There we have it, the Gray code for the first 8 values (0 to 7).

values step 1 step 2
0 00 000
1 01 001
2 11 011
3 10 010
4 10 110
5 11 111
6 01 101
7 00 100

Why is there a need for Gray code

In the past, when computers are all mechanical switches, it made sense to have as little bit flip between increment and decrement, since more bit flip equates to more chances of error.

Also, because of the way some of the mechanical hardware are designed, its easier to use a value table that only have one bit flip for increment and decrement.

If you want to learn more about the system that uses Gray code, you can go here.

How to convert between Gray code and binary

Well, is there a simple way of converting Gray code to binary? Of course, after all, there is a pattern to these things.

This is a piece of python code written by joshua, it uses the “bitwise exclusive or” operator to do the conversion.

The xor operator is a different topic altogether and I am not going to cover it here. But those interested can go read more about it here and uncover the pattern for yourselves.

def gray2binary(gray):
    binary = gray[0]
    i = 0

    while(len(gray)>i+1):
        # the xor operator
        binary += `int(binary[i] ^ int(gray[i+1]))`

Learn more about other kinds of Gray code

What about other arrangment of code that give rise to patterns where increments are one bit flip apart?

Well, this particular type of Gray code that we have discussed here is known as the “binary reversed Gray code”. (after reading so far, I hope you know the reason why)

There are other types of binary Gray code too, there is the balanced Gray code to make the transition between values more uniform and the pattern more balanced. They are other types of binary Gray code too, you can have a look at them out here.

There are Gray code in other number systems too. I mean, you can extend the reverse system idea into other number systems (base-3, base-4, etc). You can see how to adapt the idea here.

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.

Explaining 2016 Codejam round 1A

This post is going to explain how I got my answers for codejam round 1A. Hopefully, I will be able to continue writing these posts as the 2016 codejam competition furthers. But that have to depend on whether I will be able to answer the questions.

Yes, I know that Google does provide its own question analysis (it’s available here). So why do I write it, repeat it again?

Google’s answers are writtne by expert coders who have a wealth of experience writing algorithms, thinking of solutions. Most that are stuck on the problem are probably not. The little hints given might not be sufficient, hence, the tutorial.

Also partly for myself, in case I have forgotten how to solve it have couldn’t understand the analysis by Google.

Problem A

This problem is a very simple “step-by-step” problem, as long as you can figure out the method of generating the string, you can get the answer by adding characters to the string one by one.

The method goes like this: to get the largest possible string (alphabetically), process the characters one by one, if the character is larger than the character at the start of the answer, add it to the front, if not, add it to the back.

There really is not much in this, it is a pattern questions, as long as you can figure it out, the solution is easy to write.

Submission for small input

N = input()
for n in range(N):
    chars = raw_input()

    ans = chars[0]
    chars = chars[1:]

    for c in chars:
        if c>=ans[0]:
            ans = c+ans
        else:
            ans += c

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

Problem B

The second problem is actually very simple, but it is the question where I found that I am deeply dissapointed in myself. This is the problem where you have to determine the values of a missing row from a grid.

When I first started on the problem, I jumped in immediately and started working on the algorithm to find the correct order of the grid from the different pieces of information. But there was one part I overlooked — because of a few rules that are placed in the problem, there is a much much simpler answer to it.

This is the key rule: “all the row and columns must be in ascending order, from left to right, from top to bottom, with no repetition in each row or column”. From this rule, we can use the existing information from the grid to determine the missing numbers and the order it is in.

When you are in a grid, and you are required to record the sequence of the rows and columns, there a case of double counting, where each person is counted exactly twice. Since only one strip (either row or column) is missing, whatever number only appears an odd number of times, must be one of the missing number.

What if one of the row/columns have two of the same number? Doesn’t that mean that there will be an even number of occurance for that value? Well, that’s covered by the rules, “there is not repeated number in each row”.

What if we got the numbers, how do we arrange them? No problem, it’s also covered by the rules — “all sequences of the rows and columns must be in ascending order”.

success for small input

T = input()
for t in range(T):
    N = input()

    all = []
    for n in range(N*2 - 1):
        all += map(int, raw_input().strip().split())

    line = []
    for i in set(all):
        if all.count(i)%2: line.append(i)

    s = ' '.join(map(str, sorted(line)))
    print 'Case #%d: %s'%(t+1, s)

Problem C

This is one of the more classical problems, using graph as a model for the problem. To do this question, we will have to refer to a diagram for explaination. This is the diagram taken from Google’s codejam answer.

graph diagram

Try drawing a few graphs on your own. And you probably see how the friendship circle will work out. As explained in the analysis, the way to form the longest chain of amiable students sitting together is to make use of the students who mutually like each other.

But if the chain using the mutual liking students are too short, the only are option in forming a circle is to find the cycle with the longest cycle length. (eg. biggest loop), like in the first example.

So there is 2 parts to the solution. One, find the cycles in the graph. Two, Find the longest tail from the cycles with length of 2, 2 kids liking each other, then add up all of them together to form one big circle (just like in the picture, with the 2nd and 3rd part combined).

Okay, my solution for finding all the cycles in the graph might not be the most efficient, but it is definitely a method that works, and it works well within the time limit.

As for the second part when we need to find the tail, it is a depth first search for the longest link. Don’t get it? Basically we follow the data and start tracking back each chain, starting of the kid in the length-2 cycle. We will try all the combinations and then return the length of the tail which goes the deepest.

success

# current, data, not-to-be-counted
def longest(current, data, nocount): 
    nodes = [n for n in data[current[-1]] if nnocount]    
    if not nodes:
        return current

    max_line = []
    for n in nodes:
        temp = longest(current+[n], data, nocount)
        if len(max_line)<len(temp):
            max_line = temp
    return max_line

T = input()
for t in range(T):
    N = input()
    d = [int(i)-1 for i in raw_input().split()]

    c2 = []

    # normal cycle counting
    c_max = 0
    mv = range(N)
    while mv:
        c = [mv[0]]
        mv = mv[1:]

        while len(c)1][0]
        idx = c.index(start)
        c.remove(start)
        c_len = c.index(start) - idx + 1

        if c_max  m: m= c_max

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

Conclusion

The problems are solvable, but I do need sometime to write the solution and really think about the edge cases. I hope that 1B will be more lenient (although it is unlikely). And if I do understand and manage to get a solution, I will share them again when I get the writeup written.