After our heated and long-drawn May Challenge, we’re back with our highly contested May CookOff. So, without further ado let’s just dive right into it.
In Div A, the top spot was secured by the 7-star progmatic from Belarus. Presently ranked 21 globally, Progmatic has shown an awe-inspiring improvement over time. In the past 3 months alone, he has increased his overall rating by over 250 points and jumped from the orange to the red band. A huge accomplishment by any metric, and not to mention, a motivation for many. Further, progmatic is only 6 points behind the globally ranked 20, hzhz.
Apart from progmatic, there were 4 other participants in Div A who managed to score a perfect 5 in the CookOff — sam__2, mnbvmar, tautsjasiunsas, and farhod_farmon. For sam__2 and mnbvmar, the top 5 rank should hold greater importance since it was their first ever CookOff. Hats-off to them! Unfortunately, one of CodeChef’s regulars and a 7-star, uwi, didn’t fare as well as one would have hoped. Nevertheless, he ranked 8 in May’s CookOff; and overall holds the CodeChef’s global rank of 32 at the moment.
Now, over in Div B: A surprising 12 participants managed to attain a perfect 5, with CodeChef debutant geothermal leading the pack. geothermal is a student from the United States studying in Pennsylvania and is currently a 3-star. Closer home, one_more_fake, another debutant (although, with a slightly unusual handle), was the only Indian who got a score of 5 in Div B.
Moreover, school students have gradually upped the game, and have begun to pose a serious competition to our experienced coders. And this CookOff was no different. Though Div A featured only one school student in top 20, Div B had a whopping 7 school contenders listed in top 20. A great feat! We’re eagerly looking forward to the next few months to see whether the scale of balance tilts towards our young programmers.
As with all our contests, May CookOff, too, was an opportunity for many to increase their ratings. A startlingly 89 participants seized that chance, having climbed from Div B to the elusive Div A. Five of these participants happened to be school students. This follows the past trend: May Challenge saw over 150 participants graduate from Div B to Div A. These figures suggest that the stage in Div A is set for fiery battles, even more than they already are.
As we conclude this recap, we express our immense gratitude to our problem setting panel:
Setters: Mohammad Solaiman (solaimanope), Pritom Kundu (anchor)
Tester and Editorialist: Teja Vardhan Reddy (teja349)
Statement Verifier: Jakub Safin (xellos0)
Translators:
Mandarin Translator: Hu Zecong (huzecong)
Vietnamese Translator: Team VNOI (songuku95)
Russian Translator: Fedor Korobeinikov (gomelfk)
Bengali Translator: Mohammad Solaiman (solaimanope)
Hindi Translator: Akash Srivastava (devils_code)
And as always, many thanks to our problem panel admin Hasan Jaddouh (kingofnumbers) whose hard work helped us execute the contest effortlessly.
Do let us know in the comments your thoughts on the May CookOff. Until next time, keep practicing!
Our 66th Lunchtime took place on November 24 and it was a showdown to remember with a major rank list shake-up! Keep reading to read who gained ratings and who lost them in the November Lunchtime.
Leading the pack in Div 1 was uwi, who is presently ranked number 1 in Japan and number 5 globally. Following our 100th Cook-Off, we mentioned in our Contest Recap that uwi was less than a hundred rating points short of a spot in the global top 5. Looks like, uwi took up the challenge and dethroned China’s ACRush to claim the world number 5 spot. But ACRush is a regular in our Long Challenges, stay tuned to see if he makes a comeback next month.
Other notable mentions in Div 1 are zemen from Russia who moved to 5-star status in this competition and rns5 from North Korea who went from 5 stars to 6. natsugiri, also from Japan, rounded out the top 4, all of whom scored 500. rns5 has risen rapidly through the rating system, gaining a whopping 6 stars since joining CodeChef in August this year. He needs just about 182 rating points to join another, rns4 another celebrated Kim Il-sung University student, in the 7-star club.
In Div 2 mzuev from Russia, took the lead going from 2 to 3 stars in the process. Close behind was xuzijian629 from Japan who was participating in a CodeChef contest for the very first time and made a rating jump of 275 points, which is the maximum jump possible! He promises to be a coder to watch out for. Dubai based antrikshh claimed the third spot, with Indonesia’s sidiqha in 4th place. While no Indians made it to the top 10 in Div 1, 4 Indians secured spots in Div 2’s top 10. A huge shoutout to its_ulure, mindjolt, radon12 and shubham698.
School students were well-represented in the November Lunchtime Div 1 with 9 of them earning places in the top 20. The best performers were tmwilliamlin from Taiwan who was at rank 5, farhod_farmon from Tajikistan at rank 7, and Ukraine’s adalbert at rank 8. Div 2’s best performing school students were its_ulure from India at rank 5, arafat_01 from Kazakhstan at rank 9, and fake_here from China at rank 15.
Special mentions go to female coders amina283 from Azerbaijan and mh755628 from Bangladesh, both of whom made it to the Div 1 top 100. In Div 2, it was hui_yin from Hong Kong and India’s own viralivora who reached the top 100.
Joining xuzijian629 on the list of users who made sizeable rating jumps are mzuev from Russia and tyakennikku from China who improved their rating by 233 points each. Indonesian sidiqha enjoyed a rating jump of 209 points while India’s own its_ulure from West Bengal, increased his rating by 201 points.
The highest participation this month came from India, followed by Bangladesh and Ukraine. India’s National Institute of Technology, Kurukshetra and Jaypee Institute of Information Technology had the most participants in this Lunchtime. If you’d like to spread the word about competitive programming in your school or college, start by creating or joining a CodeChef Campus Chapter today.
Probability (PPAP) emerged as the least solved problem of both Divisions with no successful submissions in Div 2 and just 7 in Div 1. Event (EVENT) was the most solved problem of Div 2 with 769 successful submissions out of a total of 5738 while in Div 1, Beats and Pieces (BPS) got 169 successful submissions from a total of 576. Check out the editorials for this Lunchtime’s problems here.
As we conclude this recap, we tip our hats to our problem setting panel:
Setter: Rehim Memmedli (nots0fast)
Tester: AmirReza PoorAkhavan (arpa)
Statement verifier: Jakub Safin (xellos0)
Editorialist: Hussain Kara Fallah (deadwing97)
Translators:
Mandarin Translator: Hu Zecong (huzecong)
Vietnamese Translator: Team VNOI (khanhptnk)
Russian Translator: Fedor Korobeinikov (gomelfk)
Bengali Translator: Mohammad Solaiman (solaimanope)
Hindi Translator: Akash Srivastava (devils_code)
And as always, many thanks to our problem panel admin Hasan Jaddouh (kingofnumbers) whose hard work helped us pull the contest together.
The November Long Challenge was an exciting one and we’re reliving all the contest chaos through our official November Challenge Recap.
Our standout coders this month were ACRush (Div 1) and xhm154 (Div 2), both from China who aced the Long Challenge with scores of 800 each. In the Division 2 category, a notable mention goes to browni3141 from the US who made an ambitious leap from 1 star to 3 stars by securing the 2nd spot with a score of 799.199. Div 2’s 3-star coders zhouzhendong and zhouyuyang had snagged early leads, but while they were ousted from the top spots, they each earned a star and moved to the 4-star club. Interestingly, all of the top 10 participants in Div 2 earned at least a star in this contest, so Div 1 regulars had better watch their backs!
Meanwhile, in Division 1, most of the key players in the top 10 retained their existing status with some notable exceptions. samjia2000 from China and wmoise from the USA, both earned the elusive ticket into the red 7-star club. wmoise is now ranked 8th in the USA and 83rd worldwide, while samjia2000 has a country rank of 16 and a global rank of 75. But as we all know, the contests giveth and the contests taketh away! We hope the new entrants are prepared to fight for their spots! We also had North Korean rns5, the lone coder with the purple band, who battled 6 and 7-star competitors to add that coveted 5th star to his band with a score of 799.686.
Shoutout to our top ranking school students whzzt, peehs_moorhsum and samjia2000 who all secured spots in the Div 1 top 10 with scores of 780 and above. In Div 2, 4 of the top 10 ranked coders were students: xhm154, howarli, zhouzhendong and zhouyuyang. These rising stars will soon be keeping experienced coders on their toes!
Our homegrown coders also found themselves in the top 10 in both Div 1 and 2 categories. yash_chandnani from Jaipur retained his 7 stars and secured the 5th spot in the Div 1 rank list with a score of 799.513. In Div 2, halberdier secured the third place while thefear from Uttarakhand and Kolkata’s rv_619 landed the number 9 and 10 spots respectively.
A whopping 7421 coders increased their ratings in the November Challenge, and 301 Div 2 coders graduated to Div 1 with ab_initio from the USA who made a significant 186 point rating jump while India’s very own coder3101 from Jharkhand earned 176 rating points during the Long Challenge. Female programmers from India made their presence in the competition felt with 4 coders making rating jumps of over 200. Mumbai’s ziggywiggy led the pack with a rating increase of 217. Among school students, cunbidun from Vietnam increased his rating by 233 points while ilionoid from Kolkata, India saw a rating increase of 219. The Div 1 pool just got a lot bigger since 307 coders graduated from Div 2 to Div 1 following the contest. Salute to eriktillema from the Netherlands who earned 228 to make this leap.
As for the problems, “Chef and Difficult Contests” ironically emerged as the most solved problem with 9774 successful submissions while Max Digit Tree and Chef and Equations saw just 17 successful submissions each. You can check out editorials for all the Long Challenge problems here.
We conclude this recap with a big thanks to our problem setting panel:
And an extra special thanks to our problem panel admin, Misha Chorniy (mgch) whose efforts in the Chef’s Kitchen make our monthly contests fun for everyone!
What is happening?
In light of the recent discussions in the community over plagiarism charges and how this has affected our users and their ratings, we are taking a few steps to restore order in the universe (and to maintain fairness on our platform). Below, we outline the actions we are taking and the motivations behind them.
What action is being taken?
For users whose ratings have been dropped to zero following plagiarism charges, we are increasing the rating by a maximum of 800. We have also ensured that user is penalized by at least of a rating difference of 750.
Formally, we are increasing the rating of all those users by X, where X = minimum of 800 and (Y-750) and Y = previous rating before dropping their rating to 0. We guarantee that X is non-negative.
Why is this action being taken?
You may have been following the discussions taking place in our community over the issue.
Multiple users whose ratings had dropped to zero following plagiarism charges came to us with the concern that such a massive drop in ratings reduces their incentive to participate in contests.
The second concern was that it would take quite a long time for such users to regain their previous ratings.
Finally, some of the users with zero rating who had performed better than those with much higher ratings were getting less rating increments, which they found demotivating.
We understand that many of you felt that the decision to drop ratings was harsh and hasty. It was also pointed out to us that because the drop was not implemented after every contest, it was essentially unfair and did not give all users a fair chance to regain their ratings. After hearing from you all on the issue and brainstorming with our panel and moderators, we have come to this decision. We believe that it is the best way to address your concerns while maintaining as much fairness as possible.
How will plagiarism cases be handled in the future?
For all the future plagiarism scenarios, with each cheating attempt, we will decrease the rating of the user by 750 points flat (however ensuring that the rating doesn’t become negative). There will be no reconsideration or changes in our rating system to handle users with zero rating. No requests for leniency in this regard will be considered.
Further, we will be handling the cheating cases month by month without making any delays in the penalty.
We understand how much it affects our community when we have to take such actions. There is also a likelihood that many honest users get unnecessarily affected by the actions of a few. Do understand that plagiarism is an issue that deeply affects us all and we are trying our best to come up with new ways of combating it and making our community a better and safer place for all of you. As always, we’re there to listen to your suggestions.
Happy coding!
The Chef
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.
