The Road Leading to Google Code Jam 2013

I’m blogging after a long time today. Actually, life hasn’t been anything out of the ordinary for me,to write something about it(at least apart from the personal things in life, which I wouldn’t like to share).  The annual Google coding competition, Google Code Jam , took place last week and I had planned on participating, for the first time. So this post is going to be a gist of the significant events, since I started coding up to this point.

So, let me first explain what exactly Code Jam is all about.  According to wiki,

Google Code Jam is an international programming competition hosted and administered by Google. The competition began in 2003 as a means to identify top engineering talent for potential employment at Google. The competition consists of a set of algorithmic problems which must be solved in a fixed amount of time.

Who’s eligible?

This Contest is open to individuals who are 18 years of age or older as of August 8, 2013.

Which means, I just fit in. Now, lets examine the actual details of the contest.

Code Jam is divided into different rounds, and in each round there are eliminations, based on your rank and/or the points you’ve scored. The round which took place last week, was the Qualification Round.  This round consisted of a set of 4 problems, each of which had 2/3 data sets(think of a problem with partial marking, the small dataset is an easier subset of the main problem and the big dataset is a harder subset).  The small dataset gave you 10 points for a correct submission, while the large one gave you 35/45/60 points, based on the problem you’re solving. The round was on for 24 hours. A score of 35+ is needed to qualify for the next round. There are a total of about 4 rounds(the next one is the first round, this was kinda the 0th round) and if you achieve a rank < 1000, in the 2nd round,you get a t-shirt from Google and some bigger prizes depending on your rank. The top rankers get huge cash prizes(1st rank = 15000 $)

Since this was my first ever serious coding competition, the goal I had in mind, was to try my best to score more than 35 points, which means solve 2-3 problems correctly. I’d solved a couple of past year problems before, and they seemed quite hard for a beginner ,especially when it has been less than a year since you wrote a C program for “Hello World!”. 

The contest was to begin at 4:30 am IST. I was up at 3:30 in the morning(I slept at 8 the previous night ), because I had my college physics prelim exam at 10:30 am,  and I hadn’t even searched for my text book yet. So after brushing ,while sipping coffee I decided to check my mobile for any impending notifications. And there it was, a mail from Google, received the previous night :

Hello Nishad94,

We hope you’re ready: the Qualification Round for Google Code Jam 2013 starts in under 24 hours.

And that pretty much was the end of my search for the Physics text book, and my earlier purpose of studying for my exams. I immediately switched on my laptop, and headed straight to the website. So I was solving my first problem by 5 am. And I was getting it. That was a huge morale boost. In about 45 minutes , I’d coded the solution, and I submitted it to the Google server.  And there was the response, in green, Correct!  I’d gained the first 10 points. And the thing is , there are real time stats on the screen(Observe the left most panel in the screenshot below). So my rank, which was 16k(the competition had just started, so only a few people were in at 5am,overall there were 45k competitors this year) suddenly rose to 8k. My morale went up like crazy.

By 9 am, I’d abandoned the thought of getting up from my PC, let alone going to college and giving the exam (I don’t really care about my University results) . By 10:30 , I’d scored 40 points, and I’d qualified . Yet, I wanted to see the best I can do, so I continued till late evening. Yeah, evening. The last problem was really hard, and only 329 contestants had got it right. I wanted to crack it. But , I couldn’t. So , having exhausted my mind out of its limits, I stopped with a final score of 85. But I later found out, my 35 point solution to a problem, was slightly wrong. So in the end, the next day , my final score was 50 points, and my rank was 12142. Had my score been 85, my rank would have been < 6000. Nonetheless, I was really happy.

Lets look at the contest analysis by Google for GCJ ’13 :

Google Code Jam 2013 is off and running! We have 17059 advancers out of 21962 people who correctly solved at least one input, and 45754 registrants. All those numbers are records for us!

We started with Tomek’s variation on a game for children , and then quickly delved into the riddles of lawnmowers, palindromes, and pirates. Overall, it was a pretty tough set this year, with problem D in particular being something that could have been a Finals problem.

It was tougher than before, and I’d managed to get through . Here at some interesting region wise statistics:  (figures to the right indicate total participants, and the left indicate the people who qualified):

