rishabhk965's blog

By rishabhk965, history, 5 years ago, In English

Bit manipulation is generally faster because CPU directly supports these operations. Some of the very common use case bit hacks:

1) Swapping two numbers:

x = x ^ y
y = x ^ y
x = x ^ y

How does it work?

Because of XOR property y^(x^y) = x. and x^(x^y) = y. (be aware that it is not actually faster than the general extra variable swap, as it can’t achieve instruction parallelism.)

2) Find min(max) of two numbers(very efficient method):

min = y ^ ((x^y) & -(x < y))

How it works? (lets assume x = 3 and y = 4, min should be x)

First the last part: -(x < y), if x < y it becomes -(1). 2’s complement if of -1 is 1111(how? 1’s complement+1). If x > y it becomes -(0) => 0000.

Second part: ((x^y) & 1111) anding any number with all one return the same number, so (x^y) & 1111 => (x^y).

Third and final part, y ^ (x^y) by xor property it should be equal to x.

3) Mod of sum of two numbers:(normal method for mod of n is (x+y) % n).

z = x + y
m = z - (n & -(z >= n))

How it works?

Is simple terms, z — (n) iff z >= n, else z.

Tell us more in the comments.

Full text and comments »

  • Vote: I like it
  • +24
  • Vote: I do not like it

By rishabhk965, history, 5 years ago, In English

Even if you are not python programmer, do the following

Install python, if your system does not come with a default python version.
Run python.
Type "import this"
you will get the following output.

Understand each line. do this everyday till these rules become part of your working memory and habit.

--------------------------

import this The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than right now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it

By rishabhk965, history, 5 years ago, In English
  • Vote: I like it
  • +19
  • Vote: I do not like it

By rishabhk965, history, 5 years ago, In English

I believe anyone who wants to start out with Competitive Programming would benefit hugely from these 2 amazing resources:

  1. http://codeforces.net/blog/entry/23054

  2. https://www.commonlounge.com/discussion/55e14de95aed4baa84f61bcb4c14ca3c

Full text and comments »

Tags c++
  • Vote: I like it
  • +2
  • Vote: I do not like it

By rishabhk965, history, 5 years ago, In English

Well, everyone should read this book from Start to end (From Basics to Masters).

Here are my suggestion on How to read this Book.

Reading and Understanding CLRS:

  1. Use video lectures to understand the concept, and read the chapter from the book. Best site for CLRS lecture videos : Lecture 1: Administrivia, Introduction, Analysis of Algorithms, Insertion Sort, Mergesort

Video Lectures | Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare

Peteris Krumins has published a series of blog posts covering the lectures. You can also find his lecture notes for each video. Start with this one: http://www.catonmat.net/blog/mit....

What if you're not understanding Mathematical equations and Proofs, functions given in the Book?

  1. Watch Videos on Discrete mathematics by Arsdigita University Course 02: Discrete Mathematics (Arsdigita University) : Free Download & Streaming : Internet Archive In parallel with it read Discrete mathematics and Its Applications by Rosen Discrete Mathematics And Its Applications 7th Edition : Free Download & Streaming : Internet Archive Solve Exercises given in the Book if you solve all the Exercises on your own ;) . I'm sure you'll become Master.
  1. Attempt the exercises after every chapter of CLRS. Resist the temptation to skip the exercises or look at the solutions online right away.

  2. Practice solving algorithmic problems from sites like TopCoder, SPOJ, etc. For example, after reading the chapter on Dynamic Programming, you could filter problems belonging to this category and solve them.

  3. If you find the content in CLRS to be very theoretical as you progress (and you will), use Topcoder Algorithm Tutorials (http://community.topcoder.com/tc...) to understand them first. The contents here are more approachable.

  1. For your reference,here is the solution link to CLRS Page on compute.dtu.dk

This is how I'm currently reading the Book. I hope this works for you too ;).

Thank You!!

Full text and comments »

  • Vote: I like it
  • +15
  • Vote: I do not like it