Olayinka
Olayinka

Another coder in a pool of coders.

1.  … and for the first time in hundreds of years, the night comes alive with the music of dragons. — GRRM, AGoT

2.  My brother is undoubtedly arrogant. My father is the soul of avarice, and my sweet sister Cersei lusts for power with every waking breath. I, however, am innocent as a little lamb. Shall I bleat for you? — Tyrion Lannister

3.  Whatever you may believe of me, Lady Stark, I promise you this – I never bet against my family. — Tyrion Lannister From Tyrion’s POV, this could be another way to imply that a Lannister always pays his debt. A Lannister always finishes what he starts. Or he could be stating that he is unquestionably loyal to his family.

4. ### The purple story.

Before you go any further, be warned; this is a bragging post!

I wanted this to sound like “The Purple Wedding”, but I couldn’t pull it off.

Codeforces #$259$ Div$2$ held today and I have to say, it was fun, at least for me. It was a Chinese round, there have been a lot of that recently. Chinese rounds are always interesting, most of the problems are Maths problems that require more thinking than coding. And it was the case in this round. There were five problems in Div $2$ as usual and I managed to solve three this time around. This is only the second time where I solved three problems (A, B and C).

5.  Every flight begins with a fall. — GRRM

6. ### There are different kinds of wings.

#### An excerpt from A Song of Ice and Fire; A Game of Thrones.

The crow landed on his hand and began to eat.

“Are you really a crow?” Bran asked.

Are you really falling? the crow asked back.

“It’s just a dream,” Bran said.

“I’ll wake up when I hit the ground,” Bran told the bird.

You’ll die when you hit the ground, the crow said. It went back to eating corn.

Bran looked down. He could see mountains now, their peaks white with snow, and the silver thread of rivers in dark woods. He closed his eyes and began to cry.

That won’t do any good, the crow said. I told you, the answer is flying, not crying. How hard can it be? I’m doing it. The crow took to the air and flapped around Bran’s hand.

“You have wings,” Bran pointed out.

Maybe you do too.

Bran felt along his shoulders, groping for feathers.

There are different kinds of wings, the crow said.

7. ### An unpleasant experience with UVA (10137 - The Trip)

So I’m starting Programming Challenges to prepare for the upcoming ACM-MCPC. I figured between the summer heat and the internship I’m doing, the little I could give in is solve as many problem as time permits me.

The third problem in the book, UVA 10137 - The Trip, unexpectedly, gave me a hard time.

A group of friends who obviously weren’t sitting at home coding decided to take a trip. These guys don’t like discussing money, yet they hate being cheated so when any expense arises, one of them decides to handle it. At the end of the trip, they decided to face their fears and discuss money after all none of them likes being cheated. This may not make any sense but they somehow reduced their problem to finding the minimum amount of money that must be exchanged withing the group to distribute the total expenses amongst themselves but under the constraint that no one spends not more than $1$ cent than the other.

8. 25 posts!

9.  To see the world, things dangerous to come to, to see behind walls, draw closer, to find each other, and to feel. That is the purpose of life. — Walter Mitty, The Secret Life Of Walter Mitty

10.  Remember this, boy. All dwarfs may be bastards, yet not all bastards need be dwarfs. — Tyrion Lannister, A Game of Thrones

11.  Let me give you some counsel, bastard,” Lannister said. “Never forget what you are, for surely the world will not. Make it your strength. Then it can never be your weakness. Armor yourself in it, and it will never be used to hurt you. — Tyrion Lannister, A Game of Thrones

12. ### Linear Diophantine Equation

Simply put, a Diophantine Equation is a polynmial equation with at least two unknown variables. When the maximum power is $1$ and each term involves at most one unknown then we talk about a Linear Diophantine Equation.

Talking about the Knapsack problem, more specifically, the unbounded Knapsack problem got me thinking. The solution to the unbounded Knapsack problem is just an optimization of the positive solutions to a linear Diophantine equation defined as follows $$\sum^{n}_{i = 1} a_i w_i = W$$ And of course, all variables are positive integers, the weights are $w_i$ and the Knapsack capacity is $W$. In other words, what is required is to find $$\max _ {a \in A} \left ( \sum^{n}_{i = 1} a_i \right )$$ assuming $a = (a_i)_{1\le i \le n}$ and $A$ is the set of all possible solutions and the value of each item is $1$.

13.  Bran thought about it. “Can a man still be brave if he’s afraid?” “That is the only time a man can be brave,” his father told him. — A Game of Thrones

### The Unbounded knapsack problem

This one is a lot simpler than the $0$-$1$ knapsack problem. With this one you have unlimited resources but your knapsack capacity is still limited. The solution is quite similar to the previous one. Given $n$ items, unlike the previous one where we have two paths, here we have $n$ paths. That is if $m_w$ is the maximum value that can be obtained for a knapsack of capacity $w$ then it follows that \begin{align} m_0 &= 0 \\ m_w &=\max_{1\le w \le W}(m_{w-w_i} + v_i) \end{align}

Sorry, no implementation for this one, it’s pretty basic.

15. ### Dynamic Programming $#6$ - The Knapsack Problems $#1$

Probably the most common DP problem is the Knapsack problem.

You’re a thief, you walk into a market with the purpose of stealing some potatoes. Each potato has a value $v_i$ and weight $w_i$. Note that there may be no correlation between the weight and value of each potato. You have a knapsack that has a weight limit $W$, i.e. your sack can take as much $W\text{ kg}$ of potatoes. As a thief your aim is to take as many potatoes as possible that your sack can carry such that the total value is maximal. After all, the money is the most important. This is the classic Knapsack Problem.