UVa 1203 - Argus C++ map and priority queue

Question

Solution to this UVa problem by using simple data structures like map and priority queue.

Solution

Since priority queue stores data in descending order but we needed ascending order, we simply stored negative instead of positive. Alternatively we might have to write our own comparing function.

UVa 11173 - Grey Codes Using Bitset

This question asks to convert a decimal to gray code and print the decimal value of this gray code.

Competitive Programing: Vowel Substring

Q: Given a string find all the number of sub-strings which contain all the five vowels at least once.


It is solved in two ways:

1. A slightly more complicated linear scan method
2. By generating all the sub-strings and then checking whether or not it satisfies the our requirements. (brute force)

UVa 00637 - Booklet Printing

This problem is an adhoc problem that asks to you to design a system to print folding booklets. The problem description and test cases can be found here.

Uva 278 - Chess

This problem  is one of the best ad-hoc problems I have come across - simple but thought provoking. It asks you to the maximum number of  rooks, queens, kings or knights you could place on n*m chess board such that no piece attack another.
Given that 4<=m,n<=10.

Uva 11586 - Train Tracks

This is a solution to this Ad Hoc Problem on uva online judge.

Summing the digits of a number in C++

Q: This is a simple ad-hoc problem which asks to sum up the digits of a number repeatedly until the sum is less than 10. We are required to stop the program when input given is 0.

Generating Permutation in Python

This is the best way to generate permutations in python.

from itertools import permutations

j="1234"
for i in permutations(j):
    print "".join(i)

Maximum subarray problem

Problem Statement

Finding a contiguous sub-array which has the largest sum in an 1-D array.

Algorithm

This problem is solved by using Kadane Algorithm. This algorithm is a linear time algorithm.

C++:Printing the kth smallest suffix for a string

Prequisistes

• Stl vector
• std::sort() for vector
• Pointers

Code 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

Fenwick Tree to Maintain A count of number of even numbers

Q: Design a Fenwick Tree to maintain a count of even numbers.


References to Learn about Fenwick Trees

• HackerEarth
• Wikipedia

Language: C++

Code

Python Sets:Checking whether a given string contains all the vowels in english language

Q: To check whether the given string contains all the vowels in english language.

Common Logical Errors in C and C++

Today I spent over two hours discovering this stupid mistake in my code.

a=a++;

Thus I came up with the idea to make a cheat-sheet for common programing mistakes. I hope this is useful to you during your practical exams preparations, debugging times and coding competitions. In case, I have not mentioned one of the mistakes that you make just leave a comment and I will add it.

Finding primes in a range of numbers

The fastest way(yet easy to understand and implement) to test a prime number is Rabin-Miller Prime Test. However, it suffers from two issues:

• It is suitable for a single number
• It may give false positives

When it comes to finding primes from 1 to say 10^6. This method is not suitable. Since this method doesn't use any previously generated information. So the program will end up testing each number.

Sieve Algorithm on the other hand, uses previously generated results and works faster when determining the primes in a range.

Here is a code snippet for the same

Tournament Problem Solution

Solving Tournament Problems using Queue