Hey!

On Oct/16/2019 17:35 (Moscow time) we will host Codeforces Global Round 5.

It is the fifth round of a new series of Codeforces Global Rounds supported by XTX Markets. The rounds are open for everybody, the rating will be updated for everybody.

The round will last for 2 hours 30 minutes, 8 problems are waiting for you, and one of them will be proposed in two versions.

Scoring distribution: **500 — 750 — (750 + 750) — 2000 — 2500 — 3000 — 3750 — 4000**

The prizes for this round:

- 30 best participants get a t-shirt.
- 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2019:

- In each round top-100 participants get points according to the table.
- The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
- The best 20 participants over the whole series get sweatshirts and place certificates.

The problems of this round were developed by me, and here is the list of people who can't take part in the round as they know the problems beforehand:

KAN, Endagorion, arsijo, Rox, lperovskaya, Aleks5d, Learner99, MikeMirzayanov.

Coincidentally, this is also the list of people I'm thankful to for making this round what it is.

The round will be perfectly balanced. As all things should be.

Welcome!

**UPD:** The round is over! Editorial is here. Congratulations to the winners:

I think this is tourist's way of telling Um_nik "Go ahead, enjoy being the highest rated guy on CF while you can".

T

O

U

R

I

S

T

!

!

Press F for Um_nik

Lol :D

Omg, the GOD of CP talking to us

Reason for so early registration opening or this has been done before?

So, characters are from the Avengers in this round..

Can tourist even think about question of level A and B

I bet they all sound to him like something of "what time is it?" difficulty.

Actually I find it pretty hard to identify time in standard clocks xD

Duh bro...... Every question is A or B for tourist xD!!!

normal setters(hours before contest) — We have tried our best to keep the round balanced,

tourist(days before contest) — The round will be perfectly balanced. _/\_

Codeforces be like : best , better , bestest :DI want to win a T-shirt, I hope I'll get it.

hope c is c and not e or f.

But it is a soul for a soul

You forgot to thank

MikeMirzyanovandCodeforces.Come on, snapping half of living beings sounds very short-sighted.

Sounds as round will be semi-rated

More like only half of CF servers will be alive

omg, "semi-rated"

haha

GLHFYou ready?! Let's go!Yeah, for those of you that wanna know what codeforces all aboutIt's like this y'all (c'mon)This is ten percent bruteforceTwenty percent greedyFifteen percent concentrated power of geometryFive percent hacksFifty percent wrong answerAnd a hundred percent reason to participate in contest.GLHF everyone !!And still you are unrated

at least i am not participating in contest with alternate account

Mike shinoda

who the hell even reaches C lol

also here :))

Then hacked:-(

$$$-150$$$ after the round feels like "Mr. Mike... I don't feel so good..."

Mr. Radewoosh... I don't feel so good...

+124 feels like 'I am the one the one, who need no gun to have respect on the street' Huge respect Radewoosh :)

TOURIST!!!!!

A tourist written round?

immediate upvote of round announcementHere is the reference https://knowyourmeme.com/memes/perfectly-balanced

Why on weekdays!!

Maybe because they want less no of coders with their ratings fall ? :P

.... Wait a minute, who's gonna miss Tourist's round xD ?

Yes, why let more people to participate. Why would someone do that?

This contest announcement will definitely going to become the most upvoted contest announcement :)

UPD -: It has become the most upvoted contest announcement :)

Yes, and after this, tourist might enter in Codeforces Top Contributors list as well :)

he was top1 after hello 2018

I know, I meant by again he will enter the list :P

This is the first time I registered to participate in tourist's contest on Codeforces. Hope for high rating and a T-shirt as a souvenir.

tourist !!!

Yes, I did nothing wrong. All things should be perfectly balanced.

For normal people tourist = Someone who visits a city, town, or historic site just for the pleasure of exploring it can be described as a tourist. For a programmer tourist = Gennady Korotkevich

Everytime I refresh this blog, I can see an increase in the amount of upvotes.

Yeah Finally a tourist round :)

Hope there won't be any DDOS attacks...

I hope this round will be rated till the end

i just upvoted the blog and then refreshed it ...then i was like

Wait!..Am i worth 20 votes?...because the number of upvotes are raised by 20<3 <3

<3 <3 <3 <3 <3 <3

Sorry

Wowwww.. tourist is writer o.0 this is opportunity for Um_nik to break rank 1 CF =))

I wonder what

