새해 복 많이 받으세요, 코드포스! (Happy new year, Codeforces!)
Welcome to the first Codeforces Round of the new decade, Hello 2020! The round will be held on Jan/04/2020 15:05 MSK.
Some information about the round:
- Div 1, 2 combined
- 2.5 hours!
- 7 problems!
- No subtasks!
- Score distribution: 500-1250-1750-2500-2750-4000-4000
- Yes, it is rated!
This round is prepared by ko_osaga nong ckw1140. I am personally very thrilled to deliver my first Codeforces contest as such a memorable one!
More credits for the contest:
- Coordinator: 300iq
- Testers: kdh9949 kriii OnionPringles molamola. evenharder jihoon DongwonShin xiaowuc1 998batrr KAN Diuven
- Great Codeforces and Polygon: MikeMirzayanov
UPD: Editorial. Thank you for your participation!
UPD2: Winners:
First comment of the decade on a CF round blog.
Happy New Year!
No offense, but how can a blue coordinate a round written by orange writer? not to say such an important round.
Don't judge 300iq by its color.
yea,300iq is the best..!
300iq is not blue pal
Yes, he was the worst coordinator I've ever met in preparing CF round.
Hey, sorry, we decided to change all your problems with my problems.
It is no longer Wednesday my dudes.
Well, he is also the best coordinator you have ever met, since it's your first contest.
It's because of magic , in fact he is legendary grandmaster , but he have changed his colour . exactly like you , a green grandmaster :)
r/woooosh
Please don't link subreddits outside of Reddit
How dare you say that to the king of dank memes?
Do you know the meaning of word sarcasm?
Such shame that you don't who he is.he got rank 2 in IOI 2018
He didn’t participate in IOI 2018.
Hello ko_osaga!
Where's the interactive :o
The decade starting with Korean round! This is so great!
Hi ko_osaga.
Hi "user ainta", hope u and cafe mountain get the 1st place this year ^_^
Hi ko_osaga
Hi ko_osaga
Hi ko_osaga!
everyone can participate?
Yes
good thanks
The first contest in2020.Hope everyone can get a good place！
Then who will get the last places?
One of those guys who want to do poorly such as CyanGuy
Hope I will became expert for first time in this round!!!
But you are already a legendary grandmaster :-)
LGM's can become an expert too.
Hello 2020!
Кажется, что подзадачи на cf стали настолько нормальной практикой, что контест, который обходится без них, воспринимается как нечто необычное и хорошее, раз составитель отмечает это.
But it is not the new decade, except you consider that every year(not only year, it can be month, day, etc.) starts a new decade, with start in that year. Now it is 21 century, it started on January 1, 2001, not 2000. And this year is not a first year of 203 decade, it is the last year of 202 decade.
For your information, ISO 8601 defined decade like this.
3.1.2.22
decade
time scale unit (3.1.1.7) of 10 calendar years (3.1.2.21), beginning with a year whose year number is divisible without remainder by ten
they define century as time scale unit (3.1.1.7) of 100 calendar years (3.1.2.21)duration (3.1.1.8), beginning with a year whose year number is divisible without remainder by 100 which is let's say questionable
I always hope that every people count centuries in 0-indexed style.
hope pretest passed => system test passed
more likely pretest passed >= system test passed
more likely pretest passed == system test passed + hacked;
more likely pretest 1 passed
=> is an "implied" sign
Waiting for anyone asking if it's rated or not..
And getting downvotes :P
i hope that my rate exceeds 2020 Through 2020
Is the score format like educational rounds or like goodbye 2019 ?
Like goodbye 2019.
Thanks
Good competition is coming. (Radewoosh, EvenImage and tourist)
다들 새해 복 많이 받으세요~~ happy new year~~
I am very sad that I have no time.For a terrible exam. o(╥﹏╥)o
good bye 2019
⠀ ⠀ ⠀ ⠀
Yeah, man.
Wow!! I can't wait!!!
2020!
ko_osaga On a genuine note, in last contest too, it was said there wont be any subtasks but there were subtasks. If there are going to be subtasks, then please don't say "No subtasks"
There weren't subtasks in the last contest.
Really NOT friendly for US time T_T TAT TvT TwT
I have a suggestion guys. It would be great if the problem setters include some ques on Graphs an Trees in any of the A,B,C,D ques of the contest . It is generally there on the E,F ques which a not so good programmer like me find it too hard to solve and doesn't get enough exposure of these kind of problems in the real time.
A B C graph problems is kinda boring or well known .. if not contest would be unbalanced
Welcome 2020!
I admire the Coordinator because he usually makes simple problem statements that are easy to read and understandable.
Happy new year!
Wow there is more than 14,000 registeration.
Yes, it seems to be the contest with the most registration in the history.
Yes. Exceed Codeforces Round 595 (Div. 3) and go to 15,000...
Now it also goes to 15,000...
Ceremony sense of New Year
The prize of the contest has no T-shirt?
Happy New Year!
Look like, it going to be first contest in codeforces with 15000+ registrations.
UPD -: 15000+ registrations achieved.
Now it has come to that.
Happy New Year, Codeforces...!!!
Korean round assa!
.
15k+ registration
I think it is highest ever. Best of luck for all and server as well as.
$$$15521$$$ registered users, I think it would be wiser not to participate, as the servers will surly suffer :(
But if there is less query problem, the server would rather less suffer.
There will be a lot like you to reduce the load of server so that other can participate safely.
Oh Oh, 15k5 Participants @@
Queueforces for the first contest of this decade...
Edit: Sorry seems it didn't matter much. Next time I will sent such comment after contest.
tough one
I am new to CF. The submission result alarms me each time, as my logic works alright in IDE, but here it says it's an error
Tough!
Hardest contest I had participated so far
Seriously why this tough !! :(
What is TC9 in E ?
Mostly, it will fail if you use atan2.
Why? atan2 is a cpp function. Isn't that supposed to work correctly?
Precision error is too big to even considering passing it.
It is interesting that even atan2l which uses Long Double has not enough precision to pass...
Hm, somehow my atan2 passed system tests...
Same here. I used
long double-edatan2function and it passed. Somebody please hack my solution if you can.What is the idea to solve B other than segment tree?
How can It be solved using segment tree?
I don't know efficiently count every subsequence how many number bigger than x, or lower than x but discard that for next subsequence, so I calculate from segment tree 0 to x, or x to 1e6
Use prefix sums instead of segment tree.
If a subsequence already has an ascent, add n. If not, add (# of subsequences that have an ascent) and all subsequences that have a max value greater than this subsequence's min value (and do not have an ascent). To do this query fast, I used a suffix array from 1 to 1e6 for suffix[i] = number of sequences with max_value >= i that do not have an ascent.
ah, I just realize why suffix or prefix is good enough thanks!
I implemented exact this approach, what's wrong with my submission 68210144? I got WA on testcase 21.
Binary search?
yupp, I also used binary search to solve B.
binary search works
with binary search
First, count the sequences already with an ascent (let there be
ascof them) and discard them. Then interpret all remaining sequences as line segments (from their min value to their max value), create 2 events (start and end) for every one, and sort them. Use that to count how many segments start after the current segment ends for every segment and sum these numbers, i.e. find the number of non-overlapping segments, and use that to find the number of overlapping segments (m*m - non_overlapping_countwheremis the number of remaining segments). The answer ism*m-non_overlapping_count + 2*n*asc - asc*asc(add pairs of sequences where at least one already has an ascent, and subtract those where both do).So, there can be two types of valid concat. One is ascents exists in either the s_x or in s_y, second is smaller element exists in s_x and greater element exist in s_y.
So if we find an array where we got a ascent, we can pair it with all arrays. Now, we will count how many subarrays of type two exist. for each array which doesn't contain any ascent, you can pair this with such type of array where the maximum element is greater than the minimum element of the current array.
68188241
Why so many downvotes? My solution is accepted using segment tree, but I'm sure it should be not the intended solution. That's why I'm asking here
Good contest, thanks!
How to solve D?
Instead of checking subets, check only pairs.
I got that, but how to even check that in the required time.
Let's denote first range as $$$[a_i, b_i]$$$, and second range as $$$[c_i, d_i]$$$. Sort by a, add all $$$[c_j, d_j]$$$ where $$$b_j \lt a_i$$$ into some data structure(You can use BIT). Now check if there is intersection with segment $$$[c_i, d_i]$$$ with BIT(Don't forget case when your segment fully lies inside another segment).
My idea was the following.
Suppose you have a graph for each venue. Vertices are the intervals, we connect them only if they don’t intersect. The problem asks if those two graphs are equal.
The size of each graph is quadratic, so you can’t just create them and compare. My idea was to make the hash of each graph and compare them. For each vertex you can get the sum of its neighbors indices multiplied by some power of 2s .You can check out the hashing method in more details in my solution.
Did anyone else solve the same way with hashing?
I check all intervals that start after the current one and all intervals that finish before the current one on both sets and check that their hashes are equal. Hashes are xor of random 64 bit numbers assigned to each interval.
Update: Idea was correct, there was a bug in the code
I tried the same hash. Got WA on test 16.
I did the same, but instead of using xor, I used multiplication on Zp for large prime p (1000000007)
I also used hash, but I wonder if there are other ways to solve it (deterministic, also easier to implement.)
68193999 2 segments [u,v] and [x, y] are NOT intersecting if either y < u or v < x. With the use of multisets, you can bulk check if a segment is NOT intersecting with any of many other segments. This will take O(logN) time. Do this for each segment and you get O(NlogN) time. I saw many solutions with segment trees, this one uses only STL.
I solve it with hashing too, but way different that what you are doing. I hash for every element the set of neighbors and compare each pair of sets.
For each vertex you can get the sum of its neighbors indices multiplied by some power of 2s
How do you do that if it's a complete graph?
Sort based on left coordinate and use suffix sums. Then do the symmetric procedure with reversing the segments.
In D, I figured out one observation, say intervals at the same indices at venue A and venue B must have the same number of overlapping intervals. This is a necessary condition and we can also easily prove by induction that it is sufficient condition as well.
Now the task is to calculate the number of overlapping intervals for each index which can be easily calculated using sorting.
Interesting. I realized it was necessary but it wasn't evident to me that it was sufficient
It is sufficient when n=2, Now say it is sufficient for n=k(Somehow we figured out the number of overlapping intervals for each index), For n=k+1 if we have updated counts and result for n=k we can easily update it for n=k+1, Hence It is sufficient.
Umm, no. That is not sufficient. I am not sure how this passed, I have hacked your solution :). Poor test data?
Here's a counter case:
Yes , the test cases are very weak for D
Oh gosh! I am lucky. :P
How to solve E?
Let K be the sum of the points lying inside each triangle. The answer is: K * (N-4) / 2;
How to calculate K?
For each triangle, calculate the number of points in it. To do this, we calculate for each segment the number of points under it. Now we can calculate the number of points in the triangle for $$$O (1)$$$, we just need to analyze the cases.
And don't forget about pragmas.
I thought there's some cleaner logic to compute this. But I guess it's easier if one already has that code for some other task sitting in their computer and pastes it straight away.
What about not computing K? xd
I didn't use any prewritten code and it took me 15 minutes to solve this problem. Learn how to solve geometry problems instead of complaining.
I think further simplification might make this easier.
Instead of calculating no of points inside every triangle, we can just subtract no of convex quadrilaterals, which then gives;- $$$ K = \binom{n}{4}- num of line segment intersections $$$
Since diagonals of convex quadrilaterals intersect.
I think line segment intersections is a well known problem. However, I didn't have sufficient time left to code it during the contest, so the formula is unverified, please let me know if there are any mistakes.
How were you considering computing the number of segment intersections?
Ah, my bad. I thought Bentley ottoman would work fine, didn't remember about the no of intersections being in complexity.
Fix the point which lies inside. make it center and sort the rest of the points ccw wrt the center. Now we can count the number of triangles using prefix sums of number of points that give positive cross product for each point.
Goal : A point $$$p$$$ and a set of $$$N$$$ points $$$S$$$ are given. We want to compute the number of triangles containing $$$p$$$.
We can easily know that the answer is "$$$N \times (N-1) \times (N-2)/6$$$ — (the number of triangles which do NOT contain $$$p$$$)". If the triangle $$$s_1 s_2 s_3$$$ does not contain $$$p$$$, then there is a straight line $$$l$$$ that splits $$$p$$$ and three points $$$s_1$$$, $$$s_2$$$ and $$$s_3$$$. Thus, we can design the algorithm below:
Consider the line $$$l$$$, which passes the point $$$p$$$.
Rotate $$$l$$$ about $$$p$$$.
When $$$l$$$ touches a point of $$$S$$$, compute the number of points that are on the left side of $$$l$$$.
Let $$$k$$$ be the number, then add $$$(k-1) \times (k-2)/2$$$ to the answer.
Do the step 2. to 4. until $$$l$$$ is rotated by 360 deg.
The naive algorithm is $$$O(N^2)$$$. But you can do it in $$$O(N lgN)$$$ with sorting points $$$S$$$ about $$$p$$$ — something like ccw-sort
Now, whole the problem can be solved. Just do the steps above about all the $$$N$$$ points. The time complexity is $$$O(N^2 lgN)$$$.
Problem C was very nice.
How to solve C? TIA
We can rewrite the sum as, in how many permutations, subarray with size k exists. Then we can sum these values from k = 1 to n. This technique can be called as contribution sum technique.
Now, notice that, for a fixed k length, there can be n — k + 1 choices for min and max element. And there can be n — k + 1 subarrays in an n size permutation. So we can permute k elements in fact(k) ways, and other n — k elements as f[n — k] ways.
So ways(k) = (n — k + 1) * (n — k + 1) * fact(k) * fact(n — k)
Can you explain better on why is there
(n-k+1)choices for min and max and(n-k+1)subarrays in annsize permutation?k is the length of the sub-permutation, there are n-k+1 positions where it can start.
So It should not be k! * (n-k)! * (n-k+1)
as k numbers can be permute in k! and it can be placed in (n-k+1) position of (n-k)! possible permutation of (n-k) numbers
This n-k+1 is there twice. Once it is the number of positions where a subseq of len k can start. Second it is the number of possible smallest numbers of this subsequence.
So you multiply that twice, and once with (n-k)!.
Adding up for all possible k is answer.
What was nice about it? :)
It was nice to me. :|
F: It is always possible to achieve a perfect matching. Proof using hall's theorem.
Call the initial set of edges in $$$T_1$$$ original edges. Iterate on edges $$$(u, v)$$$ of $$$T_2$$$ and find any original edge $$$(a, b)$$$ in $$$T_1$$$ on the path between $$$u$$$ and $$$v$$$ (there will always exist an original edge, otherwise we have a cycle in $$$T_2$$$). Cut $$$(a, b)$$$ from $$$T_1$$$ and link $$$(u, v)$$$. We can use hall's theorem to prove a perfect matching among unmatched edges.
Can we solve this problem without LCT?
Yes. Try to find constructive proof not using Hall.
My solution (pending systests) doesn't use a LCT (or something similar). My solution was to find an edge $$$(u, v)$$$ in $$$T_2$$$ such that $$$u$$$ is a leaf. Let $$$w$$$ be the first neighbour of $$$u$$$ in $$$T_1$$$ on the path from $$$u$$$ to $$$v$$$ (in $$$T_1$$$). Then we print $$$(u, w)\in T_1$$$ and $$$(u, v)\in T_2$$$, remove $$$(u, v)$$$ from $$$T_2$$$ and contract the edge $$$(u, w)$$$ in $$$T_1$$$. One can prove the resulting graphs are trees on $$$n-1$$$ vertices, correctness follows inductively. The contraction operation requires some careful bookkeeping with vectors/sets, but ultimately doesn't require anything fancy.
Nice!
D was interesting to me ^^. Could you guys show your solution to this problem?
The main idea is check venue-sensitive set with size 2
For each lecture, check if the list of lectures that intersect with it in venue $$$a$$$ is the same as the list of lectures that intersect with it in venue $$$b$$$
Instead of comparing each element in two list, we'll check does any element that appear in this list but doesn't appear in the other list
What was the trick for C? So many people solved it, I haven't even got any idea how to solve it.
for length k permutations, the sum is (n-k+1) * (n-k+1) * k! * (n-k)!
eg n=4,k=2
we have 12 23 34 (4-2+1 kinds)
and for 12, it has 2! permutations
the numbers left are 34, has (4-2)! permutations
we want to put 12 into ()3()4() , which have (4-2+1 blanks)
Why we are multiplying by extra (n-k+1) ?
If we consider k numbers then they can permuted in k! manner and can be placed in (n-k+1) position. So k! * (n-k+1) and rest (n-k) numbers can be permuted in (n-k)! manner
So in total k! * (n-k+1) * (n-k)!
k numbers could be 1~k, 2~k+1, 3~k+2, total n-k+1 kinds
I made a big strategic mistake :(
It is almost always not the right idea to start with the harder problems.
Here is the explanation: It is more probable that you will get the easier problem quickly and harder problem will take more time. Submitting earlier ensures that you don't accumulate the penalty for the easier problems. Even in a simple scenario where you solve A in 3 minutes and E in 30 minutes, your penalty is 3 + 33 = 36 minutes. If you solve A later, you penalty for A is 33 minutes and so the total penalty is 63 minutes. I don't exactly know about how scoring works, but at least in the time penalty approach you can see how worse it can be to not solve an easier problem.
In task D, why the answer for test case 3 is "YES"? We can attend 1 and 3 at A (1-2 and 3-7), but can't attend at B (5-9 and 6-11)
Your input format is a bit messed up — You cannot attend 1 and 3 at A (1-5/3-6) nor can you attend 1 and 3 at B (2-9/7-11)
Oh, really, i thought format was sa, sb, ea, eb. Thank you
1 and 3 are 1-5 , 3-6 at A and 2-9 , 7-11 at B so we can't attend at A and neither at B
The difficulty of problemset was high a bit for me, but it was good problemset.
How to solve C?
$$$\sum_{i=0}^{n} {(n - i)! * (n - i) * (i + 1)!}$$$
.
Can you explain, please?
Can anyone explain me solution of Problem C I wasn't able to find any pattern in answers neither I was able to think of any dp approach
Let'x fix length of good segment, there is (n — len + 1) ways to choose starting number, (n — len + 1) ways to place those numbers, len! ways to permute those len numbers, (n-len)! ways to permute remaining numbers.
In problem D I created 2 segment tree one for a and one for b
Then in each query I check if all cells between xa and ya is empty and if it true I mark in array that he can attend this lecture and make update query and makes all this cells occupied, (the same with xb, yb).
at the end iterate over the attended array and if there is attended1 != attended2 I print No
if all have the same values I print Yes.
I got Wa on test 17, anyone know why ?
E is a very interesting and original problem. The best problem of the decade
Most geometry problems are like that.
Actually, it was very similar to problem D of Argentinian Programming Tournament 2019
how can I implement this for problem c:
Pre-compute factorials from 1 to n before implementing this loop.
ok now I feel stupid :(
A-D were trivial, F and G too hard so I was stuck solving the geometry problem for a hour and a half. And of course as is usual with geometry problems, of that around 15 minutes was spent solving the problem, then the rest trying to fix case handling to avoid double-counting and issues with angles. Why did I even try?
Could we please leave geometry to ICPC and have good problems in contests instead? :)
EDIT: 180 lines and FIVE Fenwick trees later I think I'm done debugging.
EDIT2: And my code for sorting by angle was too slow. After lots of constant optimisation of a $$$\mathcal{O}(n^{2} \log n)$$$ solution I finally got AC (68205536)
My E is about 40~50 lines...
H2S E?
As the long and detailed header of my submission for problem F might suggest, I already knew problem F. I wanted to propose it as part of an online contest.
I am happy about the rating boost I will get, but I am sad that I cannot use in a future contest the best problem I had ever invented. At least I have participated in the round, otherwise there would be only the sad part.
We are all waiting for the solutions ^^
How to solve E, I spend 1.5 hours but no idea. May be I only NEED 2 more points,then I can become CM:(
Sadly.... I need 92 more points.Because I got FST on problem D.
How do you solve C? My approach: write a stupid solution, get a table for small values of n <= 11, try to find a pattern. Unfortunately, both OEIS and me trying to figure out the pattern failed. How do you solve it then?
hello 2020 & goodbye rating again
Here's a cool reduction I made for $$$E$$$:
Claim: Find the sum of number of points in all possible triangles in the given set. Divide this by $$$2$$$ and multiply by $$$n-4$$$, that's the answer.
Proof: For any castle of $$$4$$$ points and a point $$$P$$$ which lies inside it, consider all the $$$4$$$ triangles made by taking the castle points $$$3$$$ at a time. Out of these $$$4$$$ triangles, $$$P$$$ will lie in exactly $$$2$$$ of them. Conversely, consider any triangle and any point $$$P$$$ lying inside it. If you add any of the other $$$n-4$$$ points to make the triangle into a quadrilateral, you will get a valid castle of the triangle points and this new point which will protect $$$P$$$.
Thus, we have proven a two-one bijection between these two quantities.
Now, if you could find the sum of number of points lying inside each triangle in $$$O(n^2)$$$, you have solved the problem!
cooooooool
I saw a few solution for E above, but this is the best written solution. Kudos and thanks!!!!
Is E about finding how many Concave (or) Convex Pentagons can be formed from N points? If so, then how?
Almost. Let $$$f_n = (\text{number of pentagons with n points on convex hull})$$$. Answer is $$$f_3*2+f_4$$$. We know that $$$f_3+f_4+f_5 = \binom{n}{5}$$$. In my solution i found $$$f_3*3+f_4*4+f_5*5 = \sum_{i\neq j} \binom{\text{number of point p having }(a[i]-p)\times (a[j]-a[i]) \gt 0}{3}$$$.
. Finding $f_5$ is $$$\mathcal{O}(n^3)$$$ problem. 1146H - Satanic Panic
You haven't to do it. Consider a tuple of 5 points, the contribution of this tuple to answer is ((number of lines can split plane to 2 halfplanes and a half has 1 point, another one has 2 points) — 5). It is easier to solve base on the above observation.
Damnit, slightly late with F... if I'm not completely wrong. My idea is:
UPD: Yep, it works.
I had a noob bug at F, but I want to know can flow pass this problem ?
Not intended, but one participant managed to squeeze it with push-relabel flow (We failed)
I love this problem set(especially, F&G), thank you problem setters!
Thank you very much!
I derived the formula for C with probability and found Expected number of framed segments with length i.
Why geometry problem...
In E, if I manage to find for every point P:
$$$a$$$ $$$-$$$ the number of points in the upper left side of P
$$$b$$$ $$$-$$$ the number of points in the upper right side of P
$$$c$$$ $$$-$$$ the number of points in the lower left side of P
$$$d$$$ $$$-$$$ the number of points in the lower right side of P
Won't the answer for point P be the sum of:
$$$cnk(a + b,i)$$$ $$$*$$$ $$$cnk(c + d,4 - i)$$$
$$$-$$$ $$$cnk(a,i)$$$ $$$*$$$ $$$cnk(c,4 - i)$$$
$$$-$$$ $$$cnk(b,i)$$$ $$$*$$$ $$$cnk(d,4 - i)$$$
for every $$$1 \lt =i \lt =3$$$ ?
P = 0 0
Points:
1 1
3 1
1 2
-2 -1
-1 -10000
I just realize E's polygon is NOT necessary convex...
In problem G, the checker told me that I must place a wall between rock cells. However, I couldn't find the statement which specifies that point.
Did I overlook something? Or was the statement incomplete?
How to solve G?
It's unweighted matroid intersection. The universe is the set of all edges in the graph, and we'll try to remove as many edges from the graph as possible. We intersect two matroids:
We then find the largest set belonging to the intersection. If you found enough edges to make the graph a tree, the answer is YES.
What's test 77 in G?
Some anti-random cases.
We used a bunch of hill-climbing to kill random solutions of G. kriii spent several days for preparing awesome tests of G. I think he will have a lot to talk about ;)
Yesterday matroid intersection blog came up in the CF feed, and I decided to read it. After 15 min I thought "come on, what is the chance that I will ever encounter such an unusual construct" and gave up on it...
The problem is equivalent to finding a tree over the free cells such that all the leaves are white or (1,1). This can be seen as a matroid intersection. The two matroids to intersect are:
[Not sure it is correct, since I was not able to code it]
more like Hello WW3
Once again he showed who is the real boss (respect you 3000).
How to solve D? I was thinking at hashing the intersections after you sort the intervals as you would when you want to calculate the maximum number of intervals overlapping (put both start and end points in a vector and sort). Does this lead to anything? Is there a nicer solution?
Yes, it works. You can hash random weights for it to work better. I just xored all weights of intervals not intersecting with a specific one. This can be done by using 4 maps.
Yes, I solved it like this. We need to check for each interval i if its set of intersecting intervals is equal in both the graphs. We compare two sets by considering hashing a set $$${a_1, a_2, \ldots}$$$ to a polynomial $$$p(x) = x^{a_1} + x^{a_2} + \ldots$$$. Then we can evaluate it at random points and check equality. The degree of the polynomial is $$$n$$$ so if you use a mod around $$$10^9$$$ the probability of failure is $$$10^{-4}$$$ by Schwartz-Zippel if you evaluate at a single point. I evaluate at four points for probability $$$10^{-16}$$$.
68192135
Instead of "No subtasks!" you guys should mention "No Geometry!".
Gotta feel bad for tourist. TLE on Test 77 of G.
Thanks a lot for the round!
My screencast, mostly trying to squeeze in incorrect solutions for F and G without much success :)
Good move ! by EvenImage ...
Now , he will be the rank 1 ...
when will the virtual participation for this round start?
My randomised sol for D passed:
If there exists a pair of segments which intersects in one of the events and not the other then answer is NO. So each segment has to intersect with the same exact other segments in each events. This implies that for any subset the number of intersections in each event has to be the same.
So here's what I did: Take a random subset (50% chance of a segment being in it). Count number of intersections if Event A was chose, and same for Event B. If the number of intersections is diff output NO, otherwise repeat again with a diff subset(for 50 iterations). To count number of intersections, i sorted segment by left endpoint, then used binary search on each element.
I reckon your power came from your new handle
Systests have been completed and upsolving is still unavailable. What's wrong?
System testing is at 100%.
왜 한글이 없나... 과연 어캐ㅔ 될까요
It is because foreigners can't read Hangul.
I have a technical question.
After this round I will become candidate master. but before my rating changes I registered for round 612 div2. Now... if I participate in it, will it be rated for me?
I don't think you will be able to participate for div2. If you become candidate master then you will have to register for div1, once the rating calculation is done.
And it's a moment right after contest. AND... Where is the editorial?)
It's because G is being rejudged.
Did they just rejudge G?
i don't understand why test 3 in task B have output is 72. Can you explain for me !.
My output is 74.
How are you counting?
Try this.
if you are getting 6 instead of 4. Then you might be counting
1 2 3 4and3 4 1 2twice.I'm pretty sure that the test case is large enough that there is no good explanation that is not along the lines of "because this solution, proven correct, returns 72" or "if you look at the list of all concatenations and count those with an ascent, you get 72" here.
In case it helps, check the output of this verbose brute-force solution.
1 with all 10
2 with 9 (except 2)
3 with 3(1,8,10)
4 with 7(except 2,4,6)
5 with 6(except 2,4,5,6)
6 with 8(except 6,2)
7 with 9(except 2)
8 with all 10
9 with 8(except 2,6)
10 with 2(1,8)
total 72
Does anyone know how to analyse the complexity of network flow(the number of edges can be $$$O(n\log n)$$$) in F？
There can be $$$\Theta(n^2)$$$ edges in the matching graph of F.
EDIT: Consider $$$T_1$$$ the path with vertices $$$(1,2), (2,3), (3, 4), \dots$$$, and $$$T_2$$$ a path with edges $$$(1, n), (n, 2), (2, n-1), \dots$$$. Then the $$$i^{th}$$$ edge of $$$T_2$$$ covers $$$n-i$$$ edges of $$$T_1$$$, giving the matching graph $$$\Theta(n^2)$$$ edges.
The number of edges can be $$$O(n\log n)$$$ using some optimization.
It's $$$O(n\sqrt{n}\log{n})$$$.For proof take a look at the editorial of this PrinceOfPersia's problem: ALT
I have a query : If a participant registers for a Div. 2 contest before rating change, and then enters Div. 1 after rating change, will Div. 2 be rated for him/her or do they require to re — register or something like that?
I think solutions for problem G are rejudged.
Just solved D with a 2D segment tree (more like a Dynamic segment tree + fenwick tree ) !
https://mirror.codeforces.com/contest/1284/submission/68203222
found this in tourist's code lol
А что делать с такими посылками? Понятно что этот код специально сделан нечитаемым(что вроде противоречит правилам), но непонятно кому и куда об этом писать. Возможно стоит добавить кнопку "Пожаловаться"? MikeMirzayanov
https://mirror.codeforces.com/contest/1284/challenge/68172307
"Strong testcases on problem D.." xD
Check this out -> Problem D: 68195434
Now they are a little stronger
this works pog
gamegame will win IOI2020!
Hi Guys,
In the problem E, very very high precision is needed. Can anyone calculate?(or explain)
In 68214305 24 digits of PI couldn't pass.
But 68214338 using cos(-1.0) (more than 30 digits precision) is accepted.
Regarding the limits (and no three point collinear), how is it possible?
Note: M_PI gets compile error(not in my PC tho)... Purely correct submission(in 70 min left) would be AC if it could compile T-T
Note2: arctan(1/1e9) is like 1e-10 different than the actual PI, soo 1e-24... how???
Don't use doubles to check on which side of a line a point lies (or to sort rays with common origin by angle, which is roughly equivalent). Use cross product instead
problem D is too difficult to understand the request
Can anyone please explain why my code for D is getting TLE? https://mirror.codeforces.com/contest/1284/submission/68243271
For Problem D, the statement is horrendous. You say that it is bad if they overlap, and then proceed to say it is actually fine if one is nested in the other...