| # | User | Rating |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Since the Polygon tutorial system is currently broken, I will replace the editorial with PDF format. Sorry for the inconvenience!
Problem A was authored by ko_osaga. Code
Problem B was authored by ko_osaga. Code
Problem C was authored by ko_osaga. Code
Problem D was authored by nong. Code
Problem E was authored by ckw1140. Code
Tutorial of Hello 2020
When I open the editorial for problem E, I see the editorial for problem C instead. Can the author fix this, please?
Sorry, it's fixed now.
Challenge of problem E is nice, but i have no idea how to solve it. Could you provide the solution?
You got it wrong for E.
Really liked problems B and C :)
Problem D is a lot more intuitive if you interpret the input as a collection of rectangles, where you are asked if there is a pair of rectangles that overlaps on one axis but not the other. Then a scanline solution is obvious.
Can you please give some good resources about scanline?
Topcoder Tutorials
That was the original formulation. I came up with the conference statement to make this problem much natural ;)
This was eye-opening ! So, the input format is $$$x_1, x_2, y_1, y_2$$$ and we have to look for $$$2$$$ rectangles such that their $$$x$$$-axes coincide but their $$$y$$$ do not or the other way around.
First time, we sort by $$$x$$$ and for every new line segment we process, we keep track of all the line segments it inserts with. We will check if the corresponding $$$y$$$ of the line segment fits in the bounds of all the line segments it has intersected so far.
If you could include this interpretation in the editorial, it would help in understanding a lot :)
To be honest, I think it very much depends on what you're comfortable with (Specifically, users who love geometry would love this interpretation). For me, it was easier to visualize the problem in the current format (interval format), whereas it took me a while to grasp the rectangle interpretation. It is interesting to see how the problem can be solved in so similar ways for seemingly different interpretations.
I used it too :)
When will we be able to submit?
In most contests, submission window opens 2 hours after the contest I guess.
Why people downvote this?
Because it isn't true. Usually you can submit a few minutes after system tests are over.
Now submission is open.
Exactly 2 hours :)
Randomised sol for D
There is another randomized approach involving hashes. You may assign random number to each lecture and then calculate for each interval the xor of numbers assigned to intervals it intersects. Now you should check that every lecture has same hashes in first and second places...
how do you calculate the xor of the intersections?
I think, scan-line should work. When the interval $$$[l_i,r_i]$$$ opens, you put $$$h_i$$$ in the position $$$r_i$$$ and when this interval closes you take the xor of all numbers on the $$$[l_i, \infty)$$$.
It should look like this, but it gets WA-6 and I'm to sleepy to debug it properly.
yeah I did same thing but i get wa-6
the WA is not because of hash collision
you missed the case when 2 intervals completely overlap
Not really, I just made a silly typo in my segment tree code... I got it accepted now: 68205086
Segment Tree is more popular way than multiset for this problem, I think.
It can also be treated as hashing all maximal cliques of the interval graph which should be sufficient for checking the equality of the graphs as the graph is chordal. My code for reference 68181402
Can you tell me where can I learn this stuff about graphs? It would be really helpful of you.
You can look at my submission, I kept two segment trees — in one i put the value of the lecture on the beggining of the lecture and in the other on the end. Then, for each lecture i checked for lectures than do not intersect, so lectures that have end before the current beggining and the same for other side.
I have a rather neat code doing this that might help: 68239280. I used the formula:
. Note that if a lecture ends before $$$l$$$ starts, then it also begins before $$$l$$$ ends so in the subtraction every element of the latter set is contained in the former set. Also note that we do a XOR both when we add and when we remove a set.
My solution uses hashes also :)
Let's calculate value $$$sumA=\sum_{i \, intersects \, j}(h_i\cdot h_j)$$$ by some modulo for segments in A and the same $$$sumB$$$ for segments in B. Here, $$$h_i$$$ are some random values. This can be calculated with scanline. The answer is "YES" iff $$$sumA=sumB$$$.
yeah me too but i got wa-6
Maybe my code will be helpful: 68181544
It doesn't use any data structures. Only two scan lines.
thanks
You can just treat intersections as long number in binary notification (zero means no intersection with given index's segment, one means intersection) and use its remainder as hash. See my submission https://codeforces.net/contest/1284/submission/68191562
I just leave it here. I also assign random number to each lecture, and then calculate some hashes. But to avoid cases when one segment completely inside in other, I just took complement approach. I get hash of all segments that doesn't intersect with selected. They are those who ends before selected, or starts after selected. So, I have two BIT for each place: one for lectures ending at time X and one for lectures starting at time X. This is done with packed coordinates and four BIT for each set of random identifiers. 68198554
Me too.
My randomised solution also passed.
Thank you for setting these wonderful problems. Unlike other geometry probs, E is so beautiful that I was impressed :D
Just what part of E do you think is beautiful? I agree that the model solution doesn't seem bad, but that is only in comparison to how painful writing code for the not-totally-magic solutions is. A problem with many easy to find ugly solutions does not turn good from the existence of a beautiful solution that is very difficult to find.
I don't get the point. If you failed to find good solution, then it's our fault?
Well, I found it really interesting what you can solve it in $$$O(n^2)$$$. 1146H - Satanic Panic is really similar problem and I believe it can only be solved in $$$O(n^3)$$$.
OnionPringles told me about the $$$O(n^2\log n)$$$ solution of that problem. Of course, it's much harder than our problem's solution, in any aspect.
After I found $$$3x_3+4x_4+5x_5$$$ I thought I need $$$x_5$$$... After 4 TLE attempts, I saw the magic :D
Seems like you don't understand what "right after" means.
Right after systest. I'm sorry for F.
Does the following flow solution for F run in time?
Create three sets of nodes A, B, and C. A represents the first set of edges, C represents the second set of edges. We need to match as many nodes in A as we can with nodes in C. Set B represents all the nodes in the tree. Each node in A and C will be connected to the two nodes that the edge it represents in connected to. We then run flow from the nodes in A to the nodes in C.
This graph has O(n) edges and a max flow of O(n).
Actually, nevermind, this just doesn't work
When the codes will be available?
Code is available now.
For F we can prove that answer always equals $$$n - 1$$$ easily using Hall theorem. Pick any $$$k$$$ edges in first tree, we want to prove that there are at least $$$k$$$ edges in the second tree which can be used to replace at least one of picked edges. Let's remove all picked edges from the tree, then it splits to $$$k + 1$$$ components. For each edge in the second tree let's draw an edge between components containing endpoints of the edge. Since the tree was connected before compressing edges it is still connected now, which means it has at least $$$k$$$ edges which are not self-loops, which means there are at least $$$k$$$ edges which can be used to replace one of picked edges.
Sadly this proof gives no clue on how to find the matching
In my solution (tl;dr here), it just turns out while I'm looking for some characteristics of the matching that it is perfect, and the argument for that is kinda similar to Hall's theorem — it also deals with sets of edges in T2 and adjacent edges in T1. It doesn't seem to be particularly useful for finding a way to compute a matching quickly, though.
My solution of F:
Pick a 1 edge (u, v) from the T1, s.t. u is the leaf in T1. We consider a path(u, v) in T2, and take a nearest edge of u in this path(we let (u, w)) (step A). We can find matching, (u, v) in T1 & (u, w) in T2, and remove those edges. For all x($$$x \neq w$$$), if there is a edge (u, x) in T2, we change u to v. it means, remove (u, x) and add(v, x) (step B). As a result, we can remove vertexes u and reduce problem size by one(after operate, T2 remained as tree).
How to simulate? Bottleneck is the step B, changing (u, x) to (v, x). Therefore we don't change all edges, but simply remove (u, w) and add dummy edge (u, v). We have to find nearest non-dummy edge in step A, but it's all. We can easily do it by Link-Cut Tree
Tbh when you have this, there's no need for further tricks or LCT. Just HLD over T1, store not yet taken edges in each path in a set (ordered by depth), DFS over T2 and use HLD to simulate the process for each edge in T2. That's my solution.
I solved step B by merging u,v in T2 by implementing union-find structure on LCT nodes. When merging u and v, cut all preferred children of u and v so that the children can go through union-find structure when they try to access the unpreferred parent. I think it is easy if you have a pre-written LCT code.
You can do binary lifting and dsu, which is much more easier to code than LCT/HLD
I had the same, but tbh in such contests it would be more preferable to just copy LCT.
I updated my solution to F. It is my favorite in this problem set. Hope you liked it too!
Can you explain me why is it true in step B pls, thanks
Here is a more intuitive explanation for E. Sorry if it's mentioned already.
Fix the point $$$p$$$. Translate everything such that $$$p$$$ coincides with the origin. Sort all the other points counter-clockwise. We shall now find the number of quadruples of points that don't form a polygon containing $$$p$$$.
Now consider some point $$$s$$$. Consider the half-plane $$$H$$$ of points $$$t$$$ such that the cross product $$$s \wedge t$$$ is positive. For a quadrilateral with $$$s$$$ to contain $$$p$$$, it has to have at least one point from $$$H$$$ and at least one point not from $$$H$$$. Conversely, we will count the number of quadruples $$$(s, t_1, t_2, t_3)$$$ such that $$$t_1, t_2, t_3 \in H$$$. It is just the binomial coefficient $$$|H| \choose 3$$$.
Now do that for all $$$s$$$ and all corresponding $$$H$$$, in linear time, using the two pointers method.
With iterating over all $$$p$$$ and sorting, the complexity is $$$O (n^2 \log n)$$$.
This solution works for any size of polygon right? For example if the problem was about triangles instead of quadrilaterals
thanks for sharing it btw
Looks like, yeah, the same argument about all points being in one half-plane would work for pentagons and more.
Now, if the problem asks for convex polygons, it gets trickier, even with quadrilaterals.
Where can I learn more about cross products of vectors and how they can be used in geometry problems?
Basically, scalar product and cross product are similar in behavior to cosine and sine of angle between vectors, respectively. Their signs behave the same.
The upside is that, more often than not, we are given coordinates of points as integers (or rationals). And computing scalar and cross products can be done using integers only. So we don't have to resort to floating point and then deal with a whole additional class of errors because of loss of precision.
As for more general overview, a Google search lands some nice articles on the first page.
How can I actually easily find the sign of the cross product between two vectors? I got an idea of how to do it with the angle between them, but it seems ugly and probably prone to bugs.
Edit: I found a way on Wikipedia, scroll down to the Computation Geometry section.
Can someone please explain for B
3
4 2 0 2 0
6 9 9 8 8 7 7
1 6
how is it 7?
Let's say a = [2,0,2,0], b = [9,9,8,8,7,7], c = [6], then the answers are: aa, ab, ac, ba, bb, ca, and cb.
since 2 0 2 0 has an ascent.so total pairs are 3. 2 nd sequence does not have an ascent but pairs (2,2),(2,1) has ascent. similarly for 3rd sequence pairs(3,1) and(3,2) has ascent. so total 7 pairs are possible.
I'm struggling to understand what does "but pairs (2,2),(2,1) has ascent" mean. Can you please elaborate? Thanks!
Thanks I got it!
Let 1, 2, 3 — indexes of arrays. Here is "1 + 2"
"1 + 3"
"1 + 1"
"2 + 2"
"2 + 1"
"3 + 1"
"3 + 2"
At all — answer 7.
For D, removing operation is at time ea_i + 1 ?
UPD: It's fixed.
D can be solved using "Job scheduling " algorithm. Initially we check all the intervals for both the venues individually,whether they overlap,if we get different answer,answer is "NO".
If we get same answer and both timings of both venues don't overlap,then answer is "YES".
If we get "over-lap" for both,there is a possibility that removing some lectures might make one venue overlapping and other non_overlapping
eg: 1 2 3 4
In this case,we use job scheduling algorithm to find the largest no of lectures that can be present such that,lecture timings don't overlap for venue A.
Keep only those lectures for B,check if answer is different for both venues,do the same thing for venue B.
68206806
AjaySabarish Hi, can you please explain the part about "non over-lap" in a little detail?How is there a possibility that removing some lectures might make one venue overlapping and other non_overlapping? I also thought about job scheduling algo but as mentioned in comments, did not consider such cases like finding interval in a and then checking them in b and vice versa. Do they both not give same result?
Sry there was a typo,now corrected
Still can you explain that point about removing some lectures?
Consider the above example,which I gave
3
1 2 3 4
3 4 4 5
4 5 6 7
Now,the timings overlap for both venues,but if you remove lecture 3,timings dont overlap for venue A but overlap for venue B.
This is the last case which I was talking about,now you have to use job scheduling to find the answer.
Find the highest number of non overlapping segments for A,it is lecture 1,2.
Now keep only these lectures for both venues,now the segments for B should also not overlap for "not venue sensitive". But it is overlapping,so it is venue sensitive
The test cases in D were very "weak". My solution : 68205621
For very large N, it's enough to only check if each of the lectures have the same number of intersections in A and B. Taking advantage of the fact that it's hard to put up a test case that avoids being fooled that way.
but how will you calculate the intersections in O(n) time.Can you explain once more??
Can you share other solutions to E? Except Gassa's (above)
I'll put it short:
My solution is pretty much the same as molamola's solution and I think it is not necessary to do a cool angular sweep:
Let $$$X$$$ be the number of $$$((A,B,C),D)$$$ such that $$$D$$$ lies in $$$ABC$$$ and $$$(A,B,C)$$$ is an unordered tuple. The answer is $$$(n-4)X/2$$$.
$$$X$$$ can be counted easily: fixing $$$D$$$ and sort other points by the angles, then do a bunch of lower bound.
Thanks for sharing. The solution in Editorial really beautiful, but I don't know. Is that possible to came up with such solution in ~1 hour?
Actually my solution submitted during the contest is exactly same as the tutorial solution. In fact, I tried to compute all of $$$x$$$, $$$y$$$, and $$$z$$$, so I double-counted not only the edges of the convex hull but also the diagonal edges, to obtain three linear equations.
Unfortunately, this linear system was undetermined, and all I can get was $$$(y + 2z)$$$. That was when I felt quite disappointed. But surprisingly, the answer to the problem happened to be exactly $$$(y + 2z)$$$, so I could finally solve the problem.
At first, I thought I was lucky enough to find a solution with such unsolvable system. So I headed to this tutorial to read the "official" solution, only to find my solution again. Thanks to your question, I found it in the comments :-)
68196878
Just curious,did everyone who solved C in contest,prove the solution?It was not so obvious to me,deciphering and processing what a "framed segment" is,took a lot of time.
Finding pattern was quite difficult,as manually generating test case even for n=4 is difficult
Lot of people solved it,is there any other idea?
Hi, If you now know what a "framed segment" is, then try to formulate number of "framed segment" of a particular length for a given n. For example: if we want to count "framed segement" of length 1. Let's first consider all "framed segment" containing only digit 1. For this "framed segment" to be at leftmost, there are (n — 1)! permutations. Similar argument goes for its other positions as well. This gives us count : (n — 1)! * n. Now, there are total of n single digits like "1" which can make single length "framed segement". Thus now count for all single length "framed segement" is : (n — 1)! * n * n (something missing?). I have tried to explain the solution with single length fragment above with some details missing which I think you will figure out. Please try to come-up with a general formulation for any "framed segment"length x for a given n. Summing it all up will give you the answer. Link to my submission : Here
Thanks a lot,I get the solution,but I am just curious about the high number of submissions,was it so obvious?did everyone actually prove it or used their intuition to get it?
I guess that depends on one's way of counting up to the answer. And from the number of submissions, it feels like people are actually good at counting..:P
Hi, I think I found a test case for problem D where my solution gets accepted but it should be incorrect.
I've checked with the code given in the tutorial, the answer is NO, but my solution gives YES. 68207409
I've modeled it as a graph and put an edge (u, v) if lecture u and v meet. I thought it would be enough to check two things for graph A and B (venue A and B)
I've submitted it after the contest so it doesn't effect my ratings, but I thought it was worth mentioning.
I made the same mistake. I tried to find a test case where this is not true, but I could not. Thanks you
Solution for B [Best :- O(n) Worst :- O(nlogn)]
https://codeforces.net/contest/1284/submission/68210022
The condition for a non-ascent sequence a and a non-ascen sequence b to form an ascenting sequence is
min(a) <max(b)cnt = cnt + 2*n-1n--;because that sequence will form 2n-1 sequences on concatenationSort the max and min vectors then use two pointer approach.
Involving sort gives already nlogn solution) - my code — P. S. I have similar solution, but simpler.
Someone please explain me the meaning of the last statement in C. "By observing that there exist exactly n−len+1 pairs with 1≤l≤r≤n,r−l+1=len, we can simply multiply this number for each length, giving a O(n) time solution." Please give any example.
Example of what is it about:
Consider n of 5 and len of 3
1 2 3
2 3 4
3 4 5
Permutate each of them, and you will get all framed subarrays for n and len of the example.
Can anyone explain to me the solution of problem C in a better and intuitive way?
I have tried to explain in my comment : https://codeforces.net/blog/entry/72804?#comment-570899. I hope it's helpful
let's take n = 5. ar = [1,2,3,4,5] . Now iterate for all possible length of sub-array and count number of good sub-array for that length. k = 1, 2, 3 and so on.
let take say k = 2 and n = 5. So there are n-k+1 position possible to place k elements i.e If we consider [1,2] then we can place [1,2] in position _ 3 _ 4 _ 5 _ and you can select (n-k+1) elements from n elements to i.e [1,2] , [2,3] , [3,4] and [4,5] . So this is how we got (n-k+1) * (n-k+1) and now we just have to count number of possible permutation of k and (n-k) elements left which is nothing but k! and (n-k)! .** (n-k+1) * (n-k+1) * k! * (n-k)!** is the total answer
But would that not lead to overcounting.
Consider the case 3 (1 2) 4 5 and 3 1 2 (4 5).
These 2 permutations are same and will be counted twice, once when we consider 1,2 together and second when 4,5 are taken together.
If in question C, we have given a permutation of length n then we need to find happiness... Anyone want to share their approaches ..
I have tried to explain in my comment : https://codeforces.net/blog/entry/72804?#comment-570899. I hope it's helpful
Shouldn't it be eai + 1 in D tutorial?
I had a overkill solution for $$$D$$$ which led to a good data structures problem. While, others have provided much more elegant solutions, this reduced version is a good problem on its own and worth sharing.
Here's the problem:
You are given two sequences $$$a_i$$$ and $$$b_i$$$ of length $$$2N$$$ each. Each number from $$$1$$$ to $$$N$$$ appears exactly twice in both the sequences. You have to solve $$$Q$$$ queries of the following kind:
Given $$$l$$$, $$$r$$$, $$$x$$$ and $$$y$$$, find the set of distinct elements in $$$(l, r)$$$ in $$$a$$$ is exactly equal to the set of distinct elements in $$$(x, y)$$$ in $$$b$$$. That is, any number $$$u$$$ has an appearance in segment $$$(l, r)$$$ in $$$a$$$ if and only if it has an appearance in segment $$$(x, y)$$$ in $$$b$$$. Try to solve this online in $$$O((N+Q)\log(N))$$$.
Think of how you can reduce today's $$$D$$$ into this problem.
My code for today's D: 68189310
In D: "Event removing interval [sbi, ebi] from S at time ebi+1."
ko_osaga, I think you made an error here, it should be eai + 1 instead
Sorry, fixed.
Problem B can also be solved in $$$O(n)$$$. Be $$$asc$$$ the number of sequences that have an ascent. For each sequence, check if it's non-increasing. If it isn't any concatenation we do will have an ascent, so we can add $$$n$$$ to our answer and $$$1$$$ to $$$asc$$$. Now be $$$s$$$ a non-increasing sequence and let's set it as the right part of the concatenation. We will only have an ascent in the concatenation if the left part already has an ascent or has an element smaller than any element in $$$s$$$, specially it's maximum. We have $$$asc$$$ sequences of the first type, so that's easy, and for the second part we can precalculate it by creating an array $$$minfreq$$$ where we store the minimum of each non-increasing sequence in it's position (as $$$s_{i,j} < 10^6$$$) and do a sweep from $$$1$$$ to $$$10^6$$$ to accumulate our sum ($$$minfreq[i] = minfreq[i-1] +minfreq[i]$$$). Now we have our answer for the second part in position $$$minfreq[max(s)-1]$$$, and we can just add both parts to our answer. Since we can precalculate $$$minfreq$$$, $$$max(s)$$$ and $$$asc$$$ in $$$O(n)$$$ and the answer can be calculated in $$$O(1)$$$ using our precalculations total complexity is $$$O(n)$$$
Yeah, the same idea with you!
I did the same, but this is not O(N). The time Complexity will be O(n + maxELE) where maxELE is the largest sequence element seen in input.
We were lucky that the constraint on that wasn't 10^9.
Also consider cases in which n = 5 but the elements are still very large, our code would still take lot of time to execute.
Yeah that's true, the editorial's solution is more general for that same reason
I cant understand the minfreq[i]=minfreq[i−1]+minfreq[i] . can you explain me
It's called accumulated sum. Basically we want minfreq[i] to be the frequency of all numbers $$$\leq$$$ to i, so we need to push our previous array position to our current one, so that we also take into account the occurences of numbers < i, and not just equal to i
How to count different quadrilaterals in problem E?
1146H - Satanic Panic
For example, for each pair of points $$$(i, j)$$$, we can find the number of points on one side of the line i-j ($$$a$$$), the number of points on the other side ($$$N-2-a$$$), sum that up, divide by 2 and subtract $$$2{N\choose 4}$$$. Why? For each 4-tuple of points, if one of them is inside the triangle formed by the other 3 (their convex hull is a triangle), we get 3 lines (inner point, some other point) that are counted here, and when their convex hull is a quadrilateral, we get 2 such lines — its diagonals; we subtract (2 * number of 4-tuples) to get the number of 4-tuples where one point is inside.
How to find these $$$a$$$ for each pair $$$(i, j)$$$ fast? Let's say that $$$i$$$ is fixed, sort all remaining points by their angle around point $$$i$$$, then consider a line that crosses $$$i$$$, start rotating it and whenever it crosses one of these points, update the current value of $$$a$$$.
Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).
Could anyone give me a more elaborated explanation for problem D, I didn't grasp the editorial at all.
Expected a matroid problem, as ko_osaga took matroid class last semester XD
matroid fan club!
Hack Test for D 1284D - New Year and Conference
4 1 10 51 60 2 20 44 52 3 40 43 45 42 45 50 50
Actually, Problem G can be solved easily by matroid intersection. Consider two matroid M1(S,I),M2(S,I), S is the set of wall, M1 is a graph matroid , M2 is a matroid which any black cell has at least to side without wall. Code: https://codeforces.net/contest/1284/submission/68215804
Is there anyone who solved D using coordinate compression and prefix sum ? If so, could you please share your submission.
Why does D need to check in two directions? If I check in one direction, I get wrong answer at 9th point. But I think it is appropriate to check in only one direction.
MikeMirzayanov may as well check how many visits were made to this page and later to this page in contest time
How does that problem help?
Re: "Hopefully, the first 80 tests were good enough for the contest."
My random solution fails on test 87 :) Great job making the tests indeed!
In Problem D, why does this solution not work? My Solutions is this.
Sort lectures according to their start-ending time in both venue, Then decide every lecture if it intersects with others in their own venue.
If there is at least one lecture that make difference in intersecting in both venue, then Subset can not be made. So the answer is no. If every problem either intersects in both venue or does not intersect in both venue then answer is yes. Here is my implementation 68294866
Please someone enlighten me where I am misunderstanding.
In problem D, I got wrong answer on test case 14. Can somebody please help.
2020 begins with two matroid problems. XD
btw, Challenge in Problem F is called Strong Basis Exchange as in here.
I am not able to understand problem B's solution.. can anyone please help me out..??
Why don't we have to consider the case when there's some period intersecting in A and not intersecting in B? Doesn't that mean that sometimes our code will say 'YES' but the answer is 'NO'. Why? 1284D - New Year and Conference. EDIT: Ok, I just didn't notice the part of the code where he does the same thing but reversed.
What is the hash approach for the problem D?
there is a proof for C solution ?
Here is something, that I could think of.
For each permutation, we have the same $$$r-l$$$. This value varies from $$$0$$$ to $$$n-1$$$ for all $$$n$$$. Now let us consider $$$r-l=d$$$, as a general case.
For each $$$n$$$, we have $$$n-d$$$ pairs of $$$[l, r]$$$, where $$$r-l=d$$$. Also for all numbers from $$$1$$$ to $$$n$$$, we have $$$n-d$$$ pairs of type $$$[i, j]$$$ such that $$$j-i=d$$$.
For a segment to be framed, all the other places for each $$$[l, r]$$$ must be occupied by each integer from $$$[i, j]$$$. Therefore, we have $$$d+1$$$ numbers to be arranged in this interval $$$[l, r]$$$ and $$$n-d-1$$$ to be arranged in $$$[1, l-1]$$$ and $$$[r+1, n]$$$. This can be done in $$$(d+1)! * (n-d-1)!$$$ ways.
But we have $$$n-d$$$ pairs of $$$[l, r]$$$ and $$$n-d$$$ pairs of $$$[i, j]$$$, each of which can occupy this segment. Therefore the answer becomes summation over all $$$d$$$ from $$$0$$$ to $$$n-1$$$: $$$ans = ans + (n-d) * (n-d) * (d+1)! * (n-d-1)!$$$
In problem C , do we consider that the numbers inside a particular segment [l,r] could be different such that, max-min = r-l
In Problem D I added elements in the segment tree in the decreasing order of eai and then I queried for the previous range if the min of the ls and the maxr intersect with the particular index of a I am addding . I am getting a WA at Test Case 7 for this submission.
This is my submission link: https://codeforces.net/contest/1284/submission/91535000
Can somebody help me with this solution where I went wrong?
Or is there anyway I can look at the whole testcase then please reply here about how can I do that?
Never Mind I made a silly typo in the cmp2 function.
Hi, I am not able to understand the editorial for problem C. can anyone break it down in easy way please ?
Hello, this seems to be broken (perhaps a sign of how the year 2020 has been so far)
MikeMirzayanov please take a look, thanks!
This question relates to problem B. I have a question with the second example input. Here is the input:
I believe all arrays have an ascent. In the first array, the pair $$$(i, j) = (3, 4)$$$ works. ($$$a_3 = 0, a_4 = 2.$$$) In the second array, the pair $$$(i, j) = (1, 2)$$$ works. ($$$a_1 = 6, a_2 = 9.$$$) In the third array, the pair $$$(i,j) = (1, 2)$$$ works. ($$$a_1 = 1, a_2 = 6.$$$)
Thus, shouldn't all pairs of arrays in this case work? There are $$$9$$$ such pairs, but the answer to this should be $$$7.$$$ What is wrong with my reasoning here?
Editorials that didn't age well...
Sorry for the issue with editorials. I think there is a timeout issue from Polygon. Since I can't resolve it, I will just rewrite it as a PDF form and upload here.
Weak test cases for D. Consider the following test case
My accepted solution gives YES but the answer is NO.
In case someone needs help with problem B, this might help.
https://codeforces.net/contest/1284/submission/147841447