"perfectly balanced"means?It means that the difficulty of problems in this round perfectly matches its id.

You doesn't even spell it correctly. It should be "wonder"!

*didn't

tourist's round=upvote the announcement

great ! so exited for the contest !

LOLIt will be the best contest ever

I can't wait :)

But the other writers are also very good!

Finally, So happy to see that tourist is setting problems after a long time.

"The Round will be perfectly balanced." tourist has surely earned this confidence over the years of his Competitive Programming.

The round will be perfectly balanced. As all things should beSo do you wanna wipe out half of our rating? :3 I'm quite a bit afraid

)

All of them worked very well not only tourist

Relax, I just meant that everybody wants to participate in tourist's round.

^^ yass bro

It also meant that you dislike other writers round which is not good.

I wanted to upvote for the contest but downvote for the tags so this balanced perfectly as all things should be. thanosdideverythingwrong but me, I am his greatest creation.

It's tourist!!!The GOD!!!

Will Um_nik overtake tourist in tourist's round?

As always, Pretests_Passed, Accepted and SuccessfulHackingAttempt shall be welcome to the round. Meanwhile, may _Wrong_Answer, TLE, Runtime_error_, MemoryLimitExceeded and Hacked stay away from our land. And let's all hope that queue, DDos and unrated do not cast doom on this contest.

P.S. And the occasional appearance of PresentationError is also less than desirable.

How can SuccessfulHackingAttempt and Hacked not be in the same round at the same time?

you just mentioned 11 people for a stolen yet terrible joke. good one mate

When I’m done, half of humanity will still exist. Perfectly balanced, as all things should be.

Now i got it why they are saying this round perfectly balanced

Tourist=Thanos xD Him be like-

I am inevitable

Upvotetoo.Hmm, interesting...

When you just comment your opinion or a random comment:Same, I saw some other good comments got massive downvotes, I don't understand why there are so many random downvotes.

Yeah.I think so, too.

Well, I mean there is also comments with upvotes too. Votes will be perfectly balanced. As all things should be.

Tourist posting meme is something quite special

Everyone is too much excited for the contest because of tourist.... I am also excited and also frightened about the difficulty level... Anyway hope this will be interesting...

WOW, tourist entered top contributors list

Wish everyone lots of good luck.

rating++; CBGer are champions :>>>>>>>>>>

I hope this round is not balanced according to tourist, else A be like use segment tree D:

Wish no DDOS attacks.

Writers::Tourist

Wow.....It's Really Amazing

Can upvotes become equal to tourist rating?

Good luck and high rating to all! Can’t wait to see the problems :)

It's the time for Um_nik being the highest rated guy!

tourist nb!!

I really don't know why i left a courteous comment but many people disliked it :< Because of my poor english??

it's seem interesting with you but not everybody. you should comment something useful or amusing

How does one know what is amusing to everybody, even top standup comedians don't know if they will bomb or kill.

Awesome!! hoping for good ratings :)

The comment is hidden because of too negative feedback, click here to view it

Probably it's gonna be my last round this year, I hope to do well in it, at least to stay in Div. 1

Finally a tourist round :) Yeah Enjoy.........:)

if we have a long queue in the contest

The upvotes just crossed the number of upvotes in Good Bye 2018.

Hopefully this contest is as good as iberico ham made from pigs fed entirely with acorns.

While everyone is waiting for the round to begin, I am also waiting for the editorials. Damn sure, the editorials are going to be short and crisp and with bags full of learning. All the best everyone!

I love tourist!

Wow! This blog makes tourist one of the top contributors.

Omg!! I can't wait!! I bet I'll learn a lot in this round.(hopefully without minus ratings.)

Come on. Such comments only suit when immature kids like greens and greys post them. You are orange. Maintain some dignity

Omg!! I can't wait!! I bet I'll learn a lot in this round.(hopefully without minus ratings.)

please , how many problems are prepared?

Oneday, I will precede you, tourist.

BREAKING NEWStourist tripled his practice after reading this

How making jokes is preferred than encouraging others? Idiots are spreading all the time. Go ahead, do whatever you’re good in! :D

Okay let me motivate you. Tourist is even sweating head to toe. Go ahead man. Give him a tough fight. My best wishes with you

Thanks a lot.

What will be the scoring distribution and the contest length?

Contest length will be 2.5 hours, you can see it in contests page

hey guys watch me become grandmaster

Who are these people, that they still don't upvote at this round?

