Forethought Future Cup Elimination Round Tutorial

6 лет назад, # ^ |

+10

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

→ Ответить

codeanna

6 лет назад, # |

can anyone explain the E tutorial...

→ Ответить

snuke

6 лет назад, # |

← Rev. 2 →

+10

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

Solution

Sort directed edges by gradient.
Calculate dp[s][t][l] = number of convex polyline starting from vertex s ending at vertex t containing l edges.

for(e in edges) for(s in 0..n) for(l in 0..4) dp[s][e.t][l+1] += dp[s][e.s][l];
for(v in 0..n) answer += dp[v][v][5];

my submission

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

→ Ответить

liit_mixer

6 лет назад, # |

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

→ Ответить

Ozymandias

6 лет назад, # ^ |

← Rev. 6 →

-33

Binary search:

Binary search solution

#include<bits/stdc++.h>
using namespace std;
int ask(int n1,int n2,vector <int> v1,vector <int> v2){
    cout<<n1<<' '<<n2<<' ';
    for(int k=0;k<v1.size();k++)
        cout<<v1[k]<<' ';
    for(int k=0;k<v2.size();k++)
        cout<<v2[k]<<' ';
    cout<<endl;
    fflush(stdout);
int h;
cin>>h;
return h;
}
main(){
int t;
cin>>t;
while(t--){
    int n;
    cin>>n;
    vector <int> v1,v2;
v1.push_back(1);
for(int k=2;k<=n;k++)
   v2.push_back(k);
int p=ask(v1.size(),v2.size(),v1,v2);
int l=2,r=n;
while(r!=l){
    int mid=(l+r)/2;
v2.resize(0);
for(int k=l;k<=mid;k++)
    v2.push_back(k);
int s=ask(1,v2.size(),v1,v2);
if(s==p)
    r=mid;
else l=mid+1;
}
v2.resize(0);
v1.resize(0);
v1.push_back(l);
for(int k=1;k<=n;k++)
    if(k!=l)
    v2.push_back(k);
int ans=ask(v1.size(),v2.size(),v1,v2);
  cout<<-1<<' '<<ans<<endl;
    fflush(stdout);
}

→ Ответить

malviyanshiv

6 лет назад, # ^ |

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

→ Ответить

NguyenfromVN

6 лет назад, # ^ |

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.

→ Ответить

chemthan

6 лет назад, # |

+34

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

→ Ответить

Juve45

6 лет назад, # |

+28

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

→ Ответить

codeanna

6 лет назад, # ^ |

Sir, can u explain little more...

→ Ответить

Juve45

6 лет назад, # ^ |

← Rev. 2 →

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.

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]$$$
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.

→ Ответить

codeanna

6 лет назад, # ^ |

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

→ Ответить

Golovanov399

6 лет назад, # |

+45

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";

→ Ответить

KetchupZ

6 лет назад, # |

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

→ Ответить

continuity

6 лет назад, # ^ |

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

→ Ответить

KetchupZ

6 лет назад, # ^ |

OK，thank you!

→ Ответить

Sturdy

6 лет назад, # |

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

→ Ответить

harshhx17

6 лет назад, # ^ |

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

→ Ответить

NoobCoder1998

6 лет назад, # |

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

→ Ответить

continuity

6 лет назад, # ^ |

← Rev. 3 →

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

→ Ответить

shan61916

6 лет назад, # |

  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??

→ Ответить

NewRules

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

shan61916

6 лет назад, # ^ |

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

→ Ответить

NewRules

6 лет назад, # ^ |

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 bit^th 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.

→ Ответить

tantam75

6 лет назад, # ^ |

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.

→ Ответить

Sturdy

6 лет назад, # ^ |

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

→ Ответить

tantam75

6 лет назад, # ^ |

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.

→ Ответить

Sturdy

6 лет назад, # ^ |

Thanks for explaining

→ Ответить

NewRules

6 лет назад, # |

+27

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

179000

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

wireless

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

kumarpratyush4

6 лет назад, # ^ |

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

→ Ответить

ZhouShang2003

6 лет назад, # |

-38

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

→ Ответить

KetchupZ

6 лет назад, # ^ |

Code all night。。。

→ Ответить

pupiI

6 лет назад, # |

← Rev. 2 →

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?

→ Ответить

6 лет назад, # ^ |

I fixed it. Should be $$$(j-d_i+1)/a$$$

→ Ответить

pupiI

6 лет назад, # ^ |

thanks xD

→ Ответить

6 лет назад, # |

+16

Can somebody explain me the solution of problem D?

→ Ответить

6 лет назад, # ^ |

-44

Here.

Capture

→ Ответить

6 лет назад, # ^ |

+21

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

-43

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

→ Ответить

6 лет назад, # ^ |

+11

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

→ Ответить

Have you just breathed your last breath?

6 лет назад, # ^ |

-31

Rating

→ Ответить

abandonedw1

6 лет назад, # ^ |

→ Ответить

6 лет назад, # ^ |

-21

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

nikolapesic2802

6 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

pepelats

6 лет назад, # ^ |

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

→ Ответить

nikolapesic2802

6 лет назад, # ^ |

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

→ Ответить

pepelats

6 лет назад, # ^ |

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

→ Ответить

crazy__1234

6 лет назад, # |

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

→ Ответить

Araomis

6 лет назад, # |

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?

→ Ответить

bruno.iljazovic

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Araomis

6 лет назад, # ^ |

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

→ Ответить

shivank98

6 лет назад, # |

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.

→ Ответить

brainfxxk

6 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

losmi247

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

VLamarca

6 лет назад, # |

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)

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

Svlad_Cjelli

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # |

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

→ Ответить

Swistakk

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

Swistakk

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

aditya_sheth

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

+36

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$$$.

→ Ответить

dendrite5460

5 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить

dendrite5460

5 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

dendrite5460

5 лет назад, # ^ |

← Rev. 4 →

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

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

duyiblue

5 лет назад, # ^ |

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

→ Ответить

Ex-Jmokut

6 лет назад, # |

+13

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

Swistakk

6 лет назад, # |

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.

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

ale

6 лет назад, # |

← Rev. 2 →

Please, an example of solution for problem E. tnks

→ Ответить

Ra16bit

6 лет назад, # |

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

→ Ответить

sping128

6 лет назад, # ^ |

+10

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

→ Ответить

ILoveBitches

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

ILoveBitches

6 лет назад, # ^ |

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

→ Ответить

TianyiQ

6 лет назад, # |

← Rev. 4 →

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?

→ Ответить