Hello Codeforces!

We are glad to invite you to the upcoming Codeforces Round #618, which will start at Feb/09/2020 17:05 (Moscow time).

Each division will consist of 5 problems and will have 2 hours to solve the problems. There will be an interactive problem in the round. Learn more about them here.

This round was prepared by Eva, sorry_marymarine, baumanec, danilz1806, antontrygubO_o and nvmdava. We would like to thank MetB, stefdasca, cfalas, gamegame, hugopm, Redux, dorijanlendvaj, imbr92, once_twice, 300iq, Rahul, AryaKnight, kefaa2, manish.17, Um_nik, mblazev, pseudocoder10, aryanc403, w33z8kqrqk8zzzx33 for testing and their invaluable feedbacks. And special thanks to MikeMirzayanov for making this round possible and antontrygubO_o for coordination of the round.

We hope that you will enjoy the problems we've set, and wish you good luck and a high rating.

**Upd 1.** Some of us might be online at AC discord server after the round ends.

**Upd 2.** Score distribution:

**Div2**: 500 750 1250 1750 2000**Div1**: 500 1000 1250 1750 2250

The contest is over. Congratulations to the winners.

Div1:

1. MiFaFaOvO

2. TLE

3. Radewoosh

4. zhouyuyang

5. Benq

Div2:

1. ntftxdy

2. qsmcgogo

3. ZhouShang0817

4. sarthakmanna

5. nantfaker

Ready!!

618 it is!

What about Numb

For you, he's Mr. GM

for chei he is not

Edit : flashback

5 problem! may be going to be hard problems :(

Damn, 1001 cyan setters :O

PS: Light hearted comment. Don't take offense.

Sorry for my bad memory, but I remembered that Eva and sorry_marymarine were the same person

Actually Eva = sorry_marymarine = baumanec = danilz1806 = numb. You can link to the user page to find out that they are all Eva

Нормально так тестеров нафармили

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.

Two consecutive contest from 6pm (AtCoder and codeforces), Hopefully we will enjoy.xD

Ready!

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!

unable to register. Please resolve this

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

Same here :(

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.

i did get this but how do you find the first element .

should it be the biggest number

or

which has the most number of bits set 1

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

first calculate n=(a1|a2 | a3 | a4 | ....an) and after that using fact f(x,y) = x & () keeping y as ai check if the answer is max. and then output element as first element and rest all have default sequence.

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=0Thus 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.

thanQ

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.

How to solve Div2-C?

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 reads`double`

using`getchar()`

, and implement another function that reads`int`

.You'll observe that the first one involves more operations that the second one, and also will be performing

`double`

operations instead of`int`

operations, 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!

How to solve problem Div 2 — D ?

MiFaFaOvO you surely hacked Rating predictor.

+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

`map`

with`double`

type as keys. Instead multiply all the coordinates by`n`

and 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

`cerr`

prints 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 MiFaFaOvO is +687？

It seems that for somewhat reason cf predictor thinks that MiFaFaOvO`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...

Welcome gray fields. Cool there's editorial in Top section.

Eventually the user whose maximum rating >= 3600 became two. :)

I have solved

Div2D/Div1Bduring 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

`YES`

only 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

`NO`

This 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.How to solve B?

Nobody:

Me: get a successful hacking attempt, only followed by MiFaFaOvO'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 18when 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'.Corornovirus stay winning

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)

what is wrong with this implementation of question c anu and function https://codeforces.com/contest/1300/submission/70839885