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
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 :D
But it is a soul for a soul
You forgot to thank MikeMirzyanov and Codeforces.
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"
You ready?! Let's go!
Yeah, for those of you that wanna know what codeforces all about
It's like this y'all (c'mon)
This is ten percent bruteforce
Twenty percent greedy
Fifteen percent concentrated power of geometry
Five percent hacks
Fifty percent wrong answer
And a hundred percent reason to participate in contest.
GLHF everyone !!
And still you are unrated
Mike shinoda
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 announcement
Here 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
tourist !!!
Everytime I refresh this blog, I can see an increase in the amount of upvotes.
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 !
It will be the best contest ever
I can't wait :)
But the other writers are also very good!
The round will be perfectly balanced. As all things should be
So 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.
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, ISeeDS, MemoryLimitExceeded and YaAAbu 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 YaAAbu not be in the same round at the same time?
you just mentioned 11 people for a stolen yet terrible joke. good one mate
Upvote too.
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.
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...
rating++; CBGer are champions :>>>>>>>>>>
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.
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
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!
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 NEWS
tourist 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.
Rank 3 contributors will come soon
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
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?
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.
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 variabletmp
and each time you iterate, update it to the smallest j such thata[j]
corresponding to theb[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 thata[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.
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 thatj < i
butt[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
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.
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.
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?
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.
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.
Since the test cases are still hidden, could anybody please help me find what is wrong with my solution for C1?
is 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?
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!
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.