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.