I will explain my way for solving all the problems here, if you don't understand something or have a question don't dude to ask.
If you have a different / better solution, share it with us.
THE POST IS NOT FINISHED, I WILL DO IT AS SOON AS I CAN.
I hope this can be useful for you.
The problems can be solved in COJ.
A. Naebbirac Phrases (Trivial)
B. Careful with Poison (Combinatorics)
C. Counting Figures (Ad-hoc, Sweep line?)
D. Dr. B - Tree II (DP)
E. Even Number of Divisors (Number theory, Binary Search)
F. Fast Traveler Game (Simulation)
G. Fear of the Dark (HLD, Segment Tree)
H. How Many Numbers (Backtracking)
I. List of Natural Numbers (Find the pattern)
A - Naebbicar Phares
Read two string S and T and count how many characters are different in S and T at same index, for example if S = "alex" and T = "alxs" answer is 2, is guaranteed that length of S is equal to length of T, the letters in black are the mismatches.Here is my code.
B - Careful with Poison
First how to solve the problem without the square? Binomial Coefficient is you friend.Let ways(N, K) = number of ways to choose K elements from a set of N.
This will ignore the square, we have to use the Inclusion Exclusion Principle to remove the invalid ways.
To do this, let represent the square as 9 points in the grid:
ABC
DEF
GHI
The points "C", "E" and "G" are exclusive, this means that if our path can pass only from one of these three points.
Let count(N, a, b) = the number of ways to get from point (0, 0) to point (N, N) passing the point located at (a, b), this can be broke in the number of ways to get from (0, 0) to (a, b) multiplied by the number of ways to get from (a, b) to (N, N).
Now to remove the invalid ways we can use the previous function and the result is = ways(N, N) - count(N, Cx, Cy) - count(N, Ex, Ey) - count(N, Gx, Gy).
Notice that N can be large and is an obvious overflow, we are required to compute the result modulo a prime number, this help us to use modular arithmetic to compute the answer, we can pre compute all the factorials between [0, MAX] MOD M and compute the binomial coefficient using the modular inverse.
Complexity is O(1) per query if you precomputed the modular inverse or O(log(N) ) computing it as required.
See the code for further details.
Here is my code.
C - Counting Figures
This problem can be solved detecting only the figures of 4, 6 and 8 sides.A figure have 4 sides if is a completed rectangle:
XXXX
XXXX
XXXX
The X is a filled point.
A figure have 6 sides if filling a subrectangle in a corner makes a complete rectangle:
XXEE
XXEE
XXXX
XXXX
The E is an empty point.
A figure have 8 sides if require two corners to be filled as rectangles to build a complete rectangle or if requires to fill a rectangle starting in a side but not in a corner, see the examples:
XXEE
XXEE
XXXX
XXEE
Or
XXXX
XXEE
XXEE
XXXX
This is an easy to find solution but really tedious to code, i'm trying to get a better and shorter approach, my code is around 300 lines long.
THIS WILL BE UPDATED WITH A BETTER SOLUTION.
Here is not my code.
D - Dr. B - Tree II
Let ways(L, K) = number of ways to make a string of length L with exactly K mirror couples, Z is the number of different characters allowed being 10 in this case (all the digits from 0 to 9).If L is odd that means we should place the middle character of the string and then solve the problem for a string of even length, we can place this in Z ways and only if K > 0 because always this character will be a mirror couple, example, X is the character to place.
...X...
If L is even we can split the string in two parts of length L/2 (left and right) and place exactly two characters, one in left part and one in the right one, in this way we can decide to place a mirror couple or not, for example.
X....X
In this case we are setting a mirror couple and there are Z ways to do it.
X....Y
in this case we are setting two character being not a mirror couple, there are Z*(Z-1) ways to do it, you can place every character at X and every character but X for Y.
Here is a pseudocode:
ways(L, K)
if (L == 0 && K == 0) ret 1
if (L < 0 || K < 0 ) ret 0
if (L is odd) ret Z*ways(L-1, K-1)
ret Z*ways(L-2, K-1) + Z*(Z-1)*ways(L-2, K)
The complexity is exponential but you can memoize the results using Dynamic Programming to get a complexity of O(L*K).
Don't forget to do all operation with modulo.
Here is my code.
E - Even Number of Divisors
We are given an interval [L, R] and we have to count how many numbers K in that interval have even number of divisors, for example, the next list contains the required information for the values in the interval [1, 6]:K = 1 2 3 4 5 6
D = 1 2 2 3 2 4
C = n y y n y y
K is the value we want to know if should be counted.
D is the number of divisors of K.
C is "y" if have and even number of divisors (should be counted).
This is not an obvious task but we can invert the problem.
Let f(L, R) = the number of values K in the interval [L, R] where the number of divisors of K is odd.
If we can compute f efficiently, the answer would be (R - L + 1) - f(L, R), (R - L + 1) is the length of the interval.
How to compute this? The trick is that a number K has odd number of divisors if K is a perfect square (see this to believe), there is at most sqrt(N) perfect squares in the interval [1, N], so we can pre compute all perfect squares in this interval (where N is the maximum possible value) and store it in an array.
For answer a query f(L, R) = firstLower(R) - firstHigher(L) + 1
firstLower(N) = the index of the last element in the array strictly <= N
firstHigher(N) = the index of the first element in the array strictly >= N
Both can be computed using binary search.
The complexity is O(N*log(N) ) where N = sqrt(max possible number).
Here is my code.
F - Fast Traveler Game
This is a simulation problem, do what is required and you will get accepted your solution.Here is my code.
G - Fear of the Dark
This is not an easy problem, you need to know about several non-trivial data structures:Once you about all of them the problem may seem trivial but code it without mistakes is not easy.
I hope to have the time to explain it better later.
First you need to solve FLIPCOIN in order to prove you understand how to write the required Segment Tree for this problem.
Complexity is O(N * log(N) + Q * log(N) * log(N) ) where N is the number of nodes and Q the number of queries.
Here is my long and modulated code.
H - How Many Numbers
You are given two variables, O and E, you have to count how many distinct numbers can be formed using exactly O odd digits and E even digits, including negative numbers, O + E <= 18.This is an easy problem solvable with backtracking because the constrains are small.
Is obvious that we can count only the positive numbers and multiply the result by 2.
There are two especial cases to handle here.
1.- The number can't have leading zeros.
2.- If O = 0 and E = 1 means that we need to count all even digits and the number of digits = 1, this means that we have to add 1 to the result for counting the zero, the result for this case is 9, 4 possible even digits positive and negative + the zero.
Understanding the 2 above cases makes easy to design a solution.
Suppose you have a case where O = 1 and E = 1, X and Y are both digits, we need to place them.
XY
The two possibilities are that X is and even digit and Y is an odd digit or X is and Odd digit and Y an even.
The first case is to place an odd digit at X position and an even digit for Y.
There are 5 odd digits for X (1,3,5,7,9) and 5 even digits for the Y position (0,2,4,6,8), so the total is 5*5.
The second case is to place an odd digit at X position and an even for Y.
There are 4 options for X (2,4,6,8) because the number can't start with zero and 5 options for Y, so the result is 4*5.
The answer is 5*5 + 4*5 for positive numbers, so muliply it by 2 to get the required result.
Now we need write a function for the general case.
f(first, odds, evens)
if (odds == 0 && evens == 0) ret 1
ans = 0
if (odds != 0 ) ans += 5 * f(false, odds - 1, evens)
if (evens != 0) ans += 5 - (first ? 1 : 0) * f(false, odds, evens-1)
ret ans
This help us to find the answer for positive numbers, handle the case 1 0 outside this.
In this solution we are avoiding to create numbers with leading zeros but there is other way for do it, you can count all the numbers with leading zeros and subtract the numbers starting with zero, use what you prefer.
Be careful because the result doesn't fit in an Integer data type but a Long is enough.
The complexity is O(2^N) per case, where N = E+O
Here is my code.
I - List of Natural Numbers
We can notice that a number K will be added only in the K-th step, using this information we can generate using brute force how many times a number K is added to the list for some steps like 20 for example.This is the result for the first 15 values.
2, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8
There is no obvious pattern but we can use OEIS and paste this values as input, OEIS will try to find a sequence, fortunately there is a sequence =D.
The number of times a value K is in the final list is:
- 2 if K = 1
- phi(K) if K != 1
Complexity is O( sqrt(N) ) per case.
Here is my code.
No comments:
Post a Comment
Leave me a comment