### UpS0lver's blog

By UpS0lver, 8 years ago,

First don't miss this round will be hold after one day Time HERE
Second any one got Qualification mail Result ,Till now I didn't get it.
UPD: I got TCO'14 Algorithm Round 1B official results while Writing this post.

• +14

 » 8 years ago, # |   +8 I got the qualification mail result 6 days ago
•  » » 8 years ago, # ^ |   +5 Thanks , I login to gmail using my ymail "my main mail" so most of time I open ymail (yahoo) rather than gmail(google) and I register using gmail not ymail ,that's the reason that I thought they didn't send it. but I opened gmail and I found You have advanced mail which I didn't receive on ymail .Thanks for your reply
 » 8 years ago, # | ← Rev. 2 →   +49 That's bad idea to post such topics two days before the competition starts, because it won't be on the top helping everyone who possibly forgot about the contest.I even accidentally duplicated this notification few minutes ago. So let's make this topic up!
•  » » 8 years ago, # ^ |   -11 You are totally right :)
 » 8 years ago, # |   +39 It seems I can guess the author of the problem C. Am I right, Petr?
•  » » 8 years ago, # ^ |   +48 Yeah, I'm too predictable. Did you like it?
•  » » » 8 years ago, # ^ |   +16 At least for me it was "Hey, let's try some random statistics and calculate mu and sigma for both types"
•  » » » » 8 years ago, # ^ |   +9 Exactly the same.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +9 Yes, that's what I intended, so I guess I'm happy at least :)
•  » » 8 years ago, # ^ |   +12 :O How did you know??
•  » » » 8 years ago, # ^ |   -16 I said him
 » 8 years ago, # | ← Rev. 2 →   0 What is the approach to solve C?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 const string res[] = {"BAD", "GOOD"}; void solve(){ int n; scanf("%d",&n); vector p(n); for (int i = 0; i < n; i++){ scanf("%d",&p[i]); } int cnt = 0; for (int i = 0; i < n; i++) cnt += p[i] < i; bool ok = cnt >= 485; printf("%s\n", res[ok].c_str()); } Error is about 6% in both sides. I don't know how to think about it. Just try different ideas, and check. This was third or fourth.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +4 You can think about this by plotting probabilities for a small n, say 7:You can clearly see that the probabilities are heavily biased towards points lower than main diagonal.
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   0 A plot created by running the Bad permutation generator 1,000,000 times.http://postimg.org/image/43ja8vtwf/X: Value, Y: Position
•  » » 8 years ago, # ^ |   0 I guessed BAD if atleast 55% of positions satisfies a[i]>i.
•  » » 8 years ago, # ^ |   +6 I've computed the following sum for each permutation: VI inv = get_inv(perm); long double sum = 0.0; rept(i, L(perm)) { sum += pow((long double)abs(i - inv[i]), 1.5) * (i + 1); } Then I sorted all 120 permutations by the value of sum and claimed that the first 60 of them are BAD and the rest of them are GOOD. This approach was guessing 109 out of 120 permutations in 12% of test cases on my local computer. In the first 3 tries I've submitted during the competition I mixed up GOOD and BAD and I've got AC in the fourth one, which means I was very lucky :)
•  » » 8 years ago, # ^ |   +13 Another version (I got AC only after the end): //precalc int IT = 1000 * 1000; forn (it, IT) { forn (i, n) { p[i] = i; } forn (i, n) { int r = rand() % (n - i) + i; swap(p[i], p[r]); } forn (i, n) { prGood[p[i]][i] += 1.0 / IT; } forn (i, n) { p[i] = i; } forn (i, n) { int r = rand() % n; swap(p[i], p[r]); } forn (i, n) { prBad[p[i]][i] += 1.0 / IT; } } //for each test case ld good = 1.0; ld bad = 1.0; forn (i, n) { good *= prGood[a[i]][i]; bad *= prBad[a[i]][i]; } if (good > bad) { cout << "GOOD" << endl; } else { cout << "BAD" << endl; } 
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +5 Same solution, but prBad calculated with DP (prGood[i][j] == 1/n). Local run shows >96% probability of guessing single testcase (>99.7% probability of guessing 109 out of 120).
•  » » » » 8 years ago, # ^ |   +13 Can you explain how to calculate prBad with DP?
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 It's not DP, it's just running 1M iterations of the algorithm and noting down the final position of each elementEDIT What was I thinking, ignore my comment :)
•  » » » » » 8 years ago, # ^ |   0 dp[i][j][k] = Probability that i ends up in position j after k swaps When calculating dp[i][j][k], you will swap the position k-1 with someone.if k-1 == j: dp[i][j][k] = 1/N (you have to choose the exact position i is in to swap with j)if k-1 != j: dp[i][j][k] = dp[i][j][k-1] * (1-1/N) + dp[i][k-1][k-1] * 1/N (either i was already in position j, and not swapped, or i was in position k-1 and got swapped to position j). As you only need dp[x][y][k-1] to calculate dp[i][j][k], you can do it in O(n²) memory.
•  » » 8 years ago, # ^ |   0 (in practice) I tried running the bad algorithm many times and computing the probabilities p[i][j] of π[i] being j. For a given permutation π, I computed the product of p[i][π[i]] and said that if it's  > k, then the answer's BAD.I made my own inputs using the 2 algorithms, sorted the computed products for all permutations of each input, looked at the numbers, and said that k = 1. First submit AC.
 » 8 years ago, # |   +1 Can someone explain their solution to problem A?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +6 Try matching the first outlet with each device. There are only N different configurations of switches worth looking at.
