### cgy4ever's blog

By cgy4ever, history, 18 months ago, ,

Topcoder SRM 703

•
• +89
•

 » 18 months ago, # |   +46 Contest will start in 1 day. It is sponsored by Booz Allen Hamilton.Registration will start 4 hours prior to the start time, and will close 5 minutes before it.
 » 18 months ago, # |   +13 Update: Registration is open now.
 » 18 months ago, # |   0 Your login request timed out !
 » 18 months ago, # |   0 I am not able to log in. It keeps redirecting me back to the homepage everytime I try.Anyone else facing a similar problem?
 » 18 months ago, # |   0 How to solve Div.1 Medium?
•  » » 18 months ago, # ^ |   +10 Do subsegment dp and always choose highest point first.
•  » » 18 months ago, # ^ |   +6 If we take the highest ship and fix the cannon for this ship, we will divide our plane to left and right part. So, DP state is [segment of cannons][set of ships]. I don't know why is it fast enough, I have O(n5) solution without maps: DP state [left][right][ship for left][ship for right] (the idea is the same, but for my solution complexity is obvious).
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 What do 'ship for left' and 'ship for right' mean in your DP state? Are them the two pointers of a ship subsegment? And do you sort the ships by x then y? If so, after separating the plane in two parts will we have a guarantee that the subsegment is indeed contiguous (let's say a non-vertical line separated the plane)?
•  » » » » 18 months ago, # ^ |   0 No. (left, ship for left) and (right, ship for right) are two segments which enclose current part of plane. Ships that are inside this part can be found in O(n) time (check for each ship in O(1)). Please read my code if you don't understand yet.
 » 18 months ago, # |   +1 How to solve Div2 Medium?
•  » » 18 months ago, # ^ |   0 Union-find. Note that if you can go from A to B, you can go from B to A. Just apply something like a sieve over the multiples of the numbers starting from k+1 and check if x and y are on the same subset. The complexity is O(n*logn).
•  » » » 18 months ago, # ^ |   0 More details please. Could you provide a source code?
•  » » » » 18 months ago, # ^ |   +2 int fa[1000005]; int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); } class GCDGraph { public: string possible(int n, int k, int x, int y) { for (int i = 1; i <= n; i++) { fa[i] = i; } for (int i = 1; i <= n; i++) { if (i <= k)continue; int h = getfa(i); for (int j = i; j <= n; j += i) { int g = getfa(j); fa[g] = h; } } if (getfa(x) == getfa(y)) { return "Possible"; } else { return "Impossible"; } } }; 
•  » » » » » 18 months ago, # ^ |   0 what do faget() and fa do?
•  » » » » » » 18 months ago, # ^ |   0 Just like Minimum Spanning Tree, using fa[] to record which point is connected with the point.If getfa(x)==getfa(y),they are connected.Sorry for my bad English...
•  » » » » » 18 months ago, # ^ | ← Rev. 2 →   0 Can u please explain : for (int j = i; j <= n; j += i) ? On what condition are we doing union on nodes?
•  » » » » » » 13 months ago, # ^ |   0 j is reachable from i as j is a multiple of i and gcd(i,j) > k. (i, j) are placed in the same connected component for this reason.
•  » » » » 18 months ago, # ^ |   +4 What I did was find all the vertices which can be visited from x, and find all the vertices which can be visited from y. Then if we can find a path from any vertex which can be visited from x(say a) to any vertex which can be visited from y(say b) we have a path from x to y. (The path is x-a-b-y).
•  » » » » » 18 months ago, # ^ |   -10 How to prove this?
 » 18 months ago, # | ← Rev. 2 →   +19 I used some heuristic in 1000 which doesn't rely on the constraint on the number of edges at all. I'm wondering if I just got lucky and there's a test that breaks it or if for some reason it works correctly if the number of edges is between n+1 and n+5.What I did was:0) Initialize hashes of all vertices with their degrees.1) Find a hash of each vertex by repeatedly doing the following (600 times, before the first iteration do it 5000 more times): for each vertex take hashes from previous step, sort them in ascending order, append its own previous hash and then map this vector to an integer from 0 to n-1 (distinct vectors get distinct integers).2) Pick any unused vertex V, let C be the number of vertices with the same hash. Multiply the answer by C, mark V as used and set its hash to be equal to N (i.e. make it unique).3) If there are no more unused vertices, return the answer, otherwise go to step (1) and use the current hashes as init values.This solution will work if the hashes are always computed correctly and I guess in the general case the hash computation part will break. I'm wondering if there exists a counterexample for the constraints from problem statement.
•  » » 18 months ago, # ^ |   +20 I have a few possibly hard cases in mind for your solution but I can't copy your code from the applet. Can you share it somewhere, please?
•  » » » 18 months ago, # ^ |   +10 Sure, here you go: http://pastebin.com/HM7aWK97
•  » » » » 18 months ago, # ^ |   +10 Ok, naturally this doesn't work on regular graphs which don't have automorphisms. On the Frucht graph your program outputs 12 while the answer is 1. It has 12 vertices and 18 edges though so this doesn't quite fit, but you get the kind of problems this solution can meet.
•  » » » » » 18 months ago, # ^ |   0 I see, thank you! Then I indeed got lucky that there were no test cases against such solutions (that try to hash every vertex).
•  » » » » 18 months ago, # ^ |   +40 An example suitable for the constraints (from this page) with 8 vertices and 12 edges: (0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 1), (3, 6), (6, 5), (5, 4), (7, 0), (7, 5), (7, 6). The answer is 4, but your solution should naturally output something divisible by 8 (in fact, it outputs 16).
•  » » » 18 months ago, # ^ |   +34 Have you solved the same (or similar) task before? And what is the idea behind your solution?
•  » » » » 18 months ago, # ^ |   +44 The same problem appeared in the last day contest on 2016 winter Petrozavodsk camp. The contest is curiously dubbed "Grand Prix of China" but I don't know the exact origin of the problem (probably snarknews can shed some light here).The idea is roughly as follows: first we can successively erase all leaves (degree-1 vertices), they will form several trees. Then we contract paths of degree-2 vertices. The resulting "minimized" graph will have vertices of degree 3 or more, hence it will contain at most 10 vertices (note that we never changed the |E| - |V| parameter). Now the answer is the product of: the number of automorphisms for each tree the number of ways to interchange isomorphic paths connecting the same pair of "minimized" graph vertices the number of automorphisms of the "minimized" graph that preserve the multiset of paths between each pair of vertices Equivalences can be checked with lots of hashing on trees, paths, sets of paths, etc. The last part (automorphisms of minimized graph) can be computed explicitly by trying all permutations.
•  » » » » » 18 months ago, # ^ |   0 Then it looks almost same with the reference solution, though your implementation is much simpler.By the way, does the problem of 'Petrozavodsk camp' open to public? I found http://camp.acm.petrsu.ru/2016w but looks you need a special account to access.
•  » » » » » » 18 months ago, # ^ |   0 I'm not sure if it's public. snarknews usually uploads the contests from the camp to http://opentrains.snarknews.info/~ejudge, but I can't find this particular contest there for some reason.
•  » » » » » » » 18 months ago, # ^ |   +20 "GP of China" is a contest hosted in ICPCCamp in China, and I am the author of almost all problems of that contest.
 » 18 months ago, # |   +11 How to solve Div2 1000 ?
•  » » 18 months ago, # ^ |   0 I haven't coded this but I guess this should work. We run a single DFS. For each vertex, we store the max 2 distances from that vertex to any leaf in its subtree, diameter of that subtree and the number of anti-podal pairs in that subtree.Suppose you are at vertex u. You have all the above values calculated for its children v1, v2,...vk. Let d be the max length of a path passing through u and in its subtree. Note that diameter_of_subtree[u] >= diameter_of_subtree[vi]. diameter[u] = max{d, max{diameter[vi]} }. So, diameter[u] > max{diameter[vi]} only when d > max{diameter[vi]}. You can use this to split the problem into cases. When diameter[u] == max{diameter[vi]}, then anti-podal[u] will be sum of anti-podal[vi], where diameter[vi]==diameter[u] and to this number add the number of anti-podal pairs whose path passes through u. When d > max{diameter[vi]}, then it is simpler. Just count the pairs of leaves in subtree of u, between which length of path is d.
•  » » » 18 months ago, # ^ |   0 Thanks
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 Your solution seems pretty complex. Also, in each sub-tree you can erase set of nodes — so d is not constant. You can erase nodes and make new leaves. You need to calculate max over all sub-trees. You need to take all cases which I can't deduce from your solution. I have posted my solution below which is pretty simpler.
•  » » 18 months ago, # ^ | ← Rev. 11 →   +16 Solution: http://ideone.com/1woxtj There are 2 cases — diameter of optimal subtree is odd or even. If even, then there exists a unique center. If odd, there exists an unique center edge. Try all possible combinations: Both cases can be done via simple dfs once for each node. Try each node V as center of subtree — count d[i][j] = number of nodes at distance j from ith child of V then if tot_j = sigma_j(d[i][j] for a fixed j) then ans = for all j, max(ans,sigma_over_all_children_i_considering_V_as_root(d[i][j]*(tot_j-d[i][j])/2); Try each edge(i,p[i]) as center of subtree — count d[0][j] and d[1][j] = number of nodes at distance j from each of two ends i and p[i] then ans = for all j, max(ans,d[0][j]*d[1][j]). Total Complexity: O(n^2) since j varies to max n and each edge is considered once over all V in first case and once in second case.