T O P
TheOutcast06

The source of the game is in the image so approved


WarmartZ

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


Catowong

In this problem, stars are negligible.


s-Claw

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.


Tyler89558

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


DarkSlayer415

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


Spooktato

What's this?


Low_Comment_4847

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


Aj2W0rK

H-Doujinshi


paco630527

Better solution read the official mangas


Emergency_Discount70

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


AcePhoenixGamer

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.


SkyKoala

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.


Had-Hutao_Save_Ayaka

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?


SkyKoala

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.


rokuyou

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.


AverageGamer8

damn no one captured it


LordSus07

So no Last Spell bonus?


wutengyuxi

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


rokuyou

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.


[deleted]

[удалено]


williewillus

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.


rokuyou

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".


sunnysteste

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.


LandOfLemuria

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)


AskovTheOne

Also the Black Knights from Code Geass lmao


fortunateevents

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


rokuyou

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


Daiyousei_

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


touhoufangirl27

A fun Touhou Project?


The_catakist

_roll credits_


santas_delibird

\*ding\*


touhoufangirl27

\+1 to sin counter!


i-cant-see-my-pfp

fun?


billy_bottlecap

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.


Lispardi

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.


rokuyou

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).


Lispardi

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!


WikiMobileLinkBot

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)


zephyredx

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


AverageGamer8

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


Lispardi

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.


plasticparakeet

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


Lispardi

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).


The_Gunboat_Diplomat

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 :)


Catowong

PoFV AI be like:


plasticparakeet

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).


NetNetReality

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


rokuyou

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.


plasticparakeet

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


wutengyuxi

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.


epicZvarri

ah yes, *Impershiable* Night


BrianXPlayzYT

ICE SIGN ICICLE FALL EASY


Had-Hutao_Save_Ayaka

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)


frost-raze

Master spark is not the problem it is the solution


HeftySpecialist840

I WANT THAT BOOK


Null51

Heh nice


mehvermore

Assume the stars are spherical.


zephyredx

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)**


FocusEither4519

based


memoloftsk

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


Professional-Fig5131

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


khrocksg

what's the answer


SlimeSamuraiAnims

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


long_soi

and all touhou games


long_soi

chinese momento


Seminark

Answer: Graze.


Frandle_Scarlet

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.


pgj1997

"Kirisame Marisa" smh


Sumsero

what I dont get it


pgj1997

It's "Marisa Kirisame".


ejam1

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


LukariBRo

The correct answer is even in your flare


capitaopacoca

Little knowledge moment


Heisenberg_Poppings

it's there has complete test paper?


plasticparakeet

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