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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3520 |

2 | tourist | 3461 |

3 | Um_nik | 3367 |

4 | apiadu | 3351 |

5 | mnbvmar | 3332 |

6 | Benq | 3330 |

7 | LHiC | 3276 |

8 | TLE | 3271 |

9 | Radewoosh | 3251 |

10 | ecnerwala | 3241 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 189 |

2 | Errichto | 188 |

3 | tourist | 180 |

4 | Radewoosh | 173 |

5 | vovuh | 166 |

6 | pikmike | 165 |

7 | ko_osaga | 162 |

8 | Um_nik | 161 |

9 | rng_58 | 155 |

10 | farmersrice | 153 |

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

Tutorial is loading...

First solve: tourist, 00:00:50

Tutorial is loading...

First solve: tourist, 00:02:37

Tutorial is loading...

First solve: tourist, 00:05:09

Tutorial is loading...

First solve: tourist, 00:12:53

Tutorial is loading...

First solve: tourist, 00:27:19

Tutorial is loading...

First solve: tmw168_orz, 00:16:00

Tutorial is loading...

First solve: 300iq, 00:24:05

Tutorial is loading...

First solve: snuke at 00:59:44

Tutorial of Forethought Future Cup - Elimination Round

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/23/2020 21:30:12 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Very Fast Release. :)

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

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

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.

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

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

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?

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

can anyone explain the E tutorial...

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

SolutionSort directed edges by gradient.

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

my submission

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

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

Binary search:

Binary search solutionCheckout this one: https://codeforces.com/contest/1146/submission/53065522

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.

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

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.

`> 6`

. This means that after this, all the element with absolute value greater than 6 will be -6 in the end.`< 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.At each step we keep a vector with current absolute values and positions of the

activeelements that are not currently assigned. When we fix a value for an element, we remove it from the vector withactiveelements.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

Sir, can u explain little more...

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

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

`> 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 beswapped). 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]$$$`> 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.

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

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

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

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

OK，thank you!

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

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

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

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

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

What is this part doing, for problem C.anyone??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.will that guarantee that each pair is once splitted into 2 different group?

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

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

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.

Thanks for explaining

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

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.

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

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.

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

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.

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

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

Code all night。。。

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?

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

thanks xD

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.

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

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.

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 'ловити'.

Can somebody explain me the solution of problem D?

Here.

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

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

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

Rating

Have you just breathed your last breath?

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.

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

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.

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

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

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

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

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?

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

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

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

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.

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

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

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)

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.

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.

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

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.

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.

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.

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

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

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

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

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

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

@bmerry Thank You

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

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://codeforces.com/contest/1146/submission/53095272

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

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

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 pIt was shorthand for the things I said in the previous paragraph. I edited it so it uses the full words instead of the letters.

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.

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.

Please, an example of solution for problem E. tnks

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

I think the source is connected to node

`(i, 0)`

for all`i`

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

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.

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

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?

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

Ah, I see. Thanks a lot!

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

Thanks!

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.

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

Wow, nice observation)

http://hos.ac/contest/xmas2012/problems.pdf problem G is problem H from this contest...