The source of the game is in the image so approved


I mean it's not hard to dodge the laser, what's hard is those stars


In this problem, stars are negligible.


Since stars travel in straight lines, the problem can account for them by treating them as though they draw an unremovable laser through the screen. EDIT: Oops I was looking at Double Spark. I'm not sure if Master Spark's stars have minor rotational speed after they're launched.


Assume the stars are spheres Assume the laser is a straight line. Assume you are a point.


The answer is this; Use Touhou Practice Patch, I ain’t doing all this math and programming.


What's this?


Alternate solution: turn off the game and go read some touhou "mangas" instead




Better solution read the official mangas


You really can’t escape this game my guy, it shows up when you least expect it.


The question seems to be asking if there's a point where you can stay in place to avoid every possible spark. Given that the sparks are aimed I doubt that it's possible.


The input data in these contests in usually pre-determined, and a solution is considered correct if it passes all tests with these pre-determined data (usually one or two data sets are shown to contestants to self-check their solutions). So this assumes Master Spark is a static spell.


I read it again and the problem has a time limit is 4 seconds. By which can be seen as: In 4 seconds, program a route to reach a point in the screen that can dodge both the lasers and stars effectively every time Marisa fires huh?


4 seconds is a time limit just for a program to generate the answer. This is made just to be sure a contestant doesn't just write a program that tries every point on the plane to find the safe spot. The hardest thing of these programming contests is almost always optimization.


