Saturday, 27 July 2013

Here is the rank list for the series "C For Code" after 2 contests. 6 contests are still left, lets see how much it changes:
Rank Name    Prob 1   Prob 2  Prob 3 Contest 2   Grand Total
1 Vijay Tripathi 189.94 269.42 460.42 919.78 1773.93
2 Karan Khullar 195.89 203.44 500.00 899.33 1743.24
3 Amit Jain 197.57 150.00 388.29 735.86 1483.92
4 Gourav Pathak 195.94 0.00 371.30 567.24 1387.71
5 Anuj Kumar 177.63 150.00 399.12 726.75 1270.99
6 Vaibhav Sethi 200.00 150.00 0.00 350.00 1207.66
7 Mayank Yadav 164.00 207.36 0.00 371.36 814.74
8 Abhinav Saraswat 176.70 0.00 0.00 176.70 739.41
9 Vishesh Srivastava 193.72 150.00 0.00 343.72 736.79
10 Prakhar Rastogi 195.78 150.00 0.00 345.78 699.89
11 Sumit Awasthi 140.02 0.00 0.00 140.02 661.36
12 Ashish Ranjan 194.69 0.00 0.00 194.69 623.20
13 Inderjeet Yadav 182.91 0.00 0.00 182.91 599.87
14 Prakhar Rastogi 197.63 0.00 0.00 197.63 560.28
15 Prateek Nischal 155.63 204.14 0.00 359.77 556.58
16 Arup Das 190.83 219.94 0.00 410.78 547.59
17 Anant Kumar 196.48 161.25 0.00 357.73 526.97
18 Nitish Gupta 174.59 150.00 0.00 324.59 519.61
19 Law Kumar 100.00 0.00 0.00 100.00 475.00
20 Shashank Shekhar 197.31 270.00 0.00 467.31 467.31
21 John Bupit (Mohit) 183.83 273.03 0.00 456.86 456.86
22 Aman Jain 188.59 0.00 0.00 188.59 416.59
23 Rohit Kumar 189.69 0.00 0.00 189.69 387.13
24 Robin Parashar 191.89 0.00 0.00 191.89 386.19
25 Yogendra Singh Vimal 187.41 0.00 0.00 187.41 382.02
26 Sujay Raj 184.56 0.00 0.00 184.56 374.56
27 Anil Bakhla 182.06 0.00 0.00 182.06 370.78
28 Edge_123 (Jayant) 165.81 0.00 0.00 165.81 363.65
29 Ashawani Chandil 188.89 0.00 0.00 188.89 361.43
30 Siddharth Behera 0.00 0.00 0.00 0.00 361.04
31 Adhiraj Nakhe 191.24 163.97 0.00 355.21 355.21
32 Pawan Deshmukh 188.87 0.00 0.00 188.87 352.76
33 Saurabh Prasad 176.26 0.00 0.00 176.26 351.43
34 Ashish Bahukhandi 189.61 0.00 0.00 189.61 337.59
35 Nikhil Dubey 193.28 0.00 0.00 193.28 335.11
36 Ravi Gupta 187.02 0.00 0.00 187.02 332.94
37 Anuj Asher 129.78 0.00 0.00 129.78 326.94
38 Pavan Kriplani 192.19 0.00 0.00 192.19 317.78
39 Ankur Agrawal 188.69 0.00 0.00 188.69 312.09
40 Rahul Kumar Yadav 194.57 0.00 0.00 194.57 294.57
41 Gayathri Devi 133.37 0.00 0.00 133.37 291.22
42 Deep Kumar Sakre 151.85 0.00 0.00 151.85 288.89
43 Akshay Agrawal 188.44 0.00 0.00 188.44 288.44
44 Anil Yadav 186.35 0.00 0.00 186.35 286.35
45 Anjaney Pandey 100.00 0.00 0.00 100.00 283.00
46 Sravan Kumar 134.19 0.00 0.00 134.19 234.19
47 Swapnil Gupta 117.87 0.00 0.00 117.87 217.87
48 Deepak Gupta 110.15 0.00 0.00 110.15 210.15
49 Anish Somani 106.44 0.00 0.00 106.44 206.44
50 Hitesh Sharma 100.00 0.00 0.00 100.00 200.00
51 Rohit Kumar 0.00 0.00 0.00 0.00 195.46
52 Harshit Gupta 188.65 0.00 0.00 188.65 188.65
53 Sakshi Gopal 0.00 0.00 0.00 0.00 188.15
54 Ashish Awasthi 0.00 0.00 0.00 0.00 186.43
55 Tushar Turkar 174.19 0.00 0.00 174.19 174.19
56 Kumar Vikram 171.35 0.00 0.00 171.35 171.35
57 Umang Popli 170.07 0.00 0.00 170.07 170.07
58 Naveen Yadav 167.07 0.00 0.00 167.07 167.07
59 Saurav Kothari 0.00 0.00 0.00 0.00 166.50
60 Abhishek Raj 164.50 0.00 0.00 164.50 164.50
61 Niraj Kumar 0.00 0.00 0.00 0.00 148.98
62 Priya Kumari 144.87 0.00 0.00 144.87 144.87
63 Mohit Srivastava 0.00 0.00 0.00 0.00 139.02
64 Prakash Tripathi 0.00 0.00 0.00 0.00 133.02
65 Raghav Agarwal 117.26 0.00 0.00 117.26 117.26
66 Pawan Kumar 107.06 0.00 0.00 107.06 107.06
67 Tarun Jindal 103.11 0.00 0.00 103.11 103.11
68 Aadil Khan 100.00 0.00 0.00 100.00 100.00
68 Rajan Ranbir 100.00 0.00 0.00 100.00 100.00
68 Amit Kumar Verma 100.00 0.00 0.00 100.00 100.00
68 Sshantanu Agarwal 100.00 0.00 0.00 100.00 100.00
68 Gaurav Patel 100.00 0.00 0.00 100.00 100.00
68 Mohammad Ahmed 100.00 0.00 0.00 100.00 100.00
68 Shubham Dixit 100.00 0.00 0.00 100.00 100.00
68 Kuljeet Singh 100.00 0.00 0.00 100.00 100.00
68 Yogendra Singh 100.00 0.00 0.00 100.00 100.00
68 Koteswara Rao 0.00 0.00 0.00 0.00 100.00
68 Krishan Kant Mangla 0.00 0.00 0.00 0.00 100.00
68 Raj Dosi 0.00 0.00 0.00 0.00 100.00
68 Shubham Kumar 0.00 0.00 0.00 0.00 100.00

