Daily Programming Dose Day 5

How many specific orders do you know? Ascending order, descending order, order of ascending length, order of ascending polar angle… Let’s have a look at another specific order: d-sorting. This sorting is applied to the strings of length at least d, where d is some positive integer. The characters of the string are sorted in following manner: first come all the 0-th characters of the initial string, then the 1-st ones, then the 2-nd ones and so on, in the end go all the (d - 1)-th characters of the initial string. By the i-th characters we mean all the character whose positions are exactly i modulo d. If two characters stand on the positions with the same remainder of integer division by d, their relative order after the sorting shouldn’t be changed. The string is zero-indexed. For example, for string ‘qwerty‘:

Its 1-sorting is the string ‘qwerty‘ (all characters stand on 0 positions),

Its 2-sorting is the string ‘qetwry‘ (characters ‘q‘, ‘e‘ and ‘t‘ stand on 0 positions and characters ‘w‘, ‘r‘ and ‘y‘ are on 1 positions),

Its 3-sorting is the string ‘qrwtey‘ (characters ‘q‘ and ‘r‘ stand on 0 positions, characters ‘w‘ and ‘t‘ stand on 1 positions and characters ‘e‘ and ‘y‘ stand on 2 positions),

Its 4-sorting is the string ‘qtwyer‘,

Its 5-sorting is the string ‘qywert‘.

You are given string S of length n and m shuffling operations of this string. Each shuffling operation accepts two integer arguments k and dand transforms string S as follows. For each i from 0 to n - k in the increasing order we apply the operation of d-sorting to the substringS[i..i + k - 1]. Here S[a..b] represents a substring that consists of characters on positions from a to b inclusive.

After each shuffling operation you need to print string S.

Input

The first line of the input contains a non-empty string S of length n, consisting of lowercase and uppercase English letters and digits from 0 to 9.

The second line of the input contains integer m – the number of shuffling operations (1 ≤ m·n ≤ 10⁶).

Following m lines contain the descriptions of the operations consisting of two integers k and d (1 ≤ d ≤ k ≤ n).

Output

After each operation print the current state of string S.

Sample test(s)

input

qwerty
3
4 2
6 3
5 2

output

qertwy
qtewry
qetyrw

Note

Here is detailed explanation of the sample. The first modification is executed with arguments k = 4, d = 2. That means that you need to apply 2-sorting for each substring of length 4 one by one moving from the left to the right. The string will transform in the following manner:

qwerty → qewrty → qerwty → qertwy

Thus, string S equals ‘qertwy‘ at the end of first query.

The second modification is executed with arguments k = 6, d = 3. As a result of this operation the whole string S is replaced by its 3-sorting:

qertwy → qtewry

The third modification is executed with arguments k = 5, d = 2.

qtewry → qertwy → qetyrw

Daily Programming Dose Day 4 Solutions

Due to the small restrictions, the problem could be solved with the straightforward O(n*m*(n+m)) algo of finding for each symbol whether there is other such symbol in the corresponding row or column. More fast approach is to count for each symbol how many times it appears in any row/column, and do corresponding checks in O(1) instead.

I am attaching my solution link below :

http://ideone.com/G3YKqo

Lazy Propagation in Segment Trees

This is in continuation with my previous blog on segment trees. As we have seen segment trees can be a very powerful DS for solving problems of range min,max,sum etc. But when the updates come very frequently or in large range like almost the entire array, then the update function would end up with O(n) ,so to overcome this problem, we update only when it’s required which is also called Lazy Propagation.

Here the building tree will remain the same, but we will also declare other array that contains info. whether to update the particular node or not. We will update the node only when it is queried or updated once more.

So the new query method is

private int getSum(int startIndex, int endIndex, int queryStart, int queryEnd, int current)
    {
         if(updates[current]>0) //If the current node needs to be updated, first update it
        {
                treeNode[current] += updates[current]*(endIndex - startIndex + 1) ;
                if(startIndex != endIndex) //Also set its children for update
                {
                        updates[getLeftChild(current)] += updates[current] ;
                        updates[getRightChild(current)] += updates[current] ;
                }
                updates[current] = 0 ;
        }
        if (queryStart <= startIndex && queryEnd >= endIndex ) //If it is leaf node
        {
            return treeNode[current];
        }
        if (endIndex < queryStart || startIndex > queryEnd) //out of range
        {
            return 0;
        }
        int mid = (startIndex + (endIndex - startIndex) / 2);
        return  getSum(startIndex, mid, queryStart, queryEnd, getLeftChild(current)) 
                 + getSum( mid + 1, endIndex, queryStart, queryEnd, getRightChild(current)); //return the result
    }
 
    public int query(int queryStart, int queryEnd)
    {
        if(queryStart < 0 || queryEnd > treeNode.length)  //query is out of range
        {
            return -1;
        }
        return getSum(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT);
    }

