First Problem:
250 - AliceGame
Solution:
The problem is very mathematical in a sense. First observation: there will always be one winner and one loser in a round. So if we sum up the scores obtained by the two players, we will get the total number of scores accumulated from round 0 to round N consecutively. Hence if the sum of the players score is in the form of \( 2 \sum_{i=0}^{N} {i} - N = N^2 \), for some integer N, then the players have played N rounds, otherwise it is impossible to obtain those scores.
Now we know that the two players played N rounds. How to find the minimum rounds needed for the first player to obtain score \(x\)? Here comes the second observation: If first player only need \(k\) rounds to obtain exactly score \(x\), then since each round he wins \(2i - 1\), in k rounds he wins \(2S-k = x\) scores, in other words \(x+k\) must be divisible by two, and \(S = (x+k)/2\). It remains to find an efficient way to decide whether there exist such choices of rounds such that the sum of indexes of the round is exactly \(S\). Here we employ a greedy idea: suppose first player wins all games in round 1 to round k consecutively, then the sum of the indexes of the round he won is \(K = k(k+1)/2\). If \(K\) exactly equal to \(S\), then first player indeed won those games. Otherwise we have two cases:
1. \(K > S\): then there is no way for first player to win in k rounds since the minimum possible K is already bigger than S.
2. \(K < S\): let \(R = S-K\). Then we try to distribute R equally by incrementing the k indexes. If the largest index is still less than or equal to \(N\), then first player can win in k rounds.
Our job is to find lowest k based on the above cases.
Implementation:
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; class AliceGame { public: bool check(int n, int lim, long long val){ if(n > lim) return false; long long sum = 1LL * n * (n+1) / 2LL; if(sum > val) return false; long long rem = val - sum; if(rem == 0) return true; long long eq = rem/(long long) n; if(rem % ((long long) n) != 0) ++eq; if(eq + n > (long long) lim) return false; return true; } long long findMinimumValue(long long x, long long y){ //special case: x or y = 0; int hi=2000000, lo=0, mid; long long tmp; bool found = false; while(lo<=hi){ mid = (lo+hi)/2; tmp = 1LL * mid * mid; if(tmp == (x+y)){ lo = mid; found = true; break; } else if(tmp < x+y){ lo = mid+1; } else { hi = mid-1; } } if(!found) return -1; if(x == 0LL) return 0; for(int i=1;i<=lo;++i){ if((x+i)%2LL != 0) continue; tmp = (x+i)/2LL; if(check(i, lo, tmp)){ return i; } } return -1; } };
Second Problem:
500 - BoardFolding
Solution:
This problem can be solved using a DP approach and a DFS like strategy.
Firstly note that you can consider the horizontal foldings separately from vertical foldings (yeah!). This reduces the problem into a one dimensional array in a sense. Here we will discuss about finding all sub-rectangles producible from combinations of horizontal foldings. The way to do it for vertical foldings is exactly the same.
Firstly we need to store a table symmetrical[i][len], which indicate that paper[i-len+1] has exactly the same content as paper[i+len] (in other words, the line below i-th row is treated as the line of symmetry, and paper[i-len+1] and paper[i+len] are both rows which are len rows apart from the line of symmetry). For every \(i\), starting from len = 1, 2, ..., we check for symmetry of the corresponding rows in \(O(N)\), and once we encounter a value for len that causes asymmetry, we terminate the iteration for that value of \(i\). Overall we will spend \(O(N^3)\) to fill in symmetrical[i][len].
Why do we need this information? Because we want to be able to check whether we can fold subrectangle [i...j] at line of symmetry k in \(O(1)\). Starting from i = 0, j = N-1, we recursively consider paper[i..j]: we check for every possible line of symmetry k whether paper[i..k] and paper[k+1..j]. If k is a valid line of symmetry, then we recursively consider paper[i..k] or paper[k+1..j] depending on which is the major fold. For each pair (i,j) that we visited, we mark vis[i][j] to one, and 0 otherwise. After completing the recursion, calculate the number of visited pair (i,j), which is exactly the total number of subrectangles produced by all possible combination of horizontal folding. Running time is overall \(O(N^3)\)
Do the same thing to vertical foldings. To find the number of subrectangles possible overall, multiply the number of subrectangles obtained in each foldings.
Implementation:
#include <iostream> #include <algorithm> #include <cstdio> #include <string> #include <vector> using namespace std; int v[2][255][255]; int dp[2][255][255]; class BoardFolding{ public: int N; int M; int b[255][255]; void folder(int state){ int r, c; if(state == 0){ r = N; c = M; } else { r = M; c = N; } for(int i=0;i<r;++i){ for(int j=0;j<r;++j){ v[state][i][j] = 0; } } for(int i=0;i<r;++i){ for(int j=1;j<=min(i+1,r-i-1);++j){ int s = i-j+1; int t = i+j; bool ok = true; for(int k=0;k<c;++k){ if(state == 0) if(b[s][k] != b[t][k]) ok = false; if(state == 1) if(b[k][s] != b[k][t]) ok = false; if(!ok) break; } if(ok) v[state][i][j] = 1; else break; } } } void compute(int state, int i, int j){ if(dp[state][i][j] != -1) return; if(j-i == 0){ dp[state][i][j] = 1; return; } dp[state][i][j] = 1; for(int k=i;k<=j-1;++k){ int len_left = k-i+1; int len_right = j-k; if(len_left == len_right){ if(v[state][k][len_left]) { compute(state, i, k); compute(state, k+1, j); } } if(len_left < len_right){ if(v[state][k][len_left]) compute(state, k+1, j); } if(len_left > len_right){ if(v[state][k][len_right]) compute(state, i, k); } } } int getval(char c){ if('0' <= c && c <= '9'){ return c - '0'; } if('a' <= c && c <= 'z'){ return c - 'a' + 10; } if('A' <= c && c <= 'Z'){ return c - 'A' + 36; } if(c == '#') return 62; return 63; } int howMany(int N, int M, vector<string> cm){ this->N = N; this->M = M; for(int i=0;i<N;++i){ for(int j=0;j<M;++j){ b[i][j] = (getval(cm[i][j/6]) >> (j%6))%2; } } for(int i=0;i<N;++i){ for(int j=0;j<N;++j){ dp[0][i][j] = -1; } } for(int i=0;i<M;++i){ for(int j=0;j<M;++j){ dp[1][i][j] = -1; } } folder(0); folder(1); compute(0, 0, N-1); compute(1, 0, M-1); int x = 0, y = 0; for(int i=0;i<N;++i){ for(int j=i;j<N;++j){ if(dp[0][i][j] == 1) ++x; } } for(int i=0;i<M;++i){ for(int j=i;j<M;++j){ if(dp[1][i][j] == 1) ++y; } } return x*y; } };
Last problem havent tried yet..
No comments:
Post a Comment