Lewin's blog

Forethought Future Cup Elimination Round Tutorial
By Lewin, history, 6 years ago, In English

Here's the tutorial. Code can be found in this link: https://www.dropbox.com/sh/wfr12qqhcrdwwlv/AAAgg-7NcqRHIysVjHvmcR_Ta?dl=0

Love A
Hate A
Tree Diameter
Frog Jumping
Hot is Cold
Leaf Partition
Zoning Restrictions
Satanic Panic
  • Vote: I like it
  • +199
  • Vote: I do not like it

Comments Comments (101)
| Write comment?
»
6 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Very Fast Release. :)

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

any faster than this and it would have been within the contest

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

My solution for H: the goal is to find the number of convex pentagons. We will do this through constructive DP. Take all directed segments between points and sort them by angle. Then, maintain array $$$dp[i][j][k]$$$, the number of polylines that start at vertex $$$i$$$, end at vertex $$$j$$$, contain $$$k$$$ segments, and only make clockwise turns. Loop over each directed segment in order and update the DP array accordingly. Each pentagon has exactly one traversal that satisfies the above constraints, so the answer is just the sum of all $$$dp[i][i][5]$$$.

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

    How to exclude those polygons that only have a counter-clockwise turn at vertex $$$i$$$ in your solution?

    Edit: It can be avoided by fixing vertex $$$i$$$ to be the bottomost point.

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

      We implicitly force the whole polygon to be convex by only iterating through segments once (so the sum of exterior angles must equal $$$2\pi$$$).

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

        Oh, I missed this part. I was thinking something like counting those polygons with at least 2 obtuse angles.

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

The last approach for H seems to count the numbers of the second and the fifth points independently when the 3 remaining points are fixed, but those two numbers affect each other, or have I misunderstood some part of the algorithm?

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

    If you fix the first point as the bottomost point, then the two sides don't interact with each other anymore.

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

can anyone explain the E tutorial...

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

H can be solved more easily. (ah, already commented by scott_wu)

Solution

BTW, I took a nap before the contest and overslept 40 minutes. (;_;)

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

Can someone share the code for Problem C implemented using Binary Search.

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

    Binary search:

    Binary search solution
    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Checkout this one: https://mirror.codeforces.com/contest/1146/submission/53065522

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

    My solution: Problem C By using bs, you can scale down the range that can contain the farest leaf from node no.1 Hope you get it.

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

Very disappointed for not solving H firstly. I solved the harder version of it: http://mirror.codeforces.com/gym/100162/problem/J.

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

I have a different (maybe simpler) approach on problem E (without Segment Tree or anything like this):

We will process the queries offline, in reversed order.

  • Suppose the last query is > 6. This means that after this, all the element with absolute value greater than 6 will be -6 in the end.
  • Suppose the last query is < 6. This means that after this, all the element with absolute value greater or equal with 6 will be -6 in the end, and in addition, we will swap all the elements with absolute value less than 6.
  • Similar for negative values (the operations are reversed).

At each step we keep a vector with current absolute values and positions of the active elements that are not currently assigned. When we fix a value for an element, we remove it from the vector with active elements.

We observe that our maximum absolute value decreases while processing queries, which means that we can keep a value swapped which stores how many times must be swapped the remaining active elements (e.g. If the last operation is < 100000000 and the operation before is < -4, if we can deduce some values after the operation < -4 we must note that the values will be reversed one more time.)

