A checklist for every Computer Science student

The below List contains essential things according to me a computer science student should know. Please add your views in comments. Email: Access e-mail system using username and password Change username-password. Receive / read an e-mail message Reply to an e-mail message Compose and send an original e-mail message Attach a file to an e-mail message Meaning of cc, bcc etc. To create a letter or essay, which software program would be the best choice to use? Other than CAPS LOCK, which key can you use to insert uppercase/capital letters in a document? Tell about these things Firefox, chrome, power point, excel, ms word etc. how to check whether an e-mail address is valid or not? valid email address. concept of ip address. concept of LAN. name some good search engines. Use of search engines etc. create a directory, edit files, search files, Use of ls, pwd, rm, mv, cp command. How to rename a file using mv command? How to delete a directory. How to open application through command line? How to open two programs simultaneously from your terminal? Concept of chmod, permissions, installing softwares, installing linux on your computer. How to print your files on cse ground labs? Learn use of ppr command. image editor? how to create presentations in linux or windows? how can you select multiple files from a list of files ? how to permanently delete the files? keyboard shortcuts for cut, copy, paste, changing the tabs, cut/copy/paste from terminal, open terminal, close terminal, saving a file, save as, delete a file, help, closing a program, for capitalizing a letter, for opening a new tab in browser, closing a tab in browser, refreshing the webpage, changing the current tab to another tab in browser. undo, redo, bold, italic etc. click, double click, right click, scrolling etc. concept of bits, byte, RAM, ROM, hard disk. What is inside the CPU? dragging a file what is an operating system? names of famous operating systems? meaning of www, ip, netmask, LAN etc. wikipedia. search an article. create your account. edit article. know about stackoverflow, mathoverflow, stackexchange, etc. sites? know about programming competitions like ACM-ICPC, visit spoj, topcoder.com, codechef, codeforces etc. know about top online courses of the universities around the world eg. nptel, coursera, OCW search a paper on google scholar. search for graph making softwares on web. (hint: you can use google too) create online netbanking and learn how to do online transcations. how to online order books or any other goods online? how to use google drive, google doc, creating google forms, how to create blog ? Famous sites for creating your blog? how to create a profile on social networking sites like facebook, G+, quora, twitter? how to maintain your home page? google search: how to search on a specific site? how to use it as a calculator? how to search for a specific file? how to search exact phrases? know about DC++ how to change proxy in your browser? increase your typing speed, search for good typing speed increasing softwares. how to change passwords of your computers? concept of root user on linux?, sudo etc. concept of ssh and scp. creating bookmarks. how to write README files?

Strtok Function in C

    string s;
    getline(cin,s);
    char *pch;
    char str[10000];
    // you s.c_str() returns a const char * pointer you can not directly cast to char *, Hence char * str=s.c_str() will give you compilation error, Hence allocate the memory for str first and then use strcpy function to copy the constant string into the memory.
    strcpy(str,s.c_str());
 
    pch=strtok(str,"-");
    // gives you the first token, if it is NULL, all the characters in the string were from delimeters.
    while(pch!=NULL)
    {
        printf("HI%sHI\n",pch);
        // in the subsequent calls, always pass NULL.
        pch=strtok(NULL,"-");
    }
 
    // note that str is getting changed by the the strtok function.

You can also do the same thing in this way too.
vector split(string s, string del = " ") { char *word, *buf, *delim; vector res; delim = strdup(del.c_str()); buf = strdup(s.c_str()); for (word = strtok(buf, delim); word; word = strtok(0, delim)) res.push_back(string(word)); free(buf); free(delim); return res; }

strdup can also be used instead of strcpy, but you should never forget to free the memory, though most of time not necessary in contests.

Refereneces 
http://www.cplusplus.com/reference/cstring/strtok/
http://apps.topcoder.com/forums/?module=Thread&threadID=672251&start=0

IOPC editorials

You can download the editorial from here.
https://drive.google.com/file/d/0B8cc7eHcqRVNd240QklvTE1kLU0/edit?usp=sharing

Invitation for participation in IOPC 2014, IIT Kanpur