USA              2057     2093                       CHINA    2100   2386                           INDIA      2943    4109

These were the top 3 countries in terms of number of people who participated. And my India rank is around 1732 . And the people I know who’ve qualified are a year elder to me. Knowing that you’re better than most of your peers in such a short span of time, does give you quite an emotional high . So overall, GCJ was great, and I exceeded my expectations. The next round is in 10 days, and its going to be of 2 hours and 30 minutes. And its going to be real hard, as hard as the last problem in the qualifiers.

After this nice result, I have been really motivated to practice harder and much more seriously. Let me tell you the story till now:

I’ve always been passionate about computers and mathematics. That is the reason I’m doing engineering. I had dreams of getting into IIIT Hyderabad, last year. I’m in PICT. Needless to say, I screwed up bad in the competitive exams. Thing is I can go on for hours doing a thing I’m interested in, but I just cannot spend even an hour’s worth of time on something I’m utterly uninterested in. And morally I justify that point in my mind, so I can’t even get myself to do things that are easily achievable and which have a huge benefit in certain situations.  Last year, that was chemistry. It is the reason for the whole screw up. Anyway, I’m not going to rant more about it, as doing that won’t change things. So , if we subtract the average time a student spends on chemistry from his total schedule, we get quite a few hours. I had quite a lot of such hours, which I spent doing mathematics. So, I have a pretty good base in math. And, its safe to say , I’m comfortable and confident with it. Its been my favorite subject since chuldhood. Thus , when I entered my engineering course less than a year back, I knew I could handle the mathematics part of computer science well. And , from what I know, most of CS is based  on mathematics. Its very math intense. I have been an active member IEEE member in my college, and have attended loads of seminars, workshops,etc and all of this introduced me to programming. Thus , I immediately began coding, in the 2nd or 3rd week of college. It started with a basic book on C , getting acquainted with the basics of the language. I really liked the problem assignments in the book . And PICT, being a computer institute, had a lot of people who were interested in programming. So there was a lot of discussion, and the motivation and passion to code kept on increasing. After getting comfortable with the basics, after two or three weeks, I parallely started solving problems from Codechef. Its an Indian competitive programming website, with monthly contests.( I recommend anyone who’s interested, to register there and solve those problems) .

Programming resonates perfectly with my interest of mathematics. All that I needed to know, was whether I can code well. Whether I can get as good at it as I’m comfortable with mathematics. And now, I can finally say, yeah I can code at that level. I’m quite at comfort with it.  Now, I need to get perfect at it. What I take an hour to code right now, must happen in under 10 minutes. I need to express code as good as I express English. At the same time, I need to learn a hell lot of mathematics . By mathematics, I mean algorithms. You need to have them at the back of your mind. I should be able to code a quick sort or a merge sort in no time at all, without giving it too much of thought. And this will all take loads of hours of practice. A single algorithm, could take hours to digest. A hard problem, usually requires more than an hour to get right. It can even take 5 or 6 hours. (Which means, I lose out on my college grades. But then, gladly it doesn’t matter to me. Maybe , most people judge you on the basis of your marks, but do you really need to care about the opinion of others?) But the great thing is , I love doing it. Which means, I wont ever get tired and frustrated about it. So obviously, the next thing I have in mind, is to score big in the next ACM-ICPC , that’s the IIT-JEE-equivalent of the programming world . I have a year’s time to do that. Hopefully, I’ll be good at it. Oh, and one more added benefit, and this one is huge, software biggies like Google, Facebook are always on the lookout for this specific set of people. Google specifically started this competition, to hire top talent. (same with Facebook Hacker Cup,another similar competition with the same motive)Thats the big thing , you code for passion, and getting a job out of it would be a by-product of it. It should not be the other way round. Getting a high pay should not be the very reason you code, it won’t get you too far without frustrating the hell out of you. 

Plus, if you’re doing this, the courses in college won’t seem boring and/or hard. You’ll actually be applying practically what you learn. So if you’re passionate about it, and at the time of reading this, you haven’t yet started coding seriously, what are you waiting for? Start now.

Here are a few resources for those who are interested:

Codechef : A good place to practice problems, and compete in contests.

