8VC Venture Cup 2017 — Elimination Round[Editorial]

I don't understand E, can you elaborate on why this works?

Thanks for someone hacking my D solution..

In C, I solved it slightly differently. For any vertice x whose diameter ends in y, clearly the vertice y has a diameter that ends in x (so v[x]=y and v[y]=x). Simply check for all vertices the ones that cycle back onto themselves, (i.e. v[v[i]]==i), and the number of such distinct elements is the answer.

3855373

There is some alternative solution in D without any structures. Look at this! http://codeforces.me/contest/755/submission/23862072

I solved D without segment tree, with complexity O(n)... Here is the code

int cycles = 0;
ll ans = 1;

int main() {
    int n, k;
    scanf( "%d %d", &n, &k );
    if( k > n/2 )   /// circle is symmetric
        k = n - k;

    int cur = 0;
    for( int i=0; i < n; ++i ) {

        int to = ( cur + k ) % n;
        if( to < cur && to != 0 )
            cycles++;

        ans += cycles + 1;
        if( to < cur )
            cycles++;

        cur = to;
        printf( "%lld\n", ans );
    }
    return 0;
}

System judged my A solution in 15 minutes and it gave WA test case #2 because of stupid mistake! Then I corrected my mistake less than 1 minute and got AC. But I send my first solution in 2nd minute, and after correcting mistake in 17th minute. I lost points for nothing! I know this happened not just me, but Codeforces team please don't make mistakes like that.

Nice problemset. Loved the first problem.

Можно 16 тест на Б пожалуйста?

Could someone explain the tutorial for D? I find it a little difficult to understand.

Why on solution problem D: k = min(k, n - k)?

Problem C i used disjoin set

So fast, nice contest tho :D

Am I the only one who has solved C by counting the number of connected components? link: this submission

can anyone explain D for me? why i got Time Limit? http://codeforces.me/contest/755/submission/23867206

You can test 16 B please?

Has anybody solved optimized knapsack for problem F in a different way? The author's solution is hard to understand.

Problem D can be solved in O(n). http://ideone.com/gm3MCV

Auto comment: topic has been updated by kpw29 (previous revision, new revision, compare).

23858332

Can someone explain why this implementation of C gives TLE? I made each tree a set, and every time there was another element, I scanned through all the sets to see which tree/set the element would go in. Thought it was N^2.

My 23855084 using UnionFind passed for Problem C. If you see p[i] = j simply union(i, j) and in the end count number of disjoint sets.

Could please someone explain how to understand the following in the text of the problem G : no two balls shall occur in one group,but in the first test case they say that groups are divided in such order (1),(2),(3);(1,2),(2,3) etc.So as i can see here the ball number 2 is encountered 2 times,so i consider,that the first line(when divided in 1 group is 1 case, so the ball number 2 shouldn't be in any other groups(when divided in 1+ groups),but then i see the second line when i can see ball 2 one more time(more than 1 time,actually , but nevertheless),so as i see there is a contradiction and I can't solve it by myself,could anybody help me to understand that.I'm baffled:(

For problem E: "It's easy to see that ShortestPath(1, 4) is exactly 3. Also, ShortestPath(1, 4) in the complement graph is 3." 1 — 2 2 — 3 3 — 4

Why is Shortest Path in complement graph 3? Isn't there the edge 1-4 in the complement graph?

Can someone please look at my submission in C and help me in finding out what went wrong. http://codeforces.me/contest/755/submission/23858330 Thanks in advance.

23875480 My O(n) submission from problem D in python3 is giving TLE EDIT: It works in C++

There's surely a typo in the editorial from problem E. If the shortest path between two vertices in a graph is more than 1, then the shortest path between the same two in the complement graph must be exactly 1. Please correct.

Problem C does not require implementing dfs, but knowledge of dfs. It can proven that each node in the tree has the farthest node which will be one of the two ends(nodes with farthest distance between them).There can be more than one node at one of the end but here it is fixed(with the smallest id).We can map the values which corresponding to either of these ends. Total elements in the map will be our answer.

I tried to implement authors approach in Problem F but I am getting TLE on test 6. I have tried taking T as 100 and 200.This is my approach :http://codeforces.me/contest/755/submission/23886931

Can someone explain why in problem E, k=1 is not achievable if I just add one red edge?

Ограничение по времени на задачу F точно 1,5с?

755B If k contains even number of words, PolandBall will have an advantage of one additional word.

Looks like odd.
cf: http://codeforces.me/contest/755/submission/23902417

For test case #8 of E, I don't see why does the judge's answer produces k=3, shouldn't the white subgraph has a diameter of 2?

In solution for problem F it's somewhat arbitrary to split numbers that way (smaller than T, larger than T).

Let's analyze, for some number x:

• complexity of first algorithm is where B is word-size (say B = 64) and f_x is frequency of x
• complexity of second algorithm is O(k).

We can see that complexities don't depend on x at all, but only on its frequency f_x. So what makes most sense is to use first algorithm for numbers x such that f_x < B and second algorithm for other numbers.

Splitting them in a way proposed in editorial is still good heuristics, since we can expect smaller numbers to have larger frequency.

Another way to solve problem G.

It's easy to see after after getting dp equations and interpreting each row of the dynamic as a polinomial the following result: P_n + 2 = (x + 1) * P_n + 1 + x * P_n

At the begining one approach inmediatly came into my mind (matrix exponentiation). But i was computing too many fft and it was TLE :(

Another way to tackle this equation is solving the linear homogeneous equation related. Notice that the coefficients of this equations are polynomials.

Z² = (x + 1) * Z + x

Z² - (x + 1) * Z - x = 0

The form of the formula is:

P_n = A * Z₁ⁿ + B * Z₂ⁿ

P₀ = A + B = 1

P₁ = A * Z₁ + B * Z₂ = x + 1

Solving this system to find A and B we get:

B = P₀ - A

Now we only need to figure out how to compute inverse and square root of polynomials. Using the technique described by vfleaking here we can do both things with total complexity .

The final complexity is because we need to do fast exponentiation to find the answer in steps.

Solution here.

I tried to implement FFT for problem G but somehow the FFT function went wrong, I tested the function under the circumstances [MAXN = 16, logMAXN = 4, n = 4], and the FFT result of the array is very odd. The imaginary part has incorrect positive/negative sign, and the real part output zig-zagged along the array. Can someone please help to point out where did I made a mistake?

Code: http://ideone.com/tUoCwO

The expected and actual output is also included

Thanks in advance. :)

Tee-hee, I got O(k²) to pass on Problem G after the contest.

In problem E, which sentence said that both red and white subgraphs need to cover all the n vertices?