CodeChef
  • PRACTICE
    • Easy
    • Medium
    • Hard
    • Challenge
    • Peer
  • COMPETE
  • DISCUSS
    • Wiki
    • Forums
    • Blog
    • Twitter
  • COMMUNITY
    • CodeChef Meetups
    • Campus Chapters
    • Host Your Contest
    • User Groups
    • CodeChef TechTalks
  • HELP
    • Frequently Asked Questions
    • FAQ for Problem Setters
    • Ranks
    • Tutorials
  • ABOUT
    • About CodeChef
    • Team CodeChef
    • Press Room
    • CEO's Corner
    • About Directi

The site will be offline at 16:30 IST for 5 minutes.

Posted by Tojo on September 7th, 2012 Filed in Tutorials View Comments

Hello People,

We will be taking the site offline for some changes to the website. No, we won’t say now what changes, but we assure you all that it will be eye pleasing :)

Downtime From: 16:30(IST)
Period: 5 minutes

The site will remain offline for a period of 5 minutes if every goes well. Kindly bear with us for the downtime.

-Regards,
Tojo Chacko.

  • Share/Bookmark

Site will be offline from 11PM to 12AM (IST) on June 16, 2012

Posted by abhijeet on June 16th, 2012 Filed in Tutorials View Comments

We will be taking the site offline today (June 16, 2012) for scheduled maintenance at 11:00 PM (IST). The site will be offline for a duration of an hour. Please be patient and keep watching this space on what is going to come.

-Abhijeet,
Team CodeChef.

  • Share/Bookmark

CodeChef Book Giveaway Winners

Posted by Shaheen on November 19th, 2009 Filed in Tutorials, Winners View Comments

Drumroll, please…

The winners of the CodeChef Book giveaway are:

  1. Stephen Merriman(triplem) came up with some really nice tutorials for problems as they not only mentioned the approach required to solve the problem, but also explained a number of other strategies that led to the solution.
    Tutorial for Kayaks
    Tutorial for The LCS Problem Revisited
    Tutorial for Just a simple sum

  2. Pratik Tandel (pr0ton) submitted some well written tutorials, and listed a lot of SPOJ problems based on the topics.
    Tutorial for bitwise operations
    Tutorial for binary search

  3. Neelesh (u2001137) – In his tutorials, Neelesh covers topics in mathematics which are very important in some of the problems.
    Basic Number Theory Every Programmer Should Know
    Mathematical Expectation

And just because we loved Ankit and Anil’s enthusiasm and contributions we will be sending them a CodeChef goody bag.

Ankit’s (ankitjain0912) tutorials:
Dynamic Programming
White Night

Anil’s (flying_ant) tutorial:
Graph Theory

Congratulations guys! Your books/merchandise will reach you soon.

On another note,  there are quite a few topics on the Tutorial page that people have requested for and it would be awesome to see more of you contribute to the tutorials on the wiki.

-Shaheen

  • Share/Bookmark

Video Tutorial for Puzzle Game

Posted by The Chef on October 26th, 2009 Filed in Tutorials View Comments

Aloo Makhnis,
Aniruddha from the CodeChef team has put together a video tutorial for Puzzle Game . We hope to start including more content including articles, podcasts and additional videos in the near future. The video is embedded below and also on our wiki:


CodeChef Video Tutorial : A Puzzle Game by Aniruddha Laud from Directi on Vimeo.

What do you guys think? Are video tutorials helpful? What other content can we produce that will help you become better programmers? Anyone want to volunteer to create additional videos or podcasts? These can be interviews, tips, tutorials, whatever you think will help people.

We will be announcing two contest for November and a “special” CodeChef project shortly, stay tuned…
Cheers,
Amit

  • Share/Bookmark

The CodeChef Book Giveaway

Posted by Shaheen on October 9th, 2009 Filed in Contests, Tutorials View Comments

We are constantly thinking about ways how to help people become better programmers.  We recently launched the CodeChef Wiki so that people can share tips, resources and tutorials.  Unfortunately, it seems people have been a little shy about contributing.  To get the ball rolling, we will be giving away books to the top wiki contributors this month.

