Editorials for FEB17

general
21

Please upvote me,I’m unable to post anything. Thanks in advance :slight_smile:

6 Likes
22

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

23

Why can’t I see any submissions for FEB17 ?

24

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

3 Likes
25

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

26

@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
27

How to solve Gerrymander in feb long contest?

28

I think I could do a video editorial on one of the problems, at the very least. If you guys want me to, shall we have a vote on which problem to do?

4 Likes
29

Thanks for your response.

I tried a lot on

INTERVAL(https://www.codechef.com/FEB17/problems/INTERVAL)
and DISTNUM3(https://www.codechef.com/FEB17/problems/DISTNUM3)

Selecting one is difficult for me but you can select from the above problems. I really want to solve them both.

30

@gkcs DISTNUM3 happens to be Mo’s Algo + Updates! :stuck_out_tongue:
Although it can also be solved with HLD.

2 Likes
31

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)

32

@gkcs please bro… much needed from you _/_ Also try solving all except first one…

1 Like
33

Instead of asking for karma you should answer questions.

1 Like
34

@nikhil_chandak
DISTNUM looks quite tough! It will take me some time to solve it. Will be posting it as soon as it’s done :slight_smile:

2 Likes
35

we’ll wait… @gkcs

36

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

37

I don’t solve problems on codechef, but I wonder the editorials for FEB17 and DEC16 are still not here.

38

I do care.