Solution for CHEFBEST removed from February Long 2017

Can somebody tell me how to solve CHEFBEST problem or provide the online link?

This might help - http://yougeeks.blogspot.in/2015/08/given-array-of-0s-and-1s-need-to-tell.html

Only look at the part in which you need to move it to the left.

This might help -

http://yougeeks.blogspot.in/2015/08/given-array-of-0s-and-1s-need-to-tell.html

Only look at the part in which you need to move it to the left.

link of the code
have a look

1 Like

I devoted around 11 hours to solve CHEFBEST and about 5 hours to solve KBIGNUM.
I request codechef to cancel the current ongoing contest and restart it with all new problems.

4 Likes

in Above Link given by mathecodician, 1 swap is counted as 1 seconds but here in Codechef CHEFBEST problem all possiblities of swaping in one attempt is counted as 1 second… so both are different… no need to remove problem…

2 Likes

@anshu326 Can you please explain how your code works?

Does the above problem’s solution passed the test cases provided ?? The problem is of O(N^2). Please anyone provide a good logic behind the problem solution. If the link to solution is given (very much appreciated). By the way thanks in advance…

This is a link to my solution. I wrote it after the task had been removed, so I’m not sure that it would pass system tests. It’s based on imagining the final array, and for each 1 determining how many seconds it needs to get to its place in the array from input. And the formula is (distance from position I need to get) + (number of ones right of me). Also, in the beginning I disregard all ones that are already in the far left of the array, e.g. they don’t need to be moved.

At least add the question in the practice section… so that we can check our solution.

I used a dp approach finding the best time for each element until I reached the last one.
Here is my solution - Ubuntu Pastebin

I still don’t understand though why this problem was removed. The online links are related to a different question which is a lot easier than this one.

1 Like

Hello @Admin, can you make the problems CHEFBEST and KBIGNUMB available for practising. I know a lot of programmers out there were trying really hard to solve those problems and it would be really unfair for them to see their efforts wasted which they cound not even test their solution.
Thand you.

I used the following logic to solve the problem in least time (AC in 0.05):
For each girl present on the array, exactly two cases are possible;

  1. She is obstructed by the girl immediately to her left at some point of time.
  2. Or she is able to move freely to her destination.

In case 1, the time taken by her to reach her right place would be one more than the time taken by her predecessor no matter what.
So, T=tprev+1;

In case 2, she would be free to move so time taken by her would be the distance between her initial position and the final destination.
So, T= i-girl.
The final answer to be printed is the time taken by the last girl(right most in the array) to reach her destination.
Here is a link to my solution (time complexity O(n), Space complexity O(1)).

2 Likes

Question was easy,
You could strip off the 1’s from left and 0’s from right. Then for every occurance of 1 you add 1 to ans but check if ans is negative if it is negative then you initialize with 1 and if you find a 0 you decrease the ans by 1.
In the end you have answer by adding to total count the number of zeroes in the list, logic behind this solution was that the total time takes would be total number of 0’s before last 1 plus total answe ryou calculated by traversing the list. Complexity O(n).

Wouldn’t this make it worse for all the people especially those who solved all problems?

4 Likes

Ok…yes…but you have to agree that they should make these types of checks before putting the problems in the contest.

1 Like

You should ask that question directly by mailing to codechef.

well solving every problem makes us better, so as long as new questions are added, there is no need to restart.

1 Like