CHEFFILT - Editorial

For all those who got TLE in last task, % operator for them proved really costly :smiley:

2 Likes

Unfortunately, some O(N*1024*T) solutions passed as well.

1 Like

I did it using O(N x 1024 x T) and it passed.Lucky for me. Can anyone explain why it happened?.I mean for N=100000,T=5 it becomes O(100000x1024x5).I too was surprised when it did not give tle. I used bottom-up and optimised mod using if(a>=mod)a-=mod;

Has anyone done it using Gauss elimination? A link to the solution would be great.

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.