Answers to: JUNONGF - Editorialhttps://discuss.codechef.com/questions/9733/junongf-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/JUNONGF">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/JUNONGF">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES</h1>
<p>Math, <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring">Repeated Squaring</a>, <a href="http://en.wikipedia.org/wiki/Fermat's_little_theorem">Fermat's Little Theorem</a></p>
<h1>PROBLEM</h1>
<p>You are given a <b>N</b> dimensional hyper rectangle. You have to fill each cell in the hyper rectangle with a value between <b>0</b> and <b>V-1</b>, inclusive, such that the sum of all the values in each <b>1-dimensional slice</b> of the hyper rectangle is divisible by <b>V</b>, which is also given.</p>
<p>Find the number of ways of filling the cells with the values.</p>
<h1>QUICK EXPLANATION</h1>
<p>Let the dimensions of the hyper rectangle be given in an array D = { D<sub>1</sub>, D<sub>2</sub>, ... D<sub>N</sub> }.</p>
<p>Assume we fill the each of the following cells of the hyper rectangle with any arbitrary value from 0 to V-1 of our choosing</p>
<ul>
<li>Fill { x<sub>1</sub>, x<sub>2</sub>, ... x<sub>N</sub> } iff<ul>
<li>x<sub>1</sub> < D<sub>1</sub> AND</li>
<li>x<sub>2</sub> < D<sub>2</sub> AND</li>
<li>so on..</li>
</ul>
</li>
</ul>
<p>The rest of the cells that have not been filled can only be filled by singular values that satisfy the divisibility constraint.</p>
<p>Take for example a hyper-rectangle { 4, 4, 3 } and V = 10. Suppose we fill all the cells as described above arbitrarily. There are of course 10<sup>3*3*2</sup> ways of filling them. Now, when we take any slice of this hyper-rectangle, we find that</p>
<ul>
<li>Either the cell is filled by a value of our choosing</li>
<li>The value of the cell is being forced by some or the other 1-dimensional slice</li>
</ul>
<p>All except one value in each slice will be pre-filled or forced, and the last value is of course being forced by the constraint that the sum of all the values in this slice must be divisible by V.</p>
<p>Thus, the answer for each case is going to be</p>
<p>V<sup>(D<sub>1</sub>-1)(D<sub>2</sub>-1)...(D<sub>N</sub>-1)</sup></p>
<h1>EXPLANATION</h1>
<p>V is a 64-bit integer. But we want to find the result modulo 1000000007. Thus, we can instantly change V to the remainder modulo 1000000007.</p>
<p>Given that each of the dimensions are 64-bit integers, it is obvious that the exponent of V for the answer is potentially very large. It is potentially a 6400-bit integer. Repeated squaring to find the result of V<sup>6400-bit-integer</sup> will take 6400 iterations. This is too many iterations per test case.</p>
<p>We require Fermat's Little Theorem to solve the problem now.</p>
<pre>a<sup>p-1</sup> = 1 modulo p
for some prime p
</pre>
<p>We know that 1000000007 is prime. Thus we can find</p>
<pre>T = (D<sub>1</sub> - 1)(D<sub>2</sub> - 1) ... (D<sub>N</sub> - 1) modulo 1000000006
</pre>
<p>and find V<sup>T</sup> modulo 1000000007.</p>
<p>There is one edge case that deserves special mention. V modulo 1000000007 may or may not be 0. If it is not 0, then we have no problems. But if it is 0 there is a special case that should be carefully handled. This is the case where one or more dimension is equal to 1. In this case, all the values in the hyper rectangle must be 0. This is because every cell is a single dimensional slice in a dimension that is equal to 1. Thus the answer in that case should be 1, instead of 0 (meaning the answer is actually 1, and not a multiple of 1000000007).</p>
<p>Of course, as evil as the setter and the tester are, there is no shortage of this case among the judge test cases.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/JUNONGF.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/JUNONGF.cpp">here</a>.</p>enMon, 03 Jun 2013 23:33:25 +0530Comment by viaan on viaan's answerhttps://discuss.codechef.com/questions/9733/junongf-editorial#12464<p>anyone ???</p>viaanMon, 03 Jun 2013 23:33:25 +0530https://discuss.codechef.com/questions/9733/junongf-editorial#12464Answer by viaanhttps://discuss.codechef.com/questions/9733/junongf-editorial/12458<p><a href="/users/9989/allada">@all</a> <a href="/users/387/gamabunta">@gamabunta</a>
<br>Hey<br>
I could not understand the problem.<br>
Basically I am not able to analyze/imagine the problem statement.<br>
So any hint or explanation would be highly appreciated and welcomed.<br>
Thanks !!!</p>viaanMon, 03 Jun 2013 21:48:02 +0530https://discuss.codechef.com/questions/9733/junongf-editorial/12458Comment by gamabunta on tijoforyou's answerhttps://discuss.codechef.com/questions/9733/junongf-editorial#10268<p>The official classification had not been done when the editorial was finished.</p>
<p>Changed the tag to medium.</p>gamabuntaFri, 17 May 2013 18:02:00 +0530https://discuss.codechef.com/questions/9733/junongf-editorial#10268Comment by gamabunta on prakash1529's answerhttps://discuss.codechef.com/questions/9733/junongf-editorial#9828<p>On it.</p>
<p>If you're curious what problem the tester's solution is trying to solve, it happens to be the solution to a very early version of the problem.</p>
<p>The input format was changed to improve the problem and hence this solution lost relevance. It seems the wrong solution got selected for upload. Will ask them to upload the correct version.</p>gamabuntaTue, 14 May 2013 18:41:29 +0530https://discuss.codechef.com/questions/9733/junongf-editorial#9828Answer by prakash1529https://discuss.codechef.com/questions/9733/junongf-editorial/9808<p><a href="/users/1/admin">@admin</a>: testers solution is pointing to some other problem ? It is not even reading the complete input! </p>prakash1529Tue, 14 May 2013 17:24:38 +0530https://discuss.codechef.com/questions/9733/junongf-editorial/9808Answer by tijoforyouhttps://discuss.codechef.com/questions/9733/junongf-editorial/9797<p>Any idea on why this problem is in the medium section in the practice arena?? The problem is tagged easy, here.</p>tijoforyouTue, 14 May 2013 16:59:24 +0530https://discuss.codechef.com/questions/9733/junongf-editorial/9797