EJOI 2025 Day 1 Task Collecting Diamonds Analysis Diamonds – Analysis Problem: Cheng Zhong, Analysis: Iliyan Yordanov We are given a directed weighted graph. The condition that each vertex has at least one outgoing edge means there are no dead ends – there is always an edge to continue along. Unlike classic graph problems, which maximize the total sum of weights, here the comparison is based on lexicographic order. We have to find the sum of the first 𝐾 edges on a lexicographically largest path (comparing the weights). At first glance, this might seem easier: a straightforward simulation appears sufficient; we begin the traversal at the starting vertex of the edge with the largest weight, and in each round, we choose the currently accessible edge with the largest weight. However, the situation is more complex because multiple edges may have the same weight, leading to frequent ties for the maximum. Therefore, if we rely solely on simulation, each decision may involve multiple tied maximums, resulting in exponential time complexity. Subtask 1 The small constraints allow a direct BFS-like approach for the solution. We perform a simulation where round 0 begins with all vertices active, and in each round, we select the currently accessible edges with the largest weight and store their endpoints for the next round. The answer is obtained by storing the sum of the weights for each round. Code: diamonds6.cpp Time complexity: 𝑂(𝑁 + 𝑀𝐾). Memory complexity: 𝑂(𝑁 + 𝑀𝐾). Subtask 2 It is easy to see that the exponential behavior of the previous approach is because in each round we unnecessarily repeat the same vertices multiple times. We can use a boolean array to flag the vertices that have already been added to the next round or alternatively store each round’s vertices in a boolean array (instead of an integer vector). Code: diamonds5.cpp Time complexity: 𝑂(𝐾(𝑁 + 𝑀 )). Memory complexity: 𝑂(𝑀 + 𝐾𝑁 ) or 𝑂(𝑀 + 𝑁 ) if we only store previous and current round. 1 / 8 EJOI 2025 Day 1 Task Collecting Diamonds Analysis Subtask 3 This subtask is a major step toward the full solution because 𝐾 is large. We can see that there is an optimal construction for the lexicographically largest path, since after sufficiently many rounds, some edges (and vertices) must repeat because they belong to the lexicographically largest sequence of weights among all possibilities. Lemma 1: There exists a lexicographically largest path that begins with a simple path (without duplicating vertices) and then repeats a simple cycle. go to proof If we know the optimal construction, it becomes a straightforward task to compute the answer. The sequence of weights starts with some numbers and then it becomes periodic. For greater 𝐾, we have to find the sum of the terms of a periodic sequence. There are two approaches for the task – one is by doing smarter simulation round by round and the other is by computing a dp to find the optimal decisions. Both approaches require a bound on the number of iterations. One can experimentally or intuitively find that this number of iterations is linear. In fact, two paths have identical sequences of weights for all rounds if and only if they have identical sequences of weights for the first 2𝑁 rounds. We will discuss this in detail in the next subtask. The first approach is a continuation of the idea in the previous subtasks. Let’s consider we have made sufficiently many rounds (at least 2𝑁). This means the non-optimal paths considered initially have already been eliminated, and we are now repeating the cycles of the possible optimal constructions. However, it is not straightforward, since the optimal paths can still be continued non-optimally for a couple of rounds (and then eliminated), after that these non-optimal continuations reappear, and so on. We can see that the only certain thing is that the starting vertices of all remaining paths need to be part of an optimal construction, otherwise they would have been eliminated already. So for each (𝑟, 𝑣), where 𝑟 is the round and 𝑣 is the vertex, it is enough to store a (𝑟 − 1, 𝑢) it came from (if there are multiple options, it is enough to store one). Then, after 2𝑁 rounds, we pick an arbitrary vertex, recover the path, and examine the starting part, which must be an optimal construction (a path and then a cycle). The other approach is to use dynamic programming 𝑑𝑝[𝑟][𝑣] = the optimal sequence of weights starting from vertex 𝑣 and having 𝑟 rounds (which is also the length of the sequence). Let 𝑤(𝑣, 𝑢) denote the weight of edge (𝑣, 𝑢). We have the following recursive relation: 𝑑𝑝[𝑟][𝑣] = max lexicographically 𝑢∶ for all edges (𝑣,𝑢) {𝑤(𝑣, 𝑢), 𝑑𝑝[𝑟 − 1][𝑢]}. As the constraints are smaller, we can compute the dp for sufficiently many rounds 𝑅 2 / 8 EJOI 2025 Day 1 Task Collecting Diamonds Analysis (at least 2𝑁) fast enough without optimizations. We pick the optimal sequence from 𝑑𝑝[𝑅][0], 𝑑𝑝[𝑅][1], ..., 𝑑𝑝[𝑅][𝑁 − 1]. There are different ways how exactly we can find the answer. We can store additional information so we can find the vertices of the edges that form the optimal sequence and then find the optimal construction from the vertices. Another way, used in the implementations, is to use only the sequence of weights. For this 𝑅 needs to be at least 3𝑁. We know the first elements must come from the path of an optimal construction, so to identify the repeating cycle we temporarily ignore the first 𝑁 elements. As the length of the repeating cycle in the optimal construction is at most 𝑁, we can find any valid repeating cycle in the sequence of the last 2𝑁 elements. The only drawback with the second approach is the memory if we store directly the sequences in each state. We have to be more efficient here and store the sequences as linked lists so 𝑑𝑝[𝑟][𝑣] is only the head element of the sequence, and that element is linked to some optimal (for 𝑣) 𝑑𝑝[𝑟 − 1][𝑢]. First approach Second approach Code diamonds_iliyan_n2_mem.cpp diamonds4.cpp Time complexity 𝑂(𝑁𝑀 ) 𝑂(𝑁2𝑀 ) Memory complexity 𝑂(𝑀 + 𝑁2 ) 𝑂(𝑀 + 𝑁2 ) Subtask 4 The constraints for this subtask make the graph consist of a single cycle or multiple disconnected cycles. This subtask is given so that competitors can think more about the cycles and the needed rounds for comparison. We can find the optimal traversal by comparisons: • For two traversals in the same cycle, we only need to compare their results of the first 𝑙𝑒𝑛𝑔𝑡ℎ(𝑐𝑦𝑐𝑙𝑒) rounds; • For two traversals in different cycles, we only need to compare their results of the first 𝑙𝑐𝑚(𝑙𝑒𝑛𝑔𝑡ℎ(𝑐𝑦𝑐𝑙𝑒1 ), 𝑙𝑒𝑛𝑔𝑡ℎ(𝑐𝑦𝑐𝑙𝑒2 )) rounds. Although not necessary for this subtask, we can use the following lemma, which shows that only a linear number of comparisons are needed for the second case. Lemma 2: If two periodic sequences with periods 𝑝 and 𝑞 have the same first 𝑝 + 𝑞 terms, then they are identical. go to proof There is an even stronger bound: it is enough to compare the first 𝑝 + 𝑞 − gcd(𝑝, 𝑞) terms but this is not needed for the task and does not change the complexity. The lemma tells us that we need approximately 2𝑁 rounds to compare any two cycles. In the general case 3 / 8 EJOI 2025 Day 1 Task Collecting Diamonds Analysis when the optimal construction starts with a path this would require approximately 3𝑁 rounds (additional 𝑁 to enter the cycle). But it is easy to see that still 2𝑁 rounds are enough because the cycle and the path have to be disjoint (they cannot share vertices). This is a tight bound as illustrated in the following example, where 2𝑁 − 3 rounds are required to compare the two possible optimal constructions (there are also such tests with a modified version): 1 3 2 2 2 2 2 1 2 2...2 0 1 2 3 4 N-2 N-1 ... ... Code: diamonds9.cpp Time complexity: 𝑂(𝑁2 ). Memory complexity: 𝑂(𝑁 ). Subtask 5 The task becomes much simpler when all 𝑑[𝑖] are distinct. There is only one maximum choice for each round, so the only challenge is handling large 𝐾. It is easy to see that the optimal construction is first a simple path and then repeating a simple cycle. So we follow the maximum weight for each round until we find a cycle, and then we have to find the sum of the terms of a periodic sequence. This subtask allows contestants to observe the optimal construction more easily. Code: diamonds_iliyan_unique_d.cpp Time complexity: 𝑂(𝑁 + 𝑀 ). Memory complexity: 𝑂(𝑁 + 𝑀 ). Subtask 6 This subtask is similar to the previous one as the optimal construction is much easier to see than in the general case. Let edge (𝑢, 𝑣) be the one with weight 2. We should use the weight 2 as often as possible. We have to start with (𝑢, 𝑣) and then return as quickly as possible (using the fewest number of weight-1 edges) to vertex 𝑢. If this is not possible, the answer is simply 2 + (𝐾 − 1) = 𝐾 + 1. Otherwise we have to compute how many times we will use weight 2 and the answer is 𝐾+ this number. We can use BFS to find the shortest path of 1-s from 𝑣 to 𝑢 or determine that no such path exists. Code: diamonds8.cpp Time complexity: 𝑂(𝑁 + 𝑀 ). Memory complexity: 𝑂(𝑁 + 𝑀 ). 4 / 8 EJOI 2025 Day 1 Task Collecting Diamonds Analysis Subtask 7 We now revisit the two approaches and discuss the different ways to optimize them to fit the small memory constraint. There are two ways to optimize the first approach, which relied on smarter round-by-round simulation. We can use a bitset memory optimization. Instead of storing, for each (𝑟, 𝑣), a (𝑟 − 1, 𝑢) it came from, we can use one bitset per round to record the vertices that are present. If we know the vertices in consecutive rounds it is easy to find a path that starts from (0, 𝑣) and goes to (𝑅, 𝑢) for some vertices 𝑣 and 𝑢, and a final round 𝑅. If we are at (𝑖, 𝑥) and we have an edge (𝑥, 𝑦) in the original graph, we have to check if vertex 𝑦 was present in the next round 𝑖 + 1, i.e. if (𝑖 + 1, 𝑦) existed during the simulation. Once we find a path, we can compute the answer as before. The second way to optimize the first approach uses the earlier idea of finding the answer using only the sequence of weights. We can store the maximum weight that is used for each round and construct the optimal sequence of weights without knowing the exact path. Then, as described earlier, we can find the cycle by examining the last 2𝑁 elements and then compute the final answer. (we still need at least 3𝑁 rounds of simulation) For the second approach, we will first optimize the time complexity. We recall the recursive relation: 𝑑𝑝[𝑟][𝑣] = max lexicographically 𝑢∶ for all edges (𝑣,𝑢) {𝑤(𝑣, 𝑢), 𝑑𝑝[𝑟 − 1][𝑢]}. The bottleneck is the ”max lexicographically” comparison, which we previously did in linear time, but this can be improved. We will keep a sorted list of 𝑑𝑝[𝑟 − 1][𝑣] (for fixed 𝑟 − 1) and we need to obtain a sorted list of 𝑑𝑝[𝑟][𝑣]. For this we can store in 𝑑𝑝[𝑟 − 1][𝑣] ”ranks” which are numbers that show the relative order of the weight sequences. To obtain the sorted list of 𝑑𝑝[𝑟][𝑣], for each 𝑣 we use 𝑤(𝑣, 𝑢) as a primary key and 𝑑𝑝[𝑟 − 1][𝑢] as a secondary key, where 𝑢 is the argmax in the relation above for 𝑣. Then we sort these pairs lexicographically and find the new ranks for 𝑑𝑝[𝑟][𝑣]. We can even do this in linear time as we can do a radix sort over the pairs. It is also possible not to fix the number of iterations and terminate when the ranks stop changing. Now we have good time complexity and we will find the optimal construction in the following way. Suppose we have all 𝑑𝑝[𝑅][𝑣] for some number of rounds 𝑅, and we construct a new graph with the edges (𝑣, 𝑢) for each 𝑣, where 𝑢 is the argmax in the dp relation for 𝑑𝑝[𝑅][𝑣]. We claim that if 𝑅 is at least 2𝑁 and we start from the optimal 𝑣 (with the highest rank 𝑑𝑝[𝑅][𝑣]), and follow these edges, we will find an optimal construction. This is because all paths with such length starting from 𝑣 must follow an optimal construction so even if there are ties for argmax for 𝑣, all of them will be part of optimal constructions. A similar argument holds for the other vertices we visit along the path since non-optimal possibilities would be eliminated for large enough 𝑅. Thus, we directly obtain the optimal 5 / 8 EJOI 2025 Day 1 Task Collecting Diamonds Analysis construction, from which the answer follows as before. For this solution, 𝑅 = 𝑁 is also sufficient, since the dp takes a more global view and removes non-optimal possibilities from the beginning, and needs additional iterations to propagate that information. First approach Second approach Code diamonds_encho_bitset.cpp, diamonds7.cpp diamonds1.cpp, diamonds_iliyan.cpp Time complexity 𝑂(𝑁𝑀 ) 𝑂(𝑁𝑀 + 𝑁2 log 𝑁 ) or 𝑂(𝑁𝑀 + 𝑁2 ) Memory complexity 𝑂 (𝑀 + 𝑁2 64 ) for the bitset and 𝑂(𝑁 + 𝑀 ) for the other solutions 𝑂(𝑁 + 𝑀 ) Final thoughts During testing, we found a particular variation of the first approach. Instead of reasoning about the number of rounds, we can terminate if we repeat the same set of vertices during a round (which we can find using hashing). Then the cycle is the sequence of weights between the two repetitions. It turns out exponentially many rounds may be required for the repetition to happen so we still require a bound for the rounds. The best type of test we came up with to battle such cheat solutions is the following: 3 3 3 1 2 1 2 1 2 1 2 1 2 1 2 0 1 2 3 4 5 6 7 8 9 10 12 11 The base model is we have some constant 𝑘 and then we make cycles of lengths 𝑘, 2𝑘, 3𝑘, 5𝑘, 7𝑘, 11𝑘, … that repeat 1, 2, … , 𝑘 as weights (in the example 𝑘 = 2 and the cycles are of lengths 2, 4 and 6). In this way we need the LCM of the lengths (a huge value), as the number of rounds required to repeat the same set of vertices. Also if we terminate early, it is not simple to compute the answer looking at the sequence of weights, since we still have a non-trivial repeating cycle (the simplest correct way is to have a full solution like diamonds7.cpp). Unfortunately, it turned out we had missed adding these tests in the official test data so a few contestants passed by terminating early and computing the answer in a wrong way. The original proposal for this task was even harder, but we believe the current variant is more appropriate for EJOI. In fact, it turned out to be slightly harder for contestants than we initially thought. 6 / 8 EJOI 2025 Day 1 Task Collecting Diamonds Analysis Proof of Lemma 1 Lemma 1: There exists a lexicographically largest path that begins with a simple path and then repeats a simple cycle. Suppose a lexicographically largest path is: 𝐿 ∶= (𝑣0 , 𝑣1 ), (𝑣1 , 𝑣2 ), … . As the path is infinite and the different vertices are only 𝑁, there has to be a repeated vertex. Let the first repeated vertex be 𝑣𝑗 , with its previous occurrence at 𝑣𝑖 (0 ≤ 𝑖 < 𝑗). This also means that 𝑣0 , 𝑣1 , … , 𝑣𝑖−1 is a simple path and 𝑣𝑖 , 𝑣𝑖+1, … , 𝑣𝑗−1, 𝑣𝑖 (𝑣𝑖 = 𝑣𝑗 ) is a simple cycle. Let 𝑃 ∶= (𝑣0 , 𝑣1 ), (𝑣1 , 𝑣2 ), … , (𝑣𝑖−1, 𝑣𝑖 ) and 𝐶 ∶= (𝑣𝑖 , 𝑣𝑖+1), (𝑣𝑖+1, 𝑣𝑖+2) … , (𝑣𝑗−2, 𝑣𝑗−1), (𝑣𝑗−1, 𝑣𝑖 ). We will prove the following claim by induction: for each 𝑟 ≥ 1, the sequence of weights in 𝐿 starts with the sequence of weights of {𝑃 , 𝐶(𝑟)}, where 𝐶 (𝑟) denotes 𝐶, … , 𝐶 ⏟𝑟 . Base case 𝑟 = 1. We know that the path 𝐿 starts with {𝑃 , 𝐶} so the claim holds. Induction step. Let the claim be true for some 𝑟 ≥ 1. We will prove it for 𝑟 + 1. The claim is true for 𝑟, so the weights of 𝐿 start with the weights of {𝑃 , 𝐶(𝑟)}, and we will denote the edges after that with 𝑆. We will also denote 𝑃 ′ ∶= {𝐶, 𝑆}. The sequence of weights of 𝐿 equals that of {𝑃 , 𝐶(𝑟−1), 𝑃′}. Since {𝑃 , 𝐶(𝑟−1), 𝑆} is a valid path (with one fewer cycle), 𝑃 ′ must be lexicographically larger than or equal to 𝑆. If they are equal, then we are ready as this would mean that the weights of 𝑆 are starting with the weights of 𝐶 (since 𝑃 ′ = {𝐶, 𝑆}), so 𝑃 ′ is starting with weights 𝐶 (2) and 𝐿 is starting with weights {𝑃 , 𝐶(𝑟+1)}. Let’s assume they are not equal. So there must be an edge in 𝑃 ′ with larger weight than the corresponding one in 𝑆. Let the first such edge be 𝑒. If 𝑒 is in the cycle 𝐶, then the cycle will be lexicographically larger than the corresponding part of 𝑆, so a path {𝑃 , 𝐶(𝑟+1)} will be lexicographically larger than 𝐿, which is a contradiction. The only remaining case is when 𝑒 is after the cycle 𝐶. This would mean that the sequence of weights in the cycle 𝐶 is the same as the corresponding sequence of weights in 𝑆, which means that the weights of 𝑆 are starting with the weights of 𝐶, and 𝐿 is starting with weights {𝑃 , 𝐶(𝑟+1)}. Thus, the claim follows by induction. This means that the sequence of weights in 𝐿 is the same as the sequence of weights of {𝑃 , 𝐶, 𝐶, … }. Since {𝑃 , 𝐶, 𝐶, … } is a valid path, it is a lexicographically largest path that begins with a simple path and then repeats a simple cycle. 7 / 8 EJOI 2025 Day 1 Task Collecting Diamonds Analysis Proof of Lemma 2 Lemma 2: If two periodic sequences with periods 𝑝 and 𝑞 have the same first 𝑝 + 𝑞 terms, then they are identical. Without loss of generality, assume 𝑝 ≤ 𝑞. Let the sequences be 𝑃0 , 𝑃1 , … and 𝑄0 , 𝑄1 , … We will prove the following claim by induction: for each 𝑟 ≥ 0, the sequences have the same first 𝑝 + 𝑞 + 𝑟𝑝 terms. Base case 𝑟 = 0. As the sequences have the same first 𝑝 + 𝑞 terms, the claim holds. Induction step. Let the claim be true for some 𝑟 ≥ 0. We will prove it for 𝑟 + 1. Let’s assume the contrary and let 𝑝 + 𝑞 + 𝑟𝑝 ≤ 𝑖 < 𝑝 + 𝑞 + (𝑟 + 1)𝑝 be an index such that 𝑃𝑖 ≠ 𝑄𝑖 . We have the following: • As 𝑃 has a period 𝑝, we have 𝑃𝑖 = 𝑃𝑖−𝑝. • As 𝑖 − 𝑝 < 𝑝 + 𝑞 + 𝑟𝑝, we have 𝑃𝑖−𝑝 = 𝑄𝑖−𝑝. • As 𝑄 has a period 𝑞, we have 𝑄𝑖−𝑝 = 𝑄𝑖−𝑝−𝑞. • So, 𝑃𝑖 = 𝑃𝑖−𝑝 = 𝑄𝑖−𝑝 = 𝑄𝑖−𝑝−𝑞. Similarly, 𝑄𝑖 = 𝑄𝑖−𝑞 = 𝑃𝑖−𝑞 = 𝑃𝑖−𝑝−𝑞 (since 𝑝 ≤ 𝑞, we have 𝑖 − 𝑞 ≤ 𝑖 − 𝑝 < 𝑝 + 𝑞 + 𝑟𝑝). But 0 ≤ 𝑖 − 𝑝 − 𝑞 < 𝑝 + 𝑞 + 𝑟𝑝, so 𝑃𝑖−𝑝−𝑞 = 𝑄𝑖−𝑝−𝑞 by the induction step and this means 𝑃𝑖 = 𝑄𝑖 , which is a contradiction. Thus, the claim follows by induction. This means that the sequences must be identical, since we can pick an arbitrarily large 𝑟. 8 / 8