Here the updates[] I am referring to is the array that contains amount by which that particular node needs to be updated.
Also the now since we are doing lazy propagation,I will call update method on a range of elements to exploit its full use.The new update method is

private void updateTree(int startIndex, int endIndex, int updateStart,int updateEnd, int update, int current)
    {
        if(updates[current]>0) //If current node needs to be updated,update it first
        {
                treeNode[current] += updates[current]*(endIndex - startIndex + 1) ;
                if(startIndex != endIndex)
                {
                        updates[getLeftChild(current)] += updates[current] ; //Also set update for its children
                        updates[getRightChild(current)] += updates[current] ;
                }
                updates[current] = 0 ;
        }
        if ( updateStart < startIndex || updateEnd > endIndex) //out of range
        {
            return;
        }
 
        if(startIndex >= updateStart && endIndex <= updateEnd)// Node in range totally
        {
                treeNode[current] += update*(endIndex-startIndex  + 1) ;  //update the current node
                if(startIndex != endIndex)
                {
                        updates[getLeftChild(current)] += update ;  //set update for its children
                        updates[getRightChild(current)] += update ;
                }
                return ;
        }
        int mid = (startIndex + (endIndex - startIndex) / 2); //If its not totally in range
        updateTree(startIndex, mid, updateStart,updateEnd, update, getLeftChild(current)); //Call recusively on its children
        updateTree(mid+1, endIndex, updateStart,updateEnd, update, getRightChild(current));
        treeNode[current] = treeNode[getLeftChild(current)] + treeNode[getLeftChild(current)] ; //Also update current node accordingly
       
    }
 
    public void update(int update, int updateStart,int updateEnd, int[] elements)
    {
        int updatediff = update - elements[updateStart]  ; 
        for(int i=updateStart;i<updateEnd;i++)
        elements[i] = update; //update the element array
        updateTree(STARTINDEX, ENDINDEX, updateStart,updateEnd, updatediff, ROOT); // call the update method
    }

As you can see through lazy propagation it update a node only when a query/update is called on that node.So it will only update the required node at once keep the rest of the nodes for updating next time.In this way the update order reduces to O(1) which can be very helpful when a large no of updates are fired before having any query.

Feel free to type in any suggestions/corrections in comments

Keep Learning!

Parth Panchal

Daily Programming Dose Day 4

Given a n*m grid of characters you have to perform following operations:

1.Cross out the common letters in a particular row.

2.Cross out the common letters in a particular column.

Now make a string according to the following rule:

1.The letters that occupy a higher position follow before the letters that occupy a lower position.

2.If the letters are located in one row, then the letter to the left goes first.

The resulting string is the answer.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 100). Next n lines contain m lowercase letters each.

Output

Print the encrypted word on a single line. It is guaranteed that the answer consists of at least one letter.

Sample test(s)

input

3 3
cba
bcd
cbc

output

abcd

input

5 5
fcofd
ooedo
afaoa
rdcdf
eofsf

output

codeforces

Daily Programming Dose Day 3 Solutions

You will surely appreciate the simplicity of the problem once you get the solution.

Let’s draw a straight line between the two centers.

Clearly to move the center with maximum distance we need to rotate it around the intersection of the line and the circle with 180 degrees. So the maximum distance we can move the center each time is 2 * R. Let’s continue moving the center with 2 * R distance each time until the two circles intersects. Now obviously we can make the center moves into its final position by rotating it around one of the intersection points of the two circles until it reaches the final destination.

Every time we make the circle moves 2 * R times except the last move it’ll be ≤ 2 * R. Assume that the initial distance between the two points is d So the solution to the problem will be $\text{[math]}$

You can have a look at my code below:

http://ideone.com/j4MFfL

Featured

Learn to Code

How do I Learn to Code? This is probably the most nagging question at the back of your mind, once you have decided that you want to learn programming. Like learning anything else, there is no standard process for learning to code. Of course there are guidelines, there are courses, there are ideologies and there are set traditions, but there is no one single correct way.

One school of thought which is very popular and fairly simple to begin with is Competitive Programming. Getting started with it is quite easy and if one devotes sufficient amount of time and effort, you can develop a very strong grasp of programming logic in relatively short amount of time.

Here are some steps to get started and be good at it.