Unfortunately, I wasted time on D and did not succeed in implementing this in time. AC submission: 53076099

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

    Sir, can u explain little more...

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

      Ok. so we will begin making a few observations: At each step, each element $$$a_i$$$ either remains unchanged, or it becomes $$$-a_i$$$ (we will call a swap when it changes the sign). So, to solve the problem, we will need to find out only the sign of every element.

      we then process the operations backwards. We can observe that the operations can be split into 2 categories:

      • > positive and < negative
      • > negative and < positive

      Now let's analyze what happends when the last operation is of the first type, then if it is of the second type.

      1. The last operation is > x, $$$x > 0$$$ (it is equivalent with the operation < x, where $$$x < 0$$$). Then, we can observe that all elements which have absolute value > $$$x$$$ will be negative in the end (If they were already $$$<0$$$ they remain negativeas they are already smaller than $$$x$$$, otherwise, they will be swapped). So, after this operation, we can fix the values of all $$$a_i$$$ such that $$$abs(a_i) > x$$$. Further, we will be interested only in elements such that $$$a_i \in [0, x]$$$
      2. The last operation is > x, $$$x < 0$$$ (it is equivalent with the operation < x, where $$$x > 0$$$). As in previous case, we can observe that all elements which have absolute value $$$ \geq abs(x)$$$ will be negative in the end. (The reason is similar to the 1st type operation). In addition, we observe that all other elements will be swapped (the only elements not swapped are those < $$$x$$$. But we already know the value of those, as for each of them $$$a_i \geq abs(x)$$$ holds). So, we will be interested only in elements such that $$$a_i \in [0, x]$$$, but we will keep track that there is an additional swap executed on each of the elements in the range.

      We then proceed to the next operation (in reverse order), and apply the same strategy, on the elements remaining, taking into account how many times they have been swapped already in the operations that have already been processed.

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

        Thank you so much sir... For the reply and for good explanation.

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

Wait please, has noone commented here about this solution on H yet?

For every bad configuration there are exactly two ways to choose three point of 5 so that one of the rest is inside the triangle with these vertices and the other is outside, no matter if these 5 points have triangular convex hull or with 4 vertices. So the main code of the problem becomes

	long long ans = C(n, 5) * 2;

	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			for (int k = j + 1; k < n; ++k) {
				int cn = getCntInside(i, j, k);
				ans -= cn * (n - 3 - cn);
			}
		}
	}

	cout << ans / 2 << "\n";
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1 is root in problems C ？ (问题C中1是树的根吗？)

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

    For the diameter of tree you can choose any node of the tree.let's say it is X and from that node we find the farthest node let's say it is A. And the distance of the farthest node from A is the diameter of the tree. So here we do not need to fix X we can choose any node as X. It may be root node or may be not. And also in the problem we are not given any clarification about root node. So we randomly choose 1 as X. For more clarification you can always google it :)

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

In B, is 1 assumed to be the root of the tree

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

    Ah! You mean C, have a look at continuity's answer above!

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

