fmota's blog

Grand Prix of Saratov
By fmota, history, 7 years ago, In English

How to solve C and D?
I think I have seen the problem J somewhere before

  • Vote: I like it
  • +28
  • Vote: I do not like it

Comments Comments (39)
| Write comment?
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve E and H? They are both pretty interesting problem.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +39 Vote: I do not like it

    H:

    First of all, we can ask n queries to find all leaves of the tree. To check whether a vertex is a leaf, we ask a query containing all n - 1 other vertices; if the answer is n - 1, the vertex we excluded from a query is a leaf.

    Then let's root our tree at some leaf. Let L(x) be the set of leaves in the subtree of vertex x. Since there are no vertices with degree 2, for any two vertices x and y L(x) ≠ L(y); furthermore, x is an ancestor of y iff . So if we obtain the information about L(x) for every vertex, then we can reconstruct the tree.

    For the root, L(root) is the set of all leaves. For every other leaf z, L(z) = {z}. So we need to find L(x) only for non-leaves. To check whether a leaf z is in a subtree of non-leaf vertex y, we may ask a query 3 root y z.

    So if the number of leaves is l, we have to ask (l - 1)(n - l) queries to find L(x) for all non-leaf vertices. This won't exceed 2450, and so we won't ask more than 2550 queries.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Cool! It is a really simple solution.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We had solution we the same queries but second part used different perspective.

      So, for each leaf we know the "path" to the root (only vertices, not their order). Now intersection of any two such "paths" is also path to the root from some vertex(their lca). And each vertex is lca of 2 leaves (because of no 2-degree vertices). So now we have list of "paths" for all vertices and need to reconstruct tree which may be done by simple dfs.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If the tree is a bamboo, answers for all queries of the first part of the algorithm should be n - 1, shouldn't it? If no, please explain why.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    E : In DAG every node can be reached by A and reach B, iff

    • A has no indegree
    • B has no outdegree
    • |indegree| >= 1 and |outdegree| >= 1 for all nodes not A, B

    Now you should select two disjoint edge set EA, EB such that

    • edges in EA have distinct endpoints
    • edges in EB have distinct startpoints

    This can be found by maximum matching in O(mn0.5)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Wow, flow for 1000000 edges, that's a new record I've ever seen :)

      By the way it can be solved without flow.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I don't understand why it's a new record for you, but bipartite matching on 10^6 vertices should obviously run on time :)

        Clearing the graph for every TC was a pain, though.

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Also, it can be done in O(m), and even it can be done with minmal total cost of edges in O(m) time.

      Let's add two edges from B to A. Now we have only a condition on degrees. Lets get a bipartite grpah with 2 copies of vertices in left part (corresponding to vertex in EA and to vertex in EB) and edges in right part. Every vertex in second part will have exactly two edges (to start in EA and to and in EB). The problem is to find perfect (by left part) matching in this graph.

      This can be done in two ways. First, every chain we are searching for in Kuhn method have unique edge on each step. So we can just maintain end of this chain for each vertex in disjoint set union.

      The other way, which seem to be more beautiful for me, is think about vertex of degree 2 as about an edge between it's neighbors. It can be shown, that matching is same as covering this graph by set of edges, where no component have more edges then vertices (that is a tree, or a cycle with trees on it). Such covering can be done by something like Kruskal algorithm. And two be honest, produces exactly the same code, that first method.

      And if we sort edges by increasing of cost in any of this methods, it will lead us to min-cost solution.

      → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Anyone know the intended solution to B? How are you supposed to do the computations quickly after arriving at a formula for the answer?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    While I haven't got AC, I got something in python that might pass in a faster language with builtin GMP-gcd with some constant optimizations.

    Code
    Profile Table

    Let 'avgbad' be the average cost of an unreasonable item and 'avgreason' be the average cost of a reasonable item. Let 'bads' be the number of unreasonable items. Then the answer is

    (The formula can be gotten with some calculations and [this](https://www.wolframalpha.com/input/?i=sum_%7Bk%3D1%7D%5E%7Bm%7D+binom(b,+k)%2Fbinom(n,+k)) Identity.)

    The binomials can be computed quite a bit faster by sieving over primes, this could probably be speed up more by computing the product in divide&conquer fashion. The main bottleneck was reducing the fraction. The buitin python gcd is to slow, I found a faster lehmer-gcd here, but it's still to slow.

    Loading GMP into c++ does not work on Yandex unfortunately (at least the method that works on spoj doesn't work on yandex), so I couldn't try GMP-gcd. I'll try some more stuff tomorow.

    Edit: Got some speedup in pow_binomal by computing the product in a smarter way, now TLE 36 (previously TLE 34).

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Alright, I got AC in 1.5s with some more optimizations.

    Code

    Optimizations used:

    • Formula involving only two different binomial coefficients and some smaller numbers. (See my post above.)
    • Computing the binomials by counting the number of occurrences of each prime.
    • Computing the resulting product of prime-powers by binary splitting.
    • (new) Cancel primes that occur in both binomials early.
    • Use lehmer gcd.
    • Use pypy4, not python2.7.
    → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve problem F? How do we use the constraint of ?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 10   Vote: I like it +21 Vote: I do not like it

    I think we need to use the trick from here, if we choose a random index and with probability (which by our condition is at least so we'll check around 10 cases to be sure) it will appear in the final sequence. Then we find its biggest divisor such that there are at least n - k numbers that divide this number.

    UPD. About the last part, suppose we chose number N, it has at most divisors. Suppose its divisors are 1 = d1 < d2 < ... < dK = N and prime numbers the divide it are p1 < p2 < ... < pt (1 ≤ t ≤ 15). We'll calculate an array cnt with cnti being the number of values in our sequence that divide di. In the problem mentioned above we are allowed to do the following thing:

    1. First set cnti to be equal to the number of values such that gcd between it and N is equal to i.

    2. Second, just iterate for every i from K downto 1 and for every j from i + 1 to K if we have that dj ≡  0 (mod di) then we increase cntj by cnti.

    Now we need to optimise it because O(K2) is too much, that's why I introduced the sequence of primes. Basically for every prime pi and for every j we increase by cntj the position in array cnt corresponding to the divisors (1 ≤ r, dj ≡ 0 (mod pir)). This can be done again in linear time. So the complexity becomes which in practice is way smaller.

    If you find something wrong, please let me know. I hope I didn't miss any easy solution :) .

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I got accepted with following heuristic.

    If n is less than 80, just factorize all numbers and solve the problem. Else, let's get 80 random numbers, factorize them, and get all divisors that are in at least 16 of them. For each of this divisors starting with big solve the problem in time O(number of diffrent numbers).

    Idea is that probably, if we have many big numbers which are divisors of a lot of random numbers, but of n - k numbers, we have a lot of same numbers in input. No idea about formal proofs.

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

C: On the line this problem could be solved with simple greedy: take a path with the leftest right end, take it's right end, delete all the paths that contain this point and repeat until we cover all paths. On the tree the same greedy works, except we always take a path with the lowest lca.

D: Let dpi be answer for the i-th prefix. Then dpi = minj < i(max(t[i], dp[j]) + 2 * maxj < k ≤ i(ak)). Notice that dpi is nondecreasing. Then there exists pos such that dpj < ti for j < pos and dpj ≥ ti for j ≥ pos. We can maintain pos with 2 pointers. Now we can consider j < pos and j ≥ pos separately. For j < pos we need to calculate minj < pos(ti + 2 * maxj < k ≤ i(ak)). We can mantain segment tree where j-th value is maxj < k ≤ i(ak) and update it easily with stack of maximums. The case j ≥ pos is almost the same.

→ Reply
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve J?

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve J faster than O(nm3) or O(nlognm2) ?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I found the solution just after asking it : the approach actually runs in , and the problem is almost the same as problem K from http://codeforces.net/blog/entry/55467

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    (Maybe that's the same thing you described in previous comment, but) We did it in :

    Using divide and conquer, fix center of the array. All the queries are either to the left or to the right or goes through the center. THose to the left and to the right we will do recursively. Now, from the center calculate dp[l:center] and dp[center:r] for all l and r in O(nm) Now for each query you'll answer in O(m2). So, overall complexity is O(nm2) for queries (well, O(qm2) but who cares) and for divide&conquer part

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't it O(qm)? if you let modulo as x on left part, then modulo on right part is (m - x)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks. What we actually submitted was O(qm2) but you are right, it is easier to do in O(qm)

        → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I :

Suppose you can afford a trie on given strings, then you can try DP on tree. DP[i] =  (number of subset for subtree of i). Then you have simple recurrences.

Our solution is online. We will build a tree from a set of string S, where a parent of node is a longest prefix that is not v and in S. Basically this is a sort of compressed trie, so you can try identical DP if you have this one.

We sort all strings in lexicographical order (done by suffix array). This will be a preorder traversal of such tree. With suffix array you can find whether given two substrings are prefix or not — you can decide whether string x is an ancestor of string y. Now you can use stack to iteratively make a tree.

Time complexity : O(nlogn + qlogn)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

G: Do a binary search for T. Rearrange the inequality to oaj ≤ obj + T - dj. This corresponds to an edge bj → aj with weight T - dj when interpreting ox as the distance to x. Initialize the o as given in the input and replace '?' by 109. Run Bellman-ford, if a negative cycle is found or one of the given o changes, T is too small.

L: Use Dijkstra's to compute all edges that are in some shortest path starting at the capital. Then use the solution of problem C from GP of Poland to get the number of edges which are used in all shortest paths to a given node.

K: I have solution in with rolling hashes and the fact the the query strings can have at most different lengths. Is there something faster?

For F passes in 2s if you use bitset and prune divisor candidates that are smaller than the current best or that are divided by an already discarded candidate when generating the divisors of a recursively from the prime factors.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    K: You can do with the same complexity but with trie and kmp, you build a trie for every word in the set that has length smaller than for every node in the trie you keep the the current answer and the last index last of the occurrence then updates this values running in the substrings of size smaller than of the text and for the rest of the strings in the set you do kmp. I don't know if it's faster, passed with 275 ms

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually, you can skip part with KMP. If you'll go in trie by suffix links, you can visit only sqrt(M) terminate (in which ends some word from input) nodes, where M is sum of words lengths.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am getting TLE on TC-15 by using rolling hashes for problem K.

    What I did was precompute the hash function for every prefix of S and for every query compute the hash for query substring P and traverse through S and greedily pick matches. I also stored the answers for every query in a map to avoid recomputation. What am I missing?

    118728564

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      If the query strings are all short and distinct, then caching the answers in a map doesn't help, so your solution loops over the entire string $$$s$$$ for every query, resulting in a total running time of $$$\Omega(n m)$$$, which is too slow.

      The key idea for my solution is to process all strings of the same length simultaneously in a single pass over $$$s$$$. Then the total number of passes over $$$s$$$ is at most $$$\sqrt{2 \sum_i |t_i|}$$$, which is a lot less than $$$m$$$.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any easy to code solution for A?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Count each triplet at its smallest element. When fixing the smallest element x, the other two elements need to be in [x, x + d], so we can count them with binary searches on the two other arrays. Slight care has to be taken to not count triplets with duplicate elements multiple times.

    Code
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      It may also be done in O(n) with two pointers technique insted of binary search (it also helps to take care of equal minimums automatically)

      → Reply
»
7 years ago, # |
  Vote: I like it +51 Vote: I do not like it

My problems are E and G. Hope you liked it!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    E is very cool, G is good, but isn't fresh. I am sure that already have seen it.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can we access the problem statements? Can you please provide me with the link to the problem set?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's here

    BTW, statement of most opencup rounds can be found here some times after the contest.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please tell me, where can we submit our solutions to above problems?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -13 Vote: I do not like it

        You can submit your code to me, I will review your code and give you a verdict (Accepted/ Wrong Answer/ Time limit exceeded/ Presentation error)

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        The contest is also in Codeforces gym here where you can submit.

        → Reply