This Kickstart round began with Huge Numbers, which could be solved by taking advantage of a basic property of exponents. Then came Cards Game, which appeared to be solvable via some complicated greedy approaches, but turned out to have an elegant minimum spanning tree approach. Finally, we had Matrix Cutting, which involved breaking a large matrix into smaller independent submatrices by making horizontal and vertical cuts. It could be solved via dynamic programming.
Thanks to everyone who participated!
Cast
Problem A (Huge Numbers): Written and prepared by Lalit Kundu.
Problem B (Cards Game): Written by Amit Pandey. Prepared by Amit Pandey and Lalit Kundu.
Problem C (Matrix Cutting): Written and prepared by Lalit Kundu.
Solutions and other problem preparation and review by Akashdeep Nain, Nishant Redkar, Ian Tullis and Xuan'ang Zhao.
Analyses by Lalit Kundu.
Professor Shekhu has another problem for Akki today. He has given him three positive integers A, N and P and wants him to calculate the remainder when AN! is divided by P. As usual, N! denotes the product of the first N positive integers.
The first line of the input gives the number of test cases, T. T lines follow. Each line contains three integers A, N and P, as described above.
For each test case, output one line containing Case #x: y, where x is the
test case number (starting from 1) and y is the answer.
1 ≤ T ≤ 100.
Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ A ≤ 10.
1 ≤ N ≤ 10.
1 ≤ P ≤ 10.
1 ≤ A ≤ 105.
1 ≤ N ≤ 105.
1 ≤ P ≤ 105.
2 2 1 2 3 3 2
Case #1: 0 Case #2: 1
In Sample Case #1, the answer is the remainder when 21! = 2 is divided by 2, which is 0.
In Sample Case #2, the answer is the remainder when 33! = 36 = 729 is divided by 2, which is 1.
Professor Shekhu was a famous scientist working in the field of game theory in the early days of computer science. Right now, he's working on a game which involves a box containing N distinct cards. The i-th of these cards has a red number written on one side, and a blue number written on the other side. Both of these numbers are positive integers. The game proceeds as follows:
Professor Shekhu has summoned his best student, Akki, to play this game. Can you help Akki find the minimum possible total, considering all possible ways in which he can play the game?
The first line of the input contains an integer T, the number of test cases. T test cases follow;
each test case consists of three lines:
First line of the each test case will contain an integer N.
For each test case, output one line containing Case #x: y, where x is the
test case number (starting from 1) and y is the minimum possible total that Akki can
attain, if he plays optimally.
1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ Ri ≤ 109.
1 ≤ Bi ≤ 109.
2 ≤ N ≤ 5.
2 ≤ N ≤ 100.
2 2 1 2 3 3 3 1 101 501 3 2 3
Case #1: 1 Case #2: 5
In Sample Case #1, Akki has only one move in which he picks up the available cards and has two options.
In Sample Case #2, one optimal strategy is to take the red number from first card and the blue number from second card, add 1 ^ 2 = 3 to the total, and return first card to the box. Then, take the red number from first card and the blue number from third card, add 1 ^ 3 = 2 to the total, and return either of the cards to the box. The final total is 5.
Prof Shekhu has a matrix of N rows and M columns where rows are numbered from 0 to N-1 from top to bottom, and columns are numbered from 0 to M-1 from left to right. Each cell in the matrix contains a positive integer.
He wants to cut this matrix into N * M submatrices (each of size 1 * 1) by making horizontal and vertical cuts. A cut can be made only on the boundary between two rows or two columns.
Prof Shekhu invites his best student Akki for this job and makes an interesting proposition. Every time Akki makes a cut in a submatrix, before he makes the cut, he is awarded a number of coins equal to the minimum value in that submatrix. Note that with every cut, the total number of submatrices increases. Also, cuts in any two different submatrices are independent and likewise, Akki is awarded independently for the cuts in different submatrices.
Now, Akki has various ways in which he can make the cuts. Can you help him by maximizing the total number of coins he can gain?
The first line of the input contains an integer T, the number of test cases. T test cases follow.
The first line of each test case contains two integers N and M, as described above.
For each test case, output one line containing Case #x: y, where x is the
test case number (starting from 1) and y is the maximum possible number of coins that Akki can
be awarded, if he makes the cuts in optimal order.
1 ≤ T ≤ 100.
Memory limit: 1GB.
1 ≤ each value in the matrix ≤ 105.
Time limit: 40 seconds.
N = 1.
1 ≤ M ≤ 10.
Time limit: 120 seconds.
1 ≤ N ≤ 40.
1 ≤ M ≤ 40.
3 2 2 1 2 3 4 2 3 1 2 1 2 3 2 1 2 1 2
Case #1: 5 Case #2: 7 Case #3: 1
In Sample Case #1, there are two possible ways in which Akki can make the cuts.
In Sample Case #2, Akki can be awarded at most 7 coins. One of the optimal ways is to first make the only horizontal cut to earn 1 coin. Then, in the upper submatrix [1, 2, 1], Akki can first make the cut immediately to the right of first column and then the cut immediately to the right of second column to earn a total of 2 coins. Similarly, in the lower submatrix [2, 3, 2], Akki can first make the cut immediately to the right of second column and then the cut immediately to the right of first column to earn a total of 4 coins.
In Sample Case #3, there is only one cut to be made.
For the small input, calculating the actual value of N factorial suffices, since N is up to 10. We just need to calculate An mod P, where n could be up to 10! = 3628800. We can compute this iteratively, maintaining our answer modulo P at all times, as in the following pseudocode:
ans = 1
for i = 1 to factorial(N)
// Since, multiplication is associative modulo P,
// we can maintain our answer modulo P
ans = (ans * A) % P
return ans
Since P and A are both no greater than 105, and we are taking modulo P at
each stage, we do not need to worry that (ans * A) will overflow the result, provided that
we use a long rather than an int to store ans.
At first, it may seem like this problem requires a number-theoretic approach.
But there exists a very simple solution which employs fast exponentiation.
First, let's see how efficiently we can calculate An mod P for a given n.
We can use a divide and conquer approach to come up with an O(log n) solution, as summarized by
the following algorithm:
pow(a, n, p):
if n == 0
return 1
pow_half = pow(a, n / 2, p)
pow_half_sq = (pow_half * pow_half) % p // again, multiplication is associative modulo p
if n % 2 == 0
return pow_half_sq
else
return (pow_half_sq * a) % p
We can also take advantage of a basic property of exponents: ab*c can be rewritten as abc. So, we can write AN! as A123.... And, since multiplication modulo P is associative, we can maintain our answer modulo P at all times. So, our O(N log N) algorithm is:
ans = A % P
for i = 2 to N
ans = pow(ans, i, P)
return ans
We have a 1-D array of size M which needs be broken down into M parts by making vertical cuts in an order of our choice, where each vertical cut yields a number of coins equal to the minimum value in the subarray at the time of the cut. Our objective is to make the cuts in an order that maximizes the total number of coins.
Since M can be no greater than 10 in this dataset, we can simply consider all possible orderings of the cuts. For each permutation, we can simulate the cuts and calculate the total number of coins, and then output the maximum total we find across all permutations. The complexity of this approach is O(M!), which is sufficient for the Small dataset.
However, we will have an easier time with the Large dataset if we come up with a better approach. One helpful observation is that once a cut is made, the problem has been reduced to two independent problems of the same type: one for the left subarray, and one for the right subarray. This strongly suggests a dynamic programming (DP) based solution.
We can define each subproblem in the DP as f(L, R): the answer for a subarray ranging from positions L to R, inclusive, in the original array. Our final answer is f(0, M-1). Now we need a recurrence relation, which we can develop by iterating over the position of the first cut we make, as in the following pseudocode:
f(L, R, A): // A is the original array
ans = 0
// Assuming first cut is made immediately to the right of cut_position
for cut_position in L to R - 1, inclusive
ans = max(ans , f(L, cut_position) + f(cut_position + 1, R))
// we can calculate this in O(M).
current_coins = minimum value in A over positions L to R, inclusive
// For the current cut, we get the same number of coins no matter where we cut.
return ans + current_coins
With memoization, the total complexity of this approach is O(M3). Remember, the
complexity of a DP approach is given by the number of possible distinct states times the cost of transitioning between states.
In the Large dataset, we have a 2-D matrix in which we can make horizontal cuts as well as vertical cuts. Since the total number of cuts could be up to 80, and those cuts could occur in many possible orders, our brute force method no longer works.
However, our efficient DP approach from the 1-D case can be extended to the 2-D case, by redefining our DP state to describe the answer for a submatrix instead of a subarray. So, we define f(L, R, P, Q) as the answer for a submatrix defined by the intersection of rows L through R, and columns P through Q (all limits inclusive). A recurrence relation can be derived by iterating over all possible horizontal and vertical cuts as the first cut we make. Pseudocode:
f(L, R, P, Q, A): // A is original matrix
ans = 0
// horizontal cuts
for horz_cut = L to R - 1, inclusive
ans = max(ans, f(L, horz_cut, P, Q) + f(horz_cut + 1, R, P, Q) + current_coins)
// vertical cuts
for vert_cut = P to Q - 1, inclusive
ans = max(ans, f(L, R, P, vert_cut) + f(L, R, vert_cut + 1, Q) + current_coins)
// we need to calculate this in less than O(N + M), if we don't want this step
// to dominate the transition cost
current_coins = minimum value in current submatrix (defined by L, R, P, Q)
// For the current cut, we get the same number of coins no matter where we cut.
return ans + current_coins
The only remaining piece of the puzzle is: how do we calculate the minimum value in a submatrix efficiently, in time linear or better in the number of rows and columns of the submatrix? We can pre-calculate answer for all O(N2M2) submatrices, which is easier if you fix the top-left corner of the submatrix and iterate over possible bottom-right corners. This can be done in O(N2M2) overall.
The overall complexity of our DP approach is O(N2M2(N + M)), which is fast enough for the Large dataset.