Get comfortable writing code in either of one of these languages C, C++ or Java. Why only C, C++ or Java? Because these are the standard languages allowed in any programming competition.
If you are already good at C, it is suggested to learn C++. It is the most popular language among competitive programmers because of its speed and an excellent library in the form of STL (Standard Template Library).
Pick an online judge. Recommended ones are Topcoder and Codeforces. These sites have high quality of problems and also allow you to see other’s code post contest completion. These also categorize problems based on the topic. Some other popular judges include SPOJ, CodeChef (powered by SPOJ) andHackerEarth.
To begin with, start with simple problems that typically require transforming English to code and does not require any knowledge on algorithms. Solving Div 2 250 (Division 2, 250 points) in Topcoder or Div 2 Problem A in Codeforces is a good start.
At the early stages of programming one tends to write long pieces of code, which is actually not required. Try to keep codes short and simple.
Practice these problems until you become comfortable that you can submit it for 240 odd points on any day.
Start implementing basic(or standard) algorithms. It is suggested to read them from Topcoder tutorials orIntroduction to algorithms.

Some basic concepts that you should learn are

Graph algorithms: Breadth first search(BFS), Depth first search(DFS), Strongly connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST), Topological sort.
Dynamic programming: Standard dynamic programming problems such as Rod Cutting, Knapsack, Matrix chain multiplication etc.
Number theory: Modular arithmetic, Fermat’s theorem, Chinese remainder theorem(CRT), Euclidian method for GCD, Logarithmic Exponentiation, Sieve of Eratosthenes, Euler’s totient function.
Greedy: Standard problems such as Activity selection.
Search techniques: Binary search, Ternary search and Meet in the middle.
Data structures (Basic): Stacks, Queues, Trees and Heaps.
Data structures (Advanced): Trie, Segment trees, Fenwick tree or Binary indexed tree(BIT), Disjoint data structures.
Strings: Knuth Morris Pratt(KMP), Z algorithm, Suffix arrays/Suffix trees. These are bit advanced algorithms.
Computational geometry: Graham-Scan for convex hull, Line sweep.
Game theory: Basic principles of Nim game, Grundy numbers, Sprague-Grundy theorem.

The list is not complete but these are the ones that you encounter very frequently in the contests. There are other algorithms but are required very rarely in the contests.

You can find description and implementation of standard algorithms here.

Once you have sufficient knowledge of popular algorithms, you can start solving the medium level problems. That is Div 2 all problems in Topcoder and Codeforces. It is advisable not to go for Div 1 500 at this point.
Learning to code is all about practicing. Participate regularly in the programming contests. Solve the ones that you cannot solve in the contest, after the contest. Apart from Topcoder and Codeforces you can also look at HackerEarth Challenges or Codechef contests.
Read the codes of high rated programmers. Compare your solution with them. You can observe that it is simple and shorter than your solution. Analyse how they have approached and improve your implementation skills.
Read the editorials after the contest. You can learn how to solve the problems that you were not able to solve in the contest and learn alternative ways to solve the problems which you could solve.
Always practice the problems that you could solve in the contest. Suppose if you are able to solve Div 2 250 and 500 in the contest but not Div 2 1000 then practice as many Div 2 1000 problems as as you can.
Do not spend too much time if you are not getting the solution or are stuck somewhere.
After you feel that you have spent enough time, look at the editorials. Understand the algorithm and code it. Do not look at the actual solution before you have attempted to write the code on your own.
Programming is a very practical and hands on skill. You have to continuously do it to be good at it. It’s not enough to solve the problem theoretically, you have to code it and get the solution accepted. Knowing which algorithm/logic to use and implementing it are two different things. It takes both to be good at programming.
Programming learning phase is going to take a lot of time and the key is practicing regularly. It takes some time before you can attempt Div 1 500 and other tough problems. Do not give up on reading the editorials and implementing them, even if it takes many hours/days. Remember everything requires practice to master it.

It takes considerable amount of time before you get good at it. You have to keep yourself motivated throughout. Forming a team and practicing is a good choice. Not giving up is the key here.

Segment Trees

As some of you might be knowing, Segment Trees are special type of data structure for query and updating of intervals of array in logarithmic time.Basically segment trees store data of specific intervals of array in tree form. The root contains the whole array, it’s left child contain data of start index to middle index and right child contain data of middle index +1 to end index and so on. So the leaf nodes contain data of specific element of array.

Now the data of element I have been mentioning can be anything like the sum of elements or the max element or the min element etc. I have written the code in java for data containing sum of elements. A segment tree for an array of n elements uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of queried intervals.