I want to be a Candidate Master in this month :)

He is the chosen one... He will...bring BALANCE...

And he is the guy with the high ground.

I hope there won't be a DDOS attacks sincerely.

Rank 3 contributors will come soon

Best contest announcement ever!

i hope problems grammar is clear as this blog :D

Hoping for a CodeForces round, not an AtCoder round :P

Hoping for no DDOS, no stuck queue, correct statements, no bugs in test data.

I hope attacker buys a bunch of server and becomes poor and fails in attack eventually

perfect Hello from tourist

"On Wednesday, October 16, 2019 at 15:35UTC+1 we will host Codeforces Global Round 5."

Real version:

"On Wednesday, October 16, 2019 at 15:35UTC+1 we will lost a lot of points."

After reading the names of the problems in the contest, one realizes what he meant by

`The round will be perfectly balanced.`

I am not able to submit my code. It is saying that "you have submitted the exact same code before". Why so? Did anyone facing the same problem?

I wrote to you in PM

I misunderstood perfectly balanced as perfectly balanced contest and not perfectly balanced problem statements.

Achievement unlocked: pass pretests on (Harder) problem, fail pretests on (Easier) problem.

P.S. I had at least two severe mistakes in my code, still passed C2!

How to solve C1 ?

Choose any point, and pair it with point that area will be minimised.

Are there any corner cases for this solution? I did exactly the same but failed on the pretest 4.

I think you might have had integer overflow; I also failed pretest 4 and had that issue.

sort by x,y,z 1. first if two adjacent(in the sorted list) x,y are same then they can be pair 2. Once all with x,y equal pairs are done processing all adjacent pairs with same x can be pair 3. rest of adjacent two points can be pair

need to wait system test but I solved it this way, hope its correct

me too. but it's WA :( i don't understand

Actually I did the same and I got TLE. I’m surprised

In E, I misunderstood for a while the condition of being perfectly balanced: 'max of depths" instead of "sum of depths". In that case it becomes a true counting problem, which I think is solvable in O(N log N)... If only I faced that version!

Are they both not the same thing?

If you only restrict max depth then you get a lot of play with some of the other vertices and can place them suboptimally; for example in the n=10 case for restricting sum of depths you are forced to have the complete binary tree on 7 nodes as your first three layers, and then the last three nodes can be distributed in the fourth layer, but when you only restrict max depth then you can take some of the nodes in the third layer and put them in the fourth layer without messing up the restriction.

yeah sorry my bad. i understood something else.

ohh i thought it was max depth til now lol

Did you come up with something that can be solved by FFT?

Exactly.

Well, I did and i was wondering why i was getting WA6 and after the contest i realized that it's sum and not max...

I realized that was sum instead of max only after reading your comment.

What is the pretest 4 for C1?

I initially failed pretest 4 then converted all of variables to long long :D after which it passed the pretests

Spent 1h30m debugging C1, I can't pass pretest 5, did anybody have a similar problem? What was the mistake in your case? (I still can't find my error)

I have some error and failed test 5. I don't understood what I did wrong. I wrote the stress, stressed some test with $$$n=50$$$, then remove some sorts which did nothing in the code, change some variable names and the second solution becomes correct. lol

I had WA6. I reduced the 3d problem to 2d problem (for each x), and then to 1d problem (for each y). Whenever I could not find a pair from the same vertical line, I was looking for a matching point in another vertical line in the same vertical plane, and then was deleting it. Then some lines did not contain any points, and I was still iterating through them, so that made a mess (=WA).

Well in my case I had 3 wrong submissions for pretest 5 .. but later on upsolved it.. What I did in my algo was first sorted the points on the basis of x and then y and then z. Then picked out pairs which are on the same line.. then on the same plane and then the remaining I failed pretest 5 because I didn't find the pair on same line correctly. What I did previously was that when in the sorted points list I found a pair I started searching for the next pair with first point ahead of the second point of the found pair. I changed it to first point should be ahead of the first point of the found pair and it worked! Hope it helps!

Thanks, I just realized my stupid, stupid mistake, I had forgotten to add a return in one of the cases ...

Wasted more than a hour in D because I forgot to return value in query and Codeblocks does not even show that. From now on I will use pre-written codes.

