Всем привет.
Приглашаем вас на предстоящий Codeforces Round #618, который начнётся в 09.02.2020 17:05 (Московское время).
В обоих дивизионах будет 5 задач. Вам будет дано 2 часа. В раунде будет интерактивная задача. Узнайте о таких задачах в блоге.
Задачи готовили rotavirus, rotavirus, rotavirus, rotavirus, antontrygubO_o и nvmdava. Благодарим MetB, stefdasca, cfalas, gamegame, hugopm, Redux, dorijanlendvaj, imbr92, CP_Sucks, 300iq, Rahul, AryaKnight, 244mhq, manish.17, Um_nik, mblazev, pseudocoder10, aryanc403, box за тестирование и бесценные фидбеки. Благодарим MikeMirzayanov за то, что сделал раунд возможным, и antontrygubO_o за координацию раунда.
Надеемся, вам понравятся задачи. Удачи и высокого вам рейтинга.
Разбалловка Div2: 500 750 1250 1750 2000 Div1: 500 1000 1250 1750 2250
Контест закончен, поздравляем победителей.
Div1:
1. jqdai0815
2. TLE
3. Radewoosh
4. zhouyuyang
5. Benq
Div2:
1. ntftxdy
2. qsmcgogo
3. ZhouShang0817
4. sarthakmanna
5. nantfaker
What about rotavirus
For you, he's Mr. GM
for chei he is not
Edit : flashback
5 problem! may be going to be hard problems :(
Sorry for my bad memory, but I remembered that rotavirus and rotavirus were the same person
Actually rotavirus = rotavirus = rotavirus = rotavirus = rotavirus. You can link to the user page to find out that they are all rotavirus
Нормально так тестеров нафармили
Round prepared by Eva? I'm ready to 998244853 modulo
Maybe this time the problem will ask you to modulo 10000000007(10^10 + 7) XD
It's not even a prime number; extra evil
Missed Newbie testers again.
Happy to see Educational Round 82 between Round 618 and 619 !!! Back to Back Feb12 and Feb13.
:numb:
:dumb
There will be an interactive problem in the round.
First round of codeforces 1.0!
Thanks a lot for hosting the contest on a Sunday! Let's make it a regular thing, it ensures a lot of people are able to give the contest.
I like the varying times of Codeforces rounds, this way everyone gets some chances to participate. If you do it on Sundays only (or mostly Sundays), it means that a lot of people get the chance every time and other people never get the chance.
Also, a lot of people do OpenCup rounds on Sundays.
Good luck 4 all :D
Rounds consist of 5 problems are of high quality mostly.
The round to become MASTER or expert not totally sure :D
You will become expert or will remain CM i guess, bcz the round has only 5 problems which means difficulty is gonna be high.
your hopes aren't high at all
300iq makes a round.
Interactive problem:
What's the score for each problem.
the rounds that the number mod3 is zero, are my lucky rounds!
how fast the score distribution is!
A + B + C + D... Dinner.
2E/1C http://www.usaco.org/index.php?page=viewproblem2&cpid=419
Second solution is basically it.
How to solve Div.1 C(Div.2 E) in time limit?
notice that it makes no sense to do updates with overlapping ranges. keep a stack with ranges of best updates (keep the sum and the amount of elements) add elements of the array 1 by 1 from first to last, while it is convenient to merge the last segment to the one before it, do so (if the average of both is less than the average of the one before the last)
How to solve C?
So many people did that, I couldn't even think of an approach. :(
Think of the operation as set difference.
Same..I think i should go back being a cyan :(
We need to notice that
The answer is
So, only the first element matters.
How did you derive it ? Only thing which I could make out during the contest was that f(x,y)=x-x&y.
P.S: I got it. I am just dumb.
One observation is that the subtraction is never going to carry over any bits, since the (x | y) operation makes sure all bits of y are set.
This lets us rewrite $$$f(x, y)$$$ in terms of bit operations only: it takes x, sets all bits of y, and finally unsets the same bits. This corresponds to
x & ~y.You don't need to use f(x,y) = x & () if you know f(x,y)=x-x&y
if specific bit exists in 0 or 2+ elements, result of this bit will be 0 anyway. so the idea is to find the largest element which contains unique bits and set it as first.
Think about what the operation actually means. (x|y) — y simply means, remove all the bits from x that also occur in y.
Now, the way the function is phrased, it means pick some value $$$a_1$$$ and remove all bits that are not unique to $$$a_1$$$.
After recognizing this, the solution is simple. For each bit from 0 to 31, check if it is unique. Then for each number, calculate answer for this number as just sum of all set bits that are unique. Pick maximum of all this, and put that number in the first position.
(X|Y) — Y means the bits which are set in X but not in Y — (1)
Given expression can also be written as f(a1, (a2 | a3 | a4 | ....an)) Using (1)
Now the answer is dependent on just setting the first element.
Hope this helps :)
APPROACH — Think in bit level, f(a, b) ex- f(6, 3)= f('110','11')='100' every '1' of b present in a is removed. so try to take a0 with 1's have occurrence only in that number and if their are many such numbers take the maximum one. sol — 70657021
How to solve Div2. C ??
whats the approach to div 2 C ?? :(
Let f(f(...f(a1,a2),a3...)=X.
Following points are to be noted:-
1. x=0,y=0 then f(x,y)=0
2. x=0,y=1, then f(x,y)=0
3. x=1,y=0 then f(x,y)=1
4. x=1,y=1 then f(x,y)=0.
Let us consider the jth bit of all a's , then jth bit of x = f(f(...f(a1[j],a2[j]),a3[j]..)).
In order to get jth bit of x as set bit, we should arrange the elements in such a way that jth bit of a1 is 1 and jth bit of rest of the elements is 0.(WHY? Since f(f(...f(1,0),0,0...))=1).Thus our target is to have the jth bit of a's as follows, a1's=1,a2's=0,a3'=0........an's=0
Thus in order to get the largest x, we will iterate from MSB(31st bit) and try to find which number have its jth bit as set and rest all have jth bit as 0.
If we are not able to find then any arrangement will give 0 as answer. My solution 70646858
How to solve Problem C :<
I tried to approach by separate the array into 2 part Set & Unset with O(n * bit) complexity like this problem -> https://codeforces.com/contest/1285/problem/D But I dont know what to do next after separated :<
for div 2 D, I tried this approach: if n is even and slope of opposite sides are equal, then yes else no, can someone say what's wrong with this approach. this is my submission https://codeforces.com/contest/1300/submission/70677064
should be equal and parallel
Oh wow I did that and got wrong answer. Guess I must have a bug in my code. And I thought the solution is really wrong because I could not convince myself that this must work.
Same for me, I assume this is due to a numerical precision issue. Anyway instead of calculating lengths of each edges I could've compared the x & y components on each vector
Oh yes, it was an overflow, should just use long long all the time. Guess I do not deserve to get rating
What is "equal" here?
equal means the lengths are equal
Okay, thanks.
But, is it not that if two opposite sites are not same len, then some other two sides cannot be parallel?
PS: Perhaps I better wait for editorial, thanks anyway.
take a regular octagon and shift any its side by epsilon.
I didn't get this, on shifting a side by some distance, won't some other pair of opposite sides become non-parallel
shift while not changing other sides' directions
got my mistake! really good question. Thanks for helping!
that's exactly why I wasn't checking for the lengths to be equal
Why are almost all tasks based on math?
Why Div2 D the second case answer is no? It seems to me that there are always A, B in P such that for all (x, y) in T (A, B) = (x, y). Could you give me (x, y) that the vector couldn't be made by the set of points in P.
Visualization for second case is in the description
Thanks problem setters for the problems <3
intersting problems. I did not prove anything and just guessed the solutions for div1 b and div1 c. They both worked haha
What is/are the hacking cases(s) for Div1B/Div2D
How to solve Div1C
Build a lower convex hull with points being (i, s[i]) where s[i] is the sum of the first i values, in addition to the point (0, 0). Each edge in the convex hull represents an operation on the interval [x1 + 1, x2] where x1 and x2 are the x-coordinates of the endpoints of the edge.
My submission: https://codeforces.com/contest/1299/submission/70681667
Convex Hull (though I did not manage to submit at the end).
You have to minimize the first element by choosing a segment $$$[1, i]$$$. Any operation on the segment $$$[l,r]$$$ which $$$1\le l\le r\le i$$$ or $$$i\le l\le r$$$ is unnecessary. Besides, if operating segment [l, r] which satisfies $$$l\le i\le r$$$ before [1, i] can cause the first element to be lower than operating [1, i] solely, then with some mathematics, you can prove that operating [1,r] is more optimal.
Therefore, you should find $$$i$$$ such that $$$S_i / i$$$ is minimum where array $$$S$$$ is prefix sum array. Then you fill all element from $$$1\rightarrow i$$$ with $$$S_i/i$$$. Trim the subarray $$$1\rightarrow i$$$ and repeat. The solution is optimal.
Since $$$n\le 10^{5}$$$, we can use Convex Hull trick to squeeze the solution into acceptable complexity $$$O(nlogn)$$$.
So true
The Div1B figure mislead me for over 1 hour.
Reading quiz orz.
Thanks for the contest! Problems are very interesting)
What are corner cases of div 2E? And why was this approach giving wrong answer: Traverse from right to left and calculate smallest average possible by including a[i] and in the process, also maintain the span of the current avg starting from current index to some index in right. If a[i] is smaller than current average, then set current avg to a[i] and span of current avg to 1. Finally print the answer with final values like this:
My actual solution: https://codeforces.com/contest/1300/submission/70679283
How to check if a graph has a nontrivial cycle with xor zero? I only know how to do it with gaussian elimination, but that's too slow.
actually the Gaussian elimination works because if there are more than 5 basis cycles, their costs are linear dependent.
Actually, there's only less than 400 different vector spaces in $$$Z_2^5$$$，so after some preprocessing, you can do gaussian elimination in $$$O(1)$$$ , and do dp where state is current vector space. It works in $$$O(400n)$$$ .
Coded that with an additional log and got rekt by TL :(
Oh, I misread your question. As for checking, just consider an arbitrary spanning tree, and consider all cycles consisting of exactly one edge that is not in the tree. Every nontrivial cycle can be constructed by 'xor'ing the cycles of the above type. So checking if a graph has a nontrivial cycle is equivalent to checking linear independence of all cycles of the above type. This can be done by union-find.
this solution SortWithArray is getting timelimit but the same implementation with the vector got AC sortWithVector , how could this happen ?
you have declared array which has size 100001 and it should be min. 200001 because it has to store 2*n elements.
Worst feeling ever: code general polygon similarity just to get WA due to overflow then guess the solution after 4 WA because it's div1B and people solved it fast af.
I wrote an easier version of div1c a couple of years ago here. The bounds for that allowed for n^2. Luckily, there was a description of how to do O(n) in the discussion.
Damn, my bad, downvote this comment if you want to.
Geometry Geometry Everywhere
Geometry is good bro.
When the ratings will be available? I hope to become newbie :(
Thanks for your contest :3 such an amazing performance, I will become purple <3
Congrats!
How to solve the precision problem of the Div2.E(Div3.C)1299C - Water Balance
When I used float to save my answer, I got WA 70681208
When I turn to double, I got TLE 70681660
So sad:(
The problem said that you shouldn't read input as doubles. You can read it as integers and then convert them to doubles. E.g:
It works! Thank you very much!
But one more question, what's the difference between them? I can't quite get it.
Imagine that you don't have built-in functions to read input except one function that reads a single character, which is
getchar()in C++. Try to implement a function that readsdoubleusinggetchar(), and implement another function that readsint.You'll observe that the first one involves more operations that the second one, and also will be performing
doubleoperations instead ofintoperations, hence will be slower.Yes, that's right. I never thought it in such a way. It's a totally bad coding habit.
Oops, It still doesn't work when n comes to 1e6. TLE again. :(
I have changed my approach to save number, now it will output immediately instead of saving it in the array.
Here is my code: 70690087
I don't understand. It seems your solution is $$$O(n^2)$$$?
You are right. How silllllly I am. I will try another way.
Sincere thanks!
+80
Change ID will be treat as new account by Predictor.
Can anyone tell me what went wrong with my approach for D? It failed on test 71.
I checked if polygon is symmetric. To do that, I found out the coordinates of centroid and shifted origin to centroid (hence redefined all the vertices accordingly). since our centroid is at origin, for polynomial to be symmetric, if polygon has vertex(a,b) then it must also have vertex (-a,-b).
What is wrong with this?
I checked if it was symmetric too, it failed :(((
Never use a
mapwithdoubletype as keys. Instead multiply all the coordinates bynand use integers as map keys.I don't think that's the problem, mine doesn't work either, it's probabbly the concept of the solution :(
Test case where solution is failing:
n = 6 {0,0} {2,0} {4,1} {3,2} {-1,2} {-2,1}
So I don't think issue is with using double. I manually checked it, it does look symmetric to me, still WA.
Well we are just very unlucky then my friend :(
Can 1D be solved without the condition「there isn't any simple cycle (i. e. a cycle which doesn't pass through any vertex more than once) of length greater than 3 which passes through the vertex 1」?
Yes, you can solve it with an additional state.
Delete vertex 1, solve for each connected component separately. For each component, do a dp that's almost the same as 1D but with an additional state being the distance to vertex 1 if it's already connected. Then you can just add the cycles when you choose to add other edges or not.
If someone wants to read more elaborate description based on tfg's concise idea, I have written it down here: https://codeforces.com/blog/entry/73763?#comment-579653
I am not able to understand problem div.2 D. It would be great if anyone could explain to me...
My contest rank and overall rank now converge:)
Why does leaving
cerrprints in your code give idleness limit exceeded and take so long to TLE? I waited 5 minutes just to fail in pretest 10 :/Btw on one onsite competition I made a typo and wrote cer instead of cerr in that define, so my actual cerr in code remained usual cerr and it made the judge go crazy as well giving unreasonable judging times. It seems to be some general issue or something that is easily gotten bad.
Why does CF-predictor show that Δrating of jqdai0815 is +687？
It seems that for somewhat reason cf predictor thinks that jqdai0815`s rating before contest is 1500 .
Div.2-C was good problem.Nice Contest!!
div2 problem E could be solved in Monotonic stack. If one's averge is greater than the previous one, we can merge them. The problem can be solved in O(n). Besides, I want to say that is the the data of problem E is really unstrong. My friend accept the problem in O(n^2). If there are 1e6 number, and first 999999 numbers are 1000000, while the last number is 1, he won't get accept while get TLE.
>tfw you finish writing C and then your PC crashes
It does crash from time to time but I really hoped it wouldn't happen during a contest...
Eventually the user whose maximum rating >= 3600 became two. :)
I have solved Div2D/Div1B during practice now using such an overkill solution. It may strengthen the understanding of Geometry, or it may be just useless. The approach seems correct for the most part, except case handling in one specific case that seems too hack-ish to be true. I have to admit, I was shooting for something slightly different where my solution would fail if it did exactly what I wanted it to do. With some accidental bug it gets accepted. I am not sure if the approach is correct but can someone either prove this correct or give a counterexample or some explanation about it?
Here is my approach:
$$$\textbf{( i.e.,}$$$ a number $$$\boldsymbol{1 ≤ x ≤ \frac{n}{2}}$$$ such that for all $$$\boldsymbol{0 ≤ i ≤ n - 1}:$$$ $$$\boldsymbol{length[i]}\textbf{ = }\boldsymbol{length[(i + x)}\textbf{ mod }\boldsymbol{n]}\textbf{).}$$$ Or in other words, a sequence of consecutive side lengths of size $$$\boldsymbol{x}$$$ that repeats.
Obviously $$$x$$$ must divide $$$n$$$.
I output
YESonly if there is either a period of length $$$\boldsymbol{< \frac{n}{2},\;\;}$$$ $$$\textbf{or}$$$ if there is period of length $$$\textbf{exactly}$$$ $$$\boldsymbol{\frac{n}{2}}$$$ and $$$\textbf{no sequence of side lengths of size }\boldsymbol{< \frac{n}{2}} \textbf{ repeats.}$$$ The special handling for $$$\boldsymbol{\frac{n}{2}}$$$ I've done accidentally, but it's necessary for AC.The 3rd testcase is an example of where there is a period of length $$$\boldsymbol{\frac{n}{2}}$$$ but no sequence of side lengths smaller than that repeats.
In the rest of the test cases. Some test cases have a period of length $$$\boldsymbol{\frac{n}{2}}$$$ and also smaller sequences that repeat. An example is Test: #62. Their answer is
NOThis is my solution. I used Main-Lorentz algorithm to count the periods of all lengths by concatenating the side lengths array to itself and dealing with it as a string. It runs in $$$O(n\;log n)$$$ time. I used this implementation from e-maxx, but modified it to only count the number of repetitions of each length without caring about the starting/ending indices. Note that a period of length $$$\boldsymbol{x}$$$ if it exists corresponds to repetitions of length $$$\boldsymbol{2x}$$$. There is a period of length $$$\boldsymbol{x}$$$ if the number of repetitions of length $$$\boldsymbol{2x}$$$ is $$$\boldsymbol{≥ n}$$$ in the concatenated length array (as in, a repetition for every index of the original array).
Regardless of the exact implementation to find the period lengths and/or repeated sequences. Can someone say if this approach is correct? If it exactly mirrors the state of the convex polygon having equal and parallel opposite sides?
The weird case handling of period exactly $$$\boldsymbol{\frac{n}{2}}$$$ is due to this line in the code
if(it == M.begin()) break;I break out of the inner loop for repetitions of size $$$\boldsymbol{≥ n}$$$, (originally wanted to exclude $$$\textbf{2n}$$$ and $$$\textbf{n}$$$), but I forgot to break out of the outer loop.Nobody:
Me: get a successful hacking attempt, only followed by jqdai0815's successful hacking attempt
Epic gamer move: get a successful hacking attempt at 1:59:58
About Problem 1C: https://codeforces.com/contest/1299/submission/70683614
This code can get Accepted.
But Why this code get Wrong answer on test 18 when I change eps to 1e-9?
https://codeforces.com/contest/1299/submission/70683551
And I change eps to 1e-10 will get Wrong answer on test 14 .
I thought I wanted to make eps smaller than 1e-9.
Because of 'Your answer is considered correct if the absolute or relative error of each ai does not exceed 10−9' .
Will there be Editorial?
73763
Btw, exercise in English language: find everything wrong with grammar/syntax in "how many are there such subsets, that, when removed, there is not any".
When will editorial be published?
I have studied Div.2 E / Div.1 C editorial. But I got WA at test case #7... I think it's an overflow but I cannot find it.. Help me.. https://codeforces.com/contest/1300/submission/70754718 (Sorry for bad english and bad code)