All you have to do is use the wiki as a place to note all the things you love about programming – resources, tips, tutorials, etc.  At the end of October the top three contributors to the tutorials will each receive a set of The Art of Computer Programming (Volume I, II and III) and the other contributors will receive CodeChef T-shirts and laptop stickers.

How can you contribute to the wiki?

  • Add tips, problem tutorials and topic tutorials
  • Add to the FAQs
  • Add links, resources, list down other programming contests or anything you have come across on the web that has helped you become a better programmer.

Rules:

  • The giveaway is open until 31st October 15th November and is open to everyone (regardless of geography).
  • The top contributors will be decided by the CodeChef team and announced on 3rd 20th November.
  • Making modifications for the sake of increasing your chance of winning will not do you any good. :)
  • As per our wiki guidelines, you can only edit the wiki if you’ve solved at least one contest problem.

If you have any questions, drop us a comment, email or tweet.

  • Share/Bookmark

Introducing a Wiki

Posted by Aniruddha on September 15th, 2009 Filed in Announcement, Features, Tutorials View Comments

Hello all,

At Codechef our goal is to help people become better programmers. An integral part of this is discussion and we find that sometimes, we are the bottleneck for growth amongst the community. In an effort to promote collaboration we are thinking about making the following changes.

1. Introducing a wiki: We plan on introducing a wiki where most users will be able to edit pages related to the FAQ, Tutorials, Tips, Resources, Strategies, etc… We want to create some easily achievable task as the criteria for becoming an editor. Our plan is to let anyone who has had at least one successful submission in any of our contests will be able to edit the wiki. We feel like this will encourage greater collaboration and allow all of you to contribute meaningfully.

2. Disabling comments : We thought that commenting on problems would be a good idea, but we are finding it is not being used in the way we intended it. The comments are mainly from new comers asking questions whose answers are available elsewhere. Unless we can figure out a way to ensure that comments are used for questions related to that problem specifically, we feel that through the wiki, forums, blog, email, twitter and chat (soon coming back), there are enough options to communicate with us and each other.

3. Introducing a new forum : The current forum is not well integrated into the site and also not integrated with our authentication system. We plan on introducing a forum which integrates better and retains the same look and feel as our site. We will also create a section for high priority issues which we will monitor carefully, allowing you guys to bring up any major site or contest issues to our immediate attention.

We would like to know what you think about these new features that we plan to introduce? Do you think that disabling the comments and restricting discussions about problems to the forums is a better idea? Or would you like us to scrap the forums and keep the comments’ section as it is? Also, what do you think about the idea of the wiki editing facility being open to only those who successfully solve problems in the contests? Do leave in comments to let us know what you think :)

Regards,

Aniruddha.

  • Share/Bookmark

The Basic Implementation of a Search Engine

Posted by Vikram on September 11th, 2009 Filed in Campus Chapters, Events, Tech Talks, Tutorials View Comments

On the 3rd of Sept 2009, I delivered a session at MPSTME, NMIMS (Mumbai), on ‘The Basic Implementation of a Search Engine’.

The crowd attending the session ranged from first year students to final year students and so I kept the session rather basic without going into the details of the subject. The students were bright and very enthusiastic, and the audience participation was simply awesome.

In the session I demonstrated a small Perl Script with a few functions to explain a Crawler, Indexer and Search Logic. I am attaching the code to this post and below is the video of the session.

Lastly, I would like to thank Gaurav Munjal and the entire ACM MPSTME team for all their help.

This session was part of a CodeChef Campus Chapter. Register here to start a Campus Chapter in your college as well.

CodeChef Talk at MPSTME, NMIMS (Mumbai) from Directi on Vimeo.

Cheers,
Vikram
~vix on CodeChef Twitter

  • Share/Bookmark

Tutorial for problem Quadratic Equations

Posted by Aniruddha on August 27th, 2009 Filed in Problems, Tutorials View Comments


Here is a nice tutorial for the problem Quadratic Equations, courtesy Neelesh Bodas

Introduction:

This tutorial discusses one of the “hard problems” of the July Contest – Quadratic Equations. I called this problem “hard” because it is placed in the “hard problems” category and there were only 5.25% successful submissions for this problem. However, I believe this was actually one of the easy problems in this competition – provided you knew a little bit of number theory. Let’s see how.