The segment tree is stored in a form of heap so left child of node i is 2*i and right child of node i is 2*i+1. To build the segment tree for sum of particular range problem, I have recursively called the method for child nodes. The moment it is the leaf node, it will be the base case of the recursion so the parent will get the value of sum of its childrens values. In this way the whole tree will be created from bottom up.


private int[] treeNode;
private int maxsize;
private int height;

private final int STARTINDEX = 0;
private final int ENDINDEX;
private final int ROOT = 0;

public SegmentTree(int elements[])
{
  height = (int)(Math.ceil(Math.log(elements.length) / Math.log(2))); //height of segment tree is O(log(n))
  maxsize = 2 * (int) Math.pow(2, height) - 1;  //setting maxsize
  treeNode = new int[maxsize];
  ENDINDEX = elements.length - 1; //setting global variable to size of array given
  constructSegmentTree(elements, STARTINDEX, ENDINDEX, ROOT);  // calling method to construct tree from the array
}

private int getLeftChild(int pos){
   return 2 * pos + 1;
}

private int rightchild(int pos){
   return 2 * pos + 2;
}

private int constructSegmentTree(int[] elements, int startIndex, int endIndex, int current)
{
if (startIndex == endIndex) //base case or leaf node
{
   treeNode[current] = elements[startIndex];
   return treeNode[current];
}
int mid = (startIndex + (endIndex - startIndex) / 2);
treeNode[current] = constructSegmentTree(elements, startIndex, mid, getLeftChild(current))
+ constructSegmentTree(elements, mid + 1, endIndex, rightchild(current));
return treeNode[current];  // calling it recusively and setting the current node's value to sum of its children
}

Here’s the method to get result of query.

private int getSum(int startIndex, int endIndex, int queryStart, int queryEnd, int current)
{
if (queryStart &lt;= startIndex &amp;&amp; queryEnd &gt;= endIndex )  // base case
   return treeNode[current];

if (endIndex &lt; queryStart || startIndex &gt; queryEnd)  // current node is out of range
   return 0;

int mid = (startIndex + (endIndex - startIndex) / 2);
return getSum(startIndex, mid, queryStart, queryEnd, getLeftChild(current))
+ getSum( mid + 1, endIndex, queryStart, queryEnd, rightchild(current));  //recursively calling the query method and getting the result
}

public int query(int queryStart, int queryEnd)
{
if(queryStart &lt; 0 || queryEnd &gt; treeNode.length)  // if the query is out of range
  return -1;

return getSum(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT);
}

Here’s the code for updating the tree

private void updateTree(int startIndex, int endIndex, int updatePos, int update, int current)
{
if ( updatePos &lt; startIndex || updatePos &gt; endIndex) //update pos out of range
   return;
treeNode[current] = treeNode[current] + update;  // if current node comes under the range to update, update it first and then call the method on its children
if (startIndex != endIndex)
{
  int mid = (startIndex + (endIndex - startIndex) / 2);
  updateTree(startIndex, mid, updatePos, update, getLeftChild(current));
  updateTree(mid+1, endIndex, updatePos, update, rightchild(current));
}
}

public void update(int update, int updatePos, int[] elements)  // This method first calculates the diff to be added in each of the required nodes and then calls the method on the root of the tree
{
   int updatediff = update - elements[updatePos] ;
   elements[updatePos] = update;  //the elements of the array are updated first
   updateTree(STARTINDEX, ENDINDEX, updatePos, updatediff, ROOT);  
}

This is the test run

 public static void main(String args[])
	    {
	        int[] elements = {1,2,3,4,5,6,7,8,9};
	        SegmentTree segmentTree = new SegmentTree(elements); //creating the segment tree
	        int sum = segmentTree.query(1, 4);  //querying for sum of elements in range 1-4
	 
	        System.out.println("the sum is " + sum);
	        segmentTree.update(3, 1,elements); // updating the tree
	        sum = segmentTree.query(1, 4); //getting the updated result
	        System.out.println("the sum is " + sum);	
	    }

And the output is

the sum is 14
the sum is 15

Segment tree stores cumulative values of all intervals of the array and each interval can be accessed in logarithmic time, segment tree can be very helpful for problems like range min or max or range sum which have large amount of queries.
Also if there is large amount of updates given in the problem the segment tree may not survive, for that lazy propagation comes in handy which I will discuss in my next blog.
Here is the link to 60 problems relating to segment trees,try them to get a hold of the topic
problems on segment trees

By the way,this is my first blog so feel free to write any suggestions in comments.

Keep learning!

Parth Panchal

