Saturday 4 October 2014

Computer Programming Experiences

  • 1 compilation error
  • 4 run-time error
  • 10 time limit exceeded
  • 6 wrong answer
That is quite a large list of errors and one that determines the character of any programmer.
  • Either she/he can accept that the problem is not her/his cup of tea.
  • Or no matter what happens, problem has to be solved.
I would like to share my most memorable programming contest problem : Team Split

Team Split appeared in March challenge 2014, organized by Codechef. It was the 3rd problem among 10 problems that were the part of contest. Being the 3rd problem, it was supposed to be an easy problem (and it was), but this problem gave me my worst time as an programmer(but at the end i learned the most out it). I have tackled and solved harder problem than this but never in my life I have seen so many errors and TLE in one problem.
-- Before explaining I expect a certain level of understanding of programming concepts from the readers--
Lets dive into it.

I will not bore you with the entire problem, look at TeamSplit.
Basically the problem said that N different players are to be distributed into a team. Each player has some strength Si. Players in team are selected alternatively like any normal selection of team and each team wants players of higher strengths. We have to find the absolute strength difference between the two teams. Strength can be calculated as
S0 = d,
Si = (a * Si-12 + b * Si-1 + c) mod 1000000, for i = 1 to N - 1
There were N players numbering 0 to N-1 and Si is the strength of player i. Also a,b,c,d were provided by the user.

Quite easy!!! I thought so (it really is very easy). Now i'll explain my various approaches towards solving this problem..

Approach #1 : Straight forward coding (very dangerous)
I gave just 5-10 min to the problem and devised the code.
I used two variables: sum**(strength of team 1)  & y**(strength of team 2).
** Now seeing my naming convention i am ashamed of myself :P. So for the sake of explanation i'll use variables team1 and team2.
After that i used a for loop to calculate the strength and added it both teams alternatively i.e. for even iteration team1 get the player and for odd iteration team2 gets the player.
After that i displayed the absolute of their difference.
OUTPUT: Wrong Answer
STATE OF MIND: It might be my mistake.Calm as cucumber
REASONS: 
  1. I didn't realized that the first player is never added to any team.
  2. Once the strength get over 1000000, it again starts from 0 and hence my player distribution method was wrong.
Approach #2.1 : Hashing (feeling smart)
I declared an int array of size 1000000. 
Calculated the strength and incremented array[strength], that way i have information about all the strengths and how many times they repeat.
After that i ran a loop for i<1000000 and for every array[i]!=0(player of strength i is present), i added and subtracted strengths alternatively.
OUTPUT: TimeLimitExceed
STATE OF MIND: Proud,  amazed, confused
REASONS:
  1. Running a loop of size 1000000 under 0.5sec was not prossible and hence the TLE.(I thought so, but later i realized that it was possible)
Approach #2.2 :
This time i discarded all strengths whose hash value was even, since they will get evenly distributed among the team and their difference will always be zero.
And for every strength of odd hash value, they  were divided alternatively among both teams. 
At last the absolute difference of team1 and 2 was calculated.
OUTPUT:Wrong Answer
STATE OF MIND: Little bit frustrated
REASON: Still a mystery to me..

Approach #2.3 :
Optimized the code.
I decreased the length  of final for loop from 1000000 to highest player strength.
OUTPUT: Still TLE
STATE OF MIND: Proud, frustrated

Approach #2.4 :
Optimized the code.
Used fast I/O to improve the speed
OUTPUT: Still TLE
STATE OF MIND: Frustrated as hell

Approach #3 : Binary Search Tree (feeling smarter than DR. Sheldon Cooper)
I realized that the values in hashing array were distributed very widely. 
So i came up with the idea of storing the strengths in a BST.It solved my two problems:
  1. Every node I visit will have some strength and no node will be of empty strength, So i have removed that for(i<1000000) loop.
  2. Also inorder traversal will return the tree in increasing order, easy to find the team strengths.
OUTPUT: Runtime Error
STATE OF MIND: Prouder than ever, frustrated
REASON: My tree might be leaking some memory or incorrect memory management and hence The runtime error.

Approach #4 : Random Sh!t (frustrated as hell)
I started modifying my previous codes and ran them in the hope that it'll run.
I also increased the array size from code used in approach #2.
But none of them ran. During this mess I even had a compilation error(No matter what happens you can never get a compilation error, NEVER).

I was not able to think about anything other than this problem. It was like this problem has some sort of control on me.
During this I saw that 800+ people have solved this problem, hence it is not that difficult. I realized that I might me missing some key step or have done a tiny mistake during my previous codes.
And then came that wonderful day.

Approach #5 :Approach 2.4 + A little modification
I realized that I was dividing MOD(= 1000000) with each term in the strength equation. The result was correct but dividing MOD was a very costly operation that was consuming a lot of time and I was doing this operation 7 times in each iteration of loop(Verrrrry much time consuming).
So i used the operation once per iteration and submitted the program.
OUTPUT: Accepted
STATE OF MIND: Enchanted, Knocked dead

I'm not a religious person, but I just woke up. That green icon of accepted sign gave me tears(OK i might be exaggerating, but i have spend 5 days to solve this problem).
During solving this problem I learned:
  • Practical implementation of hashing(if what i used was hashing)
  • Practical implementation of BST(So useful in many other problems that i was not able to solve earlier)
In the end the problem(BUG) was excessive division operation. So to all fellow programmers "Try to learn from my mistake and make your own mistakes" :P because you'll learn the most from your mistakes.
Also I develop video games from Android and Windows. I would definitely write about those too.

Take a look at:

Posted by at No comments:
Subscribe to: Posts (Atom)