Lewin's blog

By Lewin, history, 20 months ago, , Hi! Topcoder SRM 730 will happen soon.

I'm the writer of this round. Hope to see you all participate! srm, Comments (27)
 » Reminder: The contest starts in 4 hours! Both SRM 730 and Humblefool Cup Qualifier's registeration has started! Note that registeration ends in 5 minutes before the contest. Don't miss!
 » There is some kind of 'reward' survey when I'm trying to register this round. I did not participated in SRM 722, 723, 724, 726 and not interested in 'a chance to be recognized by the Harvard-NASA Tournament Lab and Topcoder' (btw, what does 'recognized' here mean?), but the survey asked me to select one of three. What should I do?
•  » » idk, but all I got was a sticker :)
•  » » » +1 (also just got a sticker)
•  » » » » Do you mean on your topcoder profile or it was mailed to you?
•  » » » » » It was mailed to me.
 » 20 months ago, # | ← Rev. 4 →   Hope you enjoyed the round! Here is some example code and some short explanations. div2IntervalIntersectionsThis invovles some casework. To make things easier, let's assume that x1 <= x2 to reduce the number of cases we need to consider. See the example code for details codeclass IntervalIntersections(): def minLength(self,x1,y1,x2,y2): return max(0, (x2 - y1) if x1 <= x2 else (x1 - y2)) ExpectedMinimumPowerDiv2This can be solved with dp or some combinatorics. For the combinatorics approach, fix the minimum as k. Then, the number of ways to choose the remaining numbers is (n-k choose x-1) Thus, the desired value is sum of k from 1 to n of (n-k choose x-1) * 2^k / (n choose x) code#include using namespace std; static double choose(int n, int r) { double ans = 1.0; for (int i = 1; i <= r; i++) { ans *= (n + 1 - i); ans /= i; } return ans; } class ExpectedMinimumPowerDiv2 { public: double findExp(int n, int x) { double ans = 0.0; for (int i = 1; i <= n + 1 - x; i++) ans += (1LL << i) * choose(n - i, x - 1); ans /= choose(n, x); return ans; } }; StonesOnATreeDiv2We use dp to solve this. Let dp[i] be the minimum max weight of stones we see to get a stone in node i.dp[leaf] is easy to compute, as it is just the weight of the leaves.dp[i] depends on the order that we choose to put stones on the children. Since weights are non-decreasing, it is always optimal to "pull" a stone all the way to a child and leave it there before moving on to processing a different child.For each child, we have two values dp[c], the weight needed to get a stone on child c, and w[c], the weight that the child will need to hold while processing other subtrees.If we order the children from as p_1, p_2, ..., p_n, we incur a cost of max(dp[p_1], w[p_1] + dp[p_2], w[p_1] + w[p_2] + dp[p_3], ..., w[p_1] + w[p_2] + ... + w[p_(n-1)] + dp[p_n]), and we want to minimize this value over all permutations.By an exchange argument, you can show that sorting the children by w[c] — dp[c] gives an optimal permutation. codeimport java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.stream.Stream; public class StonesOnATreeDiv2 { public int minStones(int[] p, int[] w) { int n = w.length; ArrayList[] child = Stream.generate(ArrayList::new).limit(n).toArray(ArrayList[]::new); for (int i = 1; i < n; i++) { child[p[i-1]].add(i); } int[] min = new int[n]; for (int i = n-1; i >= 0; i--) { int a1 = 0, a2 = 0; Collections.sort(child[i], Comparator.comparingLong(x -> w[x] - min[x])); for (int x : child[i]) { a2 = Math.max(a2, a1 + min[x]); a1 += w[x]; } min[i] = Math.max(a1 + w[i], a2); } return min; } } div1StonesOnATreeSee div2 hard for a harder version on a non-binary tree.For this version, we can try both orders for children. codeimport java.util.ArrayList; import java.util.stream.Stream; public class StonesOnATree { public int minStones(int[] p, int[] w) { int n = w.length; ArrayList[] child = Stream.generate(ArrayList::new).limit(n).toArray(ArrayList[]::new); for (int i = 1; i < n; i++) { child[p[i-1]].add(i); } int[] min = new int[n]; for (int i = n-1; i >= 0; i--) { if (child[i].size() == 0) { min[i] = w[i]; } else if (child[i].size() == 1) { int r1 = child[i].get(0); min[i] = Math.max(w[i] + w[r1], min[r1]); } else if (child[i].size() == 2) { int r1 = child[i].get(0), r2 = child[i].get(1); min[i] = Math.max(w[i] + w[r1] + w[r2], Math.min(Math.max(min[r1], w[r1] + min[r2]), Math.max(min[r2], w[r2] + min[r1]))); } } return min; } } SubgraphsThere are a lot of different solutions, but they probably all start similarly.Construct an independent set and a clique with k nodes. These are both necessary (and they can share at most one node in common, but given the constraints, you didn't need to share nodes).My solution is to connect the i-th node in the independent set with the 1,2,...,i-th node in the clique.Constructing the groups can be done in many different ways. In the solution I attached, I did some hill climbing to find all valid groups. codeimport java.util.Arrays; public class Subgraphs { public int count(long bs, int k) { int x = 0; for (int i = 0; i < k; i++) { for (int j = i+1; j < k; j++) { if (((bs>>i)&1) == 1 && ((bs>>j)&1) == 1) x++; } } for (int i = 0; i < k; i++) { for (int j = k; j <= k+i; j++) { if (((bs>>i)&1) == 1 && ((bs>>j)&1) == 1) x++; } } return x; } public String toString(long bs, int n) { String r = ""; for (int i = 0; i < n; i++) { if (((bs>>i)&1) == 1) r += 'Y'; else r += 'N'; } return r; } public String[] findGroups(int k) { int n = 2*k; String[] ans = new String[n+k*(k-1)/2+1]; boolean[][] conn = new boolean[n][n]; for (int i = 0; i < k; i++) { for (int j = i+1; j < k; j++) { conn[i][j] = conn[j][i] = true; } for (int j = k; j <= k+i; j++) { conn[i][j] = conn[j][i] = true; } } for (int i = 0; i < n; i++) { String r = ""; for (int j = 0; j < n; j++) { if (conn[i][j]) r += '1'; else r += '0'; } ans[i] = r; } long bs = (1L << k) - 1; for (int i = k*(k-1)/2; i >= 0; i--) { if (ans[i+n] != null) continue; int h1,h2; while ((h1 = count(bs, k)) != i) { if (ans[h1+n] == null) ans[h1+n] = toString(bs, n); int a = (int)(Math.random()*n); int b = (int)(Math.random()*n); if (((bs>>a)&1) == 1 && ((bs>>b)&1) == 0) { h2 = count(bs^(1L< Math.abs(h2-i)) { bs = bs^(1L< using namespace std; long long mod = 1000000000 + 7; long long power(long long x, long long e) { long long ret = 1; while(e > 0) { if(e % 2 == 1) ret = (ret * x) % mod; x = (x * x) % mod; e /= 2; } return ret; } long long inv(long long x) { return power(x, mod - 2); } long long f(int n, int x) { int d = n - x; long long ret = 0; long long t = power(2, d+1); ret += t; for(int i = 1; i <= d; i++) { t *= inv(2); t %= mod; t *= inv(i); t %= mod; t *= x + i - 1; t %= mod; ret += t; ret %= mod; } return ret; } class ExpectedMinimumPower { public: int findExp(int n, int x) { long long t = power(2, n+1); t -= f(n, n+1-x); t %= mod; t += mod; t %= mod; return t; } };
