### back_slash's blog

By back_slash, history, 9 months ago, ,

I am writing this blog mainly for 2 reasons. One is to discuss the problems. I want to know what is the logic behind C Large. And also if we can get a count of how many people got full points in the round.

•
• +25
•

 » 9 months ago, # |   +24 HintMatrix Exponentiation hinttry to find probabilities of starting at each vertex after some x rounds. And now with small trick(not hard) to take sum during exponentiation it is done.I leave tiny details for you to try out.
•  » » 9 months ago, # ^ |   0 Hint for B please ?
•  » » » 9 months ago, # ^ |   0 It's Greedy. First sort the given array. Then check if you can dance. If you can't dance, check if you can recruit. From the available teams, for dancing, dance with the team which has least energy. And for recruiting, recruit the team which has highest energy. Main logic sort(a.begin(), a.end()); int res = 0; int gres = 0; while(a.size()){ if(e <= a[0]){ if(res){ --res; e += a.back(); a.erase(--a.end()); } else break; } else{ ++res; e -= a[0]; gres = max(gres, res); a.erase(a.begin()); } } 
•  » » » 9 months ago, # ^ |   +6 The following observations were important: You can process the teams in any order (ie. decide to dance, recruit or truce) because if he current one isn't the one you want to process you can just make an excuse Recruiting is most beneficial when done against highest energy teams Dancing is most beneficial when done against lowest energy teams
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Can you elaborate a bit more please(for C large) ?
 » 9 months ago, # |   +15 My solutionsProblem 1. AnsRecursion. It's true if the list is empty or when pivoting as described, one of the sublists is empty and the recursive call is true. def solve(N, A): if N == 0: return True j = (len(A) - 1) // 2 B, C, P = [], [], A[j] for i, x in enumerate(A): if i == j: continue (B if x <= P else C).append(x) if B and C: return False return solve(N-1, B or C) Problem 2. AnsBecause we can excuse or ignore teams, we can choose any subset of the teams in any order. Also, if we are to beat a team, we should beat the weakest one; and if we are to recruit a team, we should recruit the strongest one. Thus our strategy is going to take the form of: "Defeat teams until we can't, then recruit a team" and we will repeat this. def solve(E, N, A): A.sort() ans = honor = 0 while A: while A and E > A[0]: E -= A.pop(0) honor += 1 if honor == 0: break ans = max(ans, honor) if A: honor -= 1 E += A.pop() return ans Problem 3. AnsFirst, use Floyd's algorithm to find dist[i][j] (0 indexed). Now, notice that if you are not home, you are in every other location with equal probability. If you are at home (location 0) then the expected travel time to your destination is sum(dist[0]) / (N-1). If you are away (ie., not at home), then the expected travel time to your destination is sum(dist[1:]) / (N-1)^2. Also, we can figure out the transition function: if you are home with probability x, then on the next monster you are home with probability (1-x)/(N-1).To solve the problem for large, you need one extra fact. For the function f(x) = (1-x)/(N-1), getting within 1e-9 of the limit of the orbit lim_{i ->inf} f^i(1) = 1/N is done very quickly. Indeed, let's look at abs(x — f(x)) = abs(Nx — 1)/(N-1), suggesting f^i(1) -> 1/N. To prove it, abs(f(x) — f(f(x))) = abs(Nf(x) — 1)/(N-1) = abs(N(1-x) — (N-1))/(N-1)^2 = abs(Nx — 1)/(N-1)^2. So the differences are getting smaller by a factor of 1/(N-1) each time. def solve(N, M, P, A): dist = [[float('inf')] * N for _ in xrange(N)] for u, v, w in A: u -= 1; v -= 1 dist[u][v] = dist[v][u] = w dist[u][u] = dist[v][v] = 0 for k in xrange(N): for i in xrange(N): for j in xrange(N): d = dist[i][k] + dist[k][j] if dist[i][j] > d: dist[i][j] = d val_home = sum(dist[0]) / float(N - 1) val_away = sum(sum(row) for row in dist[1:]) / float((N-1)**2) ans = 0 home = 1.0 MAGIC = 200 for _ in xrange(min(MAGIC, P)): delta = val_home * home + val_away * (1.0 - home) ans += delta home = (1.0 - home) / float(N-1) return ans + delta * max(0, P - MAGIC) Problem 4. AnsStraightforward DP. _issq = lambda N: int(N**.5) ** 2 == N issq = map(_issq, range(10001)) memo = {0: 0} def solve(N): if N not in memo: ans = 4 for x in xrange(1, N+1): if issq[x]: ans = min(ans, 1 + solve(N-x)) memo[N] = ans return memo[N] map(solve, range(10000)) 
 » 9 months ago, # |   -27 For problem B, my solution is incorrect. Can some body help here?My code #include using namespace std; int energy, N; vector vec; int ans; int funcc(vector vv, int ind, int en){ if(ind == vv.size()) return 0; int x = vv[ind]; int ret = INT_MIN; //dance if(en - x > 0) ret = 1 + funcc(vv, ind + 1, en - x); //truce ret = max(ret, funcc(vv, ind + 1, en)); //recruit ret = max(ret, funcc(vv, ind+1, en + x) - 1); //delay if(ind < vec.size()){ vv.push_back(x); ret = max(ret, funcc(vv, ind + 1, en)); } return ret; } int main(){ freopen("B-small-attempt1.in","r",stdin); freopen("output_file_name.out","w",stdout); int tc; cin>>tc; for(int t = 1; t <= tc; t++){ cin>>energy>>N; vec.clear(); int x; for(int i=0; i>x; vec.push_back(x); } ans = 0; ans = funcc(vec, 0, energy); cout<<"Case #"<
 » 9 months ago, # |   +8 What is with the ranking? It shows my rank when I am logged in but not otherwise??