CHEFFILT - Editorial

concise editorial of four easy problems: https://shadekcse.wordpress.com/2015/12/14/codechef-dec15-challenge/

3 Likes

solution links not woking :frowning:

1 Like

using Gaussian elimination :
https://www.codechef.com/viewsolution/8922862

1 Like

How can i access setter’s and tester’s solution, it shows access denied when clicked?

procedure to do this question by gaussian elimination

I wanted to know if the solution mentioned in the editorial is a DP with bitmask or just a normal DP approach…?

2 Likes

This is my code CodeChef: Practical coding for everyone and I have got 50points for this. The last test case gives TLE and I have no idea what I’m missing. Can anybody help me by finding the mistake.

2 Likes

In editorialist’s solution why is there condition (if j<=j^i )in second loop of calculation of do solution?

The Problem Setter’s solution is not available. Could someone please help me with that. Thank you.

Why does my solution get a WA verdict? Also, why does it TLE in the last subtask?

My Solution

Complexity: O(1024*1024)

Thanks in Advance!

with % operator : CodeChef: Practical coding for everyone

without % : CodeChef: Practical coding for everyone

I calculted the number of subsets, with XOR equal to value of the image represented as a binary number.

1 Like

Yep! I removed all the MOD’s and just calculated manually and it got me AC.
Its a really efficient optimization here.

Normal DP approach, not a bitwise-DP
For more info read at How the recursion for CHEFFILT works ? - general - CodeChef Discuss

Thnk you…

Your approach is O(N∗1024∗T). You need to be lucky to pass with that solution. Try the approach mentioned in the editorial O(T***1024***1024).

@xariniov Few of them passed all test cases with the same complexity.So I was wondering whats wrong with my code.

Mine also did pass all the test cases during the contest. I’m not sure, if they add stronger test cases for practice problem or it might be a case that your solution has a bigger hidden constant factor.

The line that follows that tries to perform two operations at once:

“new_v[j] = (v[j] + v[j^i]) * p2[c[i]-1] % mod” and
“new_v[j^i] = (v[j] + v[j^i]) * p2[c[i]-1] % mod”

This assigns the same value to two indices: j and j^i. However, without “j <= (j^i)”, this will be done twice (once for j and another for j^i), so the answer will be incorrect. We need “j <= (j^i)” for this to be only done once.

i think its because of using maps…

saved some time for me .