•  » » "By an exchange argument, you can show that sorting the children by w[p] — dp[p] gives an optimal permutation." -Div2HardCan you explain this?
•  » » » 19 months ago, # ^ | ← Rev. 2 →
•  » » Easier combinatoric interpretation:Let's look at all subsets of x or more elements and leave only x largest elements in each subset. Now each subset S of x elements appears exactly 2min(S) - 1 times.So the answer is 2·sumi = xnC(n, i), which is easy to count.
•  » » 20 months ago, # ^ | ← Rev. 3 →   I solved Div1 500pts in (probably) different way: Let's think about the following sub-problem: Sub-problemYou are given N and K (0 ≤ K ≤ C(N + 1, 2)). Find one subset of (1, 2, 3, 4, ..., N) so that the sum will be exactly K. This problem can be solved in greedy way, that does following operation in order of i = N, N - 1, N - 2, ..., 1. The operation is "If K ≥ i, select i from set and decrease K by i. So, this problem can solve in O(N) time complexity.Going back to the main problem, graph has edge (i, j) if and only if i ≠ j and i + j < n. And the "selection" is, you can restrict to selecting "either vertex k or vertex 2n - k - 1 (not both)". Let this vertex, "level-k" vertex. Suppose that you select from level-n - 1, n - 2, n - 3, ..., 0 vertex in preceding order. If you select k in level-k, the number of edges on subgraph increases by n - k - 1, and if you select n - k - 1 the number of edges doesn't change. So, you can choose arbitrary subset of level 1, 2, 3, 4, ..., n, and the "increase value" of number of edges is (n - 1, n - 2, n - 3, ..., 0). This is equivalent to the sub-problem, which N = n - 1, K = x. So this problem can be solved in O(N3), which is equivalent to output size, and the implementation is pretty easy (practically 17 lines): Code#include #include using namespace std; class Subgraphs { public: vector findGroups(int x) { vector g(2 * x, string(2 * x, '0')); for (int i = 0; i < 2 * x; i++) { for (int j = 0; j < 2 * x; j++) { if (i + j < 2 * x && i != j) g[i][j] = '1'; } } vector res(x * (x - 1) / 2 + 1, string(2 * x, 'N')); for (int i = 0; i <= x * (x - 1) / 2; i++) { int val = i; for (int j = x - 1; j >= 0; j--) { if (val >= j) val -= j, res[i][x - j - 1] = 'Y'; else res[i][x + j] = 'Y'; } } vector ret = g; ret.insert(ret.end(), res.begin(), res.end()); return ret; } };
•  » » Another solution for div1 1000:f(n, x) is of the form 2n + 1 - Px(n), where Px(n) is some polynomial of degree x - 1, and Px(i) = 2i + 1 for all i < x.Proof:f(n, 1) = 2n + 1 - 2 for x > 1. (Just iterate on the maximum).
•  » » » 20 months ago, # ^ | ← Rev. 3 →   Yes! In this way we can solve for any power. I see we need compute a sum like: . And I guess that sum is a polynomial of degree x - 1 plus .
•  » » » » Do you have any proof for this?
•  » » » » » Since you guess out it, it is not hard to proof. Just do an induction from recurence formula: f(x, n) = f(x, n - 1) + f(x - 1, n - 1).
•  » » » » » » down vote ^____^
•  » » » » » It is clearly true for x = 1. We can now use induction. For x > 1, If it is true for x - 1, = (by rearranging some terms, and using is a polynomial of degree k + 1)
•  » » Did you expect d1 hard to be hard? (It wasn't even 900).
•  » » » I didn't expect it to be hard, but it seems we forgot to adjust points accordingly (I had prepared this round a few weeks ago, so it wasn't at the top of my mind until a few days ago).The testers didn't find a combinatoric interpretation at first (and one solved it for general powers first). I believe it can be easy to miss, but it also seems obvious after the fact. I briefly considered changing the power so it's not 2 which would have made it significantly harder, but decided it's better to let some of these easier solutions pass also rather than get almost no solves.
•  » » 20 months ago, # ^ | ← Rev. 2 →   Div2Hard:I guess it's just a typo, but in the problem statement it says that weights are "non-decreasing". Or it depends on which direction you look at the tree — bottom-up or vice versa :)Update: another typo seems to be dp[c], looks like you meant dp[i] instead.
•  » » » Fixed
 » 20 months ago, # | ← Rev. 2 →   A question unrelated to this round in particular -- why do the lower numbered rooms have more red participants than higher numbered rooms? Is it intentional and "fair"? I'd expect that hacking in a room with 50% red is much more difficult, as higher percentage of submissions is expected to be correct, and there are better and faster hackers.