USACO Training Pages: Detailed structured course for training student for the International Informatics Olympiad. I just started it , and it seems pretty good.

Coursera : Loads of courses you can enroll in.

Installing Ubuntu 12.10 and fixing some frustrating startup problems

Decided to use some Linux distro(distro is a Linux-based OS like Ubuntu, Fedora,etc) as we have it in our syllabus right now , as well as for future developement/coding. I chose Ubuntu for the simple reason of it being the most popular Linux distribution, which meant greater probability of a certain OS related problem being solved quicker. So i headed straight to the Ubuntu website to download the OS.

My first problem was that I chose to download the latest Ubuntu 12.10 without thinking about any consequences. If you haven’t installed Ubuntu, please go with Ubuntu 12.04 LTS and NOT the latest version. LTS stands for Long Term Support(usually 5 year cycle) . The Ubuntu version with the LTS tag recieve constant support for 5 years and are considered stable by the community. The latest versions have not been adopted for a long time by a large userbase, hence fall into a lot of problems and huge number of bugs are reported.

I did not know any of this 2 weeks back. Thus I innocently downloaded the iso file from the website. Then I created a Live Linux USB(to get the app for creating this usb, search on google for this term), put the iso on it using an app. A Live USB is a substitute for a traditional Live CD, which is basically a bootable disc from which you install your new OS. After creation of the LiveUSB, you restart your PC, and go into the BIOS. (keep pressing F10 or some other function key[varies for different brands] at startup). Out there, change boot priority to the USB instead of HDD. Then it’ll boot from the USB, and further setup is easy.

After successful installation of the OS, I felt extremely happy as it was a quick installation, a lot faster than Windows.  After a succesfull session(install updates asap), I shut down my laptop. The next day, I started the laptop, chose Ubuntu in the GRUB(bootloader for Ubuntu, the menu where you choose which OS to load) . But then, the purple Ubuntu load screen appeared, flicked a couple of times, and stayed purple. It refused to boot up to the Unity desktop interface(Ubuntu uses Unity 3D interface, there are a lot others available). Luckily I had a seperate laptop, so I started searching the web for solution to the problem.

But the problem was, I did not know what was exactly causing this. So before, I had to know what was happening. After searching for various issues for a week , I tried various unsuccessful and temporary fixes, which did not solve the problem . Today I finally found the solution, and my laptop has booted successfully for the past 4 – 5 sessions.

So if you get a similar problem, here’s the fix that worked for me.

After we choose Ubuntu as the OS to load, the necessary video drivers are loaded by Ubuntu. If the loading of these drivers is unsuccessful for some reason, it results into the OS being stuck on the purple boot screen, also called the Purple Screen of Death(in analogy with the Windows Blue Screen of Death[BSOD]). So the basic problem , is with the video card drivers. To solve this, we need to edit the GRUB config file.

1. To do this temporarily, press ‘e’ at the boot menu(OS loading menu, the GRUB menu). Then erase the words “quiet splash” from the 2nd last line. These words tell the OS to hide the text interface while startup is on, and show the purple splash menu instead. After erasing them, type this there :

set gfxpayload=text

,save and proceed for startup.

The ‘gfxpayload=text’ disables loading of video drivers at the startup screen, and displays plain text instead. After Unity 3D is loaded, the video drivers are loaded.

2. To make these changes in the GRUB config file permenant, we need to do this through the terminal. Type the following in the terminal :

gksudo gedit /etc/default/grub

This opens the GRUB config file in the text editor. In this change this command to :

GRUB_CMDLINE_LINUX_DEFAULT=”set gfxpayload=text”

3. After this , go below this, ans search for grub_gfxmode and change it to your screen resolution. My laptop res is 1366*768. :

#GRUB_GFXMODE=1366×768

Save and exit. Then type:

sudo update-grub

in the terminal and restart. Check to see if the problem has been fixed.

Thus I wasted a huge amount of time and effort trying to solve my boot problem. The way to avoid all this would be to go for the latest LTS release, which at this point is the Ubuntu 12.04 LTS release.

Brain: The Basis of You , Your Sub-conscience and Everything

It is what separates me from you. It is the brain , which gives meaning to the world around you. You are your brain and your brain is you.

