15195 Fall 2023 #12 No Theme -- Problem Discussion

November 29, 2023

This is where we collectively describe algorithms for these problems.  To see the problem statements and scoreboard, go to this page and select this contest.

A. Mashmokh and ACM

B. Quasi Binary

It can be shown that the minimum number of quasibinary numbers needed whose sum is N is just the maximal digit in N (we call it M) - each quasibinary number will have a 1 in the position of M in N (therefore only that many numbers are needed), and you need at least that many quasibinary numbers for that reason as well. To get the numbers themselves, build them digit position-wise. For each position, if the digit in that position in N is A, then the first A quasibinary numbers will have 1s in that position, and 0s for the remaining M-A quasibinary numbers. Do an lstrip() to remove leading zeros, and print.

~ Dhruv

C. Kyoya and Colored Balls

You can place all Balls of the first color in any way (since Balls of the same color are identical, there is only 1 way to do this). Then, if there are N_i balls of color k_i for i > 1, you need to arrange N_i - 1 Balls in any way among the Balls already on the table, and the last one of color k_i at the end of the chain. This becomes a stick-and_ball problem, where the Balls of colors up to k_(i-1) are the (identical) sticks and the N_i - 1 balls of color k_i are the balls to be arranged, which can be done in (N_i - 1 + total number of Balls up to and including k_(i-1)) choose (N_i - 1) ways. Multiply this out, modulo 10^9 + 7.

~ Dhruv

D. Dima and Horses

Greedily add the horses to parties with at most one enemy. This is always possible because each horse has at most three enemies. Now, for the enemy of the horse that was added, if this enemy has more than one enemy in its party after the addition, move it to the other party. Again, this is possible. Repeat doing this recursively until all horses have at most one enemy in their parties.

- epei

(IDK the time complexity of this but it passes it’s probably O(n) but don’t know how to bound it, I thought in contest that a horse couldn’t switch parties twice, but it’s actually possible, probably, idk)

Consider this as coloring an undirected graph, we can find all the vertices that are “bad” and then color it again, repeat the process again. This process will end in less than M operations since the number of “bad” edges will always decrease by at least 1 each operation.

-Jason

E. Baldman and the military

This problem reduces to finding a MST (i think)

F. List of Primes

Binary search or something

We consider brute force when r<=1e5, with states (sum, len, lim) representing the remaining subset has sum of sum, size len and can only use primes after lim. There exists an obvious prune such that f[i][j] represents that if there exists a solution so that sum=i when lim=j. This makes the solution O(r)

We observe r-l<=1e5. So if the subset length and next state’s length has sum < l, there is no point doing the search at the time. So we can use g[i][j] as using primes >= j with the longest length. And we change f[i][j] to number of subsets after primes >= j. Then the problem becomes a trivial DP problem. We can also observe that j caps off at about 350. With careful implementation, the problem can be done in O(r-l)

-Jason

G. Game on Graph

First we can find if the current state is a tie. Obviously the vertices with out-degree 0 are not tie. Since Gennady wants tie while Georgiy does not, for Gennady, any of the post-current state being tie can lead to a tie, while for Georgiy all post-current state have to be a tie for it to be a tie. We can use a similar process to topological sort on the reverse graph to simulate this process.

For all non-tie nodes, use game theory to transition. There exists special cases when there is are cycles in the graph, those vertices can guarantee Gennady win and Georgiy lose

-Jason