To begin with, let’s get rid of all the verbosity from the problem statement and understand what the problem actually asks. In simplest terms, the problem asks us to find all possible values of w such that (Aw 2 +Bw+C) is divisible by prime P. In mathematical terms, the task is to find all possible solutions for the congruence:

Aw2+Bw+C ≡ 0 (mod P)
———–   [A]

With Constraints:   0 < A < P,  0 ≤ w, B, C < P < 106.

Incidentally, if you are a number theory fan, chances are that you already know the answer to this problem. Typically this scenario would be discussed in almost every number theory book, and is usually covered under the heading quadratic residues

Before we go into the detailed solution, let’s jot down few basic points first –

  • Can a brute-force solution work? (In almost all programming problems, it becomes very important to understand whether or not the brute-force solution would work without actually writing the code and testing it out. Of course in most of the problems it wouldn’t work.). In the current case, since there are about 10000 test cases and each test case would need 106 iterations in the worst case, the total number of iterations would be 1010. Convince yourself that an empty loop that runs 1010 times needs much more time than 3 seconds. The brute-force approach thus gets ruled out.
  • Observe that since w < P, smaller cases with lower values of P are very easy to handle. For example, when P=2, the only values that w may take are 0 and 1. Similarly when P=3, the only allowed values for w are 0,1 and 2. Thus we can use the brute-force approach for smaller values of P, like 2, 3,5 etc.
  • Since B and C can be zero, it makes sense to deal with these cases separately, as the problem could reduce to a less-complicated version in these cases. Observe that:
    • If B=C=0, then the problem reduces to finding all w such that P | (Aw2).Since 0 < A < P and 0 ≤ w < P, the only solution is w = 0.
    • If C=0 but B≠0, then the problem reduces to finding all w such that w*(Aw+B) ≡ 0 (mod P). Since P is prime, this implies that P|w or P|(Aw+B). Clearly, w = 0 is one solution, and other solutions would be obtained by solving the linear congruence
      Aw+B ≡ 0 (mod P)
      ———–   [B]

      Thus observe that in this case we have reduced the problem of solving a quadratic congruence to solving a linear congruence.

    • If B=0 but C≠0 then the problem reduces to finding all w such that
      Aw2+C ≡ 0 (mod P)
      ———–   [C]

      Again observe that we have a special case of quadratic congruence here, which doesn’t have any linear term.

  • In fact, the original congruence in [A] can always be reduced to a form similar to [C] even in the most general case, when 0 < A,B,C < P. The trick is to do the “square completion”. Observe that we can rewrite [A] as:
    A2w2+4ABw+4AC+B2-B2 ≡   0   (mod P)

    ⇔  (2Aw+B)2+(4AC-B2)   ≡   0   (mod P)

    Let u=2Aw+B and D=(4AC-B2). Then the congruence can be rewritten as:

    u2 + D   ≡   0   (mod P)

    Of course, if u or D are not between 0 to P-1, then can be changed modulo P to bring them in the required range.

    Thus, the most general case of [A] needs a two-step solution:

    1. Solve the following quadratic congruence for u:
      u2+(4AC-B2)   ≡   0   (mod P)

      ———–   [D]
    2. Solve the following linear congruence for w:
      (2Aw+B)   ≡   u   (mod P)
      i.e.   2Aw   ≡   (u-B)   (mod P)
      ———–   [E]

      where u is the solution obtained in step (1).

Thus it should be clear by now that this entire problem is all about dealing with linear and quadratic congruences. Incidentally, a quick google search provides us with all references that are necessary (and sufficient) to solve this problem. That’s why I referred this problem as an “easy problem” in the beginning.

In the remainder of this tutorial we shall see how to solve linear and quadratic congruences. The task of putting these two concepts together and solving the actual problem is (purposely) left as an exercise to the reader.

Solving linear congruences:

Task:  Find all possible solutions to the congruence

Mw   ≡   N   (mod P)

Constraints:  P is prime, 0 <   M,N,w   <   P

Let’s take a simple example to understand this case. Let M = 4, N = 3 and P = 11. The following table lists the required values-

w mod P (Mw) mod P (Mw – N) mod P
0 0 8
1 4 1
2 8 5
3 1 9
4 5 2
5 9 6
6 2 10
7 6 3
8 10 7
9 3 0
10 7 4