Friday, 26 July 2013

Editorials - C For Code 02 - Coding Club - ISM Dhanbad

Cartman Reverses String 200 pts

Difficulty Level: Cake Walk

Just take the input in a string (character array), find the no. of elements in the string and start printing character by character from the end of the string.

Here is the code for the problem:




Raise the Power 300 pts

Difficulty Level: Easy
Prerequisite: Divide and Conquer, Modular Arithmetic

If you are not acquainted with basic modular arithmetic, I recommend you to read basic number theory. Here are some modular arithmetic properties that are used here:
(A*B) mod M = (A mod M) * (B mod M)
(A^B) mod M = (A mod M) ^ B
Now since A can be as large as 10^18, we first take A=A mod (1,000,000,007).
Let me show the algorithm for solving A^B if B is very large with an example.
Let A = 3 and B = 18.
3^18 = (3^9) * (3^9)
3^9 = 3 * (3^4) * (3^4)
3^4 = (3^2) * (3^2)
3^2 = 3 * 3
So, we calculated 3^18 in just 4 steps. In this manner we can calculate A^B in O(log B).

Here is the code for this problem:




How to Handle the Fans 500 pts

Difficulty Level: Medium
Prerequisite: Binary Indexed Tree

Binary Indexed Tree is a data structure that is used to calculate the cumulative frequency. If we use an array to store the no. of fans at each point and then count them one by one, the time complexity will become O(N*Q) and it will give TLE.
Binary Indexed Tree allow us to update the no. of fans at each point and count the no. of fans from office A to B in log N steps. So the time complexity of algorithm will be O(Q * log N), this will work fine.
To read about Binary Indexed Trees, please read this:

Here is the solution for this problem:



Saturday, 20 July 2013

Here is the Rank List for the Series "C For Code" after the first contest. Problem 1 was for 200 points, Problem 2 was for 350 points and Problem 3 for 450 points. 

