ROWSOLD editorial

general
1

The problem is “bear and row 01” how to solve this question.Code c and c++ will do.

2

After a contest has ended, the submitted solutions can be seen on the problem page. You can see the successful submissions, but it might not be easy to understand the code written by someone else. If you want to understand how to solve a problem look for the “editorials” and don’t ask questions titled “editorials” The editorial for this problem has already been posted. Click here! and read it, its very well explained.

1 Like
3

Hey,

You can check out this : ROWSOLD - Editorial - editorial - CodeChef Discuss

Solution : CodeChef: Practical coding for everyone (easy to understand)

Cheers!

4

Hi Shashwat,

In this problem we have to simulate a process in which in every iteration we have to

Step 1 - select the first one (from left) with greater than 0 zeros ahead (until next 1 or end of array)

Step 2- move it right until it meets next one or the end of array.

Example (index are 0 based)

  • 10100 - we choose 1 at index 0 (in first iteration). after moving it becomes 01100. Answer = 1 (for choosing) + 1 (moving)
  • 01100 - next we choose 1 at index 2 (second iteration) after moving it becomes 01001. Answer = 2 (previous step answer) + 1 (for choosing) + 2(moving)
  • 01001 - next we choose 1 at index 1 (third iteration) after moving it become 00011. Answer = 5 (previous step answer) + 1 (for choosing) + 2 (moving) = 8

We have to do above iterations until we have all ones in the right like 0000111, 00011, 000011111 etc

The above process with give us max result.

Simulating the above process will give TLE verdict. Hence we have to optimise that.

Now observing our steps we see that every time we choose a 1 to move, after that iteration we move all the ones behind it in similar fashion in next iterations.

Example

  • 01100, we select 1 at index 2 first and move it. next we select 1 at index 1 and move it. we move both ones a distance which is equal to number of zeros ahead of first 1 selected (one that is at index 2).
  • 001110100011010, in this first we select 1 at index 4 move it now array becomes
  • 001101100011010 again we select next 1 at index 3 move it the same distance
  • 001011100011010 again we select 1 at index 2 and move it same distance
    so on.

So we maintain two arrays,

  • first stores number of ones behind for every i where ar[i] == 1 (numberOfOnesBehind)
  • second stores number of zeros ahead (till next 1 or end of array) of every i where ar[i] == 1 (numberOfZerosAhead)

So from our observation we see that our answer for i where ar[i] == 1 is

numberOfOnesBehind[i] (which is choosing time for each 1 behind) + numberOfOneBehind[i] (which is number of one behind) * numberOfZeroAhead[i] (which is distance)

we have to add above result for every i where ar[i] == 1

See my code for implementation.
https://www.codechef.com/viewsolution/13267477

1 Like
5

hey,
my solution:CodeChef: Practical coding for everyone

2 Likes
6

hey @swagger_singh ,please explain your solution

2 Likes
7

Thank u very much.