Home arrow C++ arrow Page 4 - Easy and Efficient Programming for Contests
C++

Easy and Efficient Programming for Contests


Efficient coding ensures that you complete a task in the smallest time interval possible without complicating your life too much. Now, you do not need to work like this for every little bit of code you type. This approach will be priceless, however, whenever time is of the essence, as it is for a programming contest.

Author Info:
By: Gabor Bernat
Rating: 3 stars3 stars3 stars3 stars3 stars / 9
July 07, 2009
TABLE OF CONTENTS:
  1. · Easy and Efficient Programming for Contests
  2. · How to write code
  3. · Macros, arrays and memory
  4. · Exploiting the language's strengths

print this article
SEARCH DEVARTICLES

Easy and Efficient Programming for Contests - Exploiting the language's strengths
(Page 4 of 4 )

Now we already know that every language has its strengths and weaknesses. As for the C/C++ world, it is a known truth that bitwise operations are much faster than the usual ones known from math classes. Here I will present a method that uses this knowledge to work approximately four times faster than the ones presented in manuals.

The original idea came from Mihai Patrascu, and we are talking about binary search. This type of search will find an item inside a sorted array, taking advantage of the fact that the array is sorted. It will always split the array into two, determine in which part of it is our value, and repeat for that section the upper algorithm until it finds it. The algorithm I will present here will follow this idea, however, by comparing the values directly it will start to determine bit by bit the queried value:

#include "stdio.h"

#include "stdlib.h"

 

int length;

int *array;

 

int binary_search(int value)

{

int i, step;

for (step = 1; step < length; step <<= 1);

for (i = 0; step; step >>= 1)

if (i + step < length && array[i + step] <= value)

i += step;

return i;

}

During the first step it determines how many moves it needs to make, or in more common language, calculates log 2 length. In the second step, it takes the route back and adjusts i until it finds the element.

For now we will take a break so you can digest what I've presented here so far. I leave you with the promise that next week I will finish up this series of articles with the fourth part.

Moreover, until then I also invite you to share your thought either here on the article's blog or in the forums for DevArticles and DevHardware . Joining costs nothing except a little time from you, and you will enter a community with which you can talk about your problems. Feel free to act. Until next time, Live With Passion!


DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.

blog comments powered by Disqus
C++ ARTICLES

- Intel Threading Building Blocks
- Threading Building Blocks with C++
- Video Memory Programming in Text Mode
- More Tricks to Gain Speed in Programming Con...
- Easy and Efficient Programming for Contests
- Preparing For Programming Contests
- Programming Contests: Why Bother?
- Polymorphism in C++
- Overview of Virtual Functions
- Inheritance in C++
- Extending the Basic Streams in C++
- Using Stringstreams in C++
- Custom Stream Manipulation in C++
- General Stream Manipulation in C++
- Serialize Your Class into Streams in C++

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials