[Math] Bijection ProblemSet - noodlze/Olympiad GitHub Wiki

Core problem: Is there a valid bijection from the elements in this function and the elements in the second function?

1.Dasha and friends [IMPLEMENTATION(a bit heavy here)]


Another mathematical practice that is also used in this problem is "labeling". "Labeling" has two purposes:

  • makes it easier and faster to refer to things: i.e if we denote first barrier as 1, it simplifies all subsequent references to it when problem solving.
  • in this scenario, the choice of "labeling" is not only shorter but it also contains info that intuitively understood: by labeling the barriers using numbers: 1, 2, 3... we have been able to incorporate the ordering imposed by the problem constraints("move anti-clockwise") into our labeling system such that it is intuitively understood. Thoughts: in this case, some may say this isn't labeling, cause it's just so natural to number it 1,2,3... but if u think about it, why couldn't we label it A,B,C... or 1.4, 2,4....? so when you think about it, it's just that this practice is so ingrained in your way of thinking, it's u in auto-mode. In more difficult problems, knowing this practice can be useful,it gives you a sense of direction when you first delve into the unknown, you know that you should start with the establishment of a labeling system for the problem space.

So say we (arbitrarily) choose to label barriers in the two paths A and B as 1,2,3... in the test case's given order i.e. for the given test case:

3 8

2 4 6 --> path A (=== function A)

1 5 7 --> path B (=== function B)

https://github.com/noodlze/Olympiad/blob/master/WikiPageImages/BijectionProblemset_1.PNG

So now we have labeled the elements in each function (as 1,2,3 for both A and B), we move on to solving the core problem: Is there a bijection between path A and path B such that the two paths denoted as being different by us are in fact the same path on a physical map? https://github.com/noodlze/Olympiad/blob/master/WikiPageImages/BijectionProblemset_2.PNG So we need to identify the mapping (line between function A and function B) between two elements (one from function A and one from function B) such that the 2 elements are located in the same spot on a physical map AND all subsequent elements we move based on the labeling(if we are 1, move to 2,...) are also on the same spot. say 1 in path A corresponds to 2 in B, we don't need to check for this first element (We ONLY need to check whether the the subsequent pair of barriers we go to match) So for path A, the next barrier we go to is 2, for path B, the next barrier we go to is 3. We need to check if these 2 elements lie on the same spot on a physical map, the condition we then need to check is whether the (distance from 1->2) == (distance from 2->3), if at any time in our checking, a pair of barriers don't match--> result is NO-this mapping does not work. Visually, you can think of it as if you are rotating one circular path to fit the other path!

In terms of time complexity, there are n possible elements in function B that could correspond to the element 1 in function A.For each possible mapping, we need to check n mappings. With the problem range (1 ≤ n ≤ 50, n ≤ L ≤ 100), at most 50*50=2500 checks. Observe how the the size of L doesn't affect the running time.

Implementation issues:

  • how to caculate and store(for easy access later on) distances between two barriers; i used an array dis[n], with dis[i] denoting the distance between the ith barrier and the (i+1)the barrier (1<=i<=n), in order to calculate dis[n] which is the distance from the nth barrier to the 1st barrier, cause of the circular property, you need to have the sum of the distance from the 1st barrier to the nth barrier going ANTI-CLOCKWISE, dis[n] = L - sum.

  • One of the implementation issues i encountered was finding an easy way to check whether the n pairs matched.The circular property complicated things. Initially i wanted to use a pointers approach, where I would have two pointers ptr1 and ptr2, one pointing to the current location in path A, one for path B. On each iteration(n in total), I would check whether: distance between current barrier pointed to by ptr1 and the prev barrier pointed to by ptr1 == distance between current barrier pointed to by ptr2 and the prev barrier pointed to by ptr2. but i got a bit confused about pointer management under the timed conditions cause of the circular property.(pointers use is more prone to errors)

The method i used was to use a vector to store the distance for elements in B:

https://github.com/noodlze/Olympiad/blob/master/WikiPageImages/BijectionProblemSet_3.png

Then I would use a for loop to check whether disA[i] == disB[i] for all i in [1,n].

2.Santa Claus and Keyboard Check [MATH(this results in more cases/scenarios to check)]