•  » » As I understand first coders are distributed randomly and then rooms are ordered based on strength
•  » » When I was the admin, there were a few algorithms for room assignment. In SRM it was named "Random Seeding", in TCO it was named "Ultra Random Seeding", though I don't know details.
•  » » » It used to be the case that they only used actual uniform random for rounds that had monetary prizes (TCO, sponsored SRMs). For regular SRMs they used some biased algorithm that made it more likely for higher-rated coders to end up in lower-numbered rooms. This was intentional.Given that nowadays TC doesn't really care about their Algorithm track, I'm quite sure this is still the case, and that these are the two seeding algorithms [h]rng_58[/h] mentions.(I don't know why they decided to use the biased seeding algorithm. It's not completely fair, but at the same time the bias isn't large enough, so the contestants never complained too loudly about it, I guess.)
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   majk is complaining. I was also complaining when I found myself in the room 1, with Petr and a bunch of reds. The rest was yellows and 2 blues.However it is also not completely true, that this is such a disadvantage. If the tasks are difficult, quite often lower rated coders do not submit anything, whilst higher rated coders are more likely to submit a solution. Because the task is tricky/difficult, there is also a higher chance for them to make a mistake, so I started to wonder, whether my complains were reasonable.
•  » » » » » In SRM 729 it was quite fortunate situation for uwi, who managed to win the SRM because of lot of wrong solutions in my room and his excellent speed and solid preparation in the coding phase (and my inability to stop thinking about the hard task and concentrate on the challenges :-)). The complaints are not unfounded, though. However, I doubt that they will change anything, since I also have the feeling that the algorithm track lacks a bit of love from TC staff. Case in point, the time in the web arena is still off by 4 hours.