We are what we are because of our brains. Each one of us is born with the same brain . What I mean by that is , we all have the same construct of the brain. The billions of neurons inside my brain are similar to the billions of neurons inside yours. So the natural question that arises is, why is everyone so different? Why is everyone unique? Why do I perceive and judge things in a different way compared to others?

I had these and several more such questions troubling me since a long time, so I’ve been reading about psychology and cognitive science and how the brain works. After all this time, I have a simple and basic picture of how our brains work to do certain tasks. So in this post, I’ll try to explain what I’ve come to know, in a simple manner.

To answer these questions at a primary level, we need to look at how our brain functions. Inside the brain, we have billions of neurons. According to Wiki, a neuron is an electrically – excitable cell that processes and transmits information through electrical and chemical signals. A chemical signal occurs via a ‘Synapse’ , which is a connection with another cell. Neurons connect to each other, to form ‘Neural Networks’. Neural Networks are basically pathways for a signal to flow . These neurons and neural networks are the core components of the ‘Nervous System’ .

Whenever any task has to be done, certain neurons are triggered and signals flow out of them. These are what are called synapses. Synapses can either be chemical or electrical. In an electrical synapse, the signal(or pulse) is transferred through voltage differences between the successive neurons , and in this way the pulse is passed from one neuron to another neuron or several other neurons. A chemical synapses is the transfer of signal through actual transplant of chemicals like Calcium ions between neurons. So for a certain task, a specific neural network is activated.

So lets say I touch a hot object, my hands sense this through a change of pressure on the affected part. This leads to a faster heartbeat , and in a certain more complex way this message reaches the nervous system. Then the neuron connected to touch would be activated and trigger a certain neural pathway connecting this neuron to several others. These include the neurons that involve past experiences and prior knowledge of danger and harm . These in turn will activate more neurons that will tell the brain that the hand is actually hurting , and it needs to be moved . So thus a neural pathway involving all sensory organs is activated and I finally move my hand away.

Another interesting thing , is the perception of colour (A discussion with friends got this topic into my head). Colour is not real. It is a construct of our minds. Animals percieve colour in different ways. You and I probably conceive colour in a different way. Colour is basically interpretation of our brain of different wavelengths of light. All this again happens due to trigger of various neurons that eventually builds up a network and we give that pattern a certain name .

Thus everything in our brain is the work of neurons. This helps us to look into our questions. What separates each one of us is not how are brains are created different, but how our pulses or signals flow between neurons. We can think of each one of us, having the same ‘hardware’ but running different ‘software’.

Our thoughts, perceptions, way of thinking, memories , dreams are all different. When we ‘think’, we actually are activating different neurons to form unique ‘pathways’, i.e neural networks. Our way of thinking , is our pattern of activating the neurons to create meaningful  output. This is what makes each of us different. This way of thinking is different for everyone, and as we grow up the pattern takes shape based on past experiences , our memories. When a memory is stored, what basically happens, is the neural pathway for that task is being stored. I know there’s danger in touching a hot object, because sometime before I’ve touched something hot and have got hurt. During this task, a certain neural network had been activated, a certain path for synapses had been created. A memory has been stored. I’ve stored the pathway, and hence whenever I touch a hot object again, this pathway is instantly activated. My brain has told my body to respond in a certain way .

Thus thoughts and perceptions are just patterns of neuron activation. Thoughts are random because everything around us stimulates us and everything makes us trigger different neurons. But a lot of patterns are random and hold no further value and hence are discarded. But certain patterns are interesting or helpful and are stored. Memories are stored patterns.

When we dream, one interpretation is that, memories are being stored. The neural pathways are being ‘hard-wired’ in our sleep. Hence usually dreams are based on what has happened during the day, mixed with certain experiences of the past.

Our ‘way of thinking’, our sub-conscience is our root pattern of neural flow , being enhanced with our daily experiences and insights.

Everyone has been through different experiences since he or she has been born. Thus the patterns that we all have built in our minds , are all different. These patterns separate us as individuals. Based on prior experiences, our minds have been shaped differently . This has given each one us different insights , different interests, different ambitions ,different personalities. This has made us different from each other. This has made each one of us unique in our own way.