The contest has just ended yesterday and [this is the ranking](https://board.xcpcio.com/ccpc/7th/harbin). Most teams chose to solve other problems first and only team ranked 22 (行星) solved the problem 2 minutes before the end.


damn no one captured it


So no Last Spell bonus?


Looks like team ranked 190 are Touhou fans (team name is Kaguya’s theme).


Many Chinese team have Touhou related names. Imperishable Night and Phantom Ensemble [here](https://rating.xcpcio.com/CNXCPC_2020-2021) for example. When I was in university, we loved adding Cirno to training problems.




In absolute number, definitely much larger than the Western community. They're big enough to have dedicated "Touhou Only" conventions regularly across the country. Only region other than Japan where this happens, to my knowledge. Relative to the country's population though, Touhou is still quite niche.


Depends on what you want to compare it to. I think the Chinese Touhou community is pretty large, but still nowhere near fanbases of "mainstream games".


you have to keep in mind that due to the population, even the most obscure fanbase is HUGE. For example you can find your group no matter how weird and specific your fetish is. In any city.


Damn, they had a blast coming up with team names ... Honorable mentions: * Natto gohan (Arknights) (8th) * Future Gadget Lab (Steins;Gate) (49th) * I'm not afraid of anything anymore (Madoka Magica) (92th) * Flight of the Bamboo Cutter (IN) (198th)


Also the Black Knights from Code Geass lmao


Team ranked 22 (行星) solved the problem 2 minutes before the end.


Thanks for the information! I graduated from CP many years ago and can only get second-handed news XD


Wait, so you have to code an AI to play Touhou for you? Sounds like a fun project


A fun Touhou Project?


_roll credits_




\+1 to sin counter!




No AI in this at all. Given data over what regions the sparks will be covering, calculate a point that isn't inside those regions.


I wonder what would be a good way to solve the problem, though? I wanna say some kinda recursive solution where you partition the space into fourths like a quad tree, but I’m probably overthinking it.


I managed to get a tutorial in Chinese. It says: Two approaches are known. One is to check each Spark's boundary to see if other Sparks have covered all sections of it. If not, it means that there is a safe point. Then this is a line segment coverage problem. The other method is to find all the intersection points, and then scan the line + point event to maintain the upper and lower positions of all Spark boundary lines, and then maintain a prefix sum to see if there is a gap in the middle. Time complexity: O(n^2 logn).


Huh. I guess the “sweep down each edge” solution I mentioned elsewhere wasn’t *completely* off, then. Even if I was just trying to mangle [Sweep and prune](https://en.m.wikipedia.org/wiki/Sweep_and_prune) to fit the problem. Meanwhile, the stars would have to align for me to come up with that second solution. Thanks for sharing the answer, though!


Desktop version of /u/Lispardi's link: --- ^([)[^(opt out)](https://reddit.com/message/compose?to=WikiMobileLinkBot&message=OptOut&subject=OptOut)^(]) ^(Beep Boop. Downvote to delete)


Yeah the find all intersection points then scan method is the best I could come up with (n\^2 log n).


i thought i thought of a solution until i realized that the lasers could be diagonal and decimal numbers exist. rip just assigning each integer coordinate with a bit and flip it on whenever a laser is said to pass it ever


I think with integers, it would be faster to just iterate over every coordinate until you find one that does not overlap with any spark (practically speaking - asymptotically both methods would be O(XYn)) Since these are basically overlapping shapes, however, you can reasonably assume (I hope) that at least one such safe space would be up against an edge, so you *could* try sweeping down the side of each edge of a spark until you find such a space, but I think there still ends up being an issue with decimal accuracy, and it’d probably still fail to hit the 4 second requirement. Basically, this is why I never go to programming competitions.


I thought about modelling it as an [optimization problem](https://en.m.wikipedia.org/wiki/Optimization_problem) with the collision with the master sparks as the cost function, and use something like a [gradient descent](https://en.m.wikipedia.org/wiki/Gradient_descent) algorithm to find the result, but I'm pretty sure that's extreme overkill. And it would take me days to implement, lmao


I suppose a good challenge would be to try and pick the solution whose implementation would take you the *longest* to do. Try outlining the sparks in points and draw some [Voronoi regions](https://en.m.wikipedia.org/wiki/Voronoi_diagram).


There's always just the brute force approach of stochastic gradient descent with finite difference, where you instead implement it in 10 minutes and take days to run the code :)


PoFV AI be like:


I've never had anything similar to a programming competition on college, let alone Touhou related. I would had pursued an academic career if this was the textbooks. I've tried everything (reverse image search, googling keywords, sketchy websites) but couldn't find any source. By the date on the picture this competition had taken place today, so all I got was some [references to the previous years of the contest](https://codeforces.com/blog/entry/84429).


Have you tried searching on Chinese search engines, if that's even possible?


Most information are in Chinese. Also, many files are only shared between contestants so normally you have to wait for some time before they are put on public internet.


Thanks for the info! Yeah, I guessed that was the case, specially when it is a local and pretty recent event.


I didn’t even see this on the touhou forum in Baidu Tieba yet lol. China treats its exam leaks pretty seriously so I wouldn’t be surprised if this doesn’t get posted for a while.


ah yes, *Impershiable* Night




From what I read, the problem wants you to find a safe spot and avoid the stars and lasers right? But it didn’t account for the screen shake (ofc xd)


Master spark is not the problem it is the solution




Heh nice


Assume the stars are spherical.


Cool to see Touhou appear in this context. I dabbled in computing olympiads many years ago, though I wasn't super focused on it (was more into math olympiad personally). Outline of my solution: Every ribbon has an upper boundary and a lower boundary, which are parallel lines. Create 2n sets of integers named U\_1, ..., U\_n, and L\_1, ..., L\_n, then two more set of integers named T and B. U\_i represents the set of indices of ribbons that contain the upper boundary of the *i*\-th ribbon, at some fixed *x*\-position. L\_i represents the set of indices of ribbons that contain the lower boundary of the *i*\-th ribbon, at some fixed x-position. T represents the set of indices of ribbons that contain the top boundary of the game area, at some fixed x-position. B represents the set of indices of ribbons that contain the top boundary of the game area, at some fixed x-position. There are at most O(n\^2) intersections between between boundary lines, including the boundaries of the game area. Find all of them and keep the ones that fall within the game area. Sort them into a list from left-to-right, called I. This take O(n\^2 log n) time. Start with the left boundary of the game area (x = 0). Check if there are any gaps not covered by ribbons. If so, we are done. If not, initialize the sets {U\_i}, {L\_i}, T, and B. Note that each set must be non-empty, otherwise there would be a safespot next to one of the boundaries. This takes O(n\^2) time the naive way. Or maybe O(n log n) with sorting, idk, probably doesn't matter. Then, traverse through the list of intersections I in order - in other words, scan from left to right. For each intersection point, update the corresponding maps. For example, if it is an intersection between the top of ribbon i and the bottom of ribbon j, then update U\_i and L\_j. If it is an intersection between the top of ribbon i and the top of the game area, then update U\_i and T. At any point during this process, if one of the sets {U\_i}, {L\_i}, T, or B becomes empty, then we have found a safespot next to one of the boundaries (specifically, to the right of one of the boundaries). If we reach the end without this ever occurring, then there are no safespots in the game area. The whole scan takes O(n\^2) time. Total runtime: **O(n\^2 log n)**




The answer is to play on easy mode if you cant beat it.


the full problem https://codeforces.com/gym/103447/problem/F


what's the answer


If You Win You're Gonna Get 300000+ Social Credit Points


and all touhou games


chinese momento


Answer: Graze.


Question revolving around trying to safespot an aimed attack. Now I understand why I hated math class. It’s full of absurd stuff like this, or at least it felt like that when you do the problems.


"Kirisame Marisa" smh


what I dont get it


It's "Marisa Kirisame".


Many Asian countries put last name first, Kirisame Marisa is correct here.


The correct answer is even in your flare


Little knowledge moment


it's there has complete test paper?


Someone found it and posted here: https://www.reddit.com/r/touhou/comments/r4h3by/touhou_on_a_chinese_programming_contest/hmu0rm7?utm_medium=android_app&utm_source=share&context=3