Lewin's blog

By Lewin, history, 4 weeks 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  

»
4 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

Very Fast Release. :)

»
4 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

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

»
4 weeks 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]$$$.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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$$$).

      • »
        »
        »
        »
        4 weeks 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.

»
4 weeks 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?

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

can anyone explain the E tutorial...

»
4 weeks 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. (;_;)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 6   Vote: I like it -33 Vote: I do not like it

    Binary search:

    Binary search solution
  • »
    »
    4 weeks 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.

»
4 weeks 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://codeforces.com/gym/100162/problem/J.

»
4 weeks 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

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

    Sir, can u explain little more...

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
4 weeks 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";
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks 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 :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks 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://codeforces.com/contest/1146/submission/53069201

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No that is correct actually I had some other bug in my code..I fixed it anyways thanks for reply bro:)

»
4 weeks 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??

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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?

      • »
        »
        »
        »
        4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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

      • »
        »
        »
        »
        4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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$$$?

          • »
            »
            »
            »
            »
            »
            4 weeks 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.

»
4 weeks 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.результаты

»
4 weeks 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?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I would be thankful if anyone could explain problem C at a beginner level. I'm having a hard time grasping the concept. Or if you don't have time to write the explanation, I wouldn't mind if you can post some tutorials which could help me understand the solution written here.

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

    Let's consider vertex label in positional binary notation.

    Lemma. For any pair of vertices (i,j) there exists position where digit(i)!=digit(j). Evidently.

    Hence, if for each position we ask sets a={digit==0}, b={digit==1}, we will inevitably catch the pair having maximum distance.

    Submission: 53070922

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What my brain can't comprehend is the fact that:

      " [...] if for each position we ask sets a={digit==0}, b={digit==1}, we will inevitably catch the pair having maximum distance. [...] ".

      How does this work? I've spent a bit of time thinking about it, but I just can't seem to understand it. Some basic proof or just an explanation would be really cool.

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

        Let sought-for pair with maximal distance is (i,j).

        By lemma p — position where digits of i and j are not equal.

        But we have already sent query with sets having unequal digits in this position. Just because we have sent such queries for ALL the positions.

        In this query i and j lie in different sets, so dist(i,j) (you remember it's maximal) will be the answer x after this query.

        We process the answer with clause r=max(r,x);. That process I named 'ловити'.

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Can somebody explain me the solution of problem D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -44 Vote: I do not like it

    Here.

    Capture

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it -31 Vote: I do not like it

            Rating

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it +6 Vote: I do not like it
              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it -21 Vote: I do not like it

                Sorry for the rating stereotype. I am not trying to be sarcastic/offensive here. but generally, it seems to me that low rated coders ask questions without googling or reading already provided stuff.

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

                  I think you should change your mentality about low rated coders, and do share any other ideas if you have apart from the editorial given about this problem. :)

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks 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.

»
4 weeks 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....

»
4 weeks 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?

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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!

»
4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks 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'?

  • »
    »
    4 weeks 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").

»
4 weeks 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)

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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.

»
4 weeks 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?

  • »
    »
    4 weeks 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$$$.

»
4 weeks 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

  • »
    »
    4 weeks 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.

»
4 weeks 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.

  • »
    »
    4 weeks 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.

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

Please, an example of solution for problem E. tnks

»
4 weeks 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?

  • »
    »
    4 weeks 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.

»
4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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

»
4 weeks 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?

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain D, what is a in the tutorial

Thanks!

»
3 weeks 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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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