What I’ve written here, is meant to be an introduction to how our minds work. The topics of consciousness, thinking, dreams , neural networks and a thousand more sub topics involving our brains and us in general are immensely interesting. They are far from understood and probably will never be understood. But reading about them helps you understand yourself in a better way, and it helps you make sense of why , what is happening, is happening .My interest in all this , has been growing as I dwell deeper into it.

If one day we’re able to understand all of this completely, we may be able to create the smartest , human-like ‘Artificial Intelligence’ systems that are able to create and develop these neural pathways , probably electronic neural networks that work on voltage gradients,  and such an artificial electronic fully developed ‘brain’ would be able to control an ‘electro-mechanical body’ to work like an actual human being.

Such a thing , would take decades or probably never happen because the brain is an enormously complex organ and it will take a huge amount of information processing before we even think of ways of creating such a system and sustaining it.

Quora

We all have various questions in our mind. They can be about anything and everything.They maybe ranging from neuroscience to philosophy. And most of the times these questions go unanswered, because you either get bored to look for the answers or you just forget them after a while.

Getting our attention to the first part, things sometimes get boring to look for because, for answers to different stuff , we have different sources. We end up wasting a lot of time. So a place where you can discuss everything was unknown to me. I’d never thought the same source where I would get my neuroscience or physics question answered, there would also be philosophical discussions there.

But then, I stumbled upon Quora.com. And I’ve been hooked since. Its a discussion platform for every topic possible. I mean it, its got everything. And its a really interesting community, filled with some smart and some ultra smart people and normal people too. I’ve read stuff on , how the brain works , whats it to get high on a drug, about computer science, a philospohical debate about Science and God and believers,  and lots more. The topics are diverse and the website is very informative. I havent been able to contribute any answers on my own, but in the future Ill contribute somewhere.

Some facts: It started in 2010 , and Quora’s valuation was rumored to be more than $1 billion in February 2011.Adam D’Angelo(CEO, age 27) was ranked number 22 among the smartest people in the technology industry by CNNMoney in 2010.

So if you have not checked it out, please do. You can follow people, and its kinda social too. A pretty smart concept , Quora is.

Post-Rock…. Pink Floyd and music.

My first post about music, and the first part of the title is pretty weird and most probably you havent ever heard of that term. Neither had I, until 2 days back when I heard a song(Do you call music without vocals , a song? I’m not sure) on youtube by the band ‘God Is An Astronaut’. And I pretty much became a fan of the band and I might probably become a fan of the genre, after I check out a few more bands. So, GIAA is a post rock band, and post rock is a sub genre of rock which consists of solely instrumentals. And the music is great. If you’re as much an avid listener as I am, and you prefer listening to entire albums rather than singles , you’ll love it. It just feels surreal. Its not really peaceful in the music sense, like it isnt slow, its got quite a lot of guitars and drumming , but it just seems quite. This is the kinda music, you would prefer to get yourself into a calm and deep thought. Listen to the single “zodiac” just as a check to see if you’d like the music or not.

The second part of the title is pretty much understood by everyone. Pink Floyd, who hasnt heard about them? The Psychedelic / Progressive rockers who need no introduction. I’ve been listening to Floyd since a long time, but only recently did I listen to entire albums of theirs in one go. And it feels amazing. Seriously, listening to an entire concept album is pretty much a completely different experience.(A concept album is an album with a central theme, and all songs are connected to it.)  Dark Side of The Moon has now become my favourite album . Its an album, about various phases of life and about passage of time, greed, money and mental illness . The latter part is dedicated to Syd Barret, the founding member of the band , who was there with them only on the first album. But due to excessive drug use, was not in a a healthy state of mind later on. The album has to be heard paying every bit of attention to its lyrics. They are wonderful, and the music is calm . Its no surprise, that its their biggest hit. The last 2 songs , Brain Damage and Eclipse, dealing with madness(mental illness) are my favourite tracks of the album (and overall too) along with Time.

I checked out The Wall , the concept on this one is social isolation. This ones pretty good too. But its long, and after the first listen , some of the songs get boring . Its got great songs like Floyd’s most famous  ”Another Brick”, “Comfortably Numb”, “Hey you” and some more. And they are amazing, but as an album I’d say DSOTM is much shorter, and better.

