Editorials for FEB17

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 :slight_smile: https://www.codechef.com/viewsolution/12851300

2 Likes

How to solve Gerrymander in feb long contest?

Solution for Gerrymander: CodeChef: Practical coding for everyone

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):- CodeChef Long Challenge - FEB17 - GERMANDE - YouTube .

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

I have no idea about this. You can ask this by mail to codechef

That’s a good idea but we should be aware of the true aim of a problem and what problem setter wants us to think. For a single problem there is a number of solutions exist but problem setter’s solution is the most optimal. As you know for lots of problems (for example CHAIRS from feb cook-off) the problem setter’s solution is of 30+(greater) lines, but all the other AC solutions are of just 15(less than) lines.

WAIT! Did you just provide said something and contradicted it in next line? If problem setter’s code is longer, how is it more optimal than the shorter codes? Am I missing something?

BTW-

Yes, problem setters thinking is quite important when you’re in the learning stage.

But after a certain time, you become professional enough to outsmart problem setters (depends strictly on you and the setter tho) and come up with even better implementations.

I KNEW that this thing would be brought up. I just knew it XD

You can’t claim a code not to be optimal by the number of lines…

I am talking about the approach of problem setter.

Length of code is actually a factor, just like you say approach. Sometimes the approach is easy, but code gets bulkier, sometimes approach is tricky, but code is hardly 10-20 liner. If I cant define optimal code on basis of length, even you cannot define optimal code on basis of approach as everyone has different criterias for what an optimal code is.

Yes …

i am glad i was able to put my point across you dear :slight_smile:

1 Like

lol…

DEC16 was full of challenging problems, but even after 2 months… no editorials.

2 Likes

True, Dec Long challenges were REAL tough!! Agree with @only4

1 Like

may be this can help:
https://www.codechef.com/viewsolution/12810310

Yeah, they were challenging. All the more reason to get their editorials published ASAP

3 Likes