I figured I should post something about this SRM. I've been very busy these weeks because the semester is ending and I tried to win a t-shirt in the Marathon AND I am not assigned more editorials. But there we go.
Div1 250 - The one with the bit operations
I was just returning to the topcoder mindset after working a lot on an assignment. At the start of the match I felt like running in 10% of steam capacity. I truly felt dumb. I knew what to do to solve the problem, but I was having issues translating it to code.
Kleofas tail : If x is even, x = x / 2. If x is odd then x = x - 1. Repeat and repeat until you will eventually have a sequence of tons of 0s. Given K, A and B, return the number of numbers between A and B, inclusive such that the Kleofas pairs starting from number x eventually include K.
This is heavily related to the binary representation of a number. Let us say the binary representation of x is 10010010101. The sequence goes like this: 10010010101, 10010010100, 1001001010, 100100101, 100100100, 10010010, 1001001, 1001000, 100100, 10010, 1001, 100, 10, 1, 0, 0, 0, ... - If the right most bit is 1, it becomes 0 , else it gets removed. This means that there are two ways for a number x to eventually become K:
- The binary representation of K is a prefix of the binary representation of x.
- If K is even, the binary representation of (K+1) is a prefix of the binary representation of x.
Assuming that you have a function that counts the number of times a given number K' appears as a prefix in numbers between A and B, then you have an instant solution. But we can simplify it a bit more: Let f(A, K) return the number of elements X between 0 and A, inclusive such that K appears in their Kleofas tail:
- f( A , K) = 0 for (A < K).
- f( A, K = 0) = A+1 (All numbers between 0 and A, eventually reach 0.
- f(A, 2*K1) = f(A, 2*K1+1) + (number of times 2*K1 appears as a prefix). (In other words, K = 2*K1, which means K is even).
- f(A, 2*K2 + 1) = (number of times 2*K2+1 appears as a prefix). (In other words, K = 2*K2 + 1, which means K is odd).
We just need to calculate prefixes(A, K): The number of times K is a prefix of X for every X between 0 and A, inclusive.
The problem is how to do that... This is the moment at which my brain froze. At first I tried to do it arithmetically, but I could not. (It is possible, but slightly tricky). Eventually, I recognized that I was not at full brain capacity and that the best I could do would be a bullet (and idiot)-proof dynamic programming solution for the simple counting problem.
Now that I am in my senses, here is a quick approach. Imagine there are i bits after the K part in x. For example, if K=101 then x = 101?????. The minimum x that follows that condition is: 10100000 and the maximum x is : 10111111. Both values can be calculate easily given i. (The minimum is K multiplied by 2i, the maximum is the same plus (2i-1) ). Then the true maximum is min( K*2i + 2i-1, A). There are (true_maximum - minimum + 1) values of x. Then you can just iterate through all values of i until the minimum is larger than A.
// Number of times K appears as a binary prefix of numbers between
// 0 and A, inclusive.
long prefixes(long K, long A)
{
long res = 0;
long mx = 0;
while (true) {
long lo = K;
long hi = Math.min(K + mx, A);
res += hi - lo + 1;
if (K > A/2) {
break;
}
K *= 2;
mx = mx * 2 + 1;
}
return res;
}
// Amount of times a number between 0 and A, inclusive contains
// K in the Kleofas tail :
long countGoodSequences(long K, long A)
{
if (A < K) {
return 0;
}
if (K==0) {
return A+1;
}
long res = 0;
if (K % 2 == 0) {
res += prefixes(K+1, A);
}
res += prefixes(K, A);
return res;
}
public long countGoodSequences(long K, long A, long B)
{
// This allows us to reduce the number of arguments.
return countGoodSequences(K, B) - countGoodSequences(K, A-1);
}
Mixed feelings about this problem. Although it was good, we have had too many of these (tricky binary operations) division 1 250s.
Div1 500: the one with digits
I was better now. I knew that if I wanted to save my rating I had to solve this problem. Luckily it turned out to be a typical digit dynamic programming. I am not sure why, but I find these problems very easy. I still needed a lot of time though, because when I coded it my brain was still not functioning and I left as many bugs as you would ever find.
Given N (Between 1 and 99...9 (15 times), inclusive) , digit1, count1 , digit2, count2. (count1 + count2 <= 15). Return the minimum number >= N that has digit1 at least count1 times and digit2 at least count2 times.
Thanks to the notes, we know that the result always fits a signed 64 bits integer. This means 18 digits. We will say that the maximum number has 20 digits at most. The idea is to use a recurrence relation. f(count1, count2, p, eq, zero): We have already decided the p first digits. eq means that the number is currently equal to N. zero means that the number is currently equal to 0. count1 is the minimum number of times we need to add digit1, and count2 works the same way. For convenience, we will say that numbers are strings, strings of digits. Once we get the final result we can convert it to long long. f() will actually find a string of MAX digits, it will have leading zeros when the result needs less than MAX digits.
Let us say p==MAX, this means that we have already decided all digits, what is the minimum remaining number? Well, if count1 or count2 is positive, then there is no way to fulfill this requirement anymore. Thus there is no result. We will mark instances with no result as infinite. If count1 and count2 are 0, then the result is the empty string - do not modify any new bit.
For another p, then we can try all digits from 0 to 9. Well, actually, we sometimes cannot. If eq==1, it means that all of the previous digits were equal to N, this means that the digit at first position cant be smaller than the digit at the same position in N - Because that would make our result smaller than N. If eq==0, then we can use any digit from 0 to 9. After picking a digit, the values of count1, count2, eq and zero will change according to it and we will have a new instance of the recurrence. (Just note that when zero==1, we cannot count digit 0 as part of the digits to reduce from the count1 requirement, because it is a leading 0 and will not actually appear in the number. The same happens with digit2)
And that's it:)
const int MAX = 20;
struct FavouriteDigits
{
string dp[MAX+1][MAX+1][MAX+1][2][2];
bool vis[MAX+1][MAX+1][MAX+1][2][2];
string R;
string rec(int p, char digit1, int count1, char digit2, int count2, int eq, int zero)
{
if (! vis[p][count1][count2][eq][zero] ) {
vis[p][count1][count2][eq][zero] = true;
string & res = dp[p][count1][count2][eq][zero] ;
// We mark infinite as a string that begins with :
if (p == MAX) {
// base case
if ( count1 == 0 && count2 == 0) {
res = "";
} else {
res = ":"; // no luck
}
} else {
res = string(MAX - p, ':');
for (char ch = (eq?R[p]:'0') ; ch <= '9'; ch++) {
int ncount1 = count1, ncount2 = count2;
int nzero = zero && (ch == '0'); //once we use a digit different to 0
// the number stops being equal to 0.
// update count1, note that if digit1 is 0 and zero==1,
// it does not count (leading zero)
if (ch == digit1 && (ch!='0' || !zero) ) {
ncount1 = std::max(ncount1-1, 0);
}
// update count2, similar story
if ( (ch == digit2) && (ch!='0' || !zero) ) {
ncount2 = std::max(ncount2-1, 0);
}
int neq = ( eq && (ch==R[p]) ); //once a character differs from N
//the new number is larger.
string x = rec(p+1, digit1, ncount1, digit2, ncount2, neq, nzero);
// x begins with :, there is no result in that direction...
if (x.length() > 0 && x[0] == ':') {
continue;
}
//concatenate, we now have a good result remember the minimum.
res = std::min(res, string(1,ch)+x);
}
}
}
return dp[p][count1][count2][eq][zero];
}
long findNext(long N, int digit1, int count1, int digit2, int count2)
{
// convert N to a string, with the appropriate leading zeros.
{ ostringstream st; st << N; this->N = st.str(); };
this->N = string(MAX - R.length(), '0') + this->N;
memset(vis, 0 ,sizeof(vis));
string s = rec(0, digit1+'0', count1, digit2+'0', count2, 1, 1);
// convert s to from string to long:
istringstream st(s);
long x;
st >> x;
return x;
}
};
#undef long
This problem was better. But it is odd to have two problems in the same match and same division that can be solved with the same approach. (I used a similar digit dp to solve 250).
Challenge phase, etc.
The example cases for div1 500 seemed quite strong. I knew div1 250 was tricky, but I also knew that I would likely mistaken if I tried to challenge. I preferred to go to lunch during the challenge phase. Returned, and after all the hours it takes results to arrive lately, I noticed I passed everything and somehow even my slow submissions were enough for top 100. I cannot believe I managed to increase my rating and even reach (again) the area that is close to 2200. I was just lucky though that div1 500 was my style of problem.
As far as the problem set goes. It is not misof's best problem set. But that is only because he set a great standard in previous problem sets. It was a good match, nevertheless. But we writers need to avoid those bit operations in div1 250 for a while.
No comments :
Post a Comment