The first column lists all possible values of “w mod P” and the other two columns represent the corresponding values for “(Mw) mod P” and “(Mw-N) mod P” respectively. Observe that no values seem to be repeated in second or third column.  In other words, it looks like all values of   “(Mw) mod P”  are different when w belongs to the set   {0,1,…,P-1}.

It is easy to see that this observation will always hold. To see why, suppose there are two distinct values of w, say w1 and w2, with 0 ≤ w2 < w1 < P, such that

Mw1 ≡ k (mod P)     and

Mw2 ≡ k (mod P)

for some k. This would imply that Mw1 ≡ Mw2(mod P), which means P | M(w1-w2), which in turn means P | (w1-w2) : a contradiction since P > w1 > w2 ≥ 0.

Thus we see that every entry in column-2 will be different (and each entry will be between 0 to P-1 inclusive). As there are exactly P entries in column 2, this means that every entry in the set {0,1,…,(p-1)} will occur exactly once in column-2. Consequently, there would be exactly one value of w which would evaluate to N in column-2. In fact, this is the value of w that we are looking for, since this is the only value that satisfies Mw  ≡  N  (mod P). (Applying this argument to the example above, we would return w = 9 as our answer to the congruence Mw ≡ N (mod P)).

Moral of the story – The linear congruence Mw ≡ (mod P) with 0<M,N<P has exactly one solution. And the good news is that it is not at all difficult to find what this solution would be.

Let w = k represent this solution. Then we have:

Mk ≡ N (mod P)

i.e. (Mk – N = Pu) for some integer u.

Rearranging the terms, we get Mk + P(-u) = N.

Observe that since GCD of M and P is 1,  

Bézout’s identity guarantees existence of integers x and y such that Mx+Py=1. A quick google search would reveal that the Extended Euclid’s Algorithm can be used to get values of x and y. Detailed implementation of Extended Euclid’s algorithm is easily available on the web and hence left as a (trivial) exercise to the reader. Once we get x, observe that k = xN. Of course, make sure to adjust the value of xN (if needed) to bring it in the set {0,1,…,P-1}. The solution to the equation (B) can then be obtained by plugging values M = A and N = -B in the above discussion. Similarly solution of (E) can be obtained by plugging M = 2A and N = u-B in the above discussion.

Solving quadratic congruences:

Task:  Find all possible solutions to the congruence Mw2 ≡ N (mod P)

Constraints:  P is prime, 0 <   M,N,w   <   P

Since the table-approach worked in the previous case, let’s use the same again.With M = 4, N = 3 and P = 11, we get following results:

w mod P w2mod P (Mw2)mod P (Mw2-N)mod P
0 0 0 8
1 1 4 1
2 4 5 2
3 9 3 0
4 5 9 6
5 3 1 9
6 3 1 9
7 5 9 6
8 9 3 0
9 4 5 2
10 1 4 1

Observe that unlike the previous table, the columns in this table don’t have all the values. Taking an example of second column (w2mod P ), we see that some values (like 2) are not present, whereas some other values (like 4) are repeated. More specifically –

  • if we ignore the starting 0 in this column, then the column looks symmetric – The values 1,4,9,5,3 repeat in the reverse order.
  • All values in the first half of this column are distinct.

It is easy to see that these two observations will always hold. And the proofs are very trivial:

  • Observe that (P-w)2 ≡ w2 (mod P). Thus, for any w, numbers w2 and (P-w)2 would evaluate to the same result mod P. This means that the column (Mw2 mod P) would always be symmetric around the center.
  • To see why all the values in the first half of the column would be distinct, let us assume that two values of w, say w1 and w2, (WLG let w1 > w2) both occurring in the set {0,1,…,(P-1)/2} evaluate to the same result in column-2, i.e., let Mw12 ≡ Mw22 (mod P). This would mean that P|(w12-w22), which would in turn mean P|(w1+w2) or P|(w1-w2). But this is clearly a contradiction, as both (w1+w2) and (w1-w2) are less than P but greater than zero.

Moral of the story – There are exactly (P-1)/2 distinct values for (w2mod P) with 0 < w < P, and each of these values occurs twice. (Notice the strict inequality “0 w”. This is because when w=0, the value in column-2 is 0 which is the only value that doesn’t repeat).