•  » » » 8 years ago, # ^ |   0 Thanks a lot. MikeMirzayanov's solution was easy to read and I got to learn that we can check equality of two C++ sets. Doing that, reduces some complexity in implementation. Thanks Mike!
•  » » » » 8 years ago, # ^ |   0 What is the time complexity of comparing two stl sets?
•  » » » 8 years ago, # ^ |   +18 I spent over 1.5 hours on this problem. Thought of everything, matching, dp, bitmasking, etc, but I couldn't solve it. When I saw this solution, I was like
•  » » » » 8 years ago, # ^ | ← Rev. 4 →   +13 Exact same thing for me. Fortunately it struck me at about 2:15 into the contest.There's something about this task that makes one think it's really hard :D A friend of mine wrote me in Facebook that he used bipartite matching to solve the set equality part :P
•  » » » 8 years ago, # ^ |   +3 I did the same :D :D for large input but in small input I did O(2^N)
 » 8 years ago, # |   0 What is the complexity of checking equality of two set containers in C++?
•  » » 8 years ago, # ^ |   0 Linear in the size of the container.
 » 8 years ago, # |   0 Can someone explain how to solve problem B? Thank in advance!
•  » » 8 years ago, # ^ |   +8 Assume the tree is rooted and the root is r. Also suppose that the tree is now directed with respect to the root. Now you can calculate dp[r] which represents the minimum removal of nodes to make the subtree rooted at r a full binary tree.
 » 8 years ago, # |   0 I tried to calculate the probability of a[i]
•  » » 8 years ago, # ^ |   0 Can you explain the formula?
•  » » » 8 years ago, # ^ |   0 I'll try.the probability that k is displaced from a[k] in the first k iterations of the algorithm is P(E1) = 1/n + ((n-1)/n)(1/n) + (((n-1)/n)^2)(1/n) + ...this is a GP and its sum will be P(E1) = 1-(0.999^k).The probability that it stays at the kth position(E2) is P(E2) = 0.999^k.Now in the kth iteration, assuming E2 E3 = it is swapped with arr[i] , i=kFor E4 now k will remain in arr[k,k+1,...n-1] , so this is not required.P(E2 and E3) = (0.999^k)*(k/n)Now assuming E1 E5 = k does not get swapped with arr[k].P(E1 and E5) = (1-(0.999^k))*((n-1)/n)E6 = k is currently in arr[0,1,2...k-1] after kth iteration (total k+1 iterations).P(E6) = (1-(0.999^k))*((n-1)/n) + (0.999^k)*(k/n)Now the probability that it does not get selected in the further iterations isP = P(E6)*(((n-1)/n)^(n-k-1))P = (1-(0.999^k))*(0.999^(n-k)) + ((0.999^(n-1))*(k/n))P = 0.999^(n-k) — 0.999^n + ((0.999^(n-1))*(k/n))What do you think?