The Department of Computer Science & Engineering, Indian Institute of Technology, Kanpur (http://cse.iitk.ac.in/) and the Techkriti team](http://techkriti.org/) presents the 2014 edition of IOPC, the annual International Online Programming Contest of IIT Kanpur. This 24 hour long contest will have you competing with some of the best coders in the world in solving problems of an algorithmic nature.

IOPC 2014 will be held from 1200 hrs on March 1st to 1200 hrs on March 2nd (IST) http://www.timeanddate.com/worldclock/fixedtime.html?msg=IOPC+2014&iso=20140301T12&p1=539&ah=23&am=59. Teams of upto 3 members can participate in the contest. To be eligible for prizes, the teams need to be comprised of students who are currently registered in some university only.

IOPC 2014 will be hosted on Directi's Codechef platform .Please register on the contest page(http://www.codechef.com/IOPC2014) . Teams need to register on the [IOPC](tiny.cc/iopc2014) site as well to be eligible for prizes.

Visit the Codechef contest page(http://www.codechef.com/IOPC2014) and the IOPC site (http://tiny.cc/iopc2014) for rules and more details.
Join us on our FB event page (https://www.facebook.com/events/696412627048318/) for more updates.

You can view last years problems at codechef.
http://www.codechef.com/IOPC2011
http://www.codechef.com/IOPC2012
http://www.codechef.com/IOPC2013

See you in the contest !!!!

WPC # 4 Editorials

First of all I want to say you sorry for not making some really easy problems. Next time I will make sure that this does not happen :) First time experimenting latex in editorials, Hope you will like it :)


Editorials:
Gopu and Frogs:
     If you have not come across permanent problem, Then look at  http://en.wikipedia.org/wiki/Permanent. As might you read permanent can used to find number of perfect matchings in a graph. Now you have to find perfect matchings in this case too, but in this case, you select an edge by some probability. So you just add this constraints to the problem.
   For finding number of perfect matchings in a graph, you can use a dp with bitmask in O($2^n n$).
   See the code of http://www.codechef.com/viewplaintext/460759 of uwi. go to permanent section.
   Problems to solve: http://www.codechef.com//problems/IOPC1114. You can also see its explanation by Raziman TV on http://razimantv.files.wordpress.com/2011/02/booklet1.pdf.
  
Arrangement Validity:
  From the earlier arrangement validity problem in the first part, you might have known the condition of when the answer is not possible. Go solve the problem for more clarity http://www.spoj.com/problems/SPCU/.
  Now how to build a correct order. (Exercise) You can prove that if answer exists then it is unique. Go from right to left, Suppose what is the height of last person you can have is smallest positive integer which is not equal to a[n - 1]. eg in case of last person having a[i] = 2, You can have height = 1. in case of 1, you can have 2.
   So on generalizing this, you are on the $i^{th}$ from back and you want to know its height, You have to answer queries like this. Find smallest positive integer which is not equal to any of the values from a[i + 1] to a[n - 1]. You can use segment tree or BIT for this kind of queries.
   Try solving http://www.spoj.com/problems/ORDERSET/ for getting more insight into the solution.

Maggu and Weird Things.
 This problem is really lovely problem. You can use matrix exponentiation to solve this problem. Hints of constraints being n $\leq$ 50 and m  $ \leq 10^9$.
  Basically each transformation can be characterized by a matrix multiplication. For doing the first operation, you can create matrix really easily. First try creating matrix for only operation 1, Take simple test cases, You will notice the pattern very fast.
 See the marix for only operation 1, Assume n = 4, k = 2

$ \\[ \\left( \\begin{array}{ccc}
1 & -1 & 0 & 0 \\\\
0 & 1 & -1 & 0\\\\
0 & 0 & 1 & -1 \\\\

-1 & 0 & 0 & 1\\\\

\\end{array} \\right)\\] $

Did you guys notice the pattern, if yes, then formalize the intuition.


Now let us see the case of swapping the $i^{th}$ and $(i+1)^{th}$ element.
For this you can swap two consecutive rows of matrix obtained in the first step.
ie.

$ \[ \left( \begin{array}{ccc}
0 & 1 & -1 & 0\\ 

1 & -1 & 0 & 0 \\

-1 & 0 & 0 & 1\\ 
0 & 0 & 1 & -1 \\

\end{array} \right)\] $

Now you have got your matrix, Exponentiate it n times ($\mathbb{O}$ ($n^3$ log m) and enjoy yourselves :)

Maggu and Magguness Level:
  This problem is so cute to solve. Believe me if you have not solved upto now, first solve yourself.
First let us detect when answer will be -1, When there exists cycles in the graph, You will get contradictions and hence will be -1. eg 1-> 2 and 2 -> 3 and 3 -> 1 is not possible.
  Now for first find the vertices which are connected to the vertex id in the graph. Also find the number of vertices which are connected to it in the reverse graph. Call the first number A and second number B. Then the answer to the problem should be all the number from B to N - A + 1.
 Take examples and try solving the problem.

Petya and Repairment of Roads.
  This problem is really famous. See http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf.
This book is really a gem book. See its exercise 3.2, Our problem is similar to this. Now use the hint provided in book and solve the problem.
 
Also solve http://www.codechef.com/problems/RHOUSE.

Maggu and Mystery:
   In simplified language problem is to find min no of operations needed to do on a array to get atleast d distinct elements. In a single operations you can increase or decrease the $i^{th}$ element by atmost $v_i$.
Solution is to use min-cost max flow. Note that it wont make any sense to convert a number into less than -250 (As n $\leq$ 50 and $v_i$ $\leq$ 5) and greater than 1250. So a make a graph of n nodes on one side and 1250 + 250 nodes on the other sides. For each edge add the capacity of 1 and cost equal to $ceil (abs (a_i - j), v_i$. You need to add two special vertices, start and target vertices. Connect first n vertices to start vertex using 1 cap and 0 cost. and similarly connect the target vertex to all the $j^{th}$ vertices (ie vertices on the second part).

Maggu and Vectors : (Wrriten by Abhilash Kumar)

In this problem we have to check that do 3 vectors a,b,c exists such that :

    abc=0

Because we have assumed vectors to as non-directional like a simple line segment which can be shifted along x and y axes but its orientation cannot be altered.

It can be easily noticed that solution to above equation exists if solution for one of these equation exists:

    a+b=c

    b+c=a

    c+a=b

As the x and y components lie between -1000 and 1000 we can simply precompute sum of each pair of vectors and store in  an 2-D array of bool of size 4000*4000 which denotes that is sum of two vectors equals to that index exists or not(as we can not have negative indexes we can simply shift origin by 2000 to take care of it). And later check for each vector that do we have a sum of which equals  of this vector.If any vector satisfy this then we have a solution else no.

Complexity = $\mathbb{O} ( 4000*4000 + n^2 + n )$

 Note: Many wrong answer occurred because people were also counting non-degenerate triangle.

To avoid this problem we just had to add only non-zero vectors that were non-parallel .

Maggu and Triangles : (Written by Abhilash Kumar)

We have to find number of non-congruent triangles with perimeter N.

The answer to this question is Alcuin's sequence Nth element of this sequence is coefficient of $x^n$ in $x^3/((1-x^2)*(1-x^3)*(1-x^4))$.

After solving the above sequence (as done here) we get :

    $T_n = < (n+3)^2 / 48 > $ when n is odd.
              = $ < n^2 / 48> $ if n is even.

where $ < > $ denotes the nearest integer to x . Note that here x will never be exactly between two integers.

A Cross Product Formula

\[\mathbf{V}_1 \times \mathbf{V}_2 =  \begin{vmatrix}
\mathbf{i} & \mathbf{j} & \mathbf{k} \\
\frac{\partial X}{\partial u} &  \frac{\partial Y}{\partial u} & 0 \\
\frac{\partial X}{\partial v} &  \frac{\partial Y}{\partial v} & 0
\end{vmatrix}  \]

 

Multiplication of two long numbers modulo a long number.

LL multiplication (LL a, LL b, LL mod) {
    LL res = (a * ((long double) b / (long double) mod));

    // put the number in long double, and then reduce the value to LL, forget 

    overflow.

    res = a * b - res * mod;
    if (res >= mod) res -= mod;
    if (res < 0) res += mod;
    return res;
}

WCP #3 And Editorials

WPC #3 was held on this sunday. http://aca.cse.iitk.ac.in/public/
Problems have been moved to spoj.

Editorials: (these editorials are merely hints, You need to work things yourself for final answers)
Hope you will like them. Leave a comment if something is unclear or needs to be modified, Also leave your opinion about the contest.

1. Gopu and Palindromes: (http://www.spoj.com/problems/SPCS/)

     Consider the string s. Let it has some consecutive characters of length L, Then you can directly replace L by just 1 character. After such replacements just check if the string is palindrome or not?
     eg. s = "ababbbaaa".
           s = "ababa". Replace bbb with b and aaa with a.
     You need to do this in O(n).

2.Gopu and Validity of Arrangement: (http://www.spoj.com/problems/SPCU/)
   You can easily prove that if answer exists then it is unique, Only condition you need to check that any ith indexed person does not say that $\ge$ i persons are before him. You can relate this problem with permutations.

3. Gopu and Digits Divisibility: (http://www.spoj.com/problems/SPCU/)
   You can easily do a brute force. Think about it why this works, Hint: for checking divisibility by 9, sum of digits should be divisible by 9. (Though hint is not of great use in the proof).

4. Gopu and Function: (http://www.spoj.com/problems/SPCM/)
    Value of n will be atleast halved in each computation of f. As Take the best cases when n = 2*p where p is prime, Sum of divisors is 2 + p which is 2 + n / 2. In other cases, sum would be even less than n/2. For finding prime divisors of n, use simple sqrt algorithm. Final complexity would be O($\sqrt[2]{n}$ logn).

5. Gopu and Create Collections Part two (http://www.spoj.com/problems/SPCJ/)
   You can use dp over the tree for solving this. You can use a greedy algo also. Sort the numbers in increasing order, go from right to left and for each number K if you find a number K/2 which is not yet taken then take it and add it to answer.
   You can also use greedy algorithm by constructing the binary tree explicitly and then going from leaves to the root of the tree.

6. Gopu and Combinatorics on Graphs: (http://www.spoj.com/problems/SPCE/)
  This is standard problem. You should know http://en.wikipedia.org/wiki/Cayley%27s_formula. Then figuring out things wont be tough. I dont want to give formulla as I want you to work it out.

7. Gopu and Counting bitwise prime numbers: (http://www.spoj.com/problems/SPCO/)
   This problem had one slow solution:
     use dp(i, tight): where i denotes the position in the binary representation of the number (i goes from most significant digit to lower), tight denotes wheteher the current number has overshoot the number n or n. See my slow code http://ideone.com/numnIE.
    You can optimize it slightly and get it passed. Basically think in terms of combinatorics, You will get the idea.