same problem in C :(

I think I missed 2 characters for H....................

UPD: Yep it was actually just 2 characters from my last minute submission.

How to solve B?

iterate through all

`b[i]`

reverse. keep a variable`tmp`

and each time you iterate, update it to the smallest j such that`a[j]`

corresponding to the`b[i]`

has occured. Now for each b[i], it pays a fine if curresponding a[j] occured after tmp, else update tmp. (curresponding means the choosing j such that`a[j]=b[i]`

)use two i,j indices for in and out arrays, then if in[i]!= out[j] remove out[j] element from in array and j++

otherwise i++,j++

You might fail sys tests as it looks n^2.

you are right :(

I use a similar approach but i use a set where to keep track of outgoing cars, i check every time if a[i] is already out then i++ otherwise increment j while a[i] != b[j] and adding b[j] in the set and the final answer is the size of the set.

Here is my submition.

Thanks! I used set and changed

`auto pos = find(ALL(s), in[x]);`

to`auto pos = s.find(in[x]);`

,then it passed.the solution in O(n) is more elegant.

My thought process during the contest went like this:

Let

`t[i]`

be the time the i-th car entered the tunnel.So for instance:

`in[i]: 3 5 2 1 4`

Then

`t[3] = 0, t[5] = 1, t[2] = 2, and so on..`

Also keep the opposite array so you can determine which cars to fine, that is:

`inv[t[i]] = in[i]`

When the cars leave the tunnel, if there are two cars

`j and i`

such that`j < i`

but`t[j] > t[i]`

, then that means that even though j entered the tunnel after i, it left the tunnel before i, so in that case car j definitely surpassed car i and j must be fined.Let's create a set s which will contain

the entrance times of the cars that already left the tunnel.Now let i be the i-th exiting car, for every car j that's already left the tunnel and hasn't been fined (so they are in s) such that

`t[j] > t[i]`

, j must be fined and removed from the set (you can do that by using upper_bound).Note this is $$$O(n\log{}n)$$$ because you insert and remove each element at most once.

But after the contest I realized you actually don't need that set! You can just keep the minimum entrance time :`), though at least to me this way of thinking was more natural.

How to solve problem E?

.

.

<----

can you please explain?

Not sure. Thought answer is 1 if $$$n$$$ is between $$$[2^i , 2^i + 2^i/2)$$$, otherwise 0. got $$$WA$$$ on test case 6.

I completed the code at the last moment but couldn't submit in time.

Here's my solution in short:

Perfectly balanced tree must have the condition that every level, except possible the last, must be completely filled.

What's the condition for striped BSTs? Let's find the condition for each child to match condition of its parent. So, if it's a left child, it should have key parity different than the parent and if it's a right child, it should have key parity different than the parent. Now, observe that for a left child $$$u$$$,

This tells us that every node which is a left child of its parent must have even number of nodes in its right subtree. Similary for every right child $$$u$$$,

This tells us that every node which is a right child of its parent must have odd number of children in its left subtree. With these two observations, we can find number of possible subtrees of height $$$h$$$ like this,

For height $$$1$$$, there is only one tree, one node with no children. For height $$$2$$$, there is only one tree, one node with one child on its left and no child on its right.

For each height $$$h$$$, let's store all the possible trees as a pair $$$(a,b)$$$ where $$$a$$$ is the number of nodes in the left subtree of the root and $$$b$$$ is the number of children in the right subtree of the root. Now, we observe the following simple pattern:

For height $$$1$$$ possible trees: $$$(0,0)$$$, possible sizes: $$$1$$$

For height $$$2$$$: $$$(1,0)$$$, possible sizes: $$$2$$$

For height $$$3$$$: $$$(1, 2)$$$, $$$(2,2)$$$, possible sizes: $$$4$$$, $$$5$$$

For height $$$4$$$: $$$(4, 4)$$$, $$$(5,4)$$$, possible sizes: $$$9$$$, $$$10$$$

For height $$$5$$$: $$$(9,10)$$$, $$$(10,10)$$$, possible sizes: $$$20$$$, $$$21$$$

Can you spot the pattern and prove it? For every height $$$\geq 3$$$, there are exactly two trees possible.

Proof: If for height $$$i$$$ we have possible trees $$$(a,x)$$$ and $$$(b,x)$$$ where $$$x$$$ is even, $$$a$$$ is even and $$$b$$$ is odd, then for height $$$i+1$$$, we can have the right child only as $$$(b,x)$$$ as only then then number of nodes in its left subtree will be even. But the left child can have any of the two values as both satisfy the condition of right subtree having even size. Thus, the new trees are $$$(a+x+1,b+x+1)$$$ and $$$(b+x+1,b+x+1)$$$, which can then be replaced with new $$$A$$$, $$$B$$$ and $$$X$$$ having $$$A = b + x + 1$$$, $$$B = a + x + 1$$$ and $$$X = b + x + 1$$$. Thus, we can say that the pattern holds by induction.

Base case has $$$i = 3$$$, which is satisfied as $$$a = 2$$$, $$$b=1$$$ and $$$x=2$$$.

So, find all possible trees till height $$$\log(\text{max value of n})$$$ and output $$$1$$$ if $$$n$$$ is one of those values and output $$$0$$$ if it isn't.

AC Code: 62737057

1 can be used on the left, 2 can be used oh both sides

4 can be used on both sides, 5 can be used on the left

9 can be used on the left, 10 can be used on both sides

20 can be used on both sides, 21 can be used on the left

so

Awesome round tourist. The questions were very clear and easy to understand. This made my day.

Thanks a lot!

After a long time most difficult problem of codeforces will be changed.

How to solve D ?

Here is my solution — First for each element calculate the next number in direction of clock which is less than half of this value. Build minimum segtree over this values. Then iterate elements in non-decreasing order, you can use segtree to get the moves from i then set value at i to infinity.

Maybe there is not so coding solution.

Duh, I spent freaking hour on C, it was so hard to come up with for me >_>

I am not retard anymore, thanks man for the motivation

Exactly, now I can sleep peacefully at night knowing that I took 25 minutes for a problem that a red needed 1 hour for.

He is exaggerating, he only took 35 minutes

No, I am not, I spent fair amount of time thinking on this problem before getting E, probably even more than on E itself.

.

Same happened with me...finally submitted at last minute. And didn't got time to even read D,E,..

You are lying!! :XD

Agreed, C was much harder than DEF for me (at least if you include implementation)

Good to know I'm not alone xD

I thought there are more AC of C than D. Anyway how to solve F guys ?

thanks tourist for the greatest contest of all time. great round whit great tasks!

editorial?

We all love G because of the reconstruction ;_;

What is the solution for C1 that fails on C2?

For each point, select the closest one? $$$O(N^2)$$$, I think.

You can solve C1 in n^2, but not C2.

I did this. For each point, iterate over all other remaining points, find the point which forms a cuboid with minimum area, and delete these two. Repeat till no points remain. O(n^2).

Are there any easy implementations for C? My approach to C1+C2:

For all vertical lines (x = const, y = const) containing points, just pair them (and forget) in order of increase of z. Then, you do not care about z anymore, so just drop all the points on the floor and solve 2d problem (reducing it in the same way to 1d).

Looks simple but, damn, took hours to make it work.

Well, you can just sort them by z, then y and then x.

Then for adjacent points in this sorted set if they have same y and z, pair them.

Then you do another round and pair those with same z.

Then finally pair the remaining ones.

Haha, it is actually the same approach, but very much easier to implement when phrased like this. Thanks mate!

C2. Simple greedy solution with much sort. Easy implementation.

'Pseudocode':1.1. Sort by x,y,z, scan and remove pairs of x1==x2 and y1==y2

1.2. Sort by x,z,y, scan and remove pairs of x1==x2 and z1==z2

1.3. Sort by z,y,x, scan and remove pairs of z1==z2 and y1==y2

2.1. Sort by x,y,z, scan and remove pairs of x1==x2

2.2. Sort by y,x,z, scan and remove pairs of y1==y2

2.3. Sort by z,x,y, scan and remove pairs of z1==z2

Edit. Same as errorgorn's explanation.Problem C:

My answer seems to be correct in the first example but in the secound one it apears to me as if it was inverted (first line is at the end etc.). My code is in Java 62732376. (I think in this exact submission I changed the output order therefore the TreeSet in ex 1 apperas to be inverted)

My idea is to eliminate the negative values by shifting all values by 10^8. Then I maintain a TreeSet, which is ordered by the manhattan distance to (0,0,0) (Alternatively I would have tryed euclidian distance). Then I go on to say that the first element of the TreeSet together with the last will be contained in the last "Snap" (the next two in the pre-last and so on). This should allways remove two elements that are closest together, hence there is no other element in the bounding box.

Is my solution wrong or did I mess something up?

Nevermind everything works as intended. I just didn't notice.

The queue times today were amazing, best I have ever seen. Thanks Codeforces!

one reason can be questions were good, so random submissions were less.

I am not smart as tourist, but I am smart enough to tell that this statement came out wrong- "The round will be perfectly balanced. As all things should be."(not talking about name of problems). I guess overconfidence is bad for everyone.

Anyone use BIT to solve B?

I almost did. Used ordered_set, shame on me

I used segment tree.

I did, though it seemed ridiculous to use BIT in B (which is supposed to be at Div2B level)...

I actually thought the same but BIT is intuitive. Don't want to waste time thinking.And then I found no one use BIT in my room XD.

I actually had no idea how I can do without BIT until I heard the solution from others lol Was kind of confused...

Me too,I'm stupid QAQ.

QAQ...

In problem F, if there are no dominoes initially, number of ways for a (h, w) grid, $$$f(h,w) = f(h, w-1)+\sum_{i=1}^{h}f(i-1,w-2)*f(h-i,w-2)+\sum_{i=1}^{h-1}f(i-1,w-1)*f(h-i-1,w-1)$$$

where $$$f(h, 0) = 1,f(0, w) = 1$$$. Is this recursion correct?

Edit: Okay, it was wrong.Why is it wrong?

The two parts (upper and lower) created by placing a domino in the leftmost column are not independent.

I got runtime error on test 1, but it works fine on my pc. It is simiar to this erorr: . Why does this happen? How can I get identically same compilers etc. on my machine? Because this is really frustrating.

Similar error

Have you tried custom invocation?

Yes, I am fixing it to work on custom invocation right now, but the contest is over so who cares now. I am just wondering why codeforces judge doesnt work same as mine. How can I configure my compiler to be same as cf custom invocation?

Protip:

~~to win a contest, solve problems quickly and correctly.~~if you want to see the front of the queue + failures on systests, filter by verdict Rejected and go to the page where the queue ends. You'll also see your solutions there if they fail.How to solve D ?

Can't you wait for editorial

Funny solution for C2 (surprisingly not the one I was unsuccessfully trying to debug for 1h30min...):

Use WSPD to solve the all-nearest neighbors problem in $$$O(n\log n)$$$. Observe that in the resulting graph, there is always some matching of size $$$\theta(n)$$$, which can be found greedily (max. degree is bounded).

We can surely print the matching and recursively solve the rest. The complexity of this is actually $$$O(n\log n)$$$, since we always divide $$$n$$$ by some constant.

What's WSPD?

tourist making Reds and Oranges go derp on problem AThe problem-set was indeed balanced.Atleast by their names. XD

Is the heuristic solution intended to solve H?

You can kill many heuristic solutions by setting the problem to sort a signed permutation instead of a binary sequence.

And I think this problem is also easy to solve by Google and find a paper of it.

This was not intended, I probably should've done a better research beforehand, sorry about that.

The intended solution uses exactly $$$n+1$$$ reversals, and I think it heavily utilizes the fact that it's a binary sequence.

My solution is deterministic and works for sequences over an arbitrarily large alphabet. More specifically, it does the following:

Given a sequence of numbers $$$\pm1$$$, $$$\pm2$$$, ..., $$$\pm n$$$ where each absolute value occurs exactly once, we can do the following operation: choose a prefix, reverse it and multiply it by $$$-1$$$. Using no more than $$$2n$$$ operations I can transform it into $$$(1, 2, \ldots, n)$$$.

Basically on each move we spend $$$2$$$ operations to do one of the following:

(after each operation we renumber the whole sequence for convenience, but it is more about the details)

When it's not possible to do any of the above, it means that our sequence is exactly $$$(-1, -2, -3, \ldots, -n)$$$, and now we can alternate "flipping" prefixes of length $$$n - 1$$$ and $$$n$$$ ($$$2n$$$ operations in total).

When we are lost with a sequence of length $$$1$$$ we may need to spend one more operation to make it positive. It couldn't occur in the last case, so in this case we spent no more than $$$2n - 2$$$ operations and the total number of operations is $$$2n - 1$$$. If we ended up transforming the $$$(-1, -2, -3, \ldots)$$$ then we spent $$$2n$$$ operations in total.

Could you clarify what exactly is done when the sequence is $$$(-1, -2, \dots, -n)$$$?

Do the operation with prefixes of sizes $$$n-1$$$, $$$n$$$, $$$n-1$$$, $$$n$$$, etc. Each pair of operations moves the last number to the beginning, multiplying it by $$$-1$$$. Consider it for $$$n=5$$$:

`-1 -2 -3 -4 -5`

`4 3 2 1 -5`

`5 -1 -2 -3 -4`

`3 2 1 -5 -4`

`4 5 -1 -2 -3`

`2 1 -5 -4 -3`

`3 4 5 -1 -2`

`1 -5 -4 -3 -2`

`2 3 4 5 -1`

`-5 -4 -3 -2 -1`

`1 2 3 4 5`

with same code I got WA_on_33 for C1 and AC for C2 :3 and I should have got WA for C2 also :3 have you forgot to add the same cases for C2 which have been used for C1 ? :3

Congratulations to Um_nik on the tenth place!

.

This was not all that balanced, to be honest. Though, I am not the one to complain, as I was too slow to write F in time.

I'll opt for a response that's balanced between "completely balanced" and "not all that balanced": it was quite balanced for a combined division round. There's one problem that can separate the winner, one problem that can separate the top few from the rest of skilled contestants, two that can separate the skilled contestants from the rest, two that can separate roughly div1 from div2 and then some easy shit.

The number of solutions in longer contests can be misleading if they span a wider range of points and situations like yours add some variance too.

Well, you're right, it was a good contest. But it was the first time I was participating in a Global Contest and maybe I just like the classic format more, when you have time to think on harder tasks.

I prefer that format too. I just don't care much about quickly solving easy problems or competing against low-rated people.

300iq, top 10 codeforces !!!

nope :P

top 11((

I think the contest should be rated for everyone who opens contest page not only for those who submit answers. Because one can check the problems and if they look unsolvable for him then he can leave the contest and nothing will happen!!!

The downvotes depict how much people care about what you think

It shows how many people do this cheat!!! :))))