It is not hard to prove exactly the same results for columns-3 and 4 also. The proofs are very trivial, and are left as an exercise to the reader.

What all this means is that the congruence Mw2 ≡ N(mod P) may or may not have a solution. Further, if it has a solution, say w = k , then there will be exactly one more solution, given by w = (P-k). In other words, the congruence Mw2≡ N (mod P) has either 0 or 2 solutions.

So the entire discussion for the “quadratic congruence case” boils down to two fundamental questions:

  • How do we know whether Mw2 ≡ N (mod P) has a solution or not?
  • If there is a solution, how do we find it?

Interestingly, any web search with this or related questions will certainly end up in references on quadratic residues. Looks like good time to throw-in some theory.

Consider a quadratic congruence x2≡ m(mod n) with 0≤m<n. In mathematical jargon, the number m is called quadratic residue modulo n, if there exists some x that satisfies this congruence. If there is no x that can satisfy this congruence, then m is called quadratic non-residue modulo n.
For example, with m = 9 and n = 15, observe that x = 12 satisfies this congruence, and hence we say that 9 is a quadratic reside modulo 15. Similarly, 4 is also a quadratic residue modulo 15, since x = 2 satisfies the congruence x2≡4(mod 15). On the other hand, there is no x for which x2≡11(mod 15), and hence 11 is a “quadratic non-residue” modulo 15. As another example, observe that 0,1 and 4 are the only quadratic residues modulo 8.

Interestingly, note that it is only the terminology that is new here – the underlying concept is very much close to what most of us would have already studied (hopefully!). For example, we all know that every square is of the form 4k or 4k+1. (Proof is trivial, left as an exercise to the reader). This means that x2≡v(mod 4) has a solution only when v = 0 or 1. In other words, the only quadratic residues modulo 4 are 0 and 1. Taking another example, we (definitely) know that a square always end in 0,1,4,5,6 or 9. That is to say, the congruence x2≡v(mod 10) has a solution only when v belongs to the set {0,1,4,5,6,9}. Stated differently, the set of quadratic non-residues modulo 10 is {2,3,7,8}.

Thus, in the simplest terms – A number m is a called as quadratic residue mod n if a square can take the form (nk+m) for some integer k.

Finally observe that in the current case, we are only interested in finding quadratic residues modulo a prime number. More specifically, we want to find –

  • if x2≡a  (mod p) has a solution for a given a
  • Find the value of x if this equation has a solution.

The first part is somewhat easy. Recollecting

Fermat’s little theorem, we know that xp-1≡1 (mod p) when x < p. Thus, (x2)(p-1)/2≡1 (mod p). In other words, x2≡a(mod p) would have a solution iff a(p-1)/2≡1 (mod p).

Thus, in the current context, to check whether Mw2 ≡ N(mod P) has a solution, we multiply throughout by M to get the congruence (Mw)2 ≡ MN(mod P), and then use the above test with a=MN (and x = Mw)

(An exercise for the reader- Prove xor disprove : a(p-1)/2 will either be congruent to 1 or -1 (mod P) where P is an odd prime and 0 < a < P).

This brings us to the last part of the discussion – The procedure for actually finding the value of a quadratic residue (provided it exists). This is the place where most of us would again do a web search, and would certainly come up with Shank-Tonelli algorithm. This algorithm is actually a procedure for solving quadratic congruences of the form x2≡n (mod P) where P is an odd prime and n is a quadratic residue modulo P. (Proving the correctness of this algorithm is quite complicated and beyond the scope of this tutorial.) We just re-state this algorithm at the end of this tutorial for the sake of completeness.

Thus we have now answered both the questions, and effectively learnt how to tackle quadratic congruences. This completes the discussion of the problem of quadratic equation.

