Questions Tagged With chefhackhttps://discuss.codechef.com/tags/chefhack/?type=rssquestions tagged <span class="tag">chefhack</span>enMon, 29 Jun 2015 11:32:02 +0530CHEFHACK WAhttps://discuss.codechef.com/questions/5175/chefhack-wa<p>can u please give some inputs for which this code is giving WA<a href="http://ideone.com/6XWyVR">CODE</a></p>prakhs123Tue, 15 Jan 2013 16:20:37 +0530https://discuss.codechef.com/questions/5175/chefhack-wawachefhackCHEFHACK compilerhttps://discuss.codechef.com/questions/5196/chefhack-compiler<p>I don't know why is happen in my computer answer is 1.ok check this one again wrong answer id 1724250.which compiler must I use when I submit my program because I use visual studio 2012 and there is no any mistake like you said -0.I check on the <a href="http://ideone.com">ideone.com</a> but in this site I get always wrong answer .for example in my computer give answer 20 which test case is:
1
3
2 6 4
4 8 9
7 9 4
but on website answer is 19 I don't why can you help me why this happen?</p>shikimaruTue, 15 Jan 2013 17:31:45 +0530https://discuss.codechef.com/questions/5196/chefhack-compilerchefhackChefHack WA. Please help.https://discuss.codechef.com/questions/5275/chefhack-wa-please-help<p>I had almost the same solution as the one mentioned in the editorial, but I used Java and the sieve of atkin.</p>
<p>I tried several input cases, and they all generated the right answer on my computer. Yet I still got WA after submitting :/. </p>
<p>Could somebody tell me what's wrong?</p>
<p><a href="http://www.codechef.com/viewsolution/1715077">http://www.codechef.com/viewsolution/1715077</a></p>kullalokWed, 16 Jan 2013 02:23:36 +0530https://discuss.codechef.com/questions/5275/chefhack-wa-please-helpwachefhackCHEFHACK - WAhttps://discuss.codechef.com/questions/5113/chefhack-wa<p>chefhack jan13 . every test case is passing .. don no still wrong answer is coming on submission
<a href="http://www.codechef.com/viewsolution/1717959">http://www.codechef.com/viewsolution/1717959</a></p>raj_singhaniaMon, 14 Jan 2013 11:01:19 +0530https://discuss.codechef.com/questions/5113/chefhack-wawachefhackCHEFHACK - TLEhttps://discuss.codechef.com/questions/5154/chefhack-tle<p>Hi,
I have tried a lot during the contest to submit CHEFHACK problem:<br>
<a href="http://www.codechef.com/JAN13/problems/CHEFHACK">http://www.codechef.com/JAN13/problems/CHEFHACK</a></p>
<p>but it always give me time limit exceeding ...kindly help me ??</p>
<p>this is my solution: <br>
<a href="http://www.codechef.com/viewsolution/1715546">http://www.codechef.com/viewsolution/1715546</a></p>vivek07672Tue, 15 Jan 2013 15:19:05 +0530https://discuss.codechef.com/questions/5154/chefhack-tletlechefhackchefhack -WAhttps://discuss.codechef.com/questions/5326/chefhack-wa<p>I tried it several times but wrong answer.
its running in all test cases i tried.
Can any1 provide me test cases where i go wrong?or any help...
my soln is:<a href="http://www.codechef.com/viewsolution/1725618">http://www.codechef.com/viewsolution/1725618</a>
i have used a different method...</p>
<p>1.for prime,i used seive amd marked the numbers which are prime,then binary search to get the index or count of prime......</p>
<p>2.i am looping normally in 2d grid.
any number will have 4 neighbours.if we traverse the grid,cost of 3 neighbours of even/odd number will always have been calculated by now if we keep on marking even/odd neighbours and the cost of given server is known.further all its even/odd immediate neighbour which was not marked will be marked 0 now.</p>
<p>actually,if number is even,we find its 4 neighbours.if any neighbour is even and its answer matrix is marked we return <a href="http://1.so">1.so</a> the cost for arr[i][j] server is 0.if none of its even neighbour is marked,
we mark their cost as 0 because the number which called them is even.</p>
<p>All i say that we dont need dfs.
just traverse grid and keep on marken neighbours.
its working fine.
can anybody help?
any test case... </p>calciWed, 16 Jan 2013 16:14:31 +0530https://discuss.codechef.com/questions/5326/chefhack-wachefhackCHEFHACK - WAhttps://discuss.codechef.com/questions/5638/chefhack-wa<p>I'm getting WA can anyone tell me what I'm doing wrong or the test case which fails in this.<br>
<a href="http://www.codechef.com/viewsolution/1742653">http://www.codechef.com/viewsolution/1742653</a></p>cyberghost23Mon, 21 Jan 2013 13:39:22 +0530https://discuss.codechef.com/questions/5638/chefhack-wawachefhackChefhack WAhttps://discuss.codechef.com/questions/5655/chefhack-wa<p>My chefhack is giving wrong answer.
Solution link is <a href="http://www.codechef.com/viewsolution/1696242">http://www.codechef.com/viewsolution/1696242</a>
Admin please tell me the test case where it is going wrong.</p>raman92Mon, 21 Jan 2013 17:56:20 +0530https://discuss.codechef.com/questions/5655/chefhack-wawachefhackCHEFHACK WAhttps://discuss.codechef.com/questions/5349/chefhack-wa<p>Hi! I can't seem to figure out the error in the logic for this code. It seems pretty close to the editorial given. Could anyone just give me any direction or even a test case for which this would fail? I tried both, the DFS and the BFS implementation. Below is the link for the BFS implementation.</p>
<p><a href="http://www.codechef.com/viewsolution/1724561">http://www.codechef.com/viewsolution/1724561</a></p>c0dectWed, 16 Jan 2013 22:22:45 +0530https://discuss.codechef.com/questions/5349/chefhack-wawachefhackEND OF THE WORLD (CHEFHACK)https://discuss.codechef.com/questions/53743/end-of-the-world-chefhack<p>my code runs fine on my machine but shows wrong answer on submission Please help my solution is here <a href="http://www.codechef.com/viewsolution/5203370">http://www.codechef.com/viewsolution/5203370</a></p>
<p>I have spent hours trying to debug</p>vishal7695Wed, 22 Oct 2014 11:56:41 +0530https://discuss.codechef.com/questions/53743/end-of-the-world-chefhackchefhackchefhack wrong answerhttps://discuss.codechef.com/questions/60781/chefhack-wrong-answer<p>Can anybody tell me what is wrong with my solution??</p>
<p><a href="http://ideone.com/xYVgC2"> My code </a><br>
<a href="http://www.codechef.com/JAN13/problems/CHEFHACK">Question</a></p>
<p>In editorial there are some corner test cases, and I am not able to pass them. I know for which test cases it is wrong, but not the reason why I am getting the wrong answer. Any pointers would be helpful. Thanks in advance.</p>dragonemperorMon, 05 Jan 2015 12:25:03 +0530https://discuss.codechef.com/questions/60781/chefhack-wrong-answerchefhackCHEFHACK: getting RTEhttps://discuss.codechef.com/questions/72426/chefhack-getting-rte<p>please help me i am getting rte again and again(have tried lots of stuffs) on the problem: <a href="http://www.codechef.com/problems/CHEFHACK/">http://www.codechef.com/problems/CHEFHACK/</a></p>
<p>link to my solution is: <a href="http://www.codechef.com/viewsolution/7303053">http://www.codechef.com/viewsolution/7303053</a></p>akhileshydv20Mon, 29 Jun 2015 11:32:02 +0530https://discuss.codechef.com/questions/72426/chefhack-getting-rtechefhackCHEFHACK RUNTIME ERROR (SIG SEGV)https://discuss.codechef.com/questions/53947/chefhack-runtime-error-sig-segv<p>my code gives sigsegv error on submission. Please help my code is here <a href="http://www.codechef.com/viewsolution/5211099">http://www.codechef.com/viewsolution/5211099</a>
thanx</p>vishal7695Fri, 24 Oct 2014 19:07:22 +0530https://discuss.codechef.com/questions/53947/chefhack-runtime-error-sig-segvcodechefchefhackdfs bfs learninghttps://discuss.codechef.com/questions/8471/dfs-bfs-learning<p>i learning bfs,dfs ...please provide me links to problem or theory where i could learn these</p>ayushrocker92Fri, 19 Apr 2013 17:47:33 +0530https://discuss.codechef.com/questions/8471/dfs-bfs-learningbfseditorialdfschefhackWA in CHEFHACKhttps://discuss.codechef.com/questions/5218/wa-in-chefhack<p>but still i am getting wrong answer ?? please point out my mistake ....??<br>
<a href="http://www.codechef.com/viewsolution/1724277/">http://www.codechef.com/viewsolution/1724277/</a></p>vivek07672Tue, 15 Jan 2013 21:13:35 +0530https://discuss.codechef.com/questions/5218/wa-in-chefhackchefhackwainCHEFHACK WAhttps://discuss.codechef.com/questions/5285/chefhack-wa<p>I've used sieve of atkin instead of eratosthenes,<br>
extracted all primes into a vector 'primes', added cost of all the primes to the ans.<br>
I've used a 2D character array, type[][]' to apply grid hacking if type[i][j]=='p' it is skipped (cost of primes is already added in the ans) else they are cracked by 'crack()' function.<br>
all the cracked nodes are marked 'p' and hence will be skipped later.<br></p>
<pre><code>#include<iostream>
#include<vector>
#include<math.h>
#include<bitset>
#include<fstream>
#define limit 10000050
using namespace std;
//bitset<10000050> sieve;
bool sieve[10000050];
char type[355][355];
int N;
void atkin(){
int root = 3163;
for (int z = 0; z < limit; z++) sieve[z] = false;
sieve[2]=1;
sieve[3]=1;
for (int x = 1; x <= root; x++)
{
for (int y = 1; y <= root; y++)
{
int n = (4*x*x)+(y*y);
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
n = (3*x*x)+(y*y);
if (n <= limit && n % 12 == 7) sieve[n] ^= true;
n = (3*x*x)-(y*y);
if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
}
}
for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false;
}
void crack(int i, int j){
char x= type[i][j];
type[i][j]='p';
if (x!='p'){
if (x == type[i+1][j]) crack(i+1,j);
if (x == type[i-1][j]) crack(i-1,j);
if (x == type[i][j+1]) crack(i,j+1);
if (x == type[i][j-1]) crack(i,j-1);
}
}
void Qsort(vector<int> &S, int x, int l){
if (l-x >0){
int right,left, p;
right=l;left=x+1; p=x;
while (S[left] <= S[p] && left<l) left++;
while (S[right]>= S[p] && right>x) right--;
if (left>=right){
int temp=S[p];
S[p]=S[right];
S[right]=temp;
if (right>x) Qsort(S, x,right-1);
if (right<l) Qsort(S, right+1, l);
}else{
int temp=S[left];
S[left]=S[right];
S[right]=temp;
Qsort(S, x,l);
}
}
}
main(){
int T;
atkin();
scanf("%d",&T);
while(T--){
int pwd;
scanf("%d",&N);
for (int i=0; i<N+2; i++){
type[0][i]='x';
type[i][0]='x';
type[i][N+1]='x';
type[N+1][i]='x';
}
int matrix[N+2][N+2];
vector<int> primes;
for (int i=1; i<=N; i++){
for (int j=1; j<=N; j++){
scanf("%d",&pwd);
if (sieve[pwd]==1){ //its prime!!
primes.push_back(pwd);
type[i][j]='p';
matrix[i][j]=pwd;
}else{
if (pwd%2==0){
type[i][j]='e';
matrix[i][j]= pwd/2;
}else{
matrix[i][j]= (pwd+3)/2;
type[i][j]='o';
}
}
}}// input ends here
Qsort(primes, 0, primes.size()-1);
long ans=0;
int count=0, it=0;
for (int i=0; it<primes.size(); i++){
while (i==primes[it]){
ans+=count;
it++;
}
if (sieve[i]==1) count++;
}
for (int i=1; i<=N;i++){
for (int j=1; j<=N; j++){
if (type[i][j]!='p'){
ans+=matrix[i][j];
crack(i,j);
}
}
}
cout<<ans<<endl;
}
}
</code></pre>charchitWed, 16 Jan 2013 10:09:19 +0530https://discuss.codechef.com/questions/5285/chefhack-waatkineasywachefhackCHEFHACK - Editorialhttps://discuss.codechef.com/questions/5147/chefhack-editorial<h1>SUGGESTION:</h1>
<p>Before posting your question with asking for help try <a href="http://pastebin.com/raw.php?i=j6UWCAZ5">this test</a>.<br>
The answer should be 436746489.<br>
If it is hard to debug this test for you, <a href="http://pastebin.com/raw.php?i=Q5hGmk0W">here</a> is the helpful information.<br>
It contains the number of unsuccessful tries for each cell<br>
or -1 if the cell was hacked by the "Grid Hacking Mechanism".<br>
If it still hard to debug try <a href="http://pastebin.com/raw.php?i=dcLeXChd">another smaller test</a> that contains answer and similar debug information as above.<br>
If you pass this test then read carefully the bold tip in the QUICK EXPLANATION section.<br>
If you follow this tip but still have WA then post your question and we will help you.<br>
</p>
<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CHEFHACK">Practice</a><br>
<a href="http://www.codechef.com/JAN13/problems/CHEFHACK">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/khadarbasha">Khadar Basha</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/anton_lunyov">Anton Lunyov</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/anton_lunyov">Anton Lunyov</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY</p>
<h1>PREREQUISITES:</h1>
<p><a href="http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29">Connected component</a>, <a href="http://en.wikipedia.org/wiki/Depth-first_search">Depth-first search</a>, <a href="http://en.wikipedia.org/wiki/Flood_fill">Flood fill algorithm</a>, <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a></p>
<h1>PROBLEM:</h1>
<p>You are given <strong>N × N</strong> grid filled by non-negative integers. We single out 3 types of numbers on the grid: primes, even non-primes and odd non-primes. For each number we define the cost as follows: for the prime number it is the id of this prime in the 0-based list of all primes, for even non-prime number <strong>X</strong> it is <strong>X / 2</strong>, and for odd non-prime number <strong>Y</strong> it is <strong>(Y + 3) / 2</strong> (the cost of a number is the shortcut for the number of unsuccessful tries to crack the server secured by the password equals to this number; the mentioned formulas for cost in all three cases are clear from the problem statement).</p>
<p>Two even non-prime numbers that share a side on the grid are connected to each other. The same is true for odd non-prime numbers. But prime number is not connected to any other number. In this way all cells of the grid form a bidirectional graph that has several connected components (each cell having prime number is a separate component). The cost of the component is defined as the cost of the first cell in this component that we meet traversing the grid in row-major order. Now your task is to find the sum of costs over all components.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Actually, most of the job has already made while we reformulated the problem above. Now you simply need to loop over all cells of the grid in row-major order and if we meet the unvisited cell we add its cost to the answer and run DFS from this cell in the graph constructed above to mark other cells of its connected component as visited.</p>
<p><strong>Tip: the total cost could overflow 32-bit integer type. Use 64-bit type instead.</strong></p>
<p>To be able to find the cost of the prime cell fast enough we need to run Sieve of Eratosthenes in advance (even before input the very first test) in order to find all prime numbers. Then we need to create the array of size <strong>10<sup>7</sup></strong> that contains for each prime its id. Now the cost of each number can be found in <strong>O(1)</strong>.</p>
<p>The overall complexity is <strong>O(K * log log K + T * N * N)</strong>.</p>
<h1>EXPLANATION:</h1>
<p>As mentioned above at first we run Sieve of Eratosthenes to identify all prime numbers:
</p><pre>isPrime[0] = false
isPrime[1] = false
for i = 2 to K do
isPrime[i] = true
for i = 2 to sqrt(K) do
if isPrime[i] then
for j = i * i to K with step i do
isPrime[j] = false
</pre>
where <strong>K = 10<sup>7</sup> − 1</strong>.<p></p>
<p>Next we fill array of costs. We maintain variable <code>prime_id</code> which is equal to the number of primes we met so far:
</p><pre>prime_id = 0
for i = 0 to K do
if isPrime[i] then
cost[i] = prime_id
prime_id = prime_id + 1
else
cost[i] = i div 2 + (i mod 2) * 2
</pre>
Note the formula for the cost for non-prime number.<p></p>
<p>Now we can input grids and traverse them. We use two-dimensional array <code>A[][]</code> for the initial grid. Also we use another two-dimensional array <code>visited[][]</code> to check visited cells, which could be filled by <code>false</code> while input the grid:
</p><pre>for i = 1 to N do
for j = 1 to N do
read A[i][j]
visited[i][j] = false
</pre><p></p>
<p>Now we can traverse the grid. If we meet visited cell we skip it. Otherwise we always add its cost to the answer and if it is non-prime then run DFS to fill its connected component:
</p><pre>total_cost = 0 // this should be a variable of 64-bit integer type!
for i = 1 to N do
for j = 1 to N do
if (visited[i][j]) then
continue
total_cost = total_cost + cost[A[i][j]]
if (not isPrime[A[i][j]]) then
DFS(i, j)
</pre><p></p>
<p><strong>DFS(i, j)</strong> is the recursive routine that traverse the grid passing from the cell <strong>(i, j)</strong> to its neighbors in the graph constructed above:
</p><pre>DSF(i, j)
if (not visited[i][j]) then
visited[i][j] = true
for (x, y) in {(i+1, j), (i-1, j), (i, j-1), (i, j+1)} do
if (not isPrime[A[x][y]]) and (A[x][y] is of the same parity as A[i][j]) then
DFS(x, y)
</pre>
Note that we pass to the cell <strong>(x, y)</strong> only if the number in it is non-prime and of the same parity as in the cell <strong>(i, j)</strong>. Missing of any of these checks will definitely lead to WA. Also see <a href="http://www.codechef.com/download/Solutions/2013/January/Tester/CHEFHACK.cpp">tester's solution</a> as a reference to one of the convenient ways how to implement loop:
<pre> for (x, y) in {(i+1, j), (i-1, j), (i, j-1), (i, j+1)} do
</pre><p></p>
<h1>ALTERNATIVE SOLUTION:</h1>
<p>For some languages (like Java or Python) the recursive implementation of DFS could lead to runtime error due to stack overflow. In this case you need to implement either non-recursive DFS or BFS (<a href="http://en.wikipedia.org/wiki/Breadth-first_search">breadth-first search</a>) to mark cells of each connected component. Another alternative is to use disjoint-set data structure to do the same job. But this way requires some additional thinking.</p>
<p>The alternative very fast method to find all primes is to use <a href="http://en.wikipedia.org/wiki/Atkin_Sieve">Atkin Sieve</a> invented in 2004 by Atkin and Bernstein. It allows to find all primes up to <strong>K</strong> using <strong>O(K / log log K)</strong> operations. Check it out first 6 related problems to train yourself at fast implementation of sieve.</p>
<p>The remaining 3 problems involves flood fill algorithm.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2013/January/Setter/CHEFHACK.cpp">here</a>.<br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2013/January/Tester/CHEFHACK.cpp">here</a>.<br>
</p>
<h1>RELATED PROBLEMS:</h1>
<p><a href="http://www.spoj.com/problems/TDPRIMES/">SPOJ - 6488. Printing some primes - TDPRIMES</a><br>
<a href="http://www.spoj.com/problems/TDKPRIME/">SPOJ - 6470. Finding the Kth Prime - TDKPRIME</a><br>
<a href="http://www.spoj.com/problems/PRIMES2/">SPOJ - 6488. Printing some primes (Hard) - PRIMES2</a><br>
<a href="http://www.spoj.com/problems/KPRIMES2/">SPOJ - 6489. Finding the Kth Prime (Hard) - KPRIMES2</a><br>
<a href="http://www.spoj.com/problems/CPRIME/">SPOJ - 3505. Prime Number Theorem - CPRIME</a><br>
<a href="http://www.spoj.com/problems/BSPRIME/">SPOJ - 11844. Binary Sequence of Prime Number - BSPRIME</a><br>
<a href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=288">UVA - 352 - The Seasonal War</a><br>
<a href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=410">UVA - 469 - Wetlands of Florida</a><br>
<a href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=726">UVA - 785 - Grid Colouring</a></p>anton_lunyovTue, 15 Jan 2013 15:00:30 +0530https://discuss.codechef.com/questions/5147/chefhack-editorialeditorialdfsjan13easysievechefhack