For technical reasons, some programming languages (Kotlin, C #) will not be available during round 877. ×

Miyukine's blog

By Miyukine, history, 9 months ago, In English,

8VC Venture Cup 2017 — Elimination Round[Editorial]

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +115
  • Vote: I do not like it  

»
9 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Answer is possible only for K = 2 or 3. There are two construction algorithms. For K = 2 one path works. For K = 3 idea is a bit more complex.

»
9 months ago, # |
  Vote: I like it +55 Vote: I do not like it

Thanks for someone hacking my D solution..

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you explain a little ?!

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      With each round we cross on a diagonal more. However, as an exception at the beginning of the circle only one more. At the moment, I can not rigorously prove.))

»
9 months ago, # |
  Vote: I like it +57 Vote: I do not like it

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;
}
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Me too. It's a simpler idea.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    can you please elaborate your idea? why did you increase cycle for 2nd time? thanks

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      It can be easily visualized by drawing a polygon by hand.

      In the initial round around the polygon going from 1 to n, the diagonals will not intersect. So every diagonal will produce 1 extra section. The final diagonal around which cross the point 1 will produce +2 sections because it will intersect the diagonal which starts at point 1 to (k+1). Every subsequent diagonal will intersect with two other diagonals (one starting from a point before their starting point and one between the starting and ending point) producing +3 sections each time. Suppose x sections were introduced with every diagonal. The final diagonal which crosses point 1 will introduce x+1 sections. And every subsequent diagonal in the next round will produce x+2 sections. Complexity: O(n) because every point becomes a starting point for a diagonal exactly once.

»
9 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

»
9 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Nice problemset. Loved the first problem.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    As you should just consider the number of diagonals connecting the vectices on the minor side instead of the major side.

    If you do not get n-k as k if n-k is smaller than k, you will calculate the number of diagonals connecting the vertices on the major side, which is incorrect.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain this thing more elaborately? I am unable to prove it.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why are n-k and n coprimes when k and n are also coprimes?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Lets assume the opposite: if n-k and n are not coprime, then there exists some common divisor d > 1 with n - k = d * x and n = d * y for some x and y. But then it follows: k = n - (n - k) = d * y - d * x = d * (y - x). So also k is dividable by d. But then k and n cannot be coprime, because both are a multiple of d.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        because (a,b) = (a — b , b)

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got it, thanks!

»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem C i used disjoin set

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, it can be solved by a lot of things. I used dfs to solve

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used simple DFS. Someone used DSU

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So fast, nice contest tho :D

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Set k = 106 - 2 and n = 106. Then find your code complexity.. And assume O(109) will pass in 1 second. :)

»
9 months ago, # |
  Vote: I like it -10 Vote: I do not like it

