Method for BIO 2k Q3

[Pararcana]

Please could you explain the method you used to solve that question and how the program works?

If you could also walk me through your thought process on how to solve a Q3 in general, that would be nice too.

[Ambioid]

Do you mean Q3 of 2000?

And I'd like to ask, could you also walk through your general process for solving question 2s? those are the hardest for me so far, and I don't know where I can even go, to practice implementation problems.

[Pararcana]

Yes I did, and usually, you want to be thinking with classes for Q2s.

I would class them into three categories:

Simulations (these are the most common) (1998 Q2, 2000 Q2, 2021 Q2 and 2022 Q2, etc)

For example, in the recent 2022 Q2 (Game of Drones), you have to simulate a game. For these ones, you generally want to have a 2D array as the board state, with classes defining the pieces and the methods within making the pieces move according to the question.

Sometimes, such as in 2021 and 2022, the grid is not square, and is some arbitrary shape, such as a triangle and hexagon, respectively. This makes the array more difficult to implement, but the general method is still the same.

Game theory (1997 Q2, 2011 Q2, etc)

Here, you are given the rules of the game and have to find the most optimal move. I would recommend checking each possible move and evaluating it, storing the most optimal one somewhere and returning it once the iteration has completed.

Others (2018 Q2, 2023 Q2, etc)

I don't really have a set method for solving these, as they vary a lot, but I would recommend trying some out.

---

If you haven't solved any Q2s yet or just want some practice, I would recommend: 2000 Q2 - easiest simulation problem (i don't really have a good one for 'game theory') 2018 Q2 - it feels like a Q1

If you would like help for a specific question, I may be able to help with that too.

[Ambioid]

Thank you so much for the help! I have been practicing inconsistently for this so this is very helpful to know.

I want to ask, what methods do you suggest for implementing non-square boards? The tri-game question have me a lot of trouble specifically, because I just didn't know how to implement that.

and secondly, since you've been using python I assume you'd suggest using python, but usually competive programming uses C++, does it matter which I use?

[Pararcana]

Personally, I would suggest that you do permutation questions on C++, since it is faster to run. However, python has the advantage of being much easier and faster to write, so I use it when I can. (Lua is my backup language that I use if I need something done faster).

But of course, this varies from person to person, so I suggest that you use whichever language you are most comfortable with. I would say that the language you use is secondary, and it is the ability to solve problems that is the most important. (Bar Scratch, you should solve next year's BIO with it, as Scratch is the superior language).

---

If you just want the solution, I found this one by @matthewelse which is about 100 lines shorter and more readable than the one I found in this repo. Solution

If you want how I would go about this:

The first thing that I noticed, was that if you arrange the numbers in a triangle format... Triangular Numbers ...you can see a correlation. To move to the left or right, you simply add or subtract 1. To move to the one directly below and left, you add the row number assuming your rows start at 1. To move to the one below and right, add the (row number + 1).

Of course, the question isn't asking us to implement the triangles, but the edges, which adds another layer of difficulty. I would make it a 2D array, with a list of 4 values inside each triangle, 3 for each edge and the last for what number the triangle was filled with.

Remember that triangles share edges, so you would have to update the adjacent triangle's edge as well.

Although, I haven't tested this method, so you might want to check how @matthewelse did it.

[Pararcana]

Also @Ambioid, I think I'd like to learn a faster language. Should I learn C# or C++? I know that C++ is faster, but harder to learn. Do most coding competitions use C++? if so, I might as well learn that.

[Ambioid]

yeah, C++ is the default for most programming contests, so you would want to learn that one. C# is barely used. Java is also top 3 used but I don't see any reason to actually learn it beyond that.

but thanks for the advice on Q2. It looks more do-able now, I'll definitely try that out when I can.

Now for the hard part, actually practicing.....

[Pararcana]

I see, I will learn C++ then, can you give me a couple of coding competitions/question that use it?

[Spookiel]

Please could you explain the method you used to solve that question and how the program works?

The code first generates the fairness list for the given dice. The idea behind the solution is to try all possible combinations for the first dice of the answer (note different to input dice). Then give that dice we can recursively fill in the other numbers needed for that matching dice to make it "fair" - it matches the fairness list generated by the input dice.

Note that it would be too slow to try every possible combination for both dice, which is why a recursive pruning solution is needed. We can make the recursive solution faster because we can stop considering dice if a combination definitely becomes unfair. This can happen if we choose a number which is too big and generates a value that Romulus cannot reach at all, or in general if the frequency of any values we've generated with our partial dice is greater than the target frequency.

Take for example (1,2,3,4,5,6) and (1,2,3,4,5,6) as input dice. Say we fix our first recursive dice as (2,4,1,8,3,3), then every element in our second dice must be <= 4, otherwise 13 would be a possible outcome, which is guaranteed to be unfair. This generalises. Take a second partial dice of (2,3,,,,), then 6 can already be generated 3 times, which is unfair already, so we don't have to consider other dices which contain 2,3.

Hope this helps for this question. It's been a long time since I solved this question, so there may be another method I don't know about.

In general solving Q3 is normally about applying an algorithm such as Dynamic Programming or Graph Search (Djikstra, BFS etc), these concepts are more easily learnt on "traditional" problems and then applied to BIO problems, as the topics are not normally easy to identify without experience solving the "traditional" problem. You can find the traditional problems on platforms like "cses" and "AtCoder DP contest" and "USACO guide" but there are many resources out there.

Good luck and let me know if I can help with anything else.

[Pararcana]

This is sure to help, thanks!

[Ambioid]

I see, I will learn C++ then, can you give me a couple of coding competitions/question that use it?

Sorry, I didn't realize I never replied to this one!

Every single major coding competition has CPP as an option, and CPP is most popular by a long shot. While not required, they are the large majority in preference. For example, competitions in codechef, topcoder, codeforces competitions, facebook hacker cup, USACO etc.

I'm not sure if any require it, other than the BIO round 2.