Archive for the ‘Competitive Programming’ Category

Competitive Programming vs Software Programming

Wednesday, March 15th, 2017

This dilemma always comes up for those college students engrossed in learning programming. What to invest more of their time on? Software programming vis-a-vis competitive programming.

Let’s start by comparing the two.

What is Competitive programming?
Competitive programming is what most college students do to hone their algorithmic knowledge and mastery over various data structures. It not only improves problem solving capability but also augments a person’s speed and accuracy when solving such problems. Competitive programming is basically taking programming up as a sport. Participants are given a set amount of time to solve a number of complex algorithmic questions. It tests a person’s raw thinking capability and ability to grasp problems. It expects an extremely fast solution which need not be the simplest one possible.

What is Software programming?
Software programming is less of a perfect science, compared to the calculated laser precision of competitive programming. You are expected to solve real world problems, in a way that is simple, efficient and also easy to maintain. You are not expected to use complex algorithms to calculate the answer in milliseconds, but to write simple code which gets the job done in reasonable time. Software programming is the development of apps which run on mobile, PC and other platforms.

Now let’s get to the differences between the two :

Competitive Programming

  • The problem is solvable within the given time and constraints using the given resources
  • Short time commitment and instant gratification
  • Skill level is easily quantified

Software Programming

  • The problem “may” be solvable within the given time and constraints using the given resources
  • Long time commitment and gradual gratification
  • Skill level is not easily quantifiable

So which one should you do ?
There is no right answer to this question. Most interviews are composed of algorithmic questions but the actual job will entail more of software programming. So it is obviously healthy to have a good mix of both under your belt by the time you start job hunting, The ratio of that mix is left to you to figure out.

Happy Coding,
Karthikeyan M

Posted in Competitive Programming | No Comments »

Why do we code ?

Saturday, January 21st, 2017

For people, computer programming may mean many things. It could mean their livelihood, their passion, their meal ticket, their escape from reality, a path to a better life or maybe it’s all gibberish to them no matter how you put it. Yeah, people code for many reasons.

But, why do I code ?
Many people do take up competitive programming as it pretty much guarantees you a bigger package than your peers. But those people do not mind the tireless nights, the sleep deprived mania induced by bad logic, the bleary eyed mornings and the thankless hours of effort you put in to climb the leaderboards.

But for the rest of us who are allergic to menial labour and value our sleep over all else, we need something more enticing. Something which gives a greater high than any drug known to man, something which sets the endorphin rushing through your veins, something which causes us to forego our treasured sleep, late night DOTA games, food and social life.

All for that tiny green tick mark called the AC. Once you get your first taste of the “Accepted” sign, you’ll never be able to live without it again. Your body will crave it. You’ll dream about it. You’ll obsess over it like it is the single most important thing in your life. And it may very well be. It drives your very existence. It drives you to learn and re-learn. That is what motivates the best of us. We are coders, and we are all addicted to what we do.

Posted in Competitive Programming | No Comments »

SPOJ Classical Problem FARIDA Dynamic Programming Tutorial

Friday, December 16th, 2016

 

This will be an editorial of the FARIDA problem from SPOJ which is an basic dynamic programming problem. It is easily solved by knowing the initial states and the simple transition from previous states to the next ones.

This problem is from : http://www.spoj.com/problems/FARIDA/

Problem Statement:

Once upon time there was a cute princess called Farida living in a castle with her father, mother and uncle. On the way to the castle there lived many monsters. Each one of them had some gold coins. Although they are monsters they will not hurt. Instead they will give you the gold coins, but if and only if you didn’t take any coins from the monster directly before the current one. To marry princess Farida you have to pass all the monsters and collect as many coins as possible. Given the number of gold coins each monster has, calculate the maximum number of coins you can collect on your way to the castle.

This is the problem faced by FARIDA, a cute princess, many of you would have come across early in your adventure across dynamic programming kingdom. With an acceptance percentage of around 29%. This would be one of the easiest DP problems, but can lay the foundations to better understanding of DP states and their transition.

So, the problem basically reduces to :

Given an array, output the maximum sum of elements you can make from a subset of the array such that no two consecutive numbers from the original array are included in the subset.

Now, considering a DP[i] to be the maximum sum obtainable under such conditions till ‘i’ in the array. The DP transitions are intuitively derived as:
DP[i] = Maximum of ( DP[i – 1] ) &  ( DP[i] + element ‘i’ from the array )

If we decide not to include element ‘i’ the maximum obtainable sum up to ‘i’ will be DP[i – 1]. If we decide to include DP[i] then the maximum will be DP[i – 2] + Element ‘i’, since we cant include element ‘i – 1’ in this.
So you can see how the maximum of these two values will give us the general DP recurrence. Then, the initial states easily work out to be
DP[0] = First element in array
DP[1] = Maximum of first and second elements in array.

Lastly including condition for n = 0, and n = 1, the problem is solved.

This should easily bring you an AC and 0.02 points on SPOJ as of writing the article.

The problem BadNeighbours from Top Coder is also very similar to this one.

Here is the Java code to clear things up for you:

import java.util.Scanner;

class FARIDA {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int t = sc.nextInt();
int[] a = new int[t];
for (int j = 0; j < t; j++) {

a[j] = sc.nextInt();

}

long[] dp = new long[t];

if (t == 0) {

System.out.println("Case " + (i + 1) + ": 0");

continue;

}

if (t >= 1) {
dp[0] = a[0];
}
if (t >= 2) {
dp[1] = a[0] > a[1] ? a[0] : a[1];
}
if (t >= 3) {
for (int j = 2; j < t; j++) {
dp[j] = Math.max(dp[j - 1], dp[j - 2] + a[j]);
}
}
System.out.println("Case " + (i + 1) + ": " + dp[dp.length - 1]);
}
}
}

Posted in Competitive Programming, Dynamic Programming, Programming, Tutorial | No Comments »

Powered by WordPress