One of the many reasons why SAPO is the best informatics Olympiad is that we're allowed to submit solutions in Scratch (TianCilliers wrote a CMS plugin to support Scratch a while ago)
The second round of SAPO 2020 was held earlier this week, so obviously I had to try to solve the problems using Scratch.
The problems were:
- Given
X,Y, andN, outputN / X + N / Y - N / lcm(X, Y). - Add two given numbers in base
Bfor a givenB. - This problem but modulo 1e8.
- Given a tree and some paths, find the number of edges in the union of those paths.
I was able to solve the first and third problems this way:
but I couldn't implement the second and fourth problems.
As you can see in the code for problem 3, working with multiple arrays is a bit of a nightmare.
I feel like problem 2 is solvable using Scratch (albeit very painfully), but since Scratch doesn't have 2D arrays, I don't see how one could solve problem 4 using Scratch.
Do any of you have ideas about how one can work with graphs using Scratch?
(P.S. my other Scratch implementations are available at https://github.com/dolphingarlic/ScrAtChO)
EDIT: Thanks to -is-this-fft-, I was able to implement a solution for problem 4. https://scratch.mit.edu/projects/419364160
Gone above head..
I have implemented problem 4 here. Only $$$O(nq)$$$ complexity but a brave person can try to implement binary lifting ;)
I used just the "parent links" as input, but you could use the same idea to do arbitrary graphs: make one array that's the concatenation of adjacency lists. To do that, at first count the number of neighbors each vertex has.
Also notice how I'm using tail recursion for the loop within the DFS. I'm forced to — there's no way to create a variable that isn't global.
In general it's funny how much harder it is to write stuff in an "easy to use" language.
Wow, that's a smart workaround. There's actually a simple $$$O(N)$$$ DSU solution to this problem, so I implemented that with the adjacency list thing you described. https://scratch.mit.edu/projects/419364160
(You can read the problem statements at https://saco-evaluator.org.za/cms/sapo2020round2. Unfortunately, Scratch is just a bit too slow to get AC)
Auto comment: topic has been updated by dolphingarlic (previous revision, new revision, compare).
There exists another way to make "multidimensional" arrays. It looks as though local lists ("for this sprite only") are not shared between a sprite and its clones.
In theory, this means you can make a lot of interesting things by cloning sprites, maybe recursively, and use Scratch's message passing (together with a global variable to specify which clone is sending the message). Including 2D arrays — $$$A[i][j]$$$ is the $$$j$$$-th element in the $$$i$$$-th clone's list. In practice this may be quite hard to use because you can't send two different messages of the same type — they share the same global variable — so you have to use timeouts.