Music is one of the things in life, which I’m most obsessed about. So I guess , I’d be writing about it a lot more often. I’m not really inclined to any one genre of music, I’m fine with anything good. But my most played music would be The Doors, Pink Floyd, Beatles, Led Zeppelin and recently The Velvet Underground in that order.  I’d have loved music to still be as it was in the times of these bands. Ill write more about them in later posts.

Allocation of memory and Processor Architecture

Yesterday I happened to read a post by a friend where he had mentioned a problem in a certain program.  He had mentioned that his code worked correctly only up till a certain number of digits(it was 5). The compiler he was on was “Turbo C”, which is a very old compiler (to be precise was introduced in 1987) and should not be used by anyone right now.  When I ran the same code on my laptop, on “Microsoft Visual C++ Express 2010(MVCE)”, I noticed that the code worked perfectly for numbers containing 11 digits. So, then I began to wonder what exactly is causing this problem.  After searching for quite a while , and reading up a lot of stuff about how memory allocation is done in C, how information is stored in general on the computer memory, I was able to understand why this was happening.

I knew that the problem he was facing was because of the declaration of his variable of the type “int”, which like all other data types has a certain range of permissible values.  But I was not able to figure out why it was working for a larger range of values in MVCE !

This search led to me knowing the meaning of processor architecture, and how it affects the various applications. The basics of memory allocation lie in the meaning of processor architecture.

In this post , I will try to explain how memory is allotted to different data not just in C, but in general. I will explain what exactly is the meaning of processor architecture.I will not go into too much detail like how a computer stores/fetches memory on/from the different storage devices like caches, RAMs, ROMs , hard disks, etc. For that, I’ll include some links which you can look into, if you are interested. After understanding this, its evident why this problem was occurring.

16,32,64-Bit Processors and Memory Allocation:

All information is stored on the computer in the form of 0′s and 1′s. This, as we know is the binary number system and a digit in this system is called Binary Digit . Thus information is stored in the form of bits. So all letters, symbols and numbers that we type are first converted into a pattern of bits and are then stored in memory as a computer can understand only bits.

So if we enter a number say 18(base 10) , it will be converted to base 2, which would be :

18 = 16 + 2

18 = 1*(2^4) + 1*(2^1)

18 = 1*(2^4) + 0*(2^3) + 0*(2^2) + 1*(2^1) + 0*(2^0)

Thus 18 = 10010

Hence 18, will be stored as 10010. Similarly, the letters and symbols on the keyboard are assigned certain numerical values which are based on the ASCII(American Standard Code for Information Exchange) or UTF schemes. In ASCII, A is assigned the value 65. Thus when “A” is typed on the keyboard, the computer converts 65 to binary and stores its value in memory. All symbols have such values(including space bar).

So how is this binary value stored?

For this we need to understand, what is called a “word size” of a computer. The word size is the computer’s preferred size for moving units of information around; technically it’s the width of your processor’s “registers”, which are the holding areas your processor uses to do arithmetic and logical calculations. Basically “word size” means the size of the maximum binary value the computer is able to store in a single register(register can be visualized as a box where each character/letter/number is stored in its binary form)  . 

This word size depends on your processor. This is what is meant by 16-bit/32-bit / 64-bit processors. The bit part refers to the width of the processors register, how many binary digits it can store . Hence, a 16-bit processor can store values ranging from  00000..(16 0′s) to 11111…(16 1′s). Thus the number of combinations of 0′s and 1′s in this arrangement would be (2^16). This is called the “Dynamic Range” of a system. Thus the highest integer value that can be stored in a register would be 1111…(16 times 1). In base 10 this number would be 

1*(2^15) +1*(2^14) + ……+ 1*(2^1) + 1*(2^0) 

= 1 + 2 + 4 + 8 + 16….. + 2^15 

This sum calculated  by using the GP sum formula gives (2^16) – 1 = 65,535

Hence an int data type would store the maximum number to the base 10 as 65,535. Integer values are stored in “GPR’s – General Purpose Registers”. The floating point limit is much higher as they are stored in “FPR’s – Floating Point Registers”. These work on a different principle , which at this point I haven’t looked into.   

