CHEFHACK - Editorial

editorial
, , , , ,
61

I have updated the editorial. Please read and follow the SUGGESTION at the beginning of editorial.

62

I have updated the editorial. Please read and follow the SUGGESTION at the beginning of editorial.

63

Thatā€™s great anton_lunyvon. Thanks a lot.

64

In routines oddserver and evenserver you should check before accessing valid[k][l] (or valid[m][n]) that cell (k,l) (or (m,n)) lies inside the grid. Probably this is the reason.

65

Your array for primes is too small. Add one zero to K. Like here:
http://www.codechef.com/viewsolution/1745675

1 Like
66

@anton_lunyov (valid[i][j] is itself a array which has 1 at (i,j) if i,j lies inside the grid otherwise valid[i][j] contains 0) it is also workin well .please help to sort out this problem ,still unable to fiure out the problem

67

In evenserver() instead of

 if(!valid[k][l])
     return 0;

you should write

 if(k<0 || k>=n || l<0 || l>=n || !valid[k][l])
     return 0;

where n is the size of the grid that should be defined globally.

The same should be applied to oddserver() but be careful you are using variable n there as y-coordinate of the cell.

If you will have troubles with fixing it you can refer to my edit of your code that got AC:
http://www.codechef.com/viewsolution/1745787

68

Greatly appreciated, Anton! I should have noticed it by myself!

69

Use printf("%lld\n", tries).
I should add this tip to the editorial.
Several guys who asked for help all have this bug:
they use long long but print it as %d

70

thank you for the correction.
i tried another approachā€¦ facing a similar problemā€¦

http://www.codechef.com/viewsolution/1747532

71

Wow! Your solution fails for only one grid among 80 grids we have in official test data. It is a grid having the following structure: N=350, a[i][j] are all even non-primes, except very small percent of odd non-primes. Each group of odd passwords is generated as a boundary of a small square.

Your solution is quite hard to follow so I can only suggest you to generate test of the above structure for smaller size and compare your answer with the answer generated by the correct program.

72

Hi Anton,
Is (1,1) connected to (1,4)? I donā€™t seem to understand the connectivity rules to get to answer 2.
Thank you for the small test case.
-nnovoice

73

Hi Anton, I was checking this link: CHEFHACK compiler - general - CodeChef Discuss and you have posted the same test case with 12 as the answer!
-nnovoice

74

Sorry, Iā€™ve swapped the correct and yours answers :stuck_out_tongue:
Is this clear your doubt?

75

approach is as :

  1. generate prime numbers index.
  2. read data (simultaneously add attempts for primes). store odd/even flag for remaining.
  3. get_neighbors() will store ā€˜validā€™ neighbors for each data. ā€˜validā€™ means - (i) it is either [i+1][j] or [i][j+1]. (ii) it has to be of same type (odd/even) non-primes.
  4. ā€˜tags[i][j]ā€™ for each member is assigned as ā€˜i*N+jā€™.
  5. arrange_and_compute() will do traversal over all members and update ā€˜validā€™ neighbors with lowest tags among them. this is done in loop until there is no change in an iteration.

this was an attempt on amortization. will see!

76

Thank you. BTW, that was not my answer! -nnovoice

77

You should not pass through the cells containing 2 in mark_check_even. Try this test:

4
0 4 2 12
2 1 9 24
0 1 9 12
2 8 2 18

The answer is 12 while your answer is 2.

78

Thanks a lotā€¦

79

Hi Anton,
Would you be able to help me in finding why my solution fails with SIGSEGV: CodeChef: Practical coding for everyone? If you could help me with a test case, I will try to find out. I have tried to find a problem in the code without success.
Thank you.
-nnovoice

80

The reason is stack overflow in DFS.
Try to get rid of arrays rows[] and cols[].
For example, you could make them vectors.
Then they will be allocated not in stack.

1 Like