Rank Name  Problem 1 Problem 2 Problem 3            Total
1 Vaibhav Sethi 196.87 264.12 396.67 857.66
2 Vijay Tripathi 168.35 277.05 408.75 854.15
3 Karan Khullar 179.78 277.21 386.92 843.91
4 Gourav Pathak 163.69 296.79 360.00 820.47
5 Amit Jain 195.22 175.00 377.83 748.06
6 Abhinav Saraswat 196.50 0.00 366.21 562.71
7 Anuj Kumar 194.24 350.00 0.00 544.24
8 Sumit Awasthi 157.26 0.00 364.08 521.34
9 Mayank Yadav 197.54 245.84 0.00 443.38
10 Ashish Ranjan 198.00 230.51 0.00 428.51
11 Inderjeet Yadav 151.00 265.97 0.00 416.97
12 Vishesh Srivastava 195.61 197.46 0.00 393.07
13 Law Kumar 200.00 175.00 0.00 375.00
14 Prakhar Rastogi 187.65 175.00 0.00 362.65
15 Siddharth Behera 186.04 175.00 0.00 361.04
16 Prakhar Rastogi 179.11 175.00 0.00 354.11
17 Aman Jain 0.00 0.00 228.00 228.00
18 Jayant Tiwari 197.83 0.00 0.00 197.83
19 Rohit Kumar 197.44 0.00 0.00 197.44
20 Anuj Asher 197.17 0.00 0.00 197.17
21 Prateek Kumar Nischal 196.81 0.00 0.00 196.81
22 Rohit Kumar 195.46 0.00 0.00 195.46
23 Nitish Gupta 195.02 0.00 0.00 195.02
24 Yogendra Singh Vimal 194.61 0.00 0.00 194.61
25 Robin Parashar 194.30 0.00 0.00 194.30
26 Sujay Raj 190.00 0.00 0.00 190.00
27 Anil Bakhla 188.72 0.00 0.00 188.72
28 Sakshi Gopal 188.15 0.00 0.00 188.15
29 Ashish Awasthi 186.43 0.00 0.00 186.43
30 Anjaney Pandey 183.00 0.00 0.00 183.00
31 Saurabh Prasad 175.17 0.00 0.00 175.17
32 Ashawani Chandil 172.54 0.00 0.00 172.54
33 Anant Kumar 169.24 0.00 0.00 169.24
34 Saurav Kothari 166.50 0.00 0.00 166.50
35 Pawan Deshmuch 163.89 0.00 0.00 163.89
36 Gayathri Devi 157.85 0.00 0.00 157.85
37 Niraj Kumar 148.98 0.00 0.00 148.98
38 Ashish Bahukhandi 147.98 0.00 0.00 147.98
39 Ravi Gupta 145.93 0.00 0.00 145.93
40 Nikhil Dubey 141.83 0.00 0.00 141.83
41 Mohit Srivastava 139.02 0.00 0.00 139.02
42 Deep Kumar Sakre 137.04 0.00 0.00 137.04
43 Arup Das 136.81 0.00 0.00 136.81
44 Prakash Tripathi 133.02 0.00 0.00 133.02
45 Pavan Kriplani 125.59 0.00 0.00 125.59
46 Ankur Agrawal 123.41 0.00 0.00 123.41
47 Akshay Agrawal 100.00 0.00 0.00 100.00
47 Anil Yadav 100.00 0.00 0.00 100.00
47 Anish Somani 100.00 0.00 0.00 100.00
47 Deepak Gupta 100.00 0.00 0.00 100.00
47 Hitesh Sharma 100.00 0.00 0.00 100.00
47 Koteswara Rao 100.00 0.00 0.00 100.00
47 Krishna Kumar Meena 100.00 0.00 0.00 100.00
47 Rahul Kumar Yadav 100.00 0.00 0.00 100.00
47 Raj Dosi 100.00 0.00 0.00 100.00
47 Shubham Kumar 100.00 0.00 0.00 100.00
47 Sravan Kumar 100.00 0.00 0.00 100.00
47 Swapnil Gupta 100.00 0.00 0.00 100.00

Thursday, 18 July 2013

Editorials - C For Code 01 - Coding Club - ISM Dhanbad

Problem: Easy One For Cartman

This problem was a cakewalk. We know the first term A, second term B and the no. of terms N. So common difference is D=B-A.

Formula for sum of A.P. is
Sum = ( N * ( 2 * A + (N-1) * D ) ) / 2

So, Here is the code for this problem:

http://www.codechef.com/viewplaintext/2388336




Problem: Butters Counting Problem

Prerequisite: Binary Search.

Ok, for the beginners just assume that a computer can perform around 10^8 operations per second. From this you will get an idea of Time Limit. Time Limit for this problem was 1 second.
There were "Q" queries and "N" numbers. If you perform a linear search for every query, the time complexity will be O(Q * N)
Maximum possible value of Q * N is (10^5)*(10^5) i.e. 10^10, so this is for sure that this approach will give time limit exceeded.
On the other hand, if we perform Binary Search on the N numbers for each query, the time complexity will be O(Q * log N), its maximum value will be (10^5)*log(10^5), i.e. around 2 * 10^6, so it should run within the time limit.
So we have to use Binary Search here. Since the numbers are given in sorted order, we can directly perform binary search on it. We should search for the smallest element that is greater than "L" in the list. But there can be a case when such element does not exist, i.e. all the elements are less than or equal to "L". So we can make a separate code for this case, and all the other cases can be solved by binary search.

Here is the code for this problem:

http://www.codechef.com/viewplaintext/2389023

For more help on binary search you can read this tutorial:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch




Problem: Kyle Makes a List

Prerequisite: Longest Increasing Subsequence Problem, Dynamic Programming

if (x,y) and (a,b) are two consecutive pairs in the list then, y<a, also for every pair x<y and a<b
So, we conclude that x<a for every consecutive pairs. So our first step must be to sort the given pairs according to their first co-ordinate, and if first co-ordinates are same, then according to second co-ordinates.

After this we perform a variation of Longest Increasing Subsequence. A very nice explanation is given here:

http://www.geeksforgeeks.org/dynamic-programming-set-20-maximum-length-chain-of-pairs/

For Longest Increasing Subsequence Problem, read this:

http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/

Here is the solution to this problem: (I have used vectors and pairs in this solution, those who are not familiar with them, I recommend you to learn about vectors atleast as they are very powerful templates to solve problems easily on online algorithmic contests)

http://www.codechef.com/viewplaintext/2389120