Thus now we know what the max size an integer value can take on a certain processor. We discussed that registers store this value . Registers are a storage unit, they cannot perform any operations on the numbers. For operations, these values are passed to the ALU(Arithmetic Logic Unit). The register is the fastest accessable memory storage for an ALU. But registers store values only temporarily  as their size is limited due to their high cost. Whenever the value is not needed, it is passed on to the RAM. Data is stored on the ram on “addresses” . Addresses are basically numbers. An example would be: Address #1, address #2,etc (In actuality only bits(#0, #1, #10, #11,etc.) will be allowed not #1, #2..). Thus the number of addresses possible on the ram is the number of  integer values possible. Thus on a 32-Bit processor , number of addresses would be 2^32 = 4.3 billion . Each address stores 1 byte of data, thus this means 4.3 Billions bytes = 4 GigaBytes . Hence a 32-bit processor supports a maximum RAM of 4GB.  What this means is it can store 4.3 billion addresses , each address might contain numbers(data) or operations(+, -, *, /)(code).  

This is what defines a computer at the basic level :  Manipulation of data through the use of code, which is stored in the computer’s memory and fetched from the computer’s memory.

The above statement defines all  tasks that a computer does!

Now coming back to the main problem:

Not all application can take advantage of the higher bit processors. Each application is coded for a certain type of processor. The Windows OS is available in 32-bit and 64-bit editions. The latter is only useful for 64-bit processor. A 32-bit OS would treat a 64-bit processor as a 32-bit one , and would not take the extra advantage of the extra “dynamic range” that we saw.

Now, Turbo C  is an application that was built for the 16-bit DOS operating system. Thus it is a 16-bit application. This means that its dynamic range is limited to 2^16 values. Hence the max value of an integer would be 1111…(16 times 1), which in base 10 will be 65,535 as we saw before. Hence the 5 digit limit on integers . 

MVCE, on the other hand is a 32-bit application . Thus while it wont use a 64-bit processor’s full capability, it will give us the “dynamic range” of 2^32 numbers. Max value of integer would be 1111…(32 times 1), which in base 10 would be 2^32 – 1 = 4.3 * 10^8 . Thus the extra number of digits possible in MVCE.

I have only mentioned some basic stuff here, this topic is vast and quite interesting. So here I will quote my references which are really good and informative reads:

Classic.Ars: Understanding the Microprocessor : http://archive.arstechnica.com/paedia/c/cpu/part-1/cpu1-1.html

Classic.Ars: An Introduction to 64-bit Computing and x86-64: http://arstechnica.com/features/2008/09/x86-64/

Bits and bytes , how they work: http://computer.howstuffworks.com/bytes.htm

How does my computer store things in memory? : http://en.tldp.org/HOWTO/Unix-and-Internet-Fundamentals-HOWTO/core-formats.html

How computer memory works : http://www.howstuffworks.com/computer-memory.htm

Clarification : The int values I have given will be possible only if we declare an “unsigned int”, as for an int variable , 1bit is reserved for the number sign. Hence max value of  a normal int would be 2^15 – 1 = 32,767 on 16-bit compiler and 2^31 – 1 for a 32-bit compiler.

The C Diaries: Week 1

After being comfortable in loops, there are a whole lot of problems you can solve in C. I’ve been solving quite a few and here are some I found interesting. For these you need to be comfortable with the basic syntax and loops.

Problem 1:

f(x) be a function that calculates the trailing zeroes of x!(x factorial).  So we need to write a program to :

1. Take input for number of test cases.
2. Enter first case(x).[input]
3. Output f(x).
4. Enter next case(x)
5. Output f(x).

• This goes on till the last test case, and then the program stops.

Example

Sample Input:

6
3
60
100
1024
23456
8735373

Sample Output:

0
14
24
253
5861
2183837

Solution:

The basic idea behind computing number of zeroes in x! is to find the number of times 10 comes in the factorial’s factors. Which basically means checking the number of times 2 and 5 come (as 2*5=10) . So for this the easiest straightforward method is to find the factorial first, then keep on dividing factorial by 10 untill number(mod)10 != 0. We can define a counter for this. But the problem with this is , the limit of x is 10^9 , whose factorial will be extremely large. The datatypes in C wont be able to handle such a large number. Another problem is execution time for such a program will be enormous.

