# Editorials for FEB17

3 Likes

Please @only4 wait for some time. I have already mail this question to codechef and they replied me “we are working on this, and will post it as soon as possible, so please be patience”

And i think most of the question has already been discussed in this discussion session. If you still have any doubt in any question then please ask it individually.

pls provide the editorial of gerrymander

need it soon!

Instead of waiting for editorials, I will advise you to ask the question on discussion forum. Because you will get the answer quicker, and will have a more meaningful engagement (I find discussing Q on forum better than reading editorials, cause its interactive and one can ask doubts).

So yeah, go ahead and ask the question you have doubts on, people will love to help

I think they were busy in making new problems for the long contest, thats why the delay.

You can ask whatever doubts you have and also see the discussion which has already happened on the problems.

1 Like

Does any one even care about December Long Challenge Editorials?

1 Like

@aniketsanadhya Exactly! Let’s not forget DEC16 editorials in pursuit of FEB17 editorials

1 Like

6 Likes

Why can’t I see any submissions for FEB17 ?

can anyone explain the gerrymander question… how to approach the solution?

@ghost_pilot I used dynamic programming for this approach. Let us take the example of the given test case.

3 3

0 0 1 1 0 1 1 0 0
My approach was simple. For the first o2 elements i calculated the winner and then i started removing the first element in o2 and added the (o2+1) element. For eg:-

0 0 1 - Winner (0)

Now in the next iteration the first 0 will be removed and the next element i.e 1 will be considered.

Thus now the o2 elements selected will be 0 1 1. For this case the winner is 1. In the similar way start storing the winner for each iteration. This will take o2*o1+o2 time. Now after this array is computed, then use nested for loops for iterating over the newly computed array. Increment the current position by o2 and find if the number of times 1 occurs is greater than the number of times 0 occurs. If yes, break and print 1. Else in the worst case the complexity will be o2^2.

Thus the final complexity will be(o2*o1+o2 + o2^2). This fits in the time complexity. Refer the solution link if needed https://www.codechef.com/viewsolution/12851300

2 Likes

How to solve Gerrymander in feb long contest?

Solution for Gerrymander: https://www.codechef.com/viewsolution/12820311

approach: prefix sum array
it is used here to calculate the contiguous sum of m elements

n = states
m = districts

if number of district for each state is 1 then just check if number of 1’s are greater than n/2

else

just take the sum of contiguous sum of m elements in the given array(here array ones[]) and check if the majority is 1 or not.
and increment the count (here variable c). in the last step we again check the majority of people elected from all the states(numg1>n2)

@ghost_pilot Here is a video solution that someone made(for gerrymander):- https://www.youtube.com/watch?v=0b95f4y5s6A&t=124s .

I don’t understand, the editorials of cook-off and lunchtime contests are provided so soon, but for long challenges they take so much time.

1 Like