SEABIL - Community Editorial

editorial
, ,
1

Please feel free to edit this editorial by providing your various approaches to this problem in SOLUTION section. If you are not comfortable in editing markdown,you can mentioned your ideas in answers or comments to this post. I will later revise and mention those in the editorial.

PROBLEM LINK

Practice
Contest

DIFFICULTY

challenge

PREREQUISITES

PROBLEM

SOLUTION

SOLUTION CODES

Setter’s solution
Tester’s solution

2

My idea was to first bring all the balls in each row to the corresponding cell of the main diagonal (I mean (1,1),(2,2),…). Now to do this I checked if the sum of the row if >1 and if yes find the first ball any one side and push it so that it hits the other end and goes to the corresponding diagonal cell of the row. Then finally push all balls to the pocket in a single shot. This approach got me around 72 points.

Now to improvise this approach what I did was that I traverse each row and for every negative element(<-1 and not 0) if the lower or upper cell is free I push it to that cell and then do the same idea of the diagonal cell but this time I do not skip any rows. This approach got me 97.7 points.

Link to my solution — solution

3

Setter and Tester solutions are not working.

4

My first attempt gained about 98.8%.

The idea was:

  1. In each row move positive balls to even columns, and negative ones to odd columns. If there are several positive or negative balls with no balls of another sign between them, then try to unite them with one shot in the process. This would reduce total number of balls to deal with on step 2, and give other balls some space to move.
  2. For each column with positive balls, move them to the main diagonal (I used 2 vertical moves, if I used one, like sdssudhu, it would save about 50 moves per test case). Then get rid of negative balls on main diagonal.
  3. Push all positive balls on the main diagonal to the top left corner to finish.

To improve this result, I tried to put positive balls only in each 4th, 5th, etc column, and negative everywhere else. I thought that then there would be fewer moves to do to finish step 2, and also negative balls may not need to move so much.
Also, I wrote a separate procedure for the case of no negative balls, since in that case the solution is straightforward.
The best result was about 99.1% for every 5th column.

I also tried other orders of moves on steps 2 and 3, and one of my 99.1% solutions has positive balls in each 3rd column, they are pushed down to the bottom row, and then to the bottom right corner and out.
I was not able to improve it any further.