How to solve C and D?

I think I have seen the problem J somewhere before

# | User | Rating |
---|---|---|

1 | Um_nik | 3370 |

2 | Petr | 3325 |

3 | Syloviaely | 3258 |

4 | tourist | 3206 |

5 | Radewoosh | 3158 |

6 | OO0OOO00O0OOO0O0…O | 3102 |

7 | fateice | 3099 |

8 | mnbvmar | 3096 |

9 | HYPERHYPERHYPERC…R | 3071 |

10 | dotorya | 3068 |

# | User | Contrib. |
---|---|---|

1 | tourist | 183 |

2 | rng_58 | 169 |

3 | csacademy | 162 |

4 | Petr | 158 |

5 | lewin | 152 |

6 | Swistakk | 151 |

7 | matthew99 | 146 |

8 | Errichto | 142 |

9 | BledDest | 141 |

9 | Zlobober | 141 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/25/2018 07:58:12 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|

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

H:

First of all, we can ask

nqueries to find all leaves of the tree. To check whether a vertex is a leaf, we ask a query containing alln- 1 other vertices; if the answer isn- 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 vertexx. Since there are no vertices with degree 2, for any two verticesxandyL(x) ≠L(y); furthermore,xis an ancestor ofyiff . So if we obtain the information aboutL(x) for every vertex, then we can reconstruct the tree.For the root,

L(root) is the set of all leaves. For every other leafz,L(z) = {z}. So we need to findL(x) only for non-leaves. To check whether a leafzis in a subtree of non-leaf vertexy, we may ask a query 3rootyz.So if the number of leaves is

l, we have to ask (l- 1)(n-l) queries to findL(x) for all non-leaf vertices. This won't exceed 2450, and so we won't ask more than 2550 queries.Cool! It is a really simple solution.

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.

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

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

This can be found by maximum matching in

O(mn^{0.5})Wow, flow for 1000000 edges, that's a new record I've ever seen :)

By the way it can be solved without flow.

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.

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.

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

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.

CodeProfile TableLet '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).

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

CodeOptimizations used:

Oh my...

You're awesome :)

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

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-knumbers that divide this number.UPD. About the last part, suppose we chose number

N, it has at most divisors. Suppose its divisors are 1 =d_{1}<d_{2}< ... <d_{K}=Nand prime numbers the divide it arep_{1}<p_{2}< ... <p_{t}(1 ≤t≤ 15). We'll calculate an arraycntwithcnt_{i}being the number of values in our sequence that divided_{i}. In the problem mentioned above we are allowed to do the following thing:First set

cnt_{i}to be equal to the number of values such that gcd between it and N is equal toi.Second, just iterate for every

ifromKdownto 1 and for everyjfromi+ 1 toKif we have thatd_{j}≡ 0 (modd_{i}) then we increasecnt_{j}bycnt_{i}.Now we need to optimise it because

O(K^{2}) is too much, that's why I introduced the sequence of primes. Basically for every primep_{i}and for everyjwe increase bycnt_{j}the position in arraycntcorresponding to the divisors (1 ≤r,d_{j}≡ 0 (modp_{i}^{r})). 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 :) .

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-knumbers, we have a lot of same numbers in input. No idea about formal proofs.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

dp_{i}be answer for thei-th prefix. Thendp_{i}=min_{j < i}(max(t[i],dp[j]) + 2 *max_{j < k ≤ i}(a_{k})). Notice thatdp_{i}is nondecreasing. Then there existspossuch thatdp_{j}<t_{i}forj<posanddp_{j}≥t_{i}forj≥pos. We can maintainposwith 2 pointers. Now we can considerj<posandj≥posseparately. Forj<poswe need to calculatemin_{j < pos}(t_{i}+ 2 *max_{j < k ≤ i}(a_{k})). We can mantain segment tree wherej-th value ismax_{j < k ≤ i}(a_{k}) and update it easily with stack of maximums. The casej≥posis almost the same.How to solve J?

How to solve J faster than

O(nm^{3}) orO(nlognm^{2}) ?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.com/blog/entry/55467

(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 inO(m^{2}). So, overall complexity isO(nm^{2}) for queries (well,O(qm^{2}) but who cares) and for divide&conquer partIsn't it

O(qm)? if you let modulo asxon left part, then modulo on right part is (m-x)Thanks. What we actually submitted was

O(qm^{2}) but you are right, it is easier to do inO(qm)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 notvand inS. 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)G: Do a binary search for

T. Rearrange the inequality too_{aj}≤o_{bj}+T-d_{j}. This corresponds to an edgeb_{j}→a_{j}with weightT-d_{j}when interpretingo_{x}as the distance tox. Initialize theoas given in the input and replace '?' by 10^{9}. Run Bellman-ford, if a negative cycle is found or one of the givenochanges,Tis 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

arecursively from the prime factors.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

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, whereMis sum of words lengths.Is there any easy to code solution for A?

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.CodeIt 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)My problems are E and G. Hope you liked it!

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

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

It's here

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

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

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)

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