Блог пользователя cgy4ever

Автор cgy4ever, история, 7 лет назад, По-английски
  • Проголосовать: нравится
  • +89
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +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.

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Update: Registration is open now.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Your login request timed out !

»
7 лет назад, # |
  Проголосовать: нравится 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?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div.1 Medium?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Do subsegment dp and always choose highest point first.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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).

    • »
      »
      »
      7 лет назад, # ^ |
      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)?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 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.

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve Div2 Medium?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 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).

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      More details please. Could you provide a source code?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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";
        		}
        	}
        };
        
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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).

»
7 лет назад, # |
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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Sure, here you go: http://pastebin.com/HM7aWK97

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 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).

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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).

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +34 Проголосовать: не нравится

      Have you solved the same (or similar) task before? And what is the idea behind your solution?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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.

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

How to solve Div2 1000 ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks

    • »
      »
      »
      7 лет назад, # ^ |
      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.

  • »
    »
    7 лет назад, # ^ |
    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.

    1. 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);
    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.