[Community Puzzle] Flower beds

Puzzles
#1

https://www.codingame.com/training/hard/flower-beds

Send your feedback or ask for help here!

Created by @Fluxor,validated by @Sceurpien,@JBM and @Codeab.
If you have any issues, feel free to ping them.

#2

I learned a new theorem solving this puzzle, good stuff :+1:

#3

Probably you picked the right theorem to use… :slight_smile:

6 Likes
#4

Yes you need to pick right theorem to avoid timeout issue with traditional approach.

2 Likes
#5

hey guys I’m kind of stuck here, my area is hiding an error and I can’t put my finger on it

#6

This theorem requires the full count of vertices to work. But this puzzle only provides you with the corners, you have to fill in those that were omitted.

Also you should probably replace inputs.push(readline().split(' ')) by inputs.push(readline().split(' ').map(Number)), you’re technically multiplying strings here. It works in javascript but that’s really dirty :slight_smile:

Edit : also you should delete the code in your post, if belzebuth catches you you’re going down !

1 Like
#8

If you have a segment from (1, 1) to (4, 1) for example, the points (2, 1) and (3, 1) should count as vertices too.

#10

Isn’t let B = 0; supposed to be let B = n; ? Where do you add the original vertices?

1 Like
#11

thank you!
it’s still off though

#12

The other idea is that I = abs(doubleArea) / 2 - B/2 + 1; so abs shall be on A and not on the whole expression.

#13

I tried that as well but it gives me the same result apart from the second test case that becomes negative so I’m really at loss here :thinking:

#14

Why is there the +2 here? I don’t think you need it.

#15

that was it! :sweat_smile: :sweat_smile:
I don’t know must’ve been a mistake I wrote this late at night

#16

Hello anyone/everyone.
SPOILERS
I am SO stuck, I cannot figure out what is wrong. My code passes the first two tests, but is over by 0.5 on the second two tests. I can’t figure out where it is happening, I guess I must have my math wrong somewhere or I’m implementing something wrong. Any ideas why this could be happening?

Currently my code does the following (or at least I think it does, I guess I have a bug)

  • reads every coordinate and if there are coordinates in between that and the previous coordinate, calculates the points in between and adds those to the vertices array before the read coordinate
  • uses a formula to find the area of the polygon
  • uses a theorem (I picked it if you know what I mean) using the area and the total number of vertices on the boundary to determine the number of inner points.

Somehow I get off by less than one somewhere and I have worked through my logic several times and am not finding it… any help would be appreciated.
Thanks!

#17

You don’t need to calculate the coordinates of these points or insert them, you can just calculate how many of them there are.
Hint: the first point M with integer coordinates next to A on a segment [AB] has both x-len and y-len of [AM] which divide the x-len and y-len of [AB].

1 Like
#18

I originally only counted the points on the outside and was getting a similar error, I think my code actually achieves the same results both ways I had written it. I don’t believe I’m having trouble calculating the number of boundary points because it calculates correctly for the first two tests…

#19

Update: it solves all of the IDE test cases with Math.floor() around my final answer but fails the fourth validator test with this solution. Still no idea what the problem is, I feel like my logic and math is sound.

#20

Your area formula and formula with inner/border points must be good otherwise you would fail more testcases so the problem comes with the way you calculate the number of border points.

There are no subtleties with rounding as you only work with integers (there can be half integers in the final formula when you put everything together but the final number of inner points is necessarily an integer).

So let’s talk about these border points.
I’ll detail a bit more what I hinted above.

So I said that x_AM and y_AM are multiples of x_AB and y_AB.
More precisely, x_AB = k * x_AM and y_AB = k * y_AM with the SAME integer k.
Hence, k is a common divisor of x_AB and y_AB.
And given that AM is as short as possible, it’s not a random common divisor but a very particular one.

Once you got this k, you know exactly in how many parts the edge [AB] is subdivised, and it should not be too hard to calculate how many points that makes.

#21

@pardouin, thanks for your help, I appreciate the ideas. I tried implementing your solution by doing the following:

  • loop through each X integer from point1 to point 2 until I find one that has a Y that is also an integer (using the slope derived from points 1 and 2)
  • When I find the first one that works, calculate K (as you stated) by finding the distance from X to the original point
  • calculate the number of points with this formula (point1[x] - point2[x])/(small length K) - 1 => the number of points along point1 to point2

If I’ve understood your comments right this is what you are asking me to do? Unfortunately, my numbers all end up the same… I end up with an extra half somewhere in the test case. I guess I am a lost cause.

PS Sorry if this is too explicit, I’m not trying to give answers away, I’m just going a little crazy over here! :slight_smile:

#22

I just translated my python script in JS and it still works without any problem.

I compute twice the number of interior points on the fly so that it remains an integer the whole time.
And when I print it I divide by two. It’s the only division in the whole script.
If you calculated your K right, the number of points between A included and B excluded is… K. No division needed.

Send me your script in pm if you don’t find your mistake.