Hola Amigos,
We are delighted that we turned Senary this March. All this would not have been possible without the problem setting panel in our kitchen. We are truly thankful to everyone in our kitchen for all those delicious problems, mouth watering editorials and awesome contests. We truly appreciate the efforts that our chefs put behind making this possible.
We are happy to announce that we have revamped the problem setting guidelines. You can read more about it here:
Some highlight of the newly released guidelines:
If you would like to join our kitchen as problem setter or tester or editorialist, you can apply here.
With Love and Regards,
Suraj Sharma
Team CodeChef.
Hi all,
Please find below the links to the problems that appeared in the ACM ICPC Amritapuri Regional 2012-13.
Have fun! We will be back soon with more updates.
Cheers,
Team CodeChef.
Hey CodeCheffers,
Time to flash another card from the pack. And this has been long pending. Finally we are revamping our editorials.
Yes, the editorials that we had on our wiki till now, will be on our discussion forum going forward. You can discuss all your doubts and issues regarding any problem at a single place. From the upcoming June Challenge, each and every problem will have its editorial in the form of a community wiki on discuss. You will be able to discuss all your problem related doubts under one roof and get them answered by a broader audience. The link to the problem editorial will appear on each problem page after the contest ends. During the contest, any queries pertaining to the problem can be discussed as comments on the problem page itself based on the guidelines mentioned here.
This is a part of the process to improve our editorials. We have been receiving a lot of feedback to revamp them to make them understandable to everyone including a newbie. We realized the fact that writing simple and explanatory editorials is a very important and time consuming assignment and it was too much of a burden on our problem setters to take this challenge along with the task of creating amazing problems. In spite of this burden, they have been doing a great job at it. Identifying this inadequacy in our process, we have introduced a new role that will be solely responsible for creating amazing Editorials which even an enthusiastic newbie should be able to follow and learn from. With this comes a new member in our kitchen to join the problem setters and the problem testers – the Editorialist. Read more about our editorialist .
What this also does is add one more opportunity for you to be in our list of contributors. Those of you, who have been regular in our contests and might have got bored of winning and want to experience the exchange of stimulating algorithmic discussions, while the problems are being baked in our kitchen before they are served to the rest of the world, we now have a new role to contribute to CodeChef. If you think that you are up to it, please apply.
Also, we are looking out for problem creators who can create exciting Hard and Challenge problems for us. If you have not already applied, you can do so to contribute to CodeChef as a problem setter.
Do keep your eyes broadly open. More updates coming soon…
Warm regards,
Suraj Sharma
Here is a nice tutorial for the problem Quadratic Equations, courtesy Neelesh Bodas
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:
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 –
Thus observe that in this case we have reduced the problem of solving a quadratic congruence to solving a linear congruence.
Again observe that we have a special case of quadratic congruence here, which doesn’t have any linear term.
⇔ (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:
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.
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.
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 –
It is easy to see that these two observations will always hold. And the proofs are very trivial:
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:
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 –
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.
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.
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
Hello all !
The problem that we will be taking up is http://www.codechef.com/problems/FCTRL2/ 
This problem basically asks you to calculate the factorial of a number up to 100. Now, I guess most of you know what a “factorial” is. For those who don’t, the factorial of a number N is 1*2*…*N. This problem would be very simple, had it not been for the maximum value of N. The structure of the problem is such that it asks the user to take the number of test cases as the first input. Then ‘t’ integers follow where ‘t’ is the number of test cases which was given as input previously.
For every integer here, we have to calculate the factorial. This is very simple in languages like python or java which have built-in support for big integer types. It proves to be a hassle for people using C / C++ or languages that do not have a built-in biginteger type. Let’s think about how we can store the the result.
Now, the maximum number that we can store in an unsigned 32 bit integer is 2 ^ 32 – 1 and in an unsigned 64 bit integer is 2 ^ 64 – 1. Something like 100!(‘!’ is the notation
for factorial) has over 150 decimal digits. The data types mentioned earlier can store numbers having at most 9 and 19 decimal digits respectively. So, we need to find a way to store the 150+ digits that we will get as the answer. The simplest data structure that we can use is an integer array of size of about 200 to be on the safe side.
In the simplest form, let us store one decimal digit per array index. So, if the number is say 120, then the array will have the numbers as follows:
Say a[200] is how we declare the array, then
a[0] = 0
a[1] = 2
a[2] = 1
The least significant digit is stored in the lowest index 0. The next one in index 1 and so on. Along with the array, we need an integer specifying the total number of digits in the array at the given moment. Let this number be ‘m‘. Initially, a[0] will be 1 and the value of ‘m‘ will be 1 specifying that we have just one digit in the array.
Let’s take a simple example first. Consider that the array has some value like 45 and we need to multiply it with a value 37. This can be done in the following way.
The array will be:
a[0] = 5
a[1] = 4
and the value of m will be 2 specifying that there are 2 digits in the array currently.
Now, to multiply this array with the value 37. We start off from the index 0 of the array to index 1. At every iteration, we calculate 37 * a[index]. We also maintain a temporary variable called temp which is initialized to 0. Now, at every step, we calculate x = a[index] * 37 + temp. The new value of a[index] will be x % 10 and the new value of temp will be temp / 10. We are simply carrying out multiplication the way it is carried out usually. So, for the current situation, the iterations will be something like this.
Initialize temp = 0
Iteration 1 :
array = (5, 4)
temp = 0
index = 0, a[index] = 5
x = a[index] * 37 + temp = 5 * 37 + 0 = 185.
the new value of a[index] = 185 % 10 which is 5 and the new value of temp is 185 / 10 which is 18
Iteration 2 :
array : (5, 4)
temp = 18
index = 1, a[index] = 4
x = a[index] * 37 + temp = 4 * 37 + 18 = 166.
the new value of a[index] = 166 % 10 which is 6 and the new value of temp is 166 / 10 which is 16
We have finished 2 iterations and this is the value of ‘m‘, the array size at the moment. The required number of iterations is now over, but the value of temp is still greater than 0. This means that the current value of temp is to be incorporated into the array. For that, we keep appending the last digit of temp to the array and divide temp by 10 till temp becomes 0. So, we will get something like
Iteration 1 :
temp = 16 , array = (5, 6)
So, we add 16 % 10 to the array so that the array becomes (5, 6, 6) and we divide temp by 10 so that temp becomes 1. We update the value of ‘m’ to m + 1 that is m = 3
Iteration 2 :
temp = 1, array = (5, 6, 6)
Now, we add 1 % 10 to the array so the array becomes (5, 6, 6, 1) and we divide temp by 10 so that temp becomes 0. We update the value of ‘m’ to m + 1 that is m = 4
The value of temp is now 0 and our multiplication is now over. The final array we get is (5, 6, 6, 1)
Voila, we have the answer to 45 * 37 in our array with the Least significant digit in the 0th position.
For finding the factorial, we need to carry out this exact multiplication operation at every step as we loop from 1 to N. At the end of the Nth iteration, our array will contain
the answer and the value of m will be the number of digits in the answer. We can then just print the array from the Most significant digit to the least for the answer.
The basic flow of the program will be as below :
Start
Take in the number of test cases
While there is a test case remaining to be handled
Take in the number whose factorial is to be found, let it be N
Initialize the array's 0th index to 1 and m to 1
Initialize i to 1
While i is less than or equal to N
Carry out multiplication of the array with 'i' as shown above.
Print the contents of the array starting from the most significant digit and ending with the least significant digit.
Stop
Certain improvements can be made to the above mentioned method. We are storing only one digit per array index, We can store more than 1 digit per index so that the number of computations are reduced. The method to do that is the same as above. We leave it to the reader as an exercise
© 2009, Directi Group. All Rights Reserved.
