tag:blogger.com,1999:blog-67042267676468062182024-03-07T23:08:22.582-08:00Programming and Algorithmspraveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.comBlogger30125tag:blogger.com,1999:blog-6704226767646806218.post-47717169084424523322014-07-18T06:16:00.003-07:002014-07-18T06:18:03.350-07:00A checklist for every Computer Science student<div dir="ltr" style="text-align: left;" trbidi="on">
<table align="center" border="0" cellpadding="2" cellspacing="0" style="width: 98%px;"><tbody>
<tr><td bgcolor="#dcdcdc"></td></tr>
<tr><td bgcolor="#ffffff"><tt></tt><br />
<pre><tt>The below List contains essential things according to me a</tt></pre>
<tt>
</tt>
<pre><tt>computer science student should know. Please add your views in comments.</tt></pre>
<tt>
<pre></pre>
<pre></pre>
<pre>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?</pre>
</tt></td></tr>
</tbody></table>
</div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com1tag:blogger.com,1999:blog-6704226767646806218.post-62743593935178415342014-03-20T04:03:00.000-07:002014-03-20T04:15:24.795-07:00Strtok Function in C<div dir="ltr" style="text-align: left;" trbidi="on">
string s;<br />
getline(cin,s);<br />
char *pch;<br />
char str[10000];<br />
// 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.<br />
strcpy(str,s.c_str());<br />
<br />
pch=strtok(str,"-");<br />
// gives you the first token, if it is NULL, all the characters in the string were from delimeters.<br />
while(pch!=NULL)<br />
{<br />
printf("HI%sHI\n",pch);<br />
// in the subsequent calls, always pass NULL.<br />
pch=strtok(NULL,"-");<br />
}<br />
<br />
// note that str is getting changed by the the strtok function.<br />
<br />
You can also do the same thing in this way too.<br />
<span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;">vector<string> split(</string></span><span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"><b>string</b></span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"> s, </span><span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"><b>string</b></span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"> </span><span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"><b>del</b></span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"> = </span><span style="background-color: white; color: red; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;">" "</span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;">)
</span><span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;">{</span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"> </span><span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"><b>char</b></span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"> *word, *buf, *delim;
vector<string> res;
delim = strdup(del.c_str());
buf = strdup(s.c_str());
</string></span><span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"><b>for</b></span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"> (word = strtok(buf, delim); word; word = strtok(0, delim))
res.push_back(</span><span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"><b>string</b></span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;">(word));
free(buf);
free(delim);
</span><span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"><b>return</b></span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"> res;
</span><span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;">}</span><span style="background-color: white; color: #990000; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;">
</span><br />
<div>
<span style="background-color: white; color: navy; font-family: monospace; font-size: 12px; line-height: 16.799999237060547px; white-space: pre;"><br /></span></div>
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.<br />
<br />
<b>Refereneces </b><br />
<a href="http://www.cplusplus.com/reference/cstring/strtok/">http://www.cplusplus.com/reference/cstring/strtok/</a><br />
<a href="http://apps.topcoder.com/forums/?module=Thread&threadID=672251&start=0">http://apps.topcoder.com/forums/?module=Thread&threadID=672251&start=0</a></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-87456897363479128332014-03-10T21:17:00.001-07:002014-03-25T11:16:23.531-07:00IOPC editorials<div dir="ltr" style="text-align: left;" trbidi="on">
You can download the editorial from here. <br />
<a href="https://drive.google.com/file/d/0B8cc7eHcqRVNd240QklvTE1kLU0/edit?usp=sharing">https://drive.google.com/file/d/0B8cc7eHcqRVNd240QklvTE1kLU0/edit?usp=sharing</a><br />
<br />
<br />
<iframe height="840" src="https://docs.google.com/file/d/0B8cc7eHcqRVNd240QklvTE1kLU0/preview" width="840"></iframe><br />
<br />
<br />
<br /></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-6778316982866343292014-02-26T11:30:00.000-08:002014-02-26T11:32:50.351-08:00Invitation for participation in IOPC 2014, IIT Kanpur<div dir="ltr" style="text-align: left;" trbidi="on">
The Department of Computer Science & Engineering, Indian Institute of Technology, Kanpur <b> (<a href="http://cse.iitk.ac.in/">http://cse.iitk.ac.in</a>/)</b> and the Techkriti team](<a href="http://techkriti.org/">http://techkriti.org</a>/) 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.<br />
<br />
IOPC 2014 will be held from <b> 1200 hrs on March 1st to 1200 hrs on March 2nd (IST) <a href="http://www.timeanddate.com/worldclock/fixedtime.html?msg=IOPC+2014&iso=20140301T12&p1=539&ah=23&am=59">http://www.timeanddate.com/worldclock/fixedtime.html?msg=IOPC+2014&iso=20140301T12&p1=539&ah=23&am=59</a>. </b> 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.<br />
<br />
IOPC 2014 will be hosted on Directi's Codechef platform .Please register on the <b> contest page(<a href="http://www.codechef.com/IOPC2014">http://www.codechef.com/IOPC2014</a>) </b>. Teams need to register on the <b> [IOPC](<a href="http://tiny.cc/iopc2014">tiny.cc/iopc2014</a>) </b> site as well to be eligible for prizes.<br />
<br />
Visit the <b> Codechef contest page(<a href="http://www.codechef.com/IOPC2014">http://www.codechef.com/IOPC2014</a>)</b> and the <b> IOPC site (<a href="http://tiny.cc/iopc2014">http://tiny.cc/iopc2014</a>) </b> for rules and more details.<br />
Join us on our <b> FB event page (<a href="https://www.facebook.com/events/696412627048318">https://www.facebook.com/events/696412627048318</a>/) </b> for more updates.<br />
<br />
You can view last years problems at codechef.<br />
<a href="https://www.blogger.com/goog_57324304">http://www.codechef.com/IOPC2011 </a><br />
<a href="https://www.blogger.com/goog_57324304">http://www.codechef.com/IOPC2012 </a><br />
<a href="http://www.codechef.com/IOPC2013">http://www.codechef.com/IOPC2013</a><br />
<br />
See you in the contest !!!!</div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-14629745880897476272014-02-02T09:23:00.000-08:002014-02-03T10:40:41.425-08:00WPC # 4 Editorials<div dir="ltr" style="text-align: left;" trbidi="on">
<script type="text/x-mathjax-config"> MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); </script> <script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"> </script><br />
<br />
<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<br />
<br />
<br />
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 :)<br />
<br />
<br />
<b>Editorials:</b><br />
<b>Gopu and Frogs:</b><br />
If you have not come across permanent problem, Then look at <b> </b><a href="http://en.wikipedia.org/wiki/Permanent">http://en.wikipedia.org/wiki/Permanent</a>. 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.<br />
For finding number of perfect matchings in a graph, you can use a dp with bitmask in O($2^n n$).<br />
See the code of <a href="http://www.codechef.com/viewplaintext/460759">http://www.codechef.com/viewplaintext/460759</a> of uwi. go to permanent section. <br />
Problems to solve: <a href="http://www.codechef.com//problems/IOPC1114">http://www.codechef.com//problems/IOPC1114</a>. You can also see its explanation by Raziman TV on <a href="http://razimantv.files.wordpress.com/2011/02/booklet1.pdf">http://razimantv.files.wordpress.com/2011/02/booklet1.pdf</a>.<br />
<br />
<b>Arrangement Validity:</b><br />
<b> </b>From the earlier arrangement validity problem in the first part, you might have<b> </b>known the condition of when the answer is not possible. Go solve the problem for more clarity <a href="http://www.spoj.com/problems/SPCU">http://www.spoj.com/problems/SPCU</a>/.<br />
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.<br />
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.<br />
Try solving <a href="http://www.spoj.com/problems/ORDERSET/">http://www.spoj.com/problems/ORDERSET/</a> for getting more insight into the solution.<br />
<br />
<b>Maggu and Weird Things.</b><br />
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$.<br />
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. <br />
See the marix for only operation 1, Assume n = 4, k = 2<br />
<pre>$ \\[ \\left( \\begin{array}{ccc}
1 & -1 & 0 & 0 \\\\
0 & 1 & -1 & 0\\\\
0 & 0 & 1 & -1 \\\\</pre>
<pre>-1 & 0 & 0 & 1\\\\</pre>
<pre>\\end{array} \\right)\\] $</pre>
Did you guys notice the pattern, if yes, then formalize the intuition.<br />
<br />
<br />
Now let us see the case of swapping the $i^{th}$ and $(i+1)^{th}$ element.<br />
For this you can swap two consecutive rows of matrix obtained in the first step.<br />
ie.<br />
<pre>$ \[ \left( \begin{array}{ccc}
0 & 1 & -1 & 0\\ </pre>
<pre>1 & -1 & 0 & 0 \\</pre>
<pre>-1 & 0 & 0 & 1\\
0 & 0 & 1 & -1 \\</pre>
<pre>\end{array} \right)\] $</pre>
<br />
Now you have got your matrix, Exponentiate it n times ($\mathbb{O}$ ($n^3$ log m) and enjoy yourselves :)<br />
<br />
<b>Maggu and Magguness Level:</b><br />
This problem is so cute to solve. Believe me if you have not solved upto now, first solve yourself. <br />
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.<br />
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.<br />
Take examples and try solving the problem.<br />
<b></b><br />
<b>Petya and Repairment of Roads.</b><br />
<b> </b>This problem is really famous. See <a href="http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf">http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf.</a><br />
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.<br />
<br />
Also solve <a href="http://www.codechef.com/problems/RHOUSE">http://www.codechef.com/problems/RHOUSE</a>. <br />
<br />
<b>Maggu and Mystery:</b><br />
<b> </b>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$.<br />
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).<br />
<br />
<div dir="ltr" id="docs-internal-guid-319792f5-f78d-5015-967a-7a98dce192c4" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;">Maggu and Vectors : (Wrriten by Abhilash Kumar)</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">In this problem we have to check that do 3 vectors a,b,c exists such that :</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> abc=0</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">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.</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">It can be easily noticed that solution to above equation exists if solution for one of these equation exists:</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> a+b=c </span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> b+c=a </span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> c+a=b </span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">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.</span></div>
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: italic; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">Complexity = $\mathbb{O} ( 4000*4000 + n^2 + n )$</span><br />
<div dir="ltr" id="docs-internal-guid-319792f5-f78f-a770-f2a1-22787fc06387" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;"> <i>Note: Many wrong answer occurred because people were also counting non-degenerate triangle.</i></span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">To avoid this problem we just had to add only </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;">non-zero</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> vectors that were </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;">non-parallel .</span></div>
<div dir="ltr" id="docs-internal-guid-319792f5-f790-b614-1009-7a9d53a0e9cc" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;">Maggu and Triangles : (Written by Abhilash Kumar)</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">We have to find number of non-congruent triangles with perimeter N.</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">The answer to this question is </span><a href="http://oeis.org/A005044" style="text-decoration: none;"><span style="background-color: #eeeeff; color: #1155cc; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">Alcuin's sequence</span></a><span style="background-color: #eeeeff; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> Nth element of this sequence is coefficient of $x^n$ in $x^3/((1-x^2)*(1-x^3)*(1-x^4))$. </span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">After solving the above sequence </span><a href="about:blank" style="text-decoration: none;"><span style="background-color: transparent; color: #1155cc; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: underline; vertical-align: baseline;">(as done here)</span></a><span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> we get :</span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline;">$T_n = < (n+3)^2 / 48 > $ </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;">when n is odd.</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> = $ < n^2 / 48> $ if n is even. </span></div>
<div dir="ltr" style="line-height: 1.15; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><x> where $ < > $ denotes the nearest integer to x . Note that here x will never be exactly between two integers.</x></span><br />
<br />
<br />
<br />
<br />
<br />
<br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><x></x></span><br />
<pre><span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"><span class="Apple-style-span" style="font-size: xx-small;">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} \]</span></span></pre>
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"> </span></div>
<br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 15px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span><b> </b><br />
<b> </b><br />
<b> </b><br />
<b> </b></div>
</div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com6tag:blogger.com,1999:blog-6704226767646806218.post-74805354649927232382014-01-15T16:06:00.000-08:002014-01-15T16:06:04.018-08:00Multiplication of two long numbers modulo a long number.<div dir="ltr" style="text-align: left;" trbidi="on">
<pre>LL multiplication (LL a, LL b, LL mod) {
LL res = (a * ((long double) b / (long double) mod));</pre>
<pre> // put the number in long double, and then reduce the value to LL, forget </pre>
<pre> overflow.</pre>
<pre> res = a * b - res * mod;
if (res >= mod) res -= mod;
if (res < 0) res += mod;
return res;
}</pre>
</div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-26969246703576795082014-01-14T10:38:00.001-08:002014-01-14T11:02:55.634-08:00WCP #3 And Editorials<div dir="ltr" style="text-align: left;" trbidi="on">
<b>WPC #3</b> was held on this sunday. <a href="http://aca.cse.iitk.ac.in/public/">http://aca.cse.iitk.ac.in/public/</a><br />
Problems have been moved to spoj.<br />
<br />
Editorials: (these editorials are merely hints, You need to work things yourself for final answers)<br />
Hope you will like them. Leave a comment if something is unclear or needs to be modified, Also leave your opinion about the contest.<br />
<br />
<div style="text-align: left;">
1. <b>Gopu and Palindromes: (<a href="http://www.spoj.com/problems/SPCS/">http://www.spoj.com/problems/SPCS/</a>)</b></div>
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?<br />
eg. s = "ababbbaaa".<br />
s = "ababa". Replace bbb with b and aaa with a.<br />
You need to do this in O(n).<br />
<br />
2.<b>Gopu and Validity of Arrangement:</b> (<a href="http://www.spoj.com/problems/SPCU/">http://www.spoj.com/problems/SPCU/</a>)<br />
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.<br />
<br />
3. <b>Gopu and Digits Divisibility: (</b><a href="http://www.spoj.com/problems/SPCU/">http://www.spoj.com/problems/SPCU/</a>)<br />
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).<br />
<br />
4. <b>Gopu and Function: (</b><a href="http://www.spoj.com/problems/SPCM/">http://www.spoj.com/problems/SPCM/</a><b>)</b><br />
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).<br />
<br />
5. <b>Gopu and Create Collections Part two (</b><a href="http://www.spoj.com/problems/SPCJ/">http://www.spoj.com/problems/SPCJ/</a>)<br />
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.<br />
You can also use greedy
algorithm by constructing the binary tree explicitly and then going from
leaves to the root of the tree.<br />
<br />
6. <b>Gopu and Combinatorics on Graphs: (</b><a href="http://www.spoj.com/problems/SPCE/">http://www.spoj.com/problems/SPCE/</a>)<br />
This is standard problem. You should know <a href="http://en.wikipedia.org/wiki/Cayley%27s_formula">http://en.wikipedia.org/wiki/Cayley%27s_formula</a>. Then figuring out things wont be tough. I dont want to give formulla as I want you to work it out.<br />
<br />
7. <b>Gopu and Counting bitwise prime numbers: (</b><a href="http://www.spoj.com/problems/SPCO/">http://www.spoj.com/problems/SPCO/</a><b>)</b><br />
This problem had one slow solution:<br />
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 <a href="http://ideone.com/numnIE">http://ideone.com/numnIE</a>.<br />
You can optimize it slightly and get it passed. Basically think in terms of combinatorics, You will get the idea.<br />
<br />
<br />
<br /></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com5tag:blogger.com,1999:blog-6704226767646806218.post-77700186692819417502013-12-27T13:45:00.001-08:002014-01-15T11:05:43.901-08:00Important things in Java<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><div style="font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
int [] A = new int [n];</div>
<div style="font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
for (int x : A) System.out.println (x);</div>
</pre>
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"><span class="kwd" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: darkblue; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">int</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">[]</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"> array </span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">=</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="kwd" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: darkblue; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">new</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="kwd" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: darkblue; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">int</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">[</span><span class="lit" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: maroon; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">4</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">];</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="typ" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: #2b91af; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">Arrays</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">fill</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">array</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">,</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="lit" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: maroon; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">0</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">);</span></code></pre>
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><pre class="lang-java prettyprint prettyprinted" style="border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"><span class="typ" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: #2b91af; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">System</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">out</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">println</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="typ" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: #2b91af; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">Arrays</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">deepToString</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">array</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">));</span></code></pre>
</pre>
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><div style="font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
Math.max (a, b)</div>
<div style="font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
Math.abs (a)</div>
</pre>
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><div style="font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
StringBuilder:</div>
<div style="font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
StringBuilder res = new StringBuilder ();</div>
<div style="font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
res.append (char ('A'));</div>
<div style="font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
res.append (String);</div>
<div style="font-family: 'Times New Roman'; font-size: medium; line-height: normal; white-space: normal;">
String ans = res.toString();</div>
</pre>
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><code style="border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"><span class="kwd" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: darkblue; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">int</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">[]</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"> array </span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">=</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="kwd" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: darkblue; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">new</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="kwd" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: darkblue; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">int</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">[</span><span class="lit" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: maroon; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">4</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">];</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">
</span><span class="typ" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: #2b91af; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">Arrays</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">.</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">fill</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">(</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">array</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">,</span><span class="pln" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;"> </span><span class="lit" style="background-color: transparent; background-position: initial initial; background-repeat: initial initial; border: 0px; color: maroon; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">0</span><span class="pun" style="background-color: transparent; border: 0px; font-size: 14px; margin: 0px; padding: 0px; vertical-align: baseline;">);</span></code></pre>
<br />
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;">Arrays.Sort (object[], startIndex, endIndex);</pre>
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><span style="color: darkblue;">Set<integer> st = new HashSet <integer> ();
st.add (5);
st.size();
</integer></integer></span></pre>
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><span style="color: darkblue;">List <integer> list = new ArrayList <integer> ();
Concerting Set to List type
List <integer> list = new ArrayList <integer> (st);
Collection.sort (list);</integer></integer></integer></integer></span></pre>
<br />
<pre class="lang-java prettyprint prettyprinted" style="background-color: #eeeeee; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif; font-size: 14px; line-height: 18px; margin-bottom: 10px; max-height: 600px; overflow: auto; padding: 5px; vertical-align: baseline; width: auto; word-wrap: normal;"><span style="color: darkblue;">String s = new String();
s.toCharArray();</span></pre>
<br /><span style="color: darkblue;"><code>Input Output Code in Java (Code is taken from Egor's library).</code></span><br />
<span style="color: darkblue;"><code><br /></code></span>
<span style="color: darkblue;"><code><script src="https://gist.github.com/praveendhinwa/8442154.js"></script><br /></code></span>
<br />
-------------------------------------------------------------------------------------------<br />
If you want to use something other, this is Parser class for input (Written by Rudradevbasak's team proof). For output, you can use PrintWriter class which is fast enough.<br />
<br />
<script src="https://gist.github.com/praveendhinwa/8442238.js"></script><br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br /></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-65014070332681413222013-12-26T17:12:00.000-08:002013-12-26T17:13:46.021-08:00Sliding Window Algorithms and problems related to that..<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
See the code<br />
<br />
<script src="https://gist.github.com/praveendhinwa/8140835.js"></script></div>
<br />
Amortized complexity is O(n).<br />
<br />
<div>
<b>Problems to Solve:</b></div>
<div>
<ul class="simple" style="background-color: white; font-family: Verdana, Helvetica, sans-serif; font-size: 13px; letter-spacing: 0.12999999523162842px; line-height: 20px;">
<li><a href="http://www.spoj.com/problems/ARRAYSUB/">http://www.spoj.com/problems/ARRAYSUB/</a></li>
<li>Task "sound" at <a class="reference external" href="http://www.boi2007.de/en/tasks" style="color: #7900b6;">http://www.boi2007.de/en/tasks</a></li>
<li><span style="font-size: 13px;">Task "pyramid" at </span><a class="reference external" href="http://olympiads.win.tue.nl/ioi/ioi2006/contest/day1/" style="color: #7900b6; font-size: 13px;">http://olympiads.win.tue.nl/ioi/ioi2006/contest/day1/</a><span style="font-size: 13px;"> (medium to hard problem)</span></li>
<li><span style="font-size: 13px;"><a href="http://wcipeg.com/problem/ccc03s2p5">http://wcipeg.com/problem/ccc03s2p5</a></span></li>
<li><a href="http://wcipeg.com/problem/ccc96s5">http://wcipeg.com/problem/ccc96s5</a></li>
<li><a href="http://wcipeg.com/problem/smac081p3">http://wcipeg.com/problem/smac081p3</a></li>
<li><a href="http://wcipeg.com/problem/ccc96s5">http://wcipeg.com/problem/ccc96s5</a></li>
<li><a href="http://wcipeg.com/problem/ioi0611">http://wcipeg.com/problem/ioi0611</a></li>
<li><a href="http://www.spoj.com/problems/BROKEN/">http://www.spoj.com/problems/BROKEN/</a></li>
<li><a href="http://www.spoj.com/problems/FSEATS/">http://www.spoj.com/problems/FSEATS/</a></li>
<li><a href="http://www.spoj.com/problems/KPMATRIX/">http://www.spoj.com/problems/KPMATRIX/</a></li>
<li><a href="http://www.spoj.com/problems/MATRIX2/">http://www.spoj.com/problems/MATRIX2/</a></li>
<li><a href="http://www.codechef.com/problems/CHEFTOWN">http://www.codechef.com/problems/CHEFTOWN</a></li>
<li><a href="http://wcipeg.com/problem/ioi0612">http://wcipeg.com/problem/ioi0612</a></li>
<li><a href="http://www.codechef.com/OCT12/problems/TEAMSIZE">http://www.codechef.com/OCT12/problems/TEAMSIZE</a></li>
<li><a href="http://www.spoj.com/problems/KRECT/">http://www.spoj.com/problems/KRECT/</a></li>
</ul>
</div>
<b>References:</b><br />
<br />
<ol style="text-align: left;">
<li><a href="http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html">http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html</a></li>
<li><a href="http://softwarelearner.blogspot.in/2011/04/minima-in-sliding-window.html">http://softwarelearner.blogspot.in/2011/04/minima-in-sliding-window.html</a></li>
<li><a href="http://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples/8269948#8269948">http://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples/8269948#8269948</a></li>
<li><a href="http://richardhartersworld.com/cri/2001/slidingmin.html">http://richardhartersworld.com/cri/2001/slidingmin.html</a></li>
<li><a href="http://wcipeg.com/wiki/Sliding_window">http://wcipeg.com/wiki/Sliding_window</a></li>
<li><a href="http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/">http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/</a></li>
<li><a href="http://wcipeg.com/wiki/Sliding_range_minimum_query">http://wcipeg.com/wiki/Sliding_range_minimum_query</a></li>
</ol>
<div>
<br /></div>
</div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com4tag:blogger.com,1999:blog-6704226767646806218.post-41177283343918404112013-12-26T14:49:00.000-08:002014-02-03T11:03:42.343-08:00Using Latex or Mathjax in Blogger<div dir="ltr" style="text-align: left;" trbidi="on">
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js" type="text/javascript">
MathJax.Hub.Config({
HTML: ["input/TeX","output/HTML-CSS"],
TeX: { extensions: ["AMSmath.js","AMSsymbols.js"],
equationNumbers: { autoNumber: "AMS" } },
extensions: ["tex2jax.js"],
jax: ["input/TeX","output/HTML-CSS"],
tex2jax: { inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true },
"HTML-CSS": { availableFonts: ["TeX"],
linebreaks: { automatic: true } }
});
</script><br />
<br />
<br />
<pre style="white-space: pre-wrap; width: 650px;">1. To see how any of the formulas were made in any question or answer, including this one, use the "edit" link to view the complete source. To quickly see the source of a single expression, right-click on it and choose "Show Math As > TeX Commands".
(Note that in some browsers, such as Firefox, the MathJax right-click menu that contains this command will be obscured by the browser's own right-click menu. Click somewhere outside the main browser canvas -- such as in the address bar -- to dismiss the browser menu and reveal the MathJax one behind it).
2. For inline formulas, enclose the formula in `$...$`. For displayed formulas, use `$$...$$`. These render differently: $\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{2}$ (inline) or $$\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{2}\tag{displayed}$$
3. For **Greek letters**, use `\alpha`, `\beta`, …, `\omega`: $\alpha, \beta, … \omega$. For uppercase, use `\Gamma`, `\Delta`, …, `\Omega`: $\Gamma, \Delta, …, \Omega$.
4. For **superscripts and subscripts**, use `^` and `_`. For example, `x_i^2`: $x_i^2$.
5. By default, superscripts, subscripts, and other operations apply only to the next "group". A "group" is either a single symbol, or any formula surrounded by curly braces `{`…`}`. If you do `10^10`, you will get a surprise: $10^10$. But `10^{10}` gives what you probably wanted: $10^{10}$. Use curly braces to delimit a formula to which a superscript or subscript applies: `x^5^6` is an error; `{x^y}^z` is ${x^y}^z$, and `x^{y^z}` is $x^{y^z}$. Observe the difference between `x_i^2` $x_i^2$ and `x_{i^2}` $x_{i^2}$.
6. **Parentheses** Ordinary symbols `()[]` make parentheses and brackets $(2+3)[4+4]$. Use `\{` and `\}` for curly braces $\{\}$.
These do *not* scale with the formula in between, so if you write `(\frac12)` the parentheses will be too small: $(\frac12)$. Using `\left(`…`\right)` will make the sizes adjust automatically to the formula they enclose: `\left(\frac12\right)` is $\left(\frac12\right)$.
`\left` and`\right` apply to all the following sorts of parentheses: `(` and `)` $(x)$, `[` and `]` $[x]$, `\{` and `\}` $\lbrace x \rbrace$, `|` $|x|$, `\langle` and `\rangle` $\langle x \rangle$, `\lceil` and `\rceil` $\lceil x \rceil$, and `\lfloor` and `\rfloor` $\lfloor x \rfloor$. There are also invisible parentheses, denoted by `.`: `\left.\frac12\right\rbrace` is $\left.\frac12\right\rbrace$.
7. **Sums and integrals** `\sum` and `\int`; the subscript is the lower limit and the superscript is the upper limit, so for example `\sum_1^n` $\sum_1^n$. Don't forget `{`…`}` if the limits are more than a single symbol. For example, `\sum_{i=0}^\infty i^2` is $\sum_{i=0}^\infty i^2$. Similarly, `\prod` $\prod$, `\int` $\int$, `\bigcup` $\bigcup$, `\bigcap` $\bigcap$, `\iint` $\iint$.
8. **Fractions** There are two ways to make these. `\frac ab` applies to the next two groups, and produces $\frac ab$; for more complicated numerators and denominators use `{`…`}`: `\frac{a+1}{b+1}` is $\frac{a+1}{b+1}$. If the numerator and denominator are complicated, you may prefer `\over`, which splits up the group that it is in: `{a+1\over b+1}` is ${a+1\over b+1}$.
9. **Fonts**
* Use `\mathbb` or `\Bbb` for "blackboard bold": $\mathbb{CHNQRZ}$.
* Use `\mathbf` for boldface: $\mathbf{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$ $\mathbf{abcdefghijklmnopqrstuvwxyz}$.
* Use `\mathtt` for "typewriter" font: $\mathtt{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$ $\mathtt{abcdefghijklmnopqrstuvwxyz}$.
* Use `\mathrm` for roman font: $\mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$ $\mathrm{abcdefghijklmnopqrstuvwxyz}$.
* Use `\mathcal` for "calligraphic" letters: $\mathcal{ ABCDEFGHIJKLMNOPQRSTUVWXYZ}$
* Use `\mathscr` for script letters: $\mathscr{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$
* Use `\mathfrak` for "Fraktur" (old German style) letters: $\mathfrak{ABCDEFGHIJKLMNOPQRSTUVWXYZ} \mathfrak{abcdefghijklmnopqrstuvwxyz}$.
10. **Radical signs** Use `sqrt`, which adjusts to the size of its argument: `\sqrt{x^3}` $\sqrt{x^3}$; `\sqrt[3]{\frac xy}` $\sqrt[3]{\frac xy}$. For complicated expressions, consider using `{...}^{1/2}` instead.
11. Some special functions such as "lim", "sin", "max", "ln", and so on are normally set in roman font instead of italic font. Use `\lim`, `\sin`, etc. to make these: `\sin x` $\sin x$, not `sin x` $sin x$. Use subscripts to attach a notation to `\lim`: `\lim_{x\to 0}` $$\lim_{x\to 0}$$
12. There are a very large number of special symbols and notations, too many to list here; see [this shorter listing](http://pic.plover.com/MISC/symbols.pdf), or [this exhaustive listing](http://mirror.math.ku.edu/tex-archive/info/symbols/comprehensive/symbols-a4.pdf). Some of the most common include:
* `\lt \gt \le \ge \neq` $\lt\, \gt\, \le\, \ge\, \neq$. You can use `\not` to put a slash through almost anything: `\not\lt` $\not\lt$ but it often looks bad.
* `\times \div \pm \mp` $\times\, \div\, \pm\, \mp$. `\cdot` is a centered dot: $x\cdot y$
* `\cup \cap \setminus \subset \subseteq \subsetneq \supset \in \notin \emptyset \varnothing` $\cup\, \cap\, \setminus\, \subset\, \subseteq \,\subsetneq \,\supset\, \in\, \notin\, \emptyset\, \varnothing$
* `{n+1 \choose 2k}` or `\binom{n+1}{2k}` ${n+1 \choose 2k}$
* `\to \rightarrow \leftarrow \Rightarrow \Leftarrow \mapsto` $\to\, \rightarrow\, \leftarrow\, \Rightarrow\, \Leftarrow\, \mapsto$
* `\land \lor \lnot \forall \exists \top \bot \vdash \vDash` $\land\, \lor\, \lnot\, \forall\, \exists\, \top\, \bot\, \vdash\, \vDash$
* `\star \ast \oplus \circ \bullet` $\star\, \ast\, \oplus\, \circ\, \bullet$
* `\approx \sim \cong \equiv \prec` $\approx\, \sim \, \cong\, \equiv\, \prec$.
* `\infty \aleph_0` $\infty\, \aleph_0$ `\nabla \partial` $\nabla\, \partial$ `\Im \Re` $\Im\, \Re$
* For modular equivalence, use `\pmod` like this: `a\equiv b\pmod n` $a\equiv b\pmod n$.
* `\ldots` is the dots in $a_1, a_2, \ldots ,a_n$ `\cdots` is the dots in $a_1+a_2+\cdots+a_n$
* Some Greek letters have variant forms:
`\epsilon \varepsilon` $\epsilon\, \varepsilon$, `\phi \varphi` $\phi\, \varphi$, and others. Script lowercase l is `\ell` $\ell$.
[Detexify](http://detexify.kirelabs.org/classify.html) lets you draw a symbol on a web page and then lists the $\TeX$ symbols that seem to resemble it. These are not guaranteed to work in MathJax but are a good place to start.
13. **Spaces** MathJax usually decides for itself how to space formulas, using a complex set of rules. Putting extra literal spaces into formulas will not change the amount of space MathJax puts in: `a␣b` and `a␣␣␣␣b` are both $a b$. To add more space, use `\,` for a thin space $a\,b$; `\;` for a wider space $a\;b$. `\quad` and `\qquad` are large spaces: $a\quad b$, $a\qquad b$.
To set plain text, use `\text{…}`: $\{x\in s\mid x\text{ is extra large}\}$. You can nest `$…$` inside of `\text{…}`.
14. **Accents and diacritical marks** Use `\hat` for a single symbol $\hat x$, `\widehat` for a larger formula $\widehat{xy}$. If you make it too wide, it will look silly. Similarly, there are `\bar` $\bar x$ and `\overline` $\overline{xyz}$, and `\vec` $\vec x$ and `\overrightarrow` $\overrightarrow{xy}$. For dots, as in $\frac d{dx}x\dot x = \dot x^2 + x\ddot x$, use `\dot` and `\ddot`.
15. Special characters used for MathJax interpreting can be escaped using the `\` character: `\$` $\$$, `\{` $\{$, `\_` $\_$, etc.
(Tutorial ends here.)
-------------
It is important that this note be reasonably short and not suffer from too much bloat. To include more topics, please create short addenda and post them as answers instead of inserting them into this post.</pre>
</div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com3tag:blogger.com,1999:blog-6704226767646806218.post-18928769994988473072013-12-26T14:24:00.002-08:002013-12-26T14:45:29.461-08:00Standard Vieta Jumping and examples<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="background-color: white; color: #444444; font-family: 'Helvetica Neue', HelveticaNeue, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 19px; text-align: justify;">$\sum_{k=1}^n k = \frac{n(n+1)}{2}$</span><br />
<span style="background-color: white; color: #444444; font-family: 'Helvetica Neue', HelveticaNeue, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 19px; text-align: justify;"><br /></span>
<span style="background-color: white; color: #444444; font-family: 'Helvetica Neue', HelveticaNeue, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 19px; text-align: justify;">Consider the following equation.</span><br />
<span style="background-color: white; color: #444444; font-family: 'Helvetica Neue', HelveticaNeue, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 19px; text-align: justify;">$x^2$ = $y^2 + z^2$.</span><br />
<span style="background-color: white; color: #444444; font-family: 'Helvetica Neue', HelveticaNeue, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 19px; text-align: justify;"><br /></span>
<span style="background-color: white; color: #444444; font-family: 'Helvetica Neue', HelveticaNeue, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 19px; text-align: justify;">Consider the first few numbers $x_0$, $x_1$ ,,, $x_n$.</span><br />
<span style="background-color: white; color: #444444; font-family: 'Helvetica Neue', HelveticaNeue, Helvetica, Arial, sans-serif; font-size: 14px; line-height: 19px; text-align: justify;"><br /></span></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-36546117530756091882013-12-12T10:22:00.004-08:002013-12-13T02:43:22.858-08:00binary search<div dir="ltr" style="text-align: left;" trbidi="on">
<a href="http://codeforces.com/blog/entry/9901#comment-153761">http://codeforces.com/blog/entry/9901#comment-153761</a></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-64582461194226717522013-12-12T10:22:00.001-08:002013-12-12T10:22:22.891-08:00Hackenbush games<div dir="ltr" style="text-align: left;" trbidi="on">
<a href="http://is.muni.cz/th/325040/fi_b/Combinatorial_games.pdf">http://is.muni.cz/th/325040/fi_b/Combinatorial_games.pdf</a></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-80501083098221831752013-12-10T16:35:00.000-08:002013-12-10T16:35:40.679-08:002 SAT<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Definition:</b><br />
(x1 v x2) ^ (x1 v -x2) ^ ....<br />
per clause two literals.<br />
<br />
<b>Algorithm to found whether there exits a possible assignment or not?</b><br />
Build implication graph corresponding and then check whether there exists a path from x to -x or not.<br />
If such path exists, then no valid assignment can be done.<br />
<br />
Building implication graph<br />
(x v y) add edge -x to y, and -y to x.<br />
<br />
<b>Algorithm to find a possible assignment?</b><br />
<br />
First check for the existence case.<br />
for each unassigned literal x, assign it to true and all the y such x -> y, then assign y to true,<br />
Assign all the opposite of these literals to be false.<br />
<br />
<b>Implementation:</b><br />
<br />
<b>Problems to practice:</b><br />
<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2453">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2453</a><br />
<a href="http://www.spoj.com/problems/TORNJEVI/">http://www.spoj.com/problems/TORNJEVI/</a><br />
<a href="http://www.spoj.com/problems/SUPSUP/">http://www.spoj.com/problems/SUPSUP/</a><br />
<a href="http://2011.nwerc.eu/results.php">http://2011.nwerc.eu/results.php</a> (<a href="http://2011.nwerc.eu/results.php" style="color: #000066; font-family: Arial, Helvetica, Verdana, sans-serif; font-size: 12px; line-height: 16px;">Piece it Together</a><span style="background-color: white; color: #333333; font-family: Arial, Helvetica, Verdana, sans-serif; font-size: 12px; line-height: 16px;"> ).</span><br />
<a href="http://2012.nwerc.eu/en/results/problems/">http://2012.nwerc.eu/en/results/problems/</a><br />
<br />
<b>References:</b><br />
<a href="http://users.cms.caltech.edu/~umans/cs21/lec17.pdf">http://users.cms.caltech.edu/~umans/cs21/lec17.pdf</a><br />
<a href="http://kartikkukreja.wordpress.com/2013/05/16/solving-2-sat-in-linear-time/">http://kartikkukreja.wordpress.com/2013/05/16/solving-2-sat-in-linear-time/</a><br />
<a href="http://classes.soe.ucsc.edu/cmps132/Winter05/hw/hw8sols.pdf">http://classes.soe.ucsc.edu/cmps132/Winter05/hw/hw8sols.pdf</a><br />
<a href="http://apps.topcoder.com/forums/?module=Thread&threadID=803822&start=0&mc=2">http://apps.topcoder.com/forums/?module=Thread&threadID=803822&start=0&mc=2</a><br />
<br /></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-36410643297171438952013-12-08T19:19:00.002-08:002013-12-08T19:19:37.594-08:00Important STL functions<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-87617709644263942902013-12-07T11:47:00.002-08:002013-12-07T11:50:02.081-08:00Finding nCk effectively<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
if n is or range 10^9 or so. and k is of the range <= 20, 50, 100 or so.<br />
<br />
<b>Finding nCk % mod:</b><br />
n * (n - 1) * (n - 2) * (n - k + 1) / (k !).<br />
Do the factorisation of k! easily.<br />
Make an array A such that A[i] = n - i, i >= 0 && i < k.<br />
now for each prime p, let us say it has power q in k!,<br />
Remove q powers of p from A[0] to A[k - 1].<br />
<br />
Finally multiply all the A[i]'s and then do mod to get the answer.<br />
<br />
</div>
<br />
<script src="https://gist.github.com/praveendhinwa/7847576.js">
</script><br />
<b>Another method.</b><br />
n C k = ((n - 1) C (k - 1) + (n - 1) C k) % mod; when n is odd.<br />
n C k = sum over i = 0 to k. ((n / 2) C i) * ((n / 2) C (k - i)). when n is even.<br />
This method is also included in the code, but it is not so fast :( </div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-28335325402262857802013-12-04T18:13:00.000-08:002014-01-03T18:59:00.279-08:00Important vim commands<div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: left;"></div><ul style="text-align: left;"><li>:! for running a command outside the vim. eg. :!pwd</li>
<li>set smartindent</li>
<li>Ctrl x + Ctrl l for autocompletion of entire line</li>
<li>Replacing in a line: s/foo/bar/g will replace each occurence of foo by bar.</li>
<li>Replacing in a line: s/foo/bar/gc will replace each occurence of foo by bar, but ask for confirmation.</li>
<li>Replacing in a file: %s/foo/bar/gc will replace each occurence of foo by bar, but ask for confirmation.</li>
<li>But if use s/foo/bar it then it will replace the first occurance of foo by bar in the line.</li>
<li>Use arrow keys to get the previous command.</li>
<li>Use :ab mail praveendhinwa@gmail.com etc kind of abbreviations.</li>
<li>>> and << for indentation</li>
<li>sh: temporary returns to unix.</li>
<li>e filename: opens the file with given filename.</li>
<li>browse e: graphical file opening.</li>
<li>use tab for completion of half command too </li>
<li>:g/string/d delete all lines containing string</li>
<li>:v/string/d delete all lines not containing string.</li>
<li>2,15s/foo/bar/g delete all occurences of foo by bar from line 2 to 15.</li>
<li>* for searching the word under the cursor currently.</li>
<li>/word Searching from top</li>
<li>?word Searching from bottom to top.</li>
<li>/f[ao]r will search for far and for both.</li>
<li>yy for copying a single line.</li>
<li>2yy for copying two lines.</li>
<li>y for copying the selected text.</li>
<li>p for pasting the clipboard content.</li>
<li>shift + [ or ] for moving from the end of functions to start and vice versa.</li>
<li>gg for moving the cursor to start of line</li>
<li>G for moving the cursor to the end of line.</li>
<li>:17 to move the cursor to line numbered 17.</li>
<li>0 Move the cursor to beginning of the line</li>
<li>b for start of the word</li>
<li>e for moving to end of the word</li>
<li>cc for changing an entire line.</li>
<li>Generating text to html code. :%TOhtml</li>
</ul><div><b>Mapping in Vim:</b></div><div><ul style="text-align: left;"><li>:imap ;so System.out.println() <left><left>, Whenever you will type ;so, it will autcomplete to System.out.println() with cursor between the paranthesis.</left></left></li>
<li><br />
</li>
</ul></div><div></div><div>References</div><div><a href="http://www.worldtimzone.com/res/vi.html">http://www.worldtimzone.com/res/vi.html</a></div><div><a href="http://www.catswhocode.com/blog/130-essential-vim-commands">http://www.catswhocode.com/blog/130-essential-vim-commands</a></div><div><br />
<br />
</div></div>praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-828915903544074742013-09-22T04:30:00.000-07:002013-09-22T06:31:18.237-07:00Using Templates in C++ Programming<div dir="ltr" style="text-align: left;" trbidi="on">I would describe about using templates in c++.<br />
<div><br />
</div><div><ol style="text-align: left;"><li><b>functions using templates </b><br />
<script src="https://gist.github.com/praveendhinwa/6659027.js"></script><br />
</li>
<li><b>classes using templates </b><br />
<script src="https://gist.github.com/praveendhinwa/6659078.js"></script><br />
</li>
<li><b>Template Specialization </b><br />
Template Specialization means that specialize your template for some particular type. eg. you define add function for integers to be integers addition but for strings it may be addition. So You need to define it seperately.<br />
<script src="https://gist.github.com/praveendhinwa/6659912.js"></script></li>
</ol></div></div>praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-23870332100295160662013-09-17T14:20:00.000-07:002013-09-17T16:30:44.962-07:00My Latest Template for Programming Contests<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
I have learnt few good things about c++.<br />
<br />
<br />
<ul style="text-align: left;">
<li>you can directly use this header file, it will precompile all the header files required.</li>
</ul>
<br />
#include <bits/stdc++.h><br />
using namespace std;<br />
<br />
<br />
<ul style="text-align: left;">
<li>struct _ { ios_base::Init i; _() { cin.sync_with_stdio(0); cin.tie(0); } } _;</li>
</ul>
<br />
this is meant for reducing slowness of slowness of iostream in syncing. more on<br />
<a href="http://codeforces.com/blog/entry/8387">http://codeforces.com/blog/entry/8387</a><br />
<a href="http://gcc.gnu.org/onlinedocs/libstdc++/manual/using_headers.html">http://gcc.gnu.org/onlinedocs/libstdc++/manual/using_headers.html</a><br />
<a href="http://codeforces.com/blog/entry/925">http://codeforces.com/blog/entry/925</a><br />
<br />
<b>Precaution</b>: You need to make sure that you do not use scanf and cin statements interchangibly means<br />
one code should exclusively use cin and cout's only if you are using this. Reason is quite obvious.<br />
<br />
I have tested the code on codechef. It works great :). Infact slightly faster :)<br />
<br />
Here is the link of my latest template:<br />
<br />
<script src="https://gist.github.com/praveendhinwa/6600786.js"></script><br />
<br /></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-18127993138387352872013-08-18T07:01:00.001-07:002014-01-10T07:35:38.202-08:00Weekend Programming Contest on 17 August 2013 Editorials<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<h2 style="text-align: left;">
<b>Note: For problem M, The editorial is saying that answer is -1 iff n is of form of p^i, Please read it as n is of form of p^i or 2 * p^i.</b></h2>
<b>I have lost the tex file, So I am really sorry, Next time I will try to write editorials in a doc kind of format.</b><br />
<b><br /></b>
<b>UPDATE1 </b>: Problems have been added to <b>SPOJ </b>and to our Online judge also. <a href="http://www2.cse.iitk.ac.in/judge/public/">http://www2.cse.iitk.ac.in/judge/public/</a> . So Enjoy solving them :)<br />
<a href="http://www.spoj.com/problems/IITKWPCA/">http://www.spoj.com/problems/IITKWPCA/</a><br />
See the problem from A to J, L to O.<br />
<div>
<br /></div>
<div>
<b>UPDATE2</b>: I have corrected the errors in the editorial and uploaded the latest file. If you want some more explantion.I will edit the article, just write a comment about which problem do you think that editorial can be improved and what you do not understand from the editorial.</div>
<div>
<br /></div>
You can download the <b>latest editorial </b>from this link:<br />
<br />
<a href="https://docs.google.com/file/d/0B8cc7eHcqRVNaHNWRjl0T01vX1U/edit?usp=sharing">https://docs.google.com/file/d/0B8cc7eHcqRVNaHNWRjl0T01vX1U/edit?usp=sharing</a><br />
<div>
<br /></div>
PS: I have updated the editorial, You might face some problems in viewing it in google docs itself. Please download the file and view it.<br />
<br /></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com10tag:blogger.com,1999:blog-6704226767646806218.post-37028683356378061692013-08-14T22:33:00.000-07:002013-08-17T04:58:11.933-07:00Weekend Programming Contest this week on 17 August 2013<div dir="ltr" style="text-align: left;" trbidi="on">
Hi,<br />
We as a part of ACA, IITK and PClub IITK are organising a small WPC this week. So gear up to enjoy 15 challenging programming tasks. It will start on 6pm 17 August to 6 pm 18 August, 24 hours contest.<br />
<br />
Link : <a href="http://www2.cse.iitk.ac.in/judge/public/">http://www2.cse.iitk.ac.in/judge/public/</a><br />
This is a team contest of consisting at max 3 persons. It has some prizes for top 6 teams but only for internal teams, so if you are some external participant then I am sorry about it, btw you can get a good practice of all kinds of algorithms.<br />
<br />
It will mostly contain problems of all domains and all kinds of difficulty levels. Most of the problems are created by me, Some problems are just a bit modification of standard ideas.<br />
<br />
Now time to know people behind the scenes of the WPC. Thank you Pankaj Jindal for inspiring me to write an internal contest. Thanks ACA (specifically Harshvardhan Sharama) for providing the judge, PClub (specially Ankush Sachdeva) for providing the prize money. <br />
Problem Setter for the contest is me, Problem testers are Utkarsh Lath, Bhupendra Kastore. Rizwan Hudda has tested all the problem descriptions and his guidelines about difficulty of the contest.<br />
<br />
Many many thanks to all of you. It was really a nice experience to work with you guys :)<br />
<br />
Editorial for the contest will be posted here on my blog just after the contest. Problems will also be added on spoj so that you can increase your points on spoj also and do some practice of-course.<br />
<br />
See you in the contest :) </div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com2tag:blogger.com,1999:blog-6704226767646806218.post-61961032705285247652013-08-01T12:59:00.000-07:002013-09-11T21:53:20.506-07:00Let's Learn Java.<div dir="ltr" style="text-align: left;" trbidi="on">
from 20Oct finally I would be learning Java for one week :)<br />
<br />
int [] a = new int [10];<br />
Arrays.sort (a);<br />
Arrays.fill (a, 0);<br />
Arrays.fill (a, startRange, endRange, value);<br />
Arrays.sort (a, startIndex, endIndex);<br />
String [] name = String[] {"Praveen", "Dhinwa"};<br />
<br />
Queue <Integer> q = new LinkedList <Integer> ();<br />
q.add();<br />
q.remove();<br />
<br />
String s;<br />
s.substr(startIndex, length)<br />
<span class="code-object" style="color: #910091; font-size: 12px; line-height: 13px;"><br /></span>
<span class="code-object" style="color: #910091; font-size: 12px; line-height: 13px;">String</span><span style="font-size: 12px; line-height: 13px;"> a[] = s.split(<span style="color: #009100;">token</span></span><span style="font-size: 12px; line-height: 13px;">);</span><br />
<br />
String s;<br />
<span style="font-size: 12px; line-height: 13px;">Integer.parseInt (s);</span><br />
<span style="font-size: 12px; line-height: 13px;"><br /></span>
<span style="font-size: 12px; line-height: 13px;"><br /></span>
<br />
<div>
<br /></div>
</div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com0tag:blogger.com,1999:blog-6704226767646806218.post-30472430021711688312013-06-23T12:18:00.002-07:002013-06-23T12:19:53.157-07:00Digit Dynamic Programming problemWe will solve a DP problem today.<br />
<br />
dp state is (index, tight).<br />
where index is the position where we currently are (consider the process of constructing solution from left to right).<br />
where tight is a variable which states the number which we have constructed up to now, is strictly less/greater or equal. Tight is false, means it has become less or greater. but true when equal.<br />
<br />
Ex. 1. <a href="http://www.spoj.com/problems/SQAMOD/">http://www.spoj.com/problems/SQAMOD/</a><br />
find no of binary numbers less than a given n digit number S which have sum of squares of digits modulo 3 to be zero,<br />
Solution:<br />
1. dp (index, int sumModulo3, int tight):<br />
So let us see the transitions to different states. You can understand that by reading the code.<br />
<br />
<script src="https://gist.github.com/praveendhinwa/5846181.js"></script>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com3tag:blogger.com,1999:blog-6704226767646806218.post-85199691777751271752013-06-23T05:07:00.000-07:002013-11-30T05:11:52.570-08:00700 problems to understand you complete algorithmic programming.<div dir="ltr" style="text-align: left;" trbidi="on">
<strong>1. Segment Tree:</strong><br />
<strong></strong><br />
<em>To Read :</em><br />
<a href="http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static">http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static</a><br />
<a href="http://ronzii.wordpress.com/2011/07/08/segment-tree-tutorial/">http://ronzii.wordpress.com/2011/07/08/segment-tree-tutorial/</a><br />
<a href="http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html">http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html</a><br />
<a href="http://olympiad.cs.uct.ac.za/presentations/camp3_2007/interval_trees.pdf">http://olympiad.cs.uct.ac.za/presentations/camp3_2007/interval_trees.pdf</a><br />
<a href="http://codeforces.com/blog/entry/6281">http://codeforces.com/blog/entry/6281</a><br />
<a href="http://apps.topcoder.com/forums/?module=Thread&threadID=651820&start=0&mc=2#1146133">http://apps.topcoder.com/forums/?module=Thread&threadID=651820&start=0&mc=2#1146133</a><br />
<a href="http://www.algorithmist.com/index.php/Segmented_Trees">http://www.algorithmist.com/index.php/Segmented_Trees</a><br />
<a href="http://letuskode.blogspot.in/2013/01/segtrees.html">http://letuskode.blogspot.in/2013/01/segtrees.html</a><br />
<a href="http://wcipeg.com/wiki/Heavy-light_decomposition">http://wcipeg.com/wiki/Heavy-light_decomposition</a><br />
<a href="http://discuss.codechef.com/questions/5960/rnestescape-from-the-mines">http://discuss.codechef.com/questions/5960/rnestescape-from-the-mines</a><br />
<a href="http://ideone.com/dPS5N">http://ideone.com/dPS5N</a> (Heavy Light implementation).<br />
<a href="https://sites.google.com/site/indy256/algo/heavy_light">https://sites.google.com/site/indy256/algo/heavy_light</a> (Heavy Light implementation).<br />
<br />
<em>Problems:</em><br />
<br />
<a href="http://www.spoj.com/problems/GSS1">http://www.spoj.com/problems/GSS1</a><br />
<a href="http://www.spoj.com/problems/GSS2">http://www.spoj.com/problems/GSS2</a><br />
<a href="http://www.spoj.com/problems/GSS3">http://www.spoj.com/problems/GSS3</a><br />
<a href="http://www.spoj.com/problems/GSS4">http://www.spoj.com/problems/GSS4</a><br />
<a href="http://www.spoj.com/problems/GSS5">http://www.spoj.com/problems/GSS5</a><br />
<a href="http://www.spoj.com/problems/GSS6">http://www.spoj.com/problems/GSS6</a><br />
<a href="http://www.spoj.com/problems/GSS7">http://www.spoj.com/problems/GSS7</a><br />
<a href="http://www.spoj.com/problems/ANDROUND/">http://www.spoj.com/problems/ANDROUND/</a><br />
<a href="http://www.spoj.com/problems/BRCKTS/">http://www.spoj.com/problems/BRCKTS/</a><br />
<a href="http://www.spoj.com/problems/DQUERY/">http://www.spoj.com/problems/DQUERY/</a><br />
<a href="http://www.spoj.com/problems/FREQUENT/">http://www.spoj.com/problems/FREQUENT/</a><br />
<a href="http://www.spoj.com/problems/HEAPULM/">http://www.spoj.com/problems/HEAPULM/</a><br />
<a href="http://www.spoj.com/problems/HELPR2D2/">http://www.spoj.com/problems/HELPR2D2/</a><br />
<a href="http://www.spoj.com/problems/KGSS/">http://www.spoj.com/problems/KGSS/</a><br />
<a href="http://www.spoj.com/problems/MKTHNUM/">http://www.spoj.com/problems/MKTHNUM/</a><br />
<a href="http://www.spoj.com/problems/NICEDAY/">http://www.spoj.com/problems/NICEDAY/</a><br />
<a href="http://www.spoj.com/problems/YODANESS/">http://www.spoj.com/problems/YODANESS/</a><br />
<a href="http://www.spoj.pl/problems/INCSEQ/" target="_blank">http://www.spoj.pl/problems/INCSEQ/</a><br />
<a href="http://www.spoj.pl/problems/INCDSEQ/" target="_blank">http://www.spoj.pl/problems/INCDSEQ/</a><br />
<a href="http://www.spoj.pl/problems/KQUERY/" target="_blank">http://www.spoj.pl/problems/KQUERY/</a><br />
<a href="http://www.spoj.pl/problems/QTREE/" target="_blank">http://www.spoj.pl/problems/QTREE/</a><br />
<a href="http://www.spoj.pl/problems/QTREE2/" target="_blank">http://www.spoj.pl/problems/QTREE2/</a><br />
<a href="http://www.spoj.pl/problems/QTREE3/" target="_blank">http://www.spoj.pl/problems/QTREE3/</a><br />
<a href="http://www.spoj.com/problems/QTREE4/">http://www.spoj.com/problems/QTREE4/</a><br />
<a href="http://www.spoj.com/problems/QTREE5/">http://www.spoj.com/problems/QTREE5/</a><br />
<a href="http://www.spoj.pl/problems/CTRICK/" target="_blank">http://www.spoj.pl/problems/CTRICK/</a><br />
<a href="http://www.spoj.pl/problems/MATSUM/" target="_blank">http://www.spoj.pl/problems/MATSUM/</a><br />
<a href="http://www.spoj.pl/problems/RATING/" target="_blank">http://www.spoj.pl/problems/RATING/</a><br />
<a href="http://www.spoj.pl/problems/RRSCHED/" target="_blank">http://www.spoj.pl/problems/RRSCHED/</a><br />
<a href="http://www.spoj.pl/problems/SUPPER/" target="_blank">http://www.spoj.pl/problems/SUPPER/</a><br />
<a href="http://www.spoj.pl/problems/ORDERS/" target="_blank">http://www.spoj.pl/problems/ORDERS/</a><br />
<a href="http://www.spoj.com/problems/MULTQ3/">http://www.spoj.com/problems/MULTQ3/</a><br />
<a href="http://www.spoj.com/problems/RPAR/">http://www.spoj.com/problems/RPAR/</a><br />
<a href="http://www.spoj.com/problems/PATULJCI/">http://www.spoj.com/problems/PATULJCI/</a><br />
<a href="http://www.spoj.com/problems/DISUBSTR/">http://www.spoj.com/problems/DISUBSTR/</a><br />
<a href="http://www.spoj.com/problems/HORRIBLE"><span style="color: #d52a33;">http://www.spoj.com/problems/HORRIBLE</span></a> <!-- relax, merge,update--><br />
<a href="http://www.spoj.pl/problems/IOPC1207/"><span style="color: #d52a33;">http://www.spoj.pl/problems/IOPC1207/</span></a> <br />
<a href="http://www.spoj.com/problems/SEGSQRSS/"><span style="color: #d52a33;">http://www.spoj.com/problems/SEGSQRSS/</span></a> <!-- range update, range query, merge, relax--><br />
<a href="http://www.spoj.com/problems/ORDERSET/"><span style="color: #d52a33;">http://www.spoj.com/problems/ORDERSET/</span></a> <!-- compression + merge + search--><br />
<a href="http://www.spoj.com/problems/HELPR2D2/"><span style="color: #d52a33;">http://www.spoj.com/problems/HELPR2D2/</span></a> <!-- binary search + mergeup--><br />
<a href="http://www.spoj.com/problems/TEMPLEQ"><span style="color: #d52a33;">http://www.spoj.com/problems/TEMPLEQ</span></a> <br />
<a href="http://www.codechef.com/problems/QTREE">http://www.codechef.com/problems/QTREE</a><br />
<a href="http://www.codechef.com/problems/LEBOBBLE">http://www.codechef.com/problems/LEBOBBLE</a><br />
<a href="http://www.codechef.com/problems/DGCD">http://www.codechef.com/problems/DGCD</a><br />
<a href="http://www.codechef.com/problems/QUERY">http://www.codechef.com/problems/QUERY</a><br />
<a href="http://codeforces.com/problemset/problem/280/D">http://codeforces.com/problemset/problem/280/D</a><br />
<a href="http://codeforces.com/problemset/problem/117/E">http://codeforces.com/problemset/problem/117/E</a><br />
<a href="http://codeforces.com/problemset/problem/167/D">http://codeforces.com/problemset/problem/167/D</a><br />
<a href="http://codeforces.com/problemset/problem/266/E">http://codeforces.com/problemset/problem/266/E</a><br />
<a href="http://codeforces.com/problemset/problem/145/E">http://codeforces.com/problemset/problem/145/E</a><br />
<a href="http://codeforces.com/problemset/problem/226/E">http://codeforces.com/problemset/problem/226/E</a><br />
<a href="http://codeforces.com/problemset/problem/311/C">http://codeforces.com/problemset/problem/311/C</a><br />
<a href="http://codeforces.com/problemset/problem/276/E">http://codeforces.com/problemset/problem/276/E</a><br />
<a href="http://codeforces.com/problemset/problem/221/D">http://codeforces.com/problemset/problem/221/D</a><br />
<a href="http://codeforces.com/problemset/problem/174/C">http://codeforces.com/problemset/problem/174/C</a><br />
<a href="http://codeforces.com/problemset/problem/301/D">http://codeforces.com/problemset/problem/301/D</a><br />
<a href="http://codeforces.com/problemset/problem/61/E">http://codeforces.com/problemset/problem/61/E</a><br />
<a href="http://codeforces.com/problemset/problem/103/D">http://codeforces.com/problemset/problem/103/D</a><br />
<a href="http://codeforces.com/problemset/problem/165/D">http://codeforces.com/problemset/problem/165/D</a><br />
<a href="http://codeforces.com/problemset/problem/52/C">http://codeforces.com/problemset/problem/52/C</a><br />
<a href="http://codeforces.com/problemset/problem/85/D">http://codeforces.com/problemset/problem/85/D</a><br />
<a href="http://codeforces.com/problemset/problem/242/E">http://codeforces.com/problemset/problem/242/E</a><br />
<a href="http://codeforces.com/problemset/problem/111/B">http://codeforces.com/problemset/problem/111/B</a><br />
<a href="http://codeforces.com/problemset/problem/220/B">http://codeforces.com/problemset/problem/220/B</a><br />
<a href="http://codeforces.com/problemset/problem/195/E">http://codeforces.com/problemset/problem/195/E</a><br />
<a href="http://codeforces.com/problemset/problem/219/E">http://codeforces.com/problemset/problem/219/E</a><br />
<a href="http://codeforces.com/problemset/problem/281/D">http://codeforces.com/problemset/problem/281/D</a><br />
<a href="http://codeforces.com/problemset/problem/121/E">http://codeforces.com/problemset/problem/121/E</a><br />
<a href="http://codeforces.com/problemset/problem/86/D">http://codeforces.com/problemset/problem/86/D</a><br />
<a href="http://codeforces.com/problemset/problem/182/C">http://codeforces.com/problemset/problem/182/C</a><br />
<a href="http://codeforces.com/problemset/problem/19/D">http://codeforces.com/problemset/problem/19/D</a><br />
<a href="http://codeforces.com/problemset/problem/258/E">http://codeforces.com/problemset/problem/258/E</a><br />
<a href="http://codeforces.com/problemset/problem/190/E">http://codeforces.com/problemset/problem/190/E</a><br />
<a href="http://codeforces.com/problemset/problem/295/E">http://codeforces.com/problemset/problem/295/E</a><br />
<a href="http://codeforces.com/problemset/problem/160/E">http://codeforces.com/problemset/problem/160/E</a><br />
<a href="http://codeforces.com/problemset/problem/163/E">http://codeforces.com/problemset/problem/163/E</a><br />
<a href="http://codeforces.com/problemset/problem/192/E">http://codeforces.com/problemset/problem/192/E</a><br />
<a href="http://codeforces.com/problemset/problem/316/E3">http://codeforces.com/problemset/problem/316/E3</a><br />
<a href="http://codeforces.com/problemset/problem/280/E">http://codeforces.com/problemset/problem/280/E</a><br />
<a href="http://codeforces.com/problemset/problem/238/D">http://codeforces.com/problemset/problem/238/D</a><!-- binary search, update ,relax, merge, mergeup--><!-- relax, merge, leaf--><br />
<br />
SRM 310 -> <a href="http://www.topcoder.com/stat?c=problem_statement&pm=6551&rd=9990">Floating Median</a><br />
<a href="http://www.topcoder.com/tc?module=LinkTracking&link=http://acm.pku.edu.cn/JudgeOnline/problem?id=1986&refer=" refer="lowestCommonAncestor">http://acm.pku.edu.cn/JudgeOnline/problem?id=1986</a><br />
<a href="http://www.topcoder.com/tc?module=LinkTracking&link=http://acm.pku.edu.cn/JudgeOnline/problem?id=2374&refer=" refer="lowestCommonAncestor">http://acm.pku.edu.cn/JudgeOnline/problem?id=2374</a><br />
<a href="http://www.topcoder.com/tc?module=LinkTracking&link=http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2045&refer=" refer="lowestCommonAncestor">http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2045</a><br />
<a href="http://www.topcoder.com/tc?module=LinkTracking&link=http://acm.pku.edu.cn/JudgeOnline/problem?id=2763&refer=" refer="lowestCommonAncestor">http://acm.pku.edu.cn/JudgeOnline/problem?id=2763</a><br />
<a href="http://www.topcoder.com/tc?module=LinkTracking&link=http://www.spoj.pl/problems/QTREE2/&refer=" refer="lowestCommonAncestor">http://www.spoj.pl/problems/QTREE2/</a><br />
<a href="http://www.topcoder.com/tc?module=LinkTracking&link=http://acm.uva.es/p/v109/10938.html&refer=" refer="lowestCommonAncestor">http://acm.uva.es/p/v109/10938.html</a><br />
<a href="http://acm.sgu.ru/problem.php?contest=0&problem=155" refer="lowestCommonAncestor">http://acm.sgu.ru/problem.php?contest=0&problem=155</a><br />
<br />
<strong>2. BIT (also called Fenwick Tree).</strong><br />
Mostly problems of BIT can also be solved by Segment Tree. But it is shorted and faster to code. Hence it is sometimes very easy.<br />
<br />
<em>To Read:</em><br />
<br />
<a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees">http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees</a><br />
<a href="http://p--np.blogspot.in/2011/04/binary-indexed-tree.html">http://p--np.blogspot.in/2011/04/binary-indexed-tree.html</a><br />
<a href="http://www.algorithmist.com/index.php/Fenwick_tree">http://www.algorithmist.com/index.php/Fenwick_tree</a><br />
<a href="http://en.wikipedia.org/wiki/Fenwick_tree">http://en.wikipedia.org/wiki/Fenwick_tree</a><br />
<a href="http://pavelsimo.blogspot.in/2012/09/counting-inversions-in-array-using-BIT.html">http://pavelsimo.blogspot.in/2012/09/counting-inversions-in-array-using-BIT.html</a><br />
<a href="http://petr-mitrichev.blogspot.in/2013/05/fenwick-tree-range-updates.html">http://petr-mitrichev.blogspot.in/2013/05/fenwick-tree-range-updates.html</a><br />
<br />
<em>Problems:</em><br />
<a href="http://community.topcoder.com/stat?c=problem_statement&pm=10976">http://community.topcoder.com/stat?c=problem_statement&pm=10976</a><br />
And try some earlier problems which are solvable by this data structure to practice more.<br />
Try mobile problem of IOI. 2D BIT.<br />
<br />
3. Dynamic Programming (DP):<br />
<br />
To Read:<br />
<br />
<a href="http://en.wikipedia.org/wiki/Edit_distance">http://en.wikipedia.org/wiki/Edit_distance</a><br />
<a href="http://www.codechef.com/wiki/tutorial-dynamic-programming">http://www.codechef.com/wiki/tutorial-dynamic-programming</a><br />
<br />
Problems:<br />
<br />
SGU Problems : <a href="http://acm.sgu.ru/problem.php?contest=0&problem=269">269</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=273">273</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=304">304</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=317">317</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=356">356</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=396">396</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=445">445</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=447">447</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=458">458</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=489">489</a>, <a href="http://acm.sgu.ru/problem.php?contest=0&problem=494">494</a><br />
<a href="http://www.spoj.com/problems/SAMER08D/">http://www.spoj.com/problems/SAMER08D/</a><br />
<a href="http://acm.sgu.ru/problem.php?contest=0&problem=199">http://acm.sgu.ru/problem.php?contest=0&problem=199</a><br />
<a href="http://www.spoj.com/problems/MDOLLS/">http://www.spoj.com/problems/MDOLLS/</a><br />
<a href="http://www.spoj.com/problems/MSTICK/">http://www.spoj.com/problems/MSTICK/</a><br />
<a href="http://www.spoj.com/problems/MCARDS/">http://www.spoj.com/problems/MCARDS/</a><br />
<a href="http://www.spoj.com/problems/MIXTURES/">http://www.spoj.com/problems/MIXTURES/</a><br />
<a href="http://www.spoj.com/problems/SCUBADIV/">http://www.spoj.com/problems/SCUBADIV/</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000355">http://z-trening.com/tasks.php?show_task=5000000355</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000286">http://z-trening.com/tasks.php?show_task=5000000286</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000465">http://z-trening.com/tasks.php?show_task=5000000465</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000310">http://z-trening.com/tasks.php?show_task=5000000310</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000778">http://z-trening.com/tasks.php?show_task=5000000778</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000363">http://z-trening.com/tasks.php?show_task=5000000363</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000001024">http://z-trening.com/tasks.php?show_task=5000001024</a><br />
<a href="http://www.spoj.com/problems/VOCV/">http://www.spoj.com/problems/VOCV/</a><br />
<a href="http://www.spoj.com/problems/PT07F/">http://www.spoj.com/problems/PT07F/</a><br />
<a href="http://www.spoj.com/problems/PT07X/">http://www.spoj.com/problems/PT07X/</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000070">http://z-trening.com/tasks.php?show_task=5000000070</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000569">http://z-trening.com/tasks.php?show_task=5000000569</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000441">http://z-trening.com/tasks.php?show_task=5000000441</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000050">http://z-trening.com/tasks.php?show_task=5000000050</a><br />
<a href="http://www.spoj.com/problems/RENT/">http://www.spoj.com/problems/RENT/</a><br />
<a href="http://www.spoj.com/problems/INCSEQ/">http://www.spoj.com/problems/INCSEQ/</a><br />
<a href="http://www.spoj.com/problems/INCDSEQ/">http://www.spoj.com/problems/INCDSEQ/</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000624">http://z-trening.com/tasks.php?show_task=5000000624</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000742">http://z-trening.com/tasks.php?show_task=5000000742</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000749">http://z-trening.com/tasks.php?show_task=5000000749</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000001044">http://z-trening.com/tasks.php?show_task=5000001044</a><br />
<a href="http://www.spoj.com/problems/SEQ/">http://www.spoj.com/problems/SEQ/</a><br />
<a href="http://www.spoj.com/problems/SPP/">http://www.spoj.com/problems/SPP/</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000078">http://z-trening.com/tasks.php?show_task=5000000078</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000543">http://z-trening.com/tasks.php?show_task=5000000543</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000718">http://z-trening.com/tasks.php?show_task=5000000718</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000237">http://z-trening.com/tasks.php?show_task=5000000237</a><br />
<a href="http://z-trening.com/tasks.php?show_task=5000000311">http://z-trening.com/tasks.php?show_task=5000000311</a><br />
<a href="http://www.spoj.com/problems/MORSE/">http://www.spoj.com/problems/MORSE/</a> (dp + trie) Very Hard.<br />
<a href="http://www.spoj.com/problems/MPOLY/">http://www.spoj.com/problems/MPOLY/</a><br />
<a href="http://www.spoj.com/problems/CVXPOLY/">http://www.spoj.com/problems/CVXPOLY/</a><br />
<a href="http://www.spoj.com/problems/MTRIAREA/">http://www.spoj.com/problems/MTRIAREA/</a><br />
<a href="http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=2222">http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=2222</a><br />
<a href="http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122">http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122</a><br />
<a href="http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122">http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1122</a><br />
<a href="http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1125">http://www.lightoj.com/login_main.php?url=volume_showproblem.php?problem=1125</a><br />
Game (IOI 2008, Practice session)<br />
<a href="http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static">http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static</a><br />
<br />
<br />
<br />
Graph Theory:<br />
<a href="http://community.topcoder.com/stat?c=problem_statement&pm=10736">http://community.topcoder.com/stat?c=problem_statement&pm=10736</a><br />
<a href="http://www.spoj.com/problems/TRAFFICN/">http://www.spoj.com/problems/TRAFFICN/</a><br />
<a href="http://www.spoj.com/problems/PA06ANT/">http://www.spoj.com/problems/PA06ANT/</a><br />
<a href="http://www.spoj.com/problems/PT07Z/">http://www.spoj.com/problems/PT07Z/</a><br />
<a href="http://www.spoj.com/problems/EXPLOSN/">http://www.spoj.com/problems/EXPLOSN/</a><br />
<a href="http://www.spoj.com/problems/BUGLIFE/">http://www.spoj.com/problems/BUGLIFE/</a><br />
<a href="http://www.spoj.com/problems/SSORT/">http://www.spoj.com/problems/SSORT/</a><br /><a href="http://www.spoj.com/problems/ARBITRAG/">http://www.spoj.com/problems/ARBITRAG/</a><br /><a href="http://www.spoj.com/problems/CODE/">http://www.spoj.com/problems/CODE/</a><br /><a href="http://www.spoj.com/problems/FROGGER/">http://www.spoj.com/problems/FROGGER/</a><br /><a href="http://www.spoj.com/problems/GCPC11C/">http://www.spoj.com/problems/GCPC11C/</a><br /><a href="http://www.spoj.com/problems/GCPC11J/">http://www.spoj.com/problems/GCPC11J/</a><br /><a href="http://www.spoj.com/problems/GHOSTS/">http://www.spoj.com/problems/GHOSTS/</a><br /><a href="http://www.spoj.com/problems/MAKETREE/">http://www.spoj.com/problems/MAKETREE/</a><br /><a href="http://www.spoj.com/problems/PARADOX/">http://www.spoj.com/problems/PARADOX/</a><br /><a href="http://www.spoj.com/problems/QTREE/">http://www.spoj.com/problems/QTREE/</a><br /><a href="http://www.spoj.com/problems/QTREE2/">http://www.spoj.com/problems/QTREE2/</a><br /><a href="http://www.spoj.com/problems/QUEEN/">http://www.spoj.com/problems/QUEEN/</a><br /><a href="http://www.spoj.com/problems/ROBOTGRI/">http://www.spoj.com/problems/ROBOTGRI/</a><br /><a href="http://www.spoj.com/problems/ELEVTRBL/">http://www.spoj.com/problems/ELEVTRBL/</a><br /><a href="http://www.spoj.com/problems/TRIPINV/">http://www.spoj.com/problems/TRIPINV/</a><br /><a href="http://www.spoj.com/problems/CAPCITY/">http://www.spoj.com/problems/CAPCITY/</a><br /><a href="http://www.spoj.com/problems/KOICOST/">http://www.spoj.com/problems/KOICOST/</a><br /></div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com13tag:blogger.com,1999:blog-6704226767646806218.post-3347619778136305382013-05-23T16:35:00.002-07:002013-09-27T01:18:03.240-07:00Sieve Methods : Prime, Divisor, Euler Phi etc.<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
Structure of the article. First I will explain what does sieve mean. Then I will give you some examples with corresponding java codes and finally some exercises :)<br />
<br />
According to <a href="http://www.thefreedictionary.com/sieve">http://www.thefreedictionary.com/sieve</a> , "sieve" means A utensil of wire mesh or closely perforated metal, used for straining, sifting, ricing, or puréeing. Similar to this definition sieve is a method of doing stuff, where you keep rejecting the things that are useless and reducing the space that you are currently looking at. <br />
<br />
So much of thing in air, Let us now take an example.<br />
<br />
<br />
1. <strong>Finding primes upto N.</strong><br />
You have to print all primes upto N.<br />
<br />
<br />
<em>Method1</em> : For all the numbers i from 1 to N, check if i is prime or not. If it is a prime, then print it.<br />
<br />
<u>Subproblem:</u> <br />
<u><br /></u>
Checking whether a number K is prime. <br />
<br />
<u>Solution</u>:<br />
<br />
1. For all numbers i from 2 to K-1, check if K is divisible by i (as every number is divisible by 1 and itself). If yes, then not a prime else the number is a prime.<br />
<br />
Complexity of this solution : O(K)<br />
<br />
2. Note that we do not need to check upto K-1, instead we can very well check upto sqrt(K).<br />
<br />
Proof: Let us say a number K = a * b. Note that atleast one of a and b <= sqrt(K) otherwise product of them would exceed K. So check just upto sqrt(K).<br />
<br />
3. Either use some probabilistic method for finding whether a number is prime or not.<br />
More on this later. For now see link <br />
<br />
<a href="http://en.wikipedia.org/wiki/Primality_test">http://en.wikipedia.org/wiki/Primality_test</a><br />
<a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting">http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting</a><br />
<br />
Method 2:<br />
Now here comes the idea of sieve. So initially assume that all numbers are prime. Then you try to sieve/refine your search range by not looking at the entire numbers but at the reduced space. eg. When you find all the numbers which are divisible by 2, You do not look into those again, as they are already not prime. So those numbers are sieved out. Now try for 3,4, upto n.<br />
In other terms, You first try all the numbers which are divisible are 2 (except 2 itself),<br />
Note that all those wont be primes. So you can remove those out of your consideration now. Now try the same for 3,4,...... N. Finally you will end up with only prime numbers.<br />
For understanding the actual thing going on, see the code.<br />
So the code basically sets all the numbers upto N to be prime. Then for every number that is still prime, we set all of its multiples upto N to be non-prime.<br />
</div>
<pre class="brush: csharp">import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
static boolean[] isPrime;
public static void sieveOptimized(int N) {
isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++)
isPrime[i] = true;
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
// For further optimization, You can do instead of j += i, j += (2 * i).
// Proof is left to reader :)
for (int j = i * i; j <= N; j += i)
isPrime[j] = false;
}
}
}
public static void sieve(int N) {
isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++)
isPrime[i] = true;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
for (int j = i + i; j <= N; j += i)
isPrime[j] = false;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int limit = sc.nextInt();
// call the sieve method
sieveOptimized(limit);
for (int i = 1; i <= limit; i++) {
if (isPrime[i])
System.out.printf("%d ",i);
}
}
}
</pre>
<div class="brush: csharp">
Now comes the complexity part: Complexity of this code is<strong> O(n * logn).</strong> </div>
<div class="brush: csharp">
Proof: (This proof comes a lot of times in various algorithms, So pay attention).</div>
<div class="brush: csharp">
For all numbers i going from 2 to n, you need to check all the multiples of i. Note that number of multiples of i upto n are n / i. Hence Expression for the complexity will be written as n / 2 + n / 3 + .. + 1. Take n common out of expression. Now it becomes n * (1 / 2 + ..... + 1/n). <br />
Now as the expression is definitely greater than n. So adding an n to the expression won't have any effect on the complexity, So add n to the expression and now it becomes n * (1 + 1 / 2 + ... + 1/ n). The expression (1 + 1 / 2 + 1 / 3 + ... 1 / n) is harmonic sum and it's bounded by ln(n). Hence overall complexity is O(n * logn)</div>
<div class="brush: csharp">
<em>Proof of harmonic sum</em>: </div>
<div class="brush: csharp">
A simple Proof: Let us integrate 1 / x from 1 to n. (Note that we are doing integration, which means sum of area under the curve 1/x, which is greater than (1 + 1 / 2 + ... + 1 / n). Value of the integral can be found easily. In fact integration of 1/x dx is ln(x). </div>
<div class="brush: csharp">
</div>
<div class="brush: csharp">
<strong>2. Finding Sum of divisors of numbers upto N.</strong><br />
Now you have to find sum of divisors of all numbers upto N. Here we are not just considering proper divisors(numbers other 1 and itself), we are considering all the divisors. Here you can do something like this. <br />
Here let us say divisorSum[i] denotes sum of divisors of i. Intially value of divisorSum[i] is equal to zero. Then for all the numbers i from 1 to n, We check all the multiples of i (let us say j) and add i to divisorSum[j].<br />
In other words, Start from 1 and for all the numbers which are multiples of 1, increment their sumDiviors by 1. </div>
<div class="brush: csharp">
Now do the same for 2,3, ... N. Note that for a number i, you are doing this adding operation upto N/i times. So the complexity calculation is same as before.<br />
Look the beautifully commented code.</div>
<br />
<pre class="brush: csharp">import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
int divisorSum[] = new int [n + 1];
// For every number i, You know that 2*i,3*i,4*i upto k*i such that k*i<=n, will have i
// as one of it's divisors, so add that to divisorSum[j]
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
divisorSum[j] += i;
}
}
// Complexity of this code is O(n * logn)
// Proof: Expression for the complexity can be written as n / 1 + n / 2 + ... + n / n
// take n common
// n * (1 + 1 / 2 + ..... + 1/n)
// (1 + 1 / 2 + 1 / 3 + ... 1 / n) is harmonic sum and it's bounded by logn.
// A simple Proof: Let us integrate 1 / x from 1 to n.
// (Note that we are doing integration, which means sum of area under the curve 1/x
// which is greater than (1 + 1 / 2 + ... + 1 / n)
// value of integration can be found easily
// as integration of 1/x dx is ln(x)
for (int i = 1; i <= n; i++)
System.out.printf("%d ", divisorSum[i]);
System.out.printf("\n");
}
}
}
</pre>
<br />
3. <strong>Finding No of divisors of numbers upto N.</strong><br />
<strong> </strong> This is also same as the previous example. Here instead of the storing sum in the array, store the number of divisors and for every multiple of i (say j), In the previous example, you were adding value i to divisorSum[j] , Here just increment the count of noOfDivisior[j] by one.<br />
Code is very easy and hence omitted. Complexity is also same.<br />
<br />
<strong>4. Sieve for finding euler phi function.</strong><br />
I will denote the euler phi function for a number n by phi(n). phi(n) is defined as follows.<br />
It is count of how many number from 1 to n are coprime(having gcd value 1) to n.<br />
For example phi(6) is 2 as 1,5 are coprime to 6.<br />
Few properties of phi function :<br />
a). phi(p) = p - 1. Where p is prime. All the numbers from 1 to p - 1 are coprime to p.<br />
b). phi(a * b) = phi(a) * phi(b) where a and b are coprime.<br />
c). phi(p^k) = p^k - p^(k - 1). Note that here ^ denotes power. Here all the numbers from 1 to p^k are coprime to p^k except all the multiples of p, which are exactly p^(k -1).<br />
<br />
Method for finding: <br />
1. Simple : For all numbers from 1 to n, check if it is coprime to n or not, If yes add that to your answer.<br />
2. Let us say your number is n, which can be denoted as p1^k1 * p2^k2 ..... *p_m*k_m. Note that here p1, p2.... pm are prime. Basically n is written in it's prime representation. <br />
Then phi(n) would be [ p1^k1 - (p1^(k1-1) ) ] * ....... [p_m^k_m - (p_m^(k_m-1) )] . The expression for n can also be written as p1^k1 * p2^k2 * .... * p_m^k_m * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/pm).<br />
which is equal to n * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/p_m).<br />
See the code for details.</div>
<pre class="brush: csharp">import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
public static boolean isPrime (int n) {
if (n < 2)
return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
public static int eulerPhiDirect (int n) {
int result = n;
for (int i = 2; i <= n; i++) {
if (isPrime(i))
result -= result / i;
}
return result;
}
public static int eulerPhi (int n) {
int result = n;
// think that it like this, initially all numbers have gcd with n to be equal to 1.
// Hence value of result is n
// according to formulla n * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/pm). We will be calculating value
// of the product upto i. that is n * (1 - 1/p1) * ... (1 - 1/p_i)
// So let us take example of p1. value of result after one iteration will be n - n / p1, which is precisly
// n * (1 - 1/p1).
// Similarily by induction hypthesis we can say finally the result will be as required.
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
result -= result / i;
// By using while loop here, we are ensuing that all the numbers i will be prime.
// because for every i, all it's multiples are gets removed.
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
result -= result / n;
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
// call the eulerPhiDirect or eulerPhi method.
// culerPhi is more faster as it does not take sqrt(n) for checking for prime
int ans = eulerPhiDirect (n);
System.out.println(ans);
}
}
}
</pre>
<pre class="brush: csharp"> </pre>
Now Let us calculate value of sieve of all numbers from 1 to N.</div>
<div class="brush: csharp">
Let us say eulerPhi[i] be the value of phi(i). Assign initially all the values of eulerPhi[i] to be i. Then for every prime p, for all multiples of p, we will multiply value of eulerPhi[i] by (1 - 1/p) as per the formula. multiplying eulerPhi[i] by (1 - 1/p) is exactly equal to eulerPhi[i] -= (eulerPhi[i] / p). </div>
<pre class="brush: csharp">import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
public static boolean isPrime (int n) {
if (n < 2)
return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
private static int[] eulerPhi;
public static void eulerSieve (int N) {
eulerPhi = new int[N + 1];
// set initial value of phi(i) = i
for (int i = 1; i <= N; i++)
eulerPhi[i] = i;
// for every prime i, do as described in blog.
// Note that we are using isPrime(i) function that takes sqrt(n) time. You are advised to write
// a seperate sieve of finding primes as described by me.
// which will reduce the compleixty of this to n * log(n)
// Proof of this is similar to previous ones. Left to reader.
for (int i = 1; i <= N; i++) {
if (isPrime(i))
for (int j = i; j <= N; j += i)
eulerPhi[j] -= eulerPhi[j] / i;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
eulerSieve(N);
for (int i = 1; i <= N; i++)
System.out.printf("%d ",eulerPhi[i]);
}
}
</pre>
<div class="brush: csharp">
5. <strong>Sieve for finding inverse modulo m.</strong><br />
<strong> </strong>Inverse of a number a with respect to m is defined as b * a = 1 mod m. Then b is called inverse of a modulo m. <br />
So first of all do you realize that it is not necessary to exist the inverse? Example for a = 4, b = 6.<br />
Let us play around the expressions. a * b = 1 mod m can be written as a * b = 1 + m * k. <br />
which can be written as a * b - m * k = 1. If the left side has a common factor of both a and m, means gcd(a,m) != 1, then note that right side won't be divisible by that number, Hence no solution of <br />
the equation when a and m has gcd non zero. Hence inverse will exist when a and m have non zero gcd.<br />
<br />
Now solving a * b + m * (-k) = 1. write the same as a * b + m * k1 = 1. <br />
So let us try to find solution of a * b + k * m = 1. This k is not equal to previous k, infact it is -k. It is equal to k1.<br />
So let us try to solve generic problem a * x + b * y = 1. where a and b can also be negative and gcd(a, b) = 1.<br />
Let us try a simpler version of the same problem which is solving b * x1 + (a % b) * y = 1;<br />
Now try to relate these equations. <br />
a % b = a - [ a / b] * b. where [] denotes floor function. This is same as removing all multiples of b from a, which is exactly equal to a % b.<br />
Now the equation turns into b * x1 + (a - [a/b] * b) * y1 = 1<br />
which is a * y1 + b * (x1 - [a/b] * y1) = 1. <br />
So this is recursive version of a * x + b * y = 1, where x is replaced with y1 and y is replaced with x1 - [a/b] * y1.<br />
Things getting really complex. <br />
(Note that this method is exactly similar to finding gcd of two numbers). Seeing the code will help you to understand more.)<br />
Complexity of this code is same as gcd as it has exactly the same recurrence relation as of that. Time complexity of gcd(m, n) is log (max(m , n)). Hence we can consider time complexity of this method around O(logn).<br />
<br />
<pre class="brush: csharp">import java.io.*;
import java.util.*;
import java.math.*;
class pair {
public int x, y;
pair (int x,int y) {
this.x = x;
this.y = y;
}
boolean isEquals (pair p) {
if (this.x == p.x && this.y == p.y)
return true;
else
return false;
}
}
public class Main {
public static int gcd (int a, int b) {
if (b == 0)
return a;
return gcd (b, a % b);
}
public static pair solve (int a,int b) {
if (b == 0) {
// a * x + b * y = 1
// here b = 0
// hence a * x = 1
// if a is not 1, then error else x = 1 and y = 0
// Note that error wont be here, we will always find a which is not 1
// as error case is already handle in solveThis function
return new pair (1, 0);
} else {
// do the recursive call
pair p = solve (b, a % b);
int x1 = p.x;
int y1 = p.y;
int x = y1;
int y = x1 - (a / b) * y1;
return new pair (x, y);
}
}
public static pair solveThis (int a, int b) {
if (gcd (a, b) != 1)
// (-1, -1) corresponds to error, that means no inverse exists in this case
return new pair (-1, -1);
else
return solve (a, b);
}
public static int modpow (long a, long b, long c) {
long res = 1;
while (b > 0) {
if (b % 2 == 1) {
res = (res * a) % c;
}
a = (a * a) % c;
b >>= 1;
}
return (int) res;
}
public static int findInverseModuloPrime (int a, int p) {
return modpow (a, p - 2, p);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int m = sc.nextInt();
pair p = solveThis (a, m);
if (p.isEquals(new pair(-1, -1)))
System.out.printf("Error, inverse does not exist");
else
System.out.printf("%d %d\n", p.x, p.y);
}
}
</pre>
<pre class="brush: csharp"></pre>
<pre class="brush: csharp"> </pre>
Now I will tell you another easier method . Generalized version of Fermat's theorem says that a ^ phi(m) = 1 mod m where gcd(a, m) = 1. Fir finding inverse a ^ (phi(m) - 1) = 1 / a (mod m) = (inverse(a)) mod m.<br />
Hence for finding inverse(a) mod m, You can just find a ^ (phi(m) - 1) by modular exponention method. In case of m being prime, As phi(m) = m - 1. So just find a ^ (m - 2) % m. This is what precisely computed by modpow function in the above function.<br />
<br />
Complexity: <br />
<br />
Now <em>Sieve for finding inverse modulo m:</em><br />
<em> </em>You have to find inverse(i) mod m for i ranging from 1 to n. <br />
as complexity of modpow is log (n). and we are doing this for n numbers. Hence total complexity will be O(n * logn). Here I am going to describe a better method using sieve <br />
Just use the identitiy inverse(i) = (-(m/i) * inverse(m % i) ) % m + m;<br />
Proof: It is good one. I do not want reveal it now. Try yourself. If you come up with it, post it in the comments, I would check whether it is correct or not?<br />
<br /></div>
<pre class="brush: csharp">import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // denotes the range upto which you want to find the value of modInverse[i]
int m = sc.nextInt();
int modInverse[] = new int[n + 1];
modInverse[1] = 1; // this is you know 1 * 1 mod m = 1
for (int i = 2; i <= n; i++) {
modInverse[i] = (-(m/i) * modInverse[m % i]) % m + m;
}
for (int i = 2; i <= n; i++)
System.out.printf("%d ", modInverse[i]);
}
}
</pre>
<div class="brush: csharp">
Finally, Here are some few exercises for you to try</div>
<div class="brush: csharp">
1. <a href="http://www.spoj.com/problems/GCDEX/">http://www.spoj.com/problems/GCDEX/</a></div>
<div class="brush: csharp">
I will keep adding the list if I found some problems.</div>
</div>
praveendhinwahttp://www.blogger.com/profile/03892182821438710542noreply@blogger.com2