Daily Programming Dose day 3

You have a circle of radius r and center in point (x, y). You want the circle center to be in new position (x‘, y‘).

In one step you can put a pin to the border of the circle in a certain point, then rotate the circle around that pin by any angle and finally remove the pin.

What are the minimum number of steps in which the goal could be achieved?

Input

Input consists of 5 space-separated integers r, x, y, x‘ y‘ (1 ≤ r ≤ 10⁵, - 10⁵ ≤ x, y, x‘, y‘ ≤ 10⁵), circle radius, coordinates of original center of the circle and coordinates of destination center of the circle respectively.

Output

Output a single integer — minimum number of steps required to move the center of the circle to the destination point.

Sample test(s)

input

2 0 0 0 4

output

input

1 1 1 4 4

output

input

4 5 6 5 6

output

Note

In the first sample test the optimal way is to put a pin at point (0, 2) and rotate the circle by 180 degrees counter-clockwise (or clockwise, no matter).

Daily Programming Dose Day 2 Solutions

In order to calculate the minimum possible lifted weight, we should find the initial stack first. Let’s find the positions one by one.

First, let’s decide the position of book b₁. After day 1, book b₁ will be on the top of the stack, regardless of the order of the initial stack. Therefore, in order to minimize the lifted weight during day 1, book b₁ must be on the top of the initial stack. (so actually, in day 1, you won’t lift any book)
Next, let’s decide the position of book b₂. (assume that b₁ ≠ b₂ for simplicity) Currently, b₁ is on the top of the stack, and it cannot be changed because of the procedure. Therefore, in order to minimize the lifted weight during day 2, book b₂ must be immediately below book b₁.

Considering this, we can find the optimal strategy to create the initial stack: Scan b₁, b₂, …, b_m step by step. Let’s assume that I am handling b_i now. If b_i has appeared before (formally, if $\text{[math]}$ ), erase b_i from the sequence. Otherwise, leave b_i. The resulting sequence will be the optimal stack.

You should note that it is not necessary for you to read all the books during 2015, which means the size of the resulting sequence may be smaller than n. The books which doesn’t appear in the resulting sequence must be in the bottom of the initial stack (obviously). However, this problem doesn’t require us to print the initial stack, so it turned out not to be important.

In conclusion, finding the initial stack takes O(n + m) time.

After finding the initial stack, we can simulate the procedure given in the statement naively. It will take O(nm) time.

Time: O(nm)
Memory: O(n + m)

You could also check out my solution at :

http://ideone.com/Ji4WHx

Daily Programming Dose Day 2

You have N books numbered by integers from 1 to N. The weight of the i-th (1 ≤ i ≤ N) book is wi.
You keep the N books by stacking them vertically.
When you wants to read a certain book x, you should follows the steps described below.

1.You lift all the books above book x.
2.You push book x out of the stack.
3.You put down the lifted books without changing their order.
4.After reading book x, you put book x on the top of the stack.

Now you decided to read books for m days. In the j-th (1 ≤ j ≤ m) day, you will read the book that is numbered with integer b_j (1 ≤ b_j ≤ n). To read the book, you have to use the process described in the paragraph above. It is possible that you may decides to re-read the same book several times(You are seriously a book worm).

Now the problem is that you have to rearrange the books such that the weight of books that you have to lift should be the minimum.

Input

The first line contains two space-separated integers n (2 ≤ n ≤ 500) and m (1 ≤ m ≤ 1000) — the number of books, and the number of days for which you would read books.

The second line contains n space-separated integers w₁, w₂, …, w_n (1 ≤ w_i ≤ 100) — the weight of each book.

The third line contains m space separated integers b₁, b₂, …, b_m (1 ≤ b_j ≤ n) — the order of books that you would read. Note that you can read the same book more than once.

Output

Print the minimum total weight of books he should lift, which can be achieved by rearranging the order of stacked books.

Sample test(s)

input

3 5
1 2 3
1 3 2 3 1

output

Note

Here’s a picture depicting the example. Each vertical column presents the stacked books.

note here that if the arrangement of books would have been 1 2 3 the the total weight would have been quite different.(See by yourself)

The Programming Club @ DA-IICT

for(i=0;i<n;i++)

Month: January 2015

Daily Programming Dose Day 5

Daily Programming Dose Day 4 Solutions

Lazy Propagation in Segment Trees

Daily Programming Dose Day 4

Daily Programming Dose Day 3 Solutions

Learn to Code

Segment Trees

Daily Programming Dose day 3

Daily Programming Dose Day 2 Solutions

Daily Programming Dose Day 2