You are not logged in. Please login at www.codechef.com to post your questions!

×

SEABIL - Community Editorial

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

asked 19 Apr '17, 19:56

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52136170
accept rate: 20%

edited 19 Apr '17, 19:57

Setter and Tester solutions are not working.

(19 Apr '17, 20:31) sdssudhu6★

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

link

answered 19 Apr '17, 20:12

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

edited 19 Apr '17, 20:13

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.

link

answered 20 Apr '17, 05:29

ftasb1's gravatar image

5★ftasb1
864
accept rate: 16%

edited 20 Apr '17, 05:47

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,482
×820
×122

question asked: 19 Apr '17, 19:56

question was seen: 355 times

last updated: 20 Apr '17, 05:47