I don't think so. Some people, like me, like to open the problems, think about how to do each question in their mind, and then do other things.

Also, if you're strong enough, you don't need to care about these people.

Every game will be as fair as possible, but it will not be absolutely fair.

It was not balanced.

when will T-shirts winners announce ?

I let one of my friends borrow my laptop... -198 :):):)

I'm still unable to view other users' submissions for this contest. Is that intentional? (Submission links appear the way they do when the contest is still in progress.)

Edit: now it's working as expected.

Mike is busy playing Pubg

Runtime Error in B on SysTests is not what I exactly expected. I mean I understand that is my fault, but it is really strange.

What on earth is this pretest 5 of C1!!!!

Since the test cases are still hidden, could anybody please help me find what is wrong with my solution for C1?

Codeis incorrect, it should be

Thanks a lot for your help! What a silly mistake that I couldn't find for hours!

62736318 62724834 Can anyone explain what is wrong in both submissions?

If you want to divide a negative number by 2, doing (x >> 1) is wrong ._. It will break the structure of the int, for example, it will become positive.

62747147 then why this one passed?

Similar thing happened to me.. i think it's because float has -0 .. so without converting to int it can print -0.. which is not int... int has no -0, only 0. You can test it by giving -1 as input multiple times.

This is interesting. I was wrong.

