Привет, Codeforces!
В Mar/10/2022 17:35 (Moscow time) состоится Educational Codeforces Round 124 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
UPD: Разбор опубликован
Me to chance pupil coder again,,,,,
Hope your rating can get over 1200 after this contest! By the way, your profile photo looks interesting, so I used it as my profile photo. :)
Thanks you for your wising,,,, By the way i need perform like your profile graph and reach 1600+ rating,,, how can i do..../?
Maybe you can try to solve some problems that have a higher rating than you currently have in the ProblemSet？For example, try to solve problems with a rating about 1400？
At first I thought you were talking to yourself . . .
Good luck everyone !
Very sad that I can't participate
Oh no that is so sad :( Give me your password, I shall participate in your stead.
lol
lol
Good luck everyone!!
Chance to get to pupil....
Chance to leave pupil
Sadly, overlaps with Reply Challenge.
Probably, if there's lot of participants wishing take part in both, could be moved one hour earlier?
Hope everyone to get higher rating in this round!
Good luck everyone!
contest is a kind of festival to me!
Kindly note unusually usual time.
My first comment. plz I really hope to be the expert
I should be practice more
Hope my rating will get over 1900 today.Good luck to everyone as well.
Could some one create a group to collect all educational contests like Div. 3 ?
Use this website here you can filter contest based on contest types and many more things you can do https://clashofcodes.herokuapp.com/codeforces
Why ask to signup first? How is signing up going to benefit the user?
I guess they made it mandatory recently as i made an account previously so i don't know about it but it is a good website can make accout there google auth.
Considering my downward trend of performance in the recent Educationals, I can't help but
I have a question how do we know the difference between final standings after system tests and when hacking phase is finished? from what I have seen they don't write anything to distinguish that
C was tough one
Nice joke..
DistanceForces
"absolute"ly.
$$$|$$$ codeforces $$$|$$$.
Why such a huge difference between problem B and C, kinda unfair for pupil / specialists
welcome
Why such a huge difference between problem B and C, kinda unfair for pupil / specialists
Actually it was not so unfair since you required just one observation for C.
For optimum result, it is necessary to connect the corners of both networks a and b to some computer of opposite row.
If the leftmost or rightmost connected computer of any row is broken further left or right computers respectively wont be part of combined network.
I am sorry but ... shouldn't connecting any 2 pairs do it? I mean having 2 connections between 2 distinct pairs, this way if one fails the any other is reachable.
I spent about 30 minutes asking myself why the hell does the first test case need to connect 4 pairs.
No it is not necessary.
If the leftmost or rightmost connected computer of any row is broken further left or right computers respectively wont be part of combined network. Hence corners must be connected to other row.
Shouldn't they be reachable from the other functioning corner? Or you're saying connections are directed (one way)?
No they wont be.
Look, consider any row whose corner is not connected. Lets say it is row B and its left corner is not connected. Now, if the leftmost connected system of row B is broken than any computer left of that broken computer would not be a part of combined network anymore.
Hope it helps :)
Actually I figured out all of this, but I don't know what I am missing, maybe I'll find out tomorrow, pretty stressed out from today's contest
did you figure it out?
yeah for the X, |X and X| type of cases, I was doing a loop from 1 to n — 1, but 0 to n — 1 works, I am not sure why, because I cant see the test cases. Maybe some corner cases were getting missed
The idea is that if both a0b0 and a0bn-1 have the same distance, you might choose the wrong one i.e. if you pick a0b0, there might exist a smaller cost that requires you to pick a0bn-1
Ahhh, you are making sense, damnit
I disagree with your opinion mira from aim
I think most of the people got the approach but got messed up in corner cases, including me. :(
Yes, same for me :(
welcome
I think i know my mistake in C but not enough time damn I wasted so much time thinking about stupid possibilities that doesn't help in anything
we could do it in three wires right ? like this
1 0 0 2 0 3
1 0 0 3 0 2
i tried only 2 wires or 4 but not 3.
you just need 2 wires
link 1 1 and 3 2
make it a loop
That's not the values it's how it's possible to link it the ones with the same number are linked sorry it wasn't clear
oh,yes
we need consider head-head,tail-tail,head-tail,and head-other,tail-other
possibly appear headA-headB + tailA-otherB + tailB+otherA
Experts and CMs after solving A-D:
Btw Im writing this comment 23 minutes before the end of the contest. I have no idea what to do with all this time on my hand:))
And some Ms, too
I don't know what you are talking about...
...
shake hands...
What was the testcase 2 in C ??
Isn't problem c only about first and last index of both arrays and finding optimum values in their counterpart arrays?
Yes. But you need to take into account what happens, if you connect 2 of those 4 nodes to each other.
hints for problem E pls
Dlete
The bipartite graph consists of disjoint cycles. Each cycle contains an equal number of nodes from either part.
Say that we know the sum of $$$MM(G(l,r,L,R))$$$ for some fixed $$$l,r$$$ over every $$$L,R$$$. Let us extend $$$[l,r]$$$ to $$$[l,r+1]$$$. How does this sum change?
When we add a new node, it either extends a path or completes a cycle.
Think the contribution of all subsegment in a loop
How to solve C and D?
For C : a[0],a[n-1],b[0],b[n-1] all must have connection with other row any element efficiently..
Lmao I can't believe I thought any 4 points work and now I see it's nowhere near correct. Thanks very much!
I did BFS from the borders for D. Saving information in a
map<pair<int,int>,...>D can be solve by dfs.. right ?
and C statement was confusing for me :(
My DFS failed, needed BFS. What do you do if your DFS has back edges?
I used BFS (from neighboring points not in the given set) and still got TLE. Is this not the idea? Or is there a way to speed up my BFS? 149168850
Phew, just looked at your code, it looks ok in principle, your times seem to be ~1.5-2x slower than mine. Guess you need constant optimisation here maybe? In your first loop, when looking for borders, it seems that you can push solitary points 4x into the queue. You can put a
continue;there in your ifs. Also you can mark them as used then already.Yes, constant optimisation did the trick: 149174036
Ah, didn't think to optimize constants. That did the trick. Thanks!
I passed the pretest with dp and a lot of sortings.
What was the 2nd testcase in C?? I tried all the cases can someone tell what I was missing?149157891
In the last for loop of your code, you have written: aml=min(abs(a[0]-b[i]),amf); That should be: amf=min(abs(a[0]-b[i]),amf);
Is DP the correct approach for D? I tried to check the answers of my neighbours and pick the best for me but got TLE on test case 9 :(
a topological sort to decide the distance of closest point
You can use a DP-like idea. The intuition for me was, for a point, the closest point to [x, y] must either have the same x value (so it's on the same vertical line), or it must be on a path through [x — 1, y] or [x + 1, y].
I tried your idea. Is this way is correct to implement it? 149191779
I got RE on testcase9.
Failing testcase: Ticket 1708
What's so special about the testcase? It contains all points in the interval $$$[1,5] \times [1, 5]$$$
Thanks
How to solve D? I used dfs to transmit the nearest point but got wrong answer! :-(
I solved using multi-source BFS from all untaken points neighbouring taken points
I tried something similar, but because i am not pro like it took some time for me to code it well. basically what i did is pushed all the points that has an direct answer into queue. (more like pushed the outer layer of points in queue first). then i translated outer layer's answers to inner layers. but i got Wrong answer on Test 9. can you help if you find anything sussy here?
Edit: no worries got accepted. it. was a minor issue :(.
That's unlucky. I was trying to debug for you but couldn't understand the candidates things. In principle your idea is correct, and equivalent to what I described as multi-source BFS, except starting with the outermost points rather than untaken points. Should achieve the same result.
thanks for trying your code is sooo clean.
Thanks. Although actually your approach is quicker and less memory intensive as it doesn't require storing all of the neighbouring points (which can increase the size of the graph by a factor of 5).
I used bfs and I got accepted
why does bfs not time out
200k points, at most 800k unused neighbours. Graph has max size 10^6. Why would this time out?
yeah it won't , i didn't think in the neighbour direction
I have the same problem as you
What was the technique for B? I wasted so much time on A due to a stupid typo.
any pair of i, j must satisfy Ai * 3 <= Aj
Powers of 3 work
Try writing the inequality that needs to be satisfied based on the pair you pick.
Suppose you'll do the operation on $$$x$$$ and $$$mx$$$ which are present in the array where $$$m \geq 1$$$. After the operation, $$$x$$$ and $$$mx$$$ will be replaced by $$$mx - x$$$, we want the change of the sum to be greater or equal to the previous sum, which implies $$$2(mx - x) \geq x + mx$$$ $$$\implies m \geq 3$$$
So, you build the array like this: $$$[1, 3, 9, 27, ...]$$$ until the array size is $$$n$$$ or the value gets higher than $$$10^9$$$. For the later case the output is $$$NO$$$.
How to solve C? I tried with all 3 cases, but WA on tc2 149150730
try link left and right end of A and B. either use optimal point in opposite array, or link two end points.
Failing testcase: Ticket 1579
In C my idea was that computers at end must be connected to some other computer, so we must find a way to minimize this. But for whole 1 hour I was not able to implement due to edge cases of computer at ends being connected to each other. I knew edge cases(like first computer of array A can be connected to first computer of B or last computer of B or both first and last computer of B etc.) but was not able to implement and deal with those.
Any tips on how to improve this ability? Sometimes I break down a problem in different edge cases and get overwhelmed by that.
it really was an intersting contest i have solved C with topology :" which i have studied in CS
Same! Lmao maybe that's why they ask CS fundamentals in interviews
s1=abs(a[0]-b[0])+abs(a[n-1]+b[n-1])
s2=abs(a[n-1]-b[0])+abs(a[0]-b[n-1])
s3= For a[0], find the element in b such that difference is minimum using binary search and mark the index for that element. Similarly for a[n-1]. Now if both b[0] and b[n-1] are marked then the sum is already calculated, else if any of the b[0] or b[n-1] is unmarked, find the optimum element in a and take the sum.
ans=min(s1,s2,s3)
Still WA on test 2 :( 149166751
I calculated all 7 cases.
[Updated] Failing testcase: Ticket 1699
How to solve D ? I got TLE on test 9.
I think it's BFS + Dijkstra. If a point in the input is next to any empty point, then the answer is either 1 or 2. The other points must border at least some point in the input. From there you just BFS + Dijkstra to get the point with the least distance to empty point and populate the neighboors
Can anybody help me figure out what‘s wrong with my code149129168 in problem B？ it runs well on my computer but kept failing the preset when I submit, I was literally driven crazy during the contest (╥_╥)
move "ios::sync_with_stdio(false);" to the very beginning of the main function.
maybe you can try to use CUSTOM TEST on Codeforces platform when you meet questions like this.
Put
before reading the inputs, not after.
what happens if we put after, will it cause undefined behaviour
In problem D, I used a similar idea as This Atcoder Problem. For each point, i binary searched for the shortest distance and used merge-sort tree to check the number of points that has smaller distance than a certain number with that point. I noticed that the distance should be smaller than sqrt(n), so after finding the distance i brute forced through all possible points for the answer.
I think The final complexity is
O(nlog^3 + n*sqrt(n)*log)but got TLE on test 9. This will be my 6th consecutive rating drop.(╥_╥)upd: My contest submission
my submission for D giving MLE... If anyone have experienced similar problem, please help me
How to solve D?
How to solve D?
I used bfs，put the unused neighbours in the queue，and calc the answer when you meet a node which is not among the given $$$n$$$ points.
Is $$$O(Nsqrt(NlgN))$$$ intended for problem F? I know that we can do pure $$$Nsqrt(N)$$$ if we solve for each block for each monster instead of for each monster for each block, but still, it sounds like a lot of work :(
Model solution is $$$O(N \log N)$$$, but we decided to allow slower solutions with good implementation pass (although $$$O(N \sqrt{N \log N})$$$ sounds kinda scary)
Apparently even $$$O(N \sqrt{N} \log N)$$$ can pass :)
Well, the time limits were kinda generous in this problem (the model solution runs in something like 1s on 32-bit C++ compiler). Although 3931 ms out of 4000 sounds very scary
Not at all mine runs in 1.5 seconds which is kind of okay also it's really easy to write and you can argue that if written with prefix sum the operations would be simple enough that you wouldn't be able to differentiate between $$$O(NlgN)$$$ and $$$O(NsqrtN)$$$ "unless you go full Chinese on the constraints/test data ig".
I changed to unordered_map, so $$$O(N \sqrt N)$$$, and it passed, although 3899 ms. D:
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
Thank you so much! This is amazing!
is cf_predictor give correct results? why it predicts low increasing values in this contest ? is rating in code forces changed?
is cf_predictor gives correct predicted values ? i think that there must much increasing points in rating than i see in standings.
Yes, I have found the carrot chrome extension to be more accurate.
Screw C. Took more than an hr to solve it, and 40 minutes to finish D but not time to submit it
My approach for D:
Rotate coordinate space by 45 degree by transforming (x,y) with (x+y, x-y). Now, for a point X, observe that all 4 points at distance 1 form a square, then next 8 points at distance 2 form another square and so on. Each square will have 4D points here D is distance from X.
Since N is 2*10^5, D can be at most 350. So for each point, I checked number of input points in squares of length 1, 2...350. As soon as I get a square of length d which has less than 4d points, we need to search in this square.
Then its simply searching all points at distance d and returning any one excluded point.
Complexity: O( N*Sqrt(N)*log(N) ) Solution: 149223014
But solution TLE'd on test case 30. Would appreciate if someone can take a look at my code and suggest scope for optimization.
How did you check the number of points in a square?
I got TLE on test 30 149175151. I doubt the time complexity but also can't imagine what does the worst case look like.
Yeah, I think theoretically the number of operations in the worst case would be around 5.6*10^9 [(2*10^5)*(350)*(20)*(4)]
I was trying to use openmp's parallel functionality, does cf supports it? i am not getting any error nor can i observe any significate difference in execution time.
without pragma 149232334
with pragma 149233499
changed your unordered set to set, because i guess performance of hash structure is complicated to guess.
can you find why it is printing an already existing point?
Thanks. Fixed a silly bug. Updated the comment.
You can eliminate use of set, you already have list of sorted point with respect to both dimensions.
I have a solution which barely passes and it was possible thanks to IceKnight1093 optimizing my previous code by omitting pairs.
It uses pragmas and shit so it's totally not safe for a contest submission.
Perhaps someone else can bother to optimize it further.
I solved D considering/using that answer can never be greater than 700 . I made pair of interval for each coordinate of x from 0 to 2*10^5+1 which doesn't have a y coordinate . Then for point {x_i , y_i} it's just binary search the left nearest and right nearest value of y for each z s.t. ( z>=x-700 and z<=x+700)
It's ACs in approx 1 sec
Solution
My ideas for D (not AC on contest) :
Pick a random unvisited point name it $$$p$$$ and mark this point as visited
Do floodfill to another points adjacent from $$$p$$$ and mark them all as visited (adjacent : manhattan distance is equal to 1)
So now from all the floodfilled points we form a connected component from $$$p$$$. Pick border points from this connected component (a point is called border if there's at least 1 adjacent point which doesn't exist in the input)
From all border points, we can get their respective "source" (i.e. the neighboring point which is not in the input)
Do multisource BFS from all border points and now you can get source for all non-border points by setting it to the source of their nearest border points
My implementation 149198396
I love the idea of the solution! Didn't quite like C (because caseworks), but this problem has a beautiful solution
chance to get specialist...
I want to know how people know this formula for problem B :
(b — a) * 2 >= b + a
We need the next sum to be no less than the previous one. If we change a and b to |a — b| then their sum will be equal to |a — b| + |a — b|. We can expand the module and get (a — b) *2. And by condition, we want this sum to be at least a + b. => 2 * (a — b) >= a + b
when are the ratings going to update as it's past 12 hr already?
When will the rating be changed?
same doubt its showing in unrated constest for now
System testing just started
How did you know that?
same question
You did not participate in the contest, why do you care about it? This kind of question has been asked a ton of times for every Educational round.
The rating is still not updated......
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
I didn’t get rated yet ?? Why any idea
Hey does anyone know why I didn’t get rated yet is educational round ?
No one got rated yet. The editorial has just been released so I would assume ratings will be updated soon too.
Me here reloading the website every 10 seconds for +2 delta :/
In yesterday's competition, my code for question B was judged to be duplicate with others, but my code was submitted earlier, so there is no possibility of plagiarism at all. Plus, I want to score 2100 for this game, so there's no way I'm giving away my code to anyone else. Moreover, the solution shown in my code is a very general solution, and it is very easy to repeat it in a small amount of code. I don't think it's reasonable. Please check it carefully!
MikeMirzayanov，I could have been a master, but now I'm an expert. Please check it! Thank you!
same with me bro i got plagiarism on A. how can it be possible problem A was one liner
I hope for a reasonable explanation. This accident reduced my rating by 300 :(
I can understand bro but I don't think our issues will be responded
Thank you for your comfort. I hope there will be no similar problems in the future. Good luck.
I had a coincidence of my solution(149124483) matching with solution(149099666) of Performanceartist for the problem 1651B . clearly it is a coincidence as he is a candidate master and i a newbie with no prior communication between us. He submitted his solution much before me. please look into it.
Your text to link here...
he(performanceartist) has commented for the same problem.
A sad coincidence, isn't it? Haha. We need to work hard in the coming contests bro :)
The worst C problem I have ever solved.
I can't even see if there is any same place between my code 234454715 and 234466169, can officials check again, and it's no reason to copy such a easy problem with risks.