214A - System of Equations
The first glimpse to the problem statement shows me that if m or n get their maximum value which in this case is 1000, then maximum value for a or b would be 1000 to satisfy the equation. So I must check all possible values for a(0...1000) and all values for b(0...1000), and count the pairs (a, b) such that satisfy the given equation.
214B - Hometask
After reading the problem statement, you can find out that the necessary and sufficient condition so that we can find a number which is divisible by 2, 3 and 5 is that there exists one 0 in the input, cause at least we can build 0. Then as I want to maximize the final result, I like all the input digits appear in the output, unless where it breaks the rule for divisibility of 3. (Which numbers are divisible by 3? Those which addition of their digits is divisible by 3.) So I have a variable sum which is the summation of the input digits, here we face 3 total cases:
1. sum is divisible by 3 : everything is alright, I sort input digits, reverse it, and print it.
2. the remainder of sum divided by 3 is 1 : So I have to remove (one digit 1) or (one digit 4) or (one digit 7) or (two 2's) or (one 2, one 5) or (one 2, one 8) or (two 5's) or (one 5, one 8) or (two 8's)
3. the remainder of sum divided by 3 is 2 : So I have to remove (one digit 2) or (one digit 5) or (one digit 8) or (two 1's) or (one 1, one 4) or (one 1, one 7) or (two 4's) or (one 4, one 7) or (two 7's)
If you take a look at situation 2 or 3, it's obvious that we have to act greedily, first we want the length of the output to be maximized, if there are several answers with the same length then we want to remove smaller digits, so the output is maximized.
214C - Game
You can present input as a directed graph that as stated in the problem statement it surely has a topological sort. Each part of the game is a node in this graph. One of the algorithms to find a topological sort in a directed graph is to repeatedly remove a node whose indegree is equal to zero, and remove all the outgoing edges from that node. After reading the problem statement specially where it states the costs to each action, you see that there is a circular movement for Rubik, 3->1->2->3->1->2... All we have to do is to decide where to start, from computer 1, computer 2 or computer 3, After we decided where to start, the best way to do the job is to remove the nodes that are associated with the current computer and their indegrees are equal to zero, we do this until there is no node with indegree 0 on this computer, then what's best for us to do? We leave this computer and go to the next computer(1->2, 2->3, 3->1), and do this on that computer, we do this until all parts of the game are done. At the end we print minimum cost (starting from computer 1, computer 2 or computer 3) plus n (each part takes one our).
214D - Numbers
This problem can be solved using dynamic programming.
a[i] : at least a[i] digits of i should appear in the desired sequence.
I have an array -> int dp[10][101], which dp[digit][len] counts the number of sequences which their length is equal to len and all of them satisfy input condition for all digit, digit+1, digit+2 ... 9. For example dp[8][10] counts the number of sequences which their length is equal to 10, and has at least a[8] 8's and a[9] 9's. What does dp[7][20] counts?
What is the basic state to our dp? dp[9][j] = 1 for all j = a[9]...n
Now we want to update dp table.
Consider dp[i][j+k], which j = a[i]...n and j+k <= n, We want to update dp[i][j+k].
We need at least j of digit i, and the other k of them are from digits i+1,i+2,...,9
What is dp[i+1][k], the number of sequences with length k, that satisfy condition for i+1,i+2...9, if we put j of digit i in these sequences their length would become j+k and the condition for digit i would be satisfied too, but we have to count all of them.
Consider a sequence from dp[i+1][k]. Now consider a sequence of length j+k which is empty, choose j of the j+k elements of this sequence, put j of digit i in the chosen places, and put the k digits of the original sequence in order in the empty places, now we have a sequence of length j+k which satisfies the conditions for all digits i...9
dp[i][j+k] += combination(j, j+k) * dp[i+1][k].
When i is equal to zero, the first digit could not be chosen, so dp[i][j+k] += combination(j, j+k-1) * dp[i+1][k].
For example 899, 989 and 998 are counted in dp[8][3], now we want to put 1 of 7's to satisfy the basic condition for digit 7, consider an empty sequence with length 4, ----, choose 1 of these 4 empty places and put 7 there, then put 899, 989, 998 in order in the empty places.
7--- -> 7899, 7989, 7998
-7-- -> 8799, 9789, 9798
--7- -> 8979, 9879, 9978
---7 -> 8997, 9897, 9987
so dp[7][4] += d[8][3] * combination(1, 4)
dp[7][4] += 3 * 4
dp[7][4] += 12
Now what is the final answer? dp[0][1] + dp[0][2] + dp[0][3] + ... + dp[0][n]
214E - Relay Race
This problem also can be solved using dynamic programming. (Thanks to Zool for his guide)
dp[t][x1][x2] means the maximum value earned that player one gets to row x1 in t steps, and player two gets to row x2 in t steps.
what is the answer?
dp[n+n-2][n-1][n-1] -> my calculations are 0-based
so it means maximum value that player one gets to row n-1 and player two gets to row n-1 in n+n-2 steps, cause from (0,0) to (n-1,n-1) is n+n-2 steps how do we update dp[t][x1][x2] ???
alright we decide whether player one wants to get updated from its current row or he wants to get updated from the previous row, and so for the player two.
so what happens to their row value x1 and x2???
we have this int d[4][2] = {{0, 0}, {0, -1}, {-1, 0}, {-1, -1}}; both from the same row
first player from the same row, second player from the previous row
first player from the previous row, second player from the same row
both from the previous row according to their current row
Before we update tell me about this, If player one has gotten to row x1 in t steps(we know that they can go down or right in their path), So at this time what is his/her column??? x1+y1=t so y1=t-x1 alright? Check the same thing for player two, x2+y2=t so y2=t-x2
So now we can update dp[t][x1][x2] from tmp = dp[t-1][previousX1][previousX2] + a[x1][t-x1] + a[x2][t-x2]
But pay attention if x1==x2 that means y1 is equal to y2, so they want to get updated from the same cell, so tmp -= a[x1][t-x1] or tmp -= a[x2][t-x2]
What is the basic state to our table? dp[0][0][0] = a[0][0], that means if both player want to get to row 0 with 0 steps, so they are at cell(0,0).
thank you , its very good explanation.
These explanations are very understandable. They are useful for me, specially about problem C (another way for applying topological sort on a directed graph) Thanks alot
does it have another solution besides topological sort ?
Well, you don't have to explicitly perform a topological sort. There exists an algorithm for traversing a DAG topologically (I've invented it during the contest, but it's obviously a bicycle reinvention :) ).
The algorithm is: we maintain a queue of vertices that already have all of their dependencies satisfied and an array of vertices' unsatisfied dependencies count, I mean: vertices' degrees. Initially, the queue must be filled with the vertices that have zero degree. When we take a vertex out of the queue, we decrease the degrees of vertices current vertex has incoming edges from. If some of such degrees becomes zero, we add the corresponding vertex to the queue. You can see an implementation (but I've used 3 queues, one for each computer, for obvious reason).
I had nearly same solution. Its one of the way of implementation of topological sort.
Nice one man. Keep writing for upcoming rounds. good luck
Thank you for detailed analysis of problem D(Numbers).
Thank you Mr.Kazemi! Great ;) For problem D there's also an easy combinatorics way!