Advent of Code 2024!

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as interview prep, company training, university coursework, practice problems, a speed contest, or to challenge each other.

The first puzzles will unlock on December 1st at midnight EST (UTC-5).

This is not a problem from any online judge, but for a project I am working on.

There is an ellipse and a list of points. The task is to score the list with a number between $$$0$$$ and $$$1$$$. A score of $$$1$$$ means that the list of points forms a perfect ellipse. A list forms a perfect ellipse when:

1. All the points in the list lie on the circumference of the ellipse.

2. The points are evenly spaced (distributed evenly) across the circumference.

The expected time complexity is less than $$$O(N^3)$$$, not strictly necessary. $$$N$$$ being the number of points in the list.

If you want some inspiration, I have attempted the same problem but checked matching with circles and polygons. I am explaining how I did it for the circle.

function get_projection_on_circumference(point) {
	var angle = point_direction(center_x, center_y, point.x, point.y);
	return new Point(
		center_x + radius * cos(angle),
		center_y + radius * sin(angle),
	);
}

function get_score(points) {
	static max_error = 100;
	var n_points = array_length(points);
	
	// error: distance from circumference
	var dis_error = 0;
	for (var i = 0; i < n_points; ++i) {
		var point = points[i];
		var dis = distance(center_x, center_y, point.x, point.y);
		dis_error += sqr(radius - dis);
	}
	dis_error /= n_points;
	dis_error = sqrt(dis_error);
	
	// project points on the circumference
	for (var i = 0; i < n_points; ++i) {
		points[i] = get_projection_on_circumference(points[i]);
	}
	
	// sort "points" in anti-clockwise order
	array_sort(points, function(p1, p2) {
		var dir1 = point_direction(center_x, center_y, p1.x, p1.y);
		var dir2 = point_direction(center_x, center_y, p2.x, p2.y);
		return ((dir1 < dir2) ? -1 : 1);
	});
	
	// error: evenly spaced
	var space_error = 0;
	var expected_angle = 360 / n_points;
	var j = n_points-1;
	for (var i = 0; i < n_points; ++i) {
		var p1 = points[j];
		var p2 = points[i];
		var dis = distance(p1.x, p1.y, p2.x, p2.y);
		var _val = clamp(1 - sqr(dis)/(2 * sqr(radius)), -1, 1);
		var _angle = darccos(_val);
		space_error += sqr(_angle - expected_angle);
		j = i;
	}
	space_error /= n_points;
	space_error = sqrt(space_error);
	
	// normalize error
	var error = F(dis_error, space_error);
	var error_normalized = clamp(error/max_error, 0, 1);
	
	// get score
	return (1 - error_normalized);
}

You can see how the same method will work for regular polygons. For irregular (closed) polygons, I have a more sophisticated but similar way. The closed polygon method can work for ellipses (since an ellipse is actually a closed polygon with many small lines), but I am looking for a more natural solution for ellipses.

Advent of Code 2023!

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as interview prep, company training, university coursework, practice problems, a speed contest, or to challenge each other.

The first puzzles will unlock on December 1st at midnight EST (UTC-5).

Hello!

We would like to invite you to participate in the Replay of AUST CSE Carnival 1.0 Programming Contest. It will be held on February 2, 2023 at 7:00 PM GMT+6. You will be given 11 problems and 4 hours to solve them.

AUST CSE Carnival 1.0 was a week-long event held at Ahsanullah University of Science and Technology (AUST). The event was organized by AUST CSE Society.

Participants with rating less than 1900 might find the problems interesting and/or educational.

Good luck!

I submitted exactly the same code for 86D - Мощный массив on different platforms. Here are the results:

• GNU C++17 : 165293098 -> 4086 ms (+0 KB)
• GNU C++17 (64): 165293845 -> 1152 ms (+4 KB)
• GNU C++20 (64): 165294370 -> 1122 ms (+8 KB)

There is a small increase in memory when using 64-bit, but the time difference is pretty huge!

Can anybody explain why?

The time limit per test 840D - Судьба is 2.5 seconds. But 157972351 passed in 3525 ms.

What's going on? ಠ_ಠ