Ok, so it was because of double 0.0 was outputted as "-0". It happens.

I'm really comfuse that I only change vector to array then TLE bacame AC on problem D, can anyone help me. TLE AC

(this comment is old, but in case you didn't figure that out) It's simply an out-of-bound write to array. The

`ans`

array is written to at indices > n+5.(It took me way too long to realize that it triggers undefined behavior, while if vector is used for

`ans`

then it would just cause WA and Codeforces can run the diagnostic.)When

`v`

is a local array, writing to indices past n in ans array would actually write to indices approx.`i-n`

in array v (because of how GCC implement VLA), so it doesn't affect the result.Thanks you for looking my code and reply, that was really hard to figure out.

Finally, people who will receive T-shirts!

Great!

Congrats

Wow! I can't believe I won a T-shirt. How and when do we receive it?

Our team will contact you pretty soon, no worries.

Cool, thanks.

Alhamdulillah

Wow!

{Del}

Did anyone use Kd tree to solve C2?

Can you elaborate more on how to use Kd tree for this problem?

Yes, it can be used to solve C2.

Just use Kd tree to get the closest point for each point and pair them together, there are O(logn) phases and each phase is O(N * sqrt(N)) or O(N * logN) if you assume points are randomly distributed. Overall the complexity is O(N * sqrt(N)) or O(N * logN) because the number of points gets at least halved in a phase.