Concluding Remarks:
  • The basic reason why I stated this problem as an “easy” problem in the beginning is that it doesn’t require a person to “think a lot”, or think “out of the box” or “discover” some complex logic. All that is needed is a little bit of playing around, some familiarity with Number Theory, and well-developed Google-search skills. That in fact explains why such problems are actually a feast in programming competitions.
  • The Shank-Tonelli algorithm to solve x2 ≡ a (mod P) where P is an odd prime is as follows:
    1. Express (p-1) as a product of an odd number and a power of 2 – Let p-1 = 2nk
    2. Let q be a quadratic non-residue modulo P. (To find q, set initial value of q to 2 and keep on incrementing till you don’t get q satisfying q(p-1)/2≡ -1 (mod p)
    3. Let t = a(k+1)/2 % p and let r = ak%p
    4. If r≡1 (mod p) then return t as answer (i.e. algorithm ends).
    5. Else find v = smallest power of 2 such that rv≡1(mod p). (Let v = 2i)
    6. Let e = 2(n-i-1)
    7. Let u = q(ke)%P.
    8. Set t = (t*u)%P
    9. Set r = (r*u*u)%P and goto step (4)

This completes the discussion on the problem “Quadratic Equations”. To see actual solutions based on this idea, refer Ashutosh’s Solution, or Josh Metzler’s solution or my solution.

  • Share/Bookmark

Tutorial for problem Product of Divisors

Posted by Aniruddha on August 17th, 2009 Filed in Tutorials View Comments

The problem Product of Divisors asks us to find the last 4 digits of the product of all the divisors of a number. So, suppose we are given a number like 12. The divisors for any number which is not a perfect square will occur in pairs. So, the divisors for the number 12 will be in the following pairs (1,12), (2,6), (3,4). Now, according to the problem statement, we are not to consider the number 12 while computing the answer, so effectively, we can remove the first pair. So, the answer we need will be the product of the numbers 2,6,3,4 which equals 144. Now, the purpose of grouping the numbers in pairs was to show that the product of the numbers in each pair is 12. So, if for a number N, which is not a perfect square, having D divisors, we can always group them into D/2 pairs such that the product of each pair is the original number N. Thus, we effectively transform the answer into N*N*..*N (D-2)/2 times. Thus, The answer in this case becomes N ^ (D/2) where ^ represents the power function and D represents the number of divisors. Thus, for the number 12, the number of divisors is 6, so the answer is 12 ^ ((6-2)/2) = 12 ^ 2 = 144.

Now, let us take the case of a number which is a perfect square. Consider the number 36 which is a perfect square. The divisors of 36 are 1,36,2,18,3,12,4,9,6. So now, if we start grouping them into pairs such that the product of each pair is 36, we get the following pairs (1,36), (2,18), (3,12), (4,9), (6,6). Now, we see that the divisor 6 needs to be repeated to form the pairs of the sort mentioned previously. We have 9 divisors for the number 36. As earlier, we remove 2 of the divisors, that is, the pair (1,36) as the problem statement asks us not to consider the number N while taking the product. Thus we start grouping the numbers into pairs again : (2,18), (3,12), (4,9) and we get one divisor 6 which is left without a divisor to pair up with. So, consider that we group up 6 with 6 itself to get another pair which gives us the value 36. So, the total product will be (36 ^ (number of pairs))/6. So, effectively if we have to calculate the product of divisors for a number N which is a perfect square, our equation becomes N^((D-2)/2) which is N^(D-2)/2. In the earlier case, as D would always be even, D-2 would be even and (D-2)/2 would be an integer. But in this case, as N is a perfect square, (D-2) is odd. We can reframe this as (N^(1/2))^(D-2). Now, as N is a perfect square, N^(1/2) will be an integer. So the answer in this case becomes sqrt(N)^(D-2).

So, we can see that given a number, we can find the required answer using the expressions mentioned above. So now, the only thing left to do is to find the number of divisors. Now, let us see how to calculate the number of divisors of a particular number. Suppose the number N is factorized into its prime factors and their powers as p1^a1 * p2^a2 * … * pn^an. Then, the number of divisors of the number N including 1 and N are (a1+1)*(a2+1)*…*(an+1). Let us see why this is so. Take the case that N is a prime number, then the prime factorization of N can be p1^1 where p1=N. N has 2 divisors 1 and N so the answer is (1+1) which is 2. Now consider a number N which has prime factorization p1^a1 * p2^a2 * … * pn^an. Now, suppose a number B which equals N*P where P is a prime number. Now, the prime factorization of B becomes p1^a1 * p2^a2 * … * pn^an * p^1. Suppose the number N had X divisors. B equals N*P, so all divisors of N are divisors of B. Also, if T is a divisor of B, then so is P*T. Thus, we see that the number of divisors in this case has doubled. That is because of the introduction of P^1 in the sequence, the number of divisors has become X * (1+1). This can easily be extended to introduction of P^Z in the sequence to show that because of this introduction, the number of divisors is increased by a factor (Z+1).

So, now we know how to calculate the number of divisors of a number. We also know that once we know the number of divisors of a number, we can find the required answer using the formulae we derived. But, there is a small catch here. The number N can be pretty large and we need to find the power of N raised to a number which can be a about 100. Also, we need to do this for about 300000 numbers. If we calculate the power of the number modulo some value using an iterative function that iterates over the value of the exponent, our code won’t run within time. We can use a nice little trick here to calculate the value of (a^b)%p by using the observation that if ‘b’ is even, then a^b = a^(b/2) * a^(b/2) and if ‘b’ is odd, a^b = b*pow(a,b-1). Using this, we can calculate the power of a number pretty quickly taking about log(exponent) iterations.


Thus, the rough outline of the required code would be something as follows :
Start
Precompute all primes below 500000
Precompute what numbers below 500000 are perfect squares and their squareroots
Take in number of test cases
While there exists a test case we haven't processed
	Take in the number.
	Find the number of divisors.
	Calculate the answer using the formulae we derived.
	Take the remainder with 10000 while calculating the answers.
	Take care to make sure that we print the last 4 digits correctly with necessary number of 0s. Simply taking modulo 10000 will not work.
	Print the answer
Stop


We leave it to the reader to handle the part where the last 4 digits have to be correctly displayed.

  • Share/Bookmark

Tutorial for problem “Paying Up”

Posted by Aniruddha on July 9th, 2009 Filed in Problems, Tutorials View Comments

Hello,

The problem “Paying Up” was one of the easy ones in the March 2009 contest on Codechef. It is considered an easy problem, because it has a couple of approaches that work. The problem statement boils down to finding a subset of banknotes such that their sum is exactly equal to a certain value. Now, this problem is somewhat similar to the knapsack problem which asks for ways to fill up a knapsack of a certain size optimally with the given blocks. There is a solution based on dynamic programming for this problem, but we will be taking up a solution which makes good use of the way integers are represented in binary to solve this problem.

Now, the limit on the number of banknotes is ‘n’. Let us see how many subsets exist for these banknotes. For finding the number of subsets, we see that for every banknote, we have two choices, either to choose it in our calculation for the sum of notes or to ignore it in calculating the sum. Thus, we have 2 options per banknote and ‘n’ banknotes. So, the total number of subsets thus becomes 2^n where ^ represents the power operation. The number of subsets are small enough for us to bruteforce through them and the program to run in time.

An interesting way to generate all subsets of ‘n’ objects when ‘n’ is considerably small (n <= 20) is to use the properties of how unsigned integers are stored. Consider the number 2^n. This number is represented in binary form as ’10000…0′, that is, 1 followed by n 0s. Also, any number containing a 1 at the same position will surely be greater than 2^n. Thus, all numbers below 2^n do not have a 1 in a position greater than or equal to ‘n’ starting from the LSB. By induction, we can do the same for values of n = n-1 and n-2 and so on. Thus, we can see that any number between 2^(n-1) and 2^n will have a 1 in the position n-1. Extending this logic, we can say that if we consider the numbers from 1 to 2^n, we would be considering all possible ways in which we can choose some objects from ‘n’ objects.

For example, consider n = 3, so 2^n = 8. Let us list ‘i’ and its binary representation
i    Binary representation using ‘n’ bits
0    000
1    001
2    010
3    011
4    100
5    101
6    110
7    111

As you can see, if we consider that 1 means that we have selected object at that position and 0 means that we have not selected the object at that position, we can get all possible subsets of ‘n’ objects by looping over numbers from 1 to 2^n.

For calculating the sum of the subset represented by ‘i’, we loop from 0 to ‘n’ and we check whether the corresponding bit is set in the value for ‘i’ or not. If it is, we include that object in calculating our sum else we don’t. In this way, we can get the sum for all possible subsets of the ‘n’ objects.

This is exactly what we need for this problem. After taking in the number of objects, we loop ‘i’ from 1 to 2^n incrementing the value of ‘i’ by 1 at every stage to give us a new subset. Then for a particular value of ‘i’, we loop ‘j’ from 0 to n and check if the bit at that particular value is set or not. Languages like C / C++ provide bit-wise operators for leftshift and rightshift. For checking if the bit is set at position ‘j’(starting from 0) we can just check if the value of (i & (1<<j)) is 0. If it is 0, then the bit is not set, while if it is greater than 0, then the bit is set. Alternatively, we can also loop from 0 to n and at each stage check whether ‘i’ modulo 2 is equal to 1 or not. If it is 1, then the bit at that position is set, else it’s not. Then we divide ‘i’ by 2 and proceed. At the end of the ‘n’ iterations, ‘i’ will equal 0. The problem with this appraoch is that the modulo operations take much more time compared to the bitwise operations. Thus, now that we know how to check if the bit is set, we initialize a value ‘sum’ equal to 0 at the start of the ‘n’ iterations for a value of ‘i’ and if the bit at position ‘j’ is set, we add the corresponding banknote value to ‘sum’ else we don’t. At the end of these iterations, we check if the value of ‘sum’ equals the required value. If it does, then we have found a subset with the required sum and so we print a “Yes” and exit. Else, if at the end of 2^n iterations of ‘i’ we don’t have a subset with the required sum, then we print a “No” and exit.

The program should look something like this :

Start
Take in the value of 'n' and the required value of sum 'm'
Take in all the values for the banknotes in array 'd[]'
For i = 1 and i < (2^n)
    sum = 0
    For j = 0 and j < n
        if jth bit of i is set
            sum = sum + d[j]
    if sum equals m
        print Yes and return
Print No and return

  • Share/Bookmark
« Previous Entries

Recent Posts

  • The late conquest of dzhulgakov
  • CodeChef judge will be down
  • ACRush eclipsed
  • … and we meet!
  • Progress report of April contests

Categories

  • About (8)
  • ACM ICPC (9)
  • Announcement (121)
  • Campus Chapters (6)
  • College Contests (8)
  • Contests (127)
  • Events (23)
  • FAQ (1)
  • Features (34)
  • Languages (1)
  • Meetup (5)
  • Open Source (1)
  • Practice Problems (7)
  • Prizes (17)
  • Problems (5)
  • Programmer of the Month (27)
  • Tech Talks (6)
  • Tutorials (15)
  • Winners (80)

Recent Comments

  • CodeChef on CodeChef judge will be down
  • Ritwik on CodeChef judge will be down
  • CodeChef on ACRush eclipsed
  • CodeChef on ACRush eclipsed
  • random123 on ACRush eclipsed

Recent Pictures

Blogroll

  • Documentation
  • Plugins
  • Suggest Ideas
  • Support Forum
  • Themes
  • WordPress Blog
  • WordPress Planet

Archives

  • May 2013
  • April 2013
  • March 2013
  • February 2013
  • January 2013
  • December 2012
  • October 2012
  • September 2012
  • August 2012
  • July 2012
  • June 2012
  • May 2012
  • April 2012
  • March 2012
  • February 2012
  • January 2012
  • December 2011
  • November 2011
  • October 2011
  • September 2011
  • August 2011
  • July 2011
  • June 2011
  • May 2011
  • April 2011
  • March 2011
  • February 2011
  • January 2011
  • December 2010
  • November 2010
  • October 2010
  • September 2010
  • August 2010
  • July 2010
  • June 2010
  • May 2010
  • April 2010
  • March 2010
  • February 2010
  • January 2010
  • December 2009
  • November 2009
  • October 2009
  • September 2009
  • August 2009
  • July 2009
  • June 2009
  • May 2009
  • April 2009
  • March 2009
  • February 2009
  • January 2009

Company Blogs

  • Directi
  • .pw Corp Blog
  • CEOs Blog

Careers@Directi


  • About CodeChef
  • About Directi
  • CEO's Corner
  • CodeChef Campus Chapters
  • Blogger Community Program
  • User Group Outreach Program

© 2009, Directi Group. All Rights Reserved.

Sponsors