If we think a bit more closely, we see that x = x.(x-1).(x-2)….3.2.1 . So here we can count individual 2′s and 5′s from x, x-1, x-2 … uptill 1.  But we see that the number of 2′s will always exceed number of 5′s in any number. So we will check for only number of 5′s, and this will give us 10′s which will give us zeroes.

To check for 5′s we can first caluculate the number of mutiples of 5 which are less than or equal to that factorial. So lets say x = 100, the multiples are 5,10,15…100.  So there are 100/5 = 20 5′s present. After this we’ll check number of multiples of 25 in the number. These are 25,50,75,100 i.e 100/25 = 4. We have to add these to our total count of 5. 25 is 5^2 , which means it contains two 5′s. But we already have accounted for one 5 in the first step, hence we just add 4 directly to our previous answer. so number of 5′s uptill now : 20 + 4 = 24. Now we consider number of multiples of 5^3=125. But 125 > 100, hence no multiples. Thus our loop must stop when 5^n > x(our number).  Thus we get number of zeroes.

#include<stdio.h>
int main()

{
int t, a, d, c, b;  //t is the number of test cases, a is the input number, d is the counter for total number of 5′s, c is used for incrementing powers of 5, b is used for number of 5′s in one cycle of the loop.
scanf(“%d”, &t); //Enter number of test cases.
for(; t > 0; t–)
{
scanf(“\n%d”, &a); // Enter input number
d = 0 ;
c = 1 ;
for (; c <= a ; )
{
c = c * 5 ;
b = a / c ;
d = d + b ;
}
printf(“%d\n”, d) ; // Output number of 5′s = zero.

}

return 0;
}

Problem 2:

There is a job to fill n vacancies. But number of applications(x) are more than n. So the people are made to stand in a line, and are named serially from 1 to x. Then the odd numbered people are elminated. Then next again odd numbered people are eliminated. In this way the elimination continues. Compute a program (with number of test cases counter) to calculate the position in which a man should be in, so that he’s most probable to get the job.

Example

Input:
2
5
12

Output:
4
8

Solution:

The question says that only even numbered positions are entitled to go ahead. So only the 2nd, 4th, 6th …. positions will go ahead after 1st elimination. Now these terms respectively take the 1st, 2nd, 3rd…  positions. Next elimination 2nd, 4th,6th… positions of this  new series will go ahead(which are respectively 4th, 8th,12th terms of the original series). This will continue untill for a certain input, only 1 number is remaining.

Lets take an example by considering n = 10.

• 1  2  3  4  5  6  7  8  9  10                   Position of the number 8 in the series  =  8                      Total terms = 10
  
•     2       4       6       8       10                  Position of the number 8 in the series  = 8/2 = 4         Total terms = 10/2 = 5 (intdiv)
  
•                4                8                             Position of the number 8 in the series  =  4/2 = 2         Total terms = 5/2 = 2(intdiv)
•                                   8                             Position of the number 8 in the series  = 2/2 = 1           Total terms = 2/2 = 1

As odd cases are being elminated in every round, the successive position of a number is equal to previous position /2 .  The most favourable case will last untill the end, which in this case is 8. Hence the key to this problem seems to be to keep on successively dividing the number of people(n) by 2(n/2) untill n = 1.  Hence we can setup a counter (i = 0) to count the number of times n can be divided by 2 untill n = 1.  And then we can back calculate the number by continuously multiplying by 2, i times, i.e 2^i. 

In this case i = 3. Hence number is equal to 2^3 = 8.

Code:

#include<stdio.h>
#include<math.h>

int main()
{
int t;   //Number of test cases
int i, n, k; // i = counter that describes number of times n can be divided by 2 , n = number of persons(terms), k = final answer
scanf(“%d”, &t);
for(; t > 0 ; t–)
{
scanf(“%d”, &n);
for(i = 0 ; n > 1; i++)
{
n = n / 2;
}
k = pow(2,i);
printf(“%d\n”, k);
}
return 0;
}