Can anybody pls help me with question B why is it giving WA on test 12? https://mirror.codeforces.com/contest/1146/submission/53069201

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

    i think this line is wrong in your code ---if(s[s.length()-1]=='a'){cout<<":("; return 0;}---

    because of this line your code fails on this type of testcases. for example = "bbbaab"

    check correct answer and your answer

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
  for (int bit = 0; bit < 9; bit++) {
      vector<int> a;
      vector<int> b;
      for (int i = 0; i < n; i++) {
        if ((i >> bit) & 1) {
          a.push_back(i);
        } else {
          b.push_back(i);
        }
      }

What is this part doing, for problem C.

anyone??

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

    The numbers having bitth bit set are pushed in vector a and the numbers having bitth bit unset are pushed in vector b.

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

      will that guarantee that each pair is once splitted into 2 different group?

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

        Suppose there is a pair of numbers (X,Y) which is never split into different groups, if X and Y would have differed in any of the bitth bit,they would have been split in different groups as per the loop. That means X and Y do not differ in a single bit, which implies X==Y. So by contradiction, there exists no pair (X,Y) such X!=Y which hasn't been considered in different groups.

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

    You can do a simpler binary search: First we have to query 1 n — 1 1 2 3 ... n to get the maximum distance D from 1 other nodes. Let l = 2, r = n, then we binary search query range for second set: m = (l + r) / 2 if query 1 m — l + 1 1 l l+1 l+2 ... m equals D then farest node must be in range l, m. Otherwise it will be in range m+1, r. Repeat until l = r, then u = l is the farest node from 1. Now result is anwser for query from set contains only u to other nodes.

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

      Is 1 considered to the root of the tree. Or if it is just a random node then what is the proof of this fact : the farthest node from any random node must be a part of the diameter

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

        We can take any node as a root of tree. For the proof, first we can prove it is true for unweighted tree (every edge has weight 1). For weighted tree, assume we have edge u — v with weight w, then you can expand this edge to w edges with weight 1. Do it for every edge and weighted tree become unweighted tree. So you can apply the algorithm of unweighted tree to the weighted one.

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

Can someone explain the solution for D? Could not understand the editorial.

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

    I want to make the editorial more useful, and it seems many people have asked about it. What part of it is confusing? Maybe going through an example might help? It is hard to know what to improve if people only vaguely ask for me to re-explain everything without saying what part they're stuck on.

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

      --- For each i modulo a ---

      does it mean "for each i=0..a-1"? This assumption takes 20 min from me, still i'm not sure.

      --- the leftmost node that the frog can reach modulo i ---

      Maybe zero, given start is from here? What means 'modulo' here?

      Further i saw two "we can do" and no "why can we do this" and didn't dare to puzzle out.

      Thank you for interesting problems.

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

        Yes, for each i=0..a-1, we will solve a separate problem and only consider the problem of positions the frog can reach i modulo a in the sum.

        For i=0, the leftmost point is zero. For other i, it will be different.

        About "we can do" vs "why", is it unclear what we are doing, or are you unsure if we can do these steps? If it's the latter, I can try to justify. I didn't include it initially since I thought it was easy to do on your own if you tried, but maybe it's harder than I thought. I'll try to elaborate a bit.

        For the first one, we can do it greedily since from a position k mod a, we can only go to (k-b) mod a, so we might as well greedily do that move when it's available if we want to get the leftmost point we can reach.

        For the second point, if we only consider positions modulo i, for a fixed $$$j \geq x_i$$$, we can reach $$$d_i$$$ and get $$$d_i$$$, $$$d_i+a$$$, $$$d_i+2a$$$, and so on, up until $$$j$$$. If you write it out another way, the contribution of the sum of positions modulo i in the sum from the problem is the sum from the editorial.

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

          Hello, I'm having a tough time with intuition behind $$$d_i$$$. Can you give an example where $$$d_i \neq i$$$?

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

            It probably is the case that d_i is i. I didn’t want to claim it since I don’t have a easy proof for why that’s true.

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

              Lewin how are you saying that you will always reach the all unique(i mod a) before reaching a repeated (i mod a)

              → Reply
»
6 years ago, # |
  Vote: I like it -38 Vote: I do not like it

The contest time is really unfriendly to the Chinese. When I woke up in the middle of the night, I could think of nothing except sleeping.standings

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

Is the last formula in problem D correct?

$$$floor((x_i-d_i+1)/a)$$$ is nothing to do with $$$j$$$.

Is $$$j$$$ exist for fun?

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

Can somebody explain me the solution of problem D?

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

    Here.

    Capture

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

      I wasn't able to understand the editorial thats why I asked for some other explaination.

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

        You should have made it clear in your original comment that you wanted an alternative explanation.

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

          What made you think that I will ask the solution through comments directly without looking the editorial?

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

    After f(a+b) the funtion becomes predictable. It becomes f(i) = i/gcd(a,b)+1. So we simulate the first 2e5 function iterations with some bfs or something in O(2e5) marking every value we can get to. After that the problem becomes calculating the predictable function which can be done in multiple ways. You can see my code here.

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

      Why not after f(a+b) f becomes predictable?

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

        Yea that is the exact limit probably, i just put the wrote the limit i used during the contest.

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

          Maybe even from f(a+b-gcd(a,b)) ? :-O

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

Please anyone explain the soution for D more clearly...unable to understand editorial....

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

I first tried the following for problem C which is similar to the bitmask approach:

I wrote down the 9 first primes. Then I created n numbers such that every number x of those n numbers can be written as x = a * b * c where a, b, c are among the first 9 primes. This gave me a way to map the nodes 1 ... n to n distinct numbers which all have a unique prime factorization using only the first 9 primes. For every testcase I asked 9 questions: In question i the first set of nodes consists of all nodes v for which map(v) % prime(i) == 0 and the second set of nodes consists of all nodes v for which map(v) % prime(i) != 0. I took the maximum response i got as the answer to the testcase.

My intuition was that for every two distinct nodes v and u it will be the case that in one of the 9 questions v will not be in the same group as u and thus my answer must be maximal. But I received WA on the second testcase and I cannot find my mistake. In particular, of the 1000 subtests of testcase 2 the 558th fails and I didn't find any way of finding out what this particular test looks like.

I then modified my program to use the bitmask idea and this works fine (passed all tests). So my question is: Is there some problem with the theory of my solution?

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

    I went through your code and in vector key you have numbers like 12 and 18 which don't have different prime factor, so it fails.

    I'm trying to filter out those but I'm afraid you'll have less than 100 then, so it won't work.

    EDIT: It works! 53094357 Congratz on the idea

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

      Oh right. Thanks alot! I was really stuck and couldn't figure out what was wrong. This helps alot!

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

We also check that after removing all "a"s from t, the first and second half of the strings are equal.

How can it be true for 'baba'? after removing 'a' it is 'bb' i.e both half part is equal.

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

    editorial also says: we know the suffix of length c1/2 of t must be s′. it means that after removing 'a' from original string, the suffix of the new without-'a'-string should be the same as the suffix of the original, and the length of the suffix should be the half of the new string.

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

Can anyone explain what this means in editorial for problem F: 'node has to be connected above'?

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

    Let's suppose we have a node is only directly connected to one child below, and all leaves in the same partition set are in its subtree. We can remove that node from the $$$f$$$ value to get a smaller connected subgraph that contains all the leaves. Thus, if a node is only directly connected to one child below, then that means there must be leaf in the same partition set but in a different subtree, so it must "connect above" (or maybe a different way is to say it must "connect outside").

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

I also do not understand the tutorial for D (even though I passed the problem in contest time). What is missing for me is the proof that when x is not too big (maybe x==a+b+1 is enough) it is possible to reach every position multiple to gcd(a,b)

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

    The tutorial does not use that fact. There are alternate solutions that use that fact, and I haven't tried to prove the exact bounds on what $$$x$$$ is needed for those.

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

    It is possible to reach every point up to a+b-1 without going farther than a+b-1.

    Let x be in the interval [0,a+b-1] (and a multiple of the gcd). Then we can represent x as ka-lb for some k,l>0. Now, follow a greedy strategy — start at 0, and make a +a jump whenever you can, and a -b jump if you cannot.

    At any point you land that is less than b, you can make a +a move, and otherwise you can make a -b move. So if you get stuck, that means you ran out of some kind of move. But it's easy to see that the only way that happens is if you reached your target.

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

For H, how does one compute all $$$f_i$$$ in cubic time?

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

    Computing f_i is kinda cryptic way of describing simply enumerating all triangles and determining number of points within them in constant time. We can do this in a similar way as we compute areas of polygons by adding and subtracting areas of some trapezes. For every pair of points (i, j) compute number of points under that segment and call it under[i][j]. Then, number of points in triangle (i,j,k) is more or less under[i][j]+under[j][k]+under[k][i]. "More or less" because you should take care of signs, points on borders and one of points being possibly under segment from the other two, but that can be handled.

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

      Thanks. It's one of those things that seems obvious after someone has explained it. It might be easier to fix some point A and then to compute the number of points inside triangle XYZ, $$$c(XYZ)$$$ as $$$c(XYZ) = c(AXY) + c(AYZ) + c(AZX)$$$ (where $$$c$$$ is negative for triangles with negative winding). That way, the constraint that no three points are collinear eliminates most of the special cases, and the only correction is to add 1 if A is inside XYZ.

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

        What about the case when X is inside a triangle AYZ. Shouldn't we add/subtract one in that case as well? Seems to be a nice idea, but evergreen "include left border, exclude right border" worked nicely for me as well.

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

          You're right, it is going to get more complicated than I thought.

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

Can someone give an alternative solution for Problem D, Or explain what is given in editorial?

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

    I found the editorial pretty confusing too. Here's my approach. For each $$$x$$$, there is some minimal $$$y$$$ such that it is possible to reach $$$x$$$ without going outside $$$[0, y]$$$ (or $$$y=\infty$$$ if it's not possible). Call this value $$$h(x)$$$. Then $$$x$$$ will appear in $$$f(y), f(y+1), \ldots, f(m)$$$. So we want to find the sum of $$$\sum_{x=0}^m \max(0, m-h(x))$$$.

    If $$$m$$$ was smaller, we could compute all $$$h(x)$$$ by priority-first search: if we can reach $$$x$$$ without going beyond $$$h(x)$$$, then we can also reach $$$x-b$$$ (if $$$x \ge b$$$) without going beyond $$$h(x)$$$, and we can reach $$$x+a$$$ without going beyond $$$\max(x+a, h(x))$$$.

    For larger $$$x$$$ (I used $$$x > a + b$$$, although possibly it can be tighter), one can show that $$$h(x) = x$$$ if $$$x$$$ is a multiple of the GCD of $$$a$$$ and $$$b$$$, otherwise $$$h(x) = \infty$$$. This is because one can always reorder the jumps to stay within $$$[0, a+b]$$$ until all the left jumps have been used up. From there it is a bit of linear algebra to get a closed formula for the larger values of $$$x$$$.

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

      [user:bmerry]Can you elaborate more on the case x>a+b for calculating the formula? Thankyou

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

        It might be easier with an example. Let's say a=4, b=6, m=21. Then the GCD is 2, and considering just the range (a + b, m]:

        • $$$h(12) = 12, m - h(12) = 9$$$
        • $$$h(14) = 14, m - h(14) = 7$$$
        • $$$h(16) = 16, m - h(16) = 5$$$
        • $$$h(18) = 18, m - h(18) = 3$$$
        • $$$h(20) = 20, m - h(20) = 1$$$

        and $$$m - h(x) \le 0$$$ for all other $$$x > a + b$$$. So we're just finding the sum of an arithmetic series.

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

          bmerry Proof for h(x)=x for gcd multiples of a,b where x>a+b. Can u please share your code too? I am struggling with this problem since 3 days.

          Thank You

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

            There's a standard number theory result that if g = gcd(a, b) then there is a solution to g = au — bv. And with x>a+b you always have enough space to make another jump without going past x.

            Code is at https://mirror.codeforces.com/contest/1146/submission/53095272

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

              bmerry int u = r / g * g + g; if (u <= m) { int v = m / g * g; int k = (v — u) / g + 1; //for (int i = u; i <= v; i += g) // ans += m — i + 1; ans += ll((m — u + 1) + (m — v + 1)) * k / 2; }

              I checked so many solutions , I asked you doubts in first place because of this part only. Could you please explain that part?( Like why v=m/g*g,u=r/g*g+g) Thank you

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

                v is m rounded down to a multiple of g, u is r rounded up to the next multiple of g.

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

      it should be $$$m-h(x)+1$$$ instead of $$$m-h(x)$$$. It's a little mistake.

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

Problem E. in the statement below, what does k mean?what is p? and can any one explain why this works exactly? there is almost no detail in the editorial

For example if it's <x where x is positive, then that means each wi from 0 to x−1 goes from k<->f or p<->n (i.e. flipping lowest bit of the number), and each wi from x to 10^5 is set to p

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

    It was shorthand for the things I said in the previous paragraph. I edited it so it uses the full words instead of the letters.

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

Btw, sad that n^4 was able to get accepted in H as well. You should have made it more clear with constraints and time limits whether it is possible to get AC with significantly easier n^4.

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

    Yeah, it is a bit unfortunate. I wanted n^3 log n to pass and my solution took almost 3s (the n^3 solution, on the other hand, only takes about 300ms). I would rather have slow n^3 log n pass rather than making the tl 1s or so.

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

Please, an example of solution for problem E. tnks

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

In min cut solution of G, what vertices is the source connected with?

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

    I think the source is connected to node (i, 0) for all i.

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

Lewin Can you please elaborate more on what are the edges and what is the cost for that in problem G? Thanks.

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

    Which edges are you confused about? You can also see the attached code for what exactly the edges are if code is easier to read.

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

      Yeah. Sorry for bothering. Got AC already. I was confused about how connecting kth node to sink with capacity ci will ensure flow. Nvm! Got it. Thanks

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

On the O(n^3 log n) solution for H:

(points are labeled A-B-C-D-E in clockwise order)

I don't think "lying in the intersection of some half-planes" is sufficient to being a legal B(or E) if you have determined ACD, as this cannot prevent A from lying on the wrong side of segment BE.

Or did i misunderstood something?

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

    Remember that we fixed A as the bottommost point, which makes it so it can’t lie on the wrong side of BE.

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

In problem E, I didn't actually get this part "for ai=j then we look at w|j|". How can we do this? Because I think even though they have the same absolute value, but for each query they have no relation to each other.

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

53068542 "suggests" that H was already published in "Xmas Contest 2012".

→ Reply