You can test 16 B please?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same problem. I don't know what is that test exactly! I hope somebody can help us.

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    you can break frequency into binary and then do normal knapsack , number of elements are now about . code .

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 3   Vote: I like it +92 Vote: I do not like it

      Number of elements is at most now. To see this, we first observe that number of elements is about . Number of k, such that cnt[k] ≥ 1, is at most . Number of k, such that cnt[k] ≥ 2k, is at most . So, .

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        I'm having trouble to: 1) understand the following passage; and 2) assuming it is correct, how to apply it to the final inequality.

        "Number of k, such that cnt[k]  ≥  2k, is at most ."

        Would you please explain it in more details? Also, would you please give the intuition behind this bound? Is it something like: Suppose you have k different cycle lengths and this k is maximum. Then k is around . Also, k being maximum implies that each cycle length occurs with frequency around 1. If these frequencies start to increase, then k becomes smaller than enough to compensate these repetitions and the overall sum stays around . Is that it?

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
          Rev. 2   Vote: I like it +23 Vote: I do not like it

          Of course, intuition behind the argument is like you have described.

          Assume, that cnt[k1] ≥ m, ..., cnt[kl] ≥ m. Then the sum of lengths of cycles is at least k1cnt[k1] + ... + klcnt[kl] ≥ m(k1 + ... + kl). Since ki are all different, k1 + ... + kl ≥ l(l + 1) / 2. So, the sum of lengths of cycles is at least ml(l + 1) / 2, so .

          Now, , where [x > 2r] equals 1, if x > 2r, and 0 otherwise. So, .

          Anyway, solution described below by egor_bb has obviously operations with bitset and is not harder to implement.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    Another solution is similar to binary.

    The goal is to leave no more than 2 items of each weight. Then we'll have items and solve knapsack either in a simple way or with bitset.

    We can notice that for each weight in optimal answer we'll take either odd or even number of items. Let's fix weight w. We can leave one item of this weight and merge other items in pairs. If number of items with weight w was even — we'll have 2 items left, if odd — 1 item. Also now we have more items with weight 2w.

    Easy way of implementing it is to iterate from small weights to big and perform merging.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      After this reduction, only items remain to be considered by the usual knapsack. This follows by the same arguments pointed by ershov.stanislav in the comments above, am I right?

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        It is a popular idea that if you have a set of numbers with fixed sum S then there is different values in set. Easy proof is following:

        When is sum of k different positive numbers minimal? When these numbers are from 1 to k.

        An interesting case of applying this idea is a set of strings with fixed total length. Since there are at most around different lengths, often handling all strings with the same length in some simple way is enough.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, that is a valid argument, but only before the reduction you applied. We need another argument to prove that the total number of items remains after the reduction you proposed. And as you break the frequencies in halves, I think that the arguments above also apply to your reduction! It'd be great if someone could confirm that.

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            After the whole process of reduction we have no more than 2 items of each weight. Thus, total number of items is no more than 2 times "number of different weights" which is

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              That argument is not valid, because your algorithm creates some new weights that possibly didn't exist before. Here:

              		if (rem / 2 > 0)
              			lens.insert(l * 2);
              		num[l * 2] += rem / 2;
              

              And it will continue to do that until the frequencies cannot be halved anymore. So there's a possibility that for each weight w, you'll create around new weights.

              So we still need additional arguments to prove that, despite some new weights are created, the total number of items remains .

              • »
                »
                »
                »
                »
                »
                »
                »
                9 months ago, # ^ |
                Rev. 2   Vote: I like it +13 Vote: I do not like it

                C'mon, sum remains the same all the time and it's enough. You can apply the proof at any moment. Read the explanation of algorithm again, please.

                I believe that your misunderstanding is small enough to stop the conversation here and continue it in private messages.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                  Rev. 4   Vote: I like it 0 Vote: I do not like it

                  Yes, I do believe in the bound! I'm just trying to point the exact proof for your version! I'm not trying to contradict you.

                  UPD: Okay, got it! This last comment is enough: the sum will remain the same all the time, so the bound is valid all the time!

                  UPD2: And I believe that others could learn from someone else's mistakes... So it's okay and desirable to keep the conversation here. But now I got the proof, anyway. Thanks!

»
9 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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:(

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Also thinking about the same thing, don't mind me just leave a comment here to get notifications if someone answer it

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    The longest shortest path in complement graph is for (2,3) of length 3(2->4->1->3).The problem doesn't require the two pairs of vertices to be same in both the graphs.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    consider the following forest: 2-1-3-4. Then the input would be 4 4 2 2. running your code outputs 2 when it should output 1.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The reason is that you made multiple print out. As far as I know, it is better to declare a String variable output and keep updating that, subsequently only call print() once at the end of the program.

    My Java code took almost 3s to run problem D because of the same reason. When I changed to a StringBuilder to maintain the output, the runtime reduced to only 0.3s.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

my code is giving right answers on my ide (codeblocks) for problem c but its giving wa (like which answer is 2 on my ide its showing 4 in cf) here... whats the problem :( ...here is my code 23878095

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why, one of the graphs should contain an edge between them bcs two of them concatened should make fully connected graph.

»
9 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is an error in problem B solution: PolandBall will have an advantage of one additional word if k has an odd number of words. If k has an even number of words then each player can say the same amount of repeated words and therefore subtract the same number of words to the other player's set of words, so there is no advantage in this case.

Great contest, thanks!

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

To solve problem D using Fenwick Tree , how to find the answer when ending point of range is less than the starting point, can someone explain the else part of the below code.

// for i = 4

int l = ((ll) k*i)%n;

int r = (l+k)%n;

int a = l+1;

int b = r-1;

if (b>=a) ans+=query(b+1)-query(a-1+1);

else ans+=query(n-1+1)-query(a-1+1)+query(b+1);

UPD : Nevemind , got it !

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/755/submission/23886931

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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 fx 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 fx. So what makes most sense is to use first algorithm for numbers x such that fx < 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.

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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: Pn + 2 = (x + 1) * Pn + 1 + x * Pn

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.

Z2 = (x + 1) * Z + x

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

The form of the formula is:

Pn = A * Z1n + B * Z2n

P0 = A + B = 1

P1 = A * Z1 + B * Z2 = x + 1

Solving this system to find A and B we get:

B = P0 - 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.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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. :)

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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