Привет, Codeforces!
Мы с Igorfardoc рады представить вам наш Codeforces Round 813 (Div. 2), который пройдет в 13.08.2022 17:35 (Московское время). Этот раунд будет рейтинговым для участников, чей рейтинг ниже, чем 2100.
Мы хотим выразить благодарность:
- DishonoredRighteous за координацию раунда.
- Um_nik, Ormlis, errorgorn, FairyWinx, golikovnik, 74TrAkToR, thenymphsofdelphi, plagues, Kon567889, AlperenT, Alexdat2000, gotexans, welleyth, GlowCheese, satyam343, thanhchauns2, SlavicG, _Vanilla_, jampm, QBaraki, LeCaToX за тестирование раунда и полезный фидбэк.
- MikeMirzayanov за Codeforces и Polygon.
Вам будут поданы 6 задач, одна из которых поделена на 2 подзадачи, и у вас будет 2 часа 15 минут, чтобы их распробовать.
Надеюсь вы не подавитесь 😋
Разбалловка: 500 — 1000 — 1500 — 2000 — (2000 — 750) — 3500
PS
UPD2: Поздравляем победителей!
Div. 2:
Div. 1:
As a tester, don’t even think of skipping this round…
As a competitive programmer I never even think about SKIPPING A ROUND.
So true
You can do anything, just don't give up!
I read this in Naruto's voice lmao. Epic!
dattebayo
sure won't
As a tester, I can confirn this round is great.
As an author's helper, I think it will be nice
PermutationMathCodeforces round.Codeforces Round 813 (Div.2) rp ++ ！！！
Hope to expert！
As a tester I tested this round
As a down-voter I down-voted this comment
[Deleted]
As a BlindingKnight-voter I BlindingKnight-voted this comment
I hope I can solve ABC！
Best of luck
Good luck
wish u luck
Hope I became CM on this round and tasks would be good.
Hope I become an Expert and you become CM.
Good luck :)
What's the meaning of "You will be served 6 problems, one of which is divided into two subtasks," ✍(◔◡◔)
One problem has an easy version and a hard version.
Thank You
Looking forward to it !
looking forward to [ hidden reference] and [bonus versions]
Most of the references are not very hidden, just some quote in the start of the statement...
True AF.
Hope to specialist
Hope to expert
Good luck
Thanks for releasing the score distribution very early. I liked it
This round looks so balanced. Hope everyone get a positive delta :P
My man got the time machine
apparently not
As a tester, this round is gud
-QuangBuiCP
Do we uniformly pick $$$k$$$ unique problems to solve or what? thinking
There is plenty of time to sample all the problems! But maybe not enough time to complete all of them, since some of the dishes are quite big.
Oh nice, that sounds promising.
Good luck to all participants of this round, as well as IOI participants. Hope to rating>=1300
As a tester of the this round and the recent one, I confirm that both rounds are really great!!!
As a tester give me
GFcontributionProblems are great! It was interesting to solve them.
this contest seems suspect, I will participate from alt account
Is Marinush your alt?
oh god damnit
oh god damnit
Could anyone tell me what does "a hidden reference" mean?
The emoji after "Hope you don't choke" seems sus
Anyways good luck to everyone who is doing the round!
Good luck to everyone!
good luck to you too ☺
I wish and hope short statements like this post. I like it
hope i will become specialist after this round
As a participant, I never skip any Div. 2's, unless it's bad.
Codeforces Round 813 (Div.2) rp ++ ！！！
Hope to specialist！
damn
I didn't know palindromes would ever make me think that much.
As a specialist, I hope I can reach expert.
Good luck to everyone, don't skip a contest just because you are afraid to lose rating! You got this!
Hope to get to Master.
Looks like a fun round, will be participating
Ah great, Round 813 on 8/13 and my birthday.
Wish everyone good luck and hope I will be well enough to participate.
Is there a food theme? "You will be served ...", "you will have 2 hours and 15 minutes to sample them", "Hope you don't choke"
No, only in the announcement)
Will your next round be on CodeChef
No.
Hope I become specialist this time!
Vladithur is a giga chad, so I'll have to participate.
I am sorry, unable to attend since it is 1:35 am in my timezone. Hope others have fun
can anyone please explain to me the hidden reference thing?
It just means that each problem has some kind of reference. For example, maybe the problem contains a quote from some particular movie or something. This has no bearing on the actual problem design whatsoever, so you don't have to worry about trying to find these references.
as a participant, i am going to participate
Friends, is E(2000-750) saying it's in that range of difficulty?
Problem E will have two subtasks: the first has a base score of 2000 and the second has a base score of 750.
Since the first one is scored much higher than the second, my guess is that the second subtask is an extension or improvement to the first subtask, so you would need to be able to complete the first subtask first to be able to solve the second subtask. Solving the first subtask only achieves a base score of 2000, but solving both subtasks is worth a base score of (2000 + 750 = 2750).
I don't think it would be possible to solve the second subtask before the first (since such problems would generally present the Easy version before the Hard version).
Ouch, thanks!
I think E1 is easier than D.
I don't think so >_<
I have been very lucky in the past few contests, but feel like I would eat a heavy negative delta this round. :_)
Trying to reach Expert ;-)
HORAYYY!!
today is 8/13 and this is round 813, wow!
The Date is 8.13 and the Round is 813
Wish Everyone non-negative rating changes...
All the Best Guys!!!
Good luck to everyone participating!
.
I think it's completely unreasonable to expect a random user who decided to problemset to have power just because they are high rated. I won't get into the semantics of what you should have done, but expecting a user to know what to do is like walking up to a customer who's looking at bad standards (as another customer) in a shop and asking them where you can report bad standards. At best, you might be referred to a website, and at worst they won't know.
Hope to get to Master.
Really happy right now :>.
Nice! Good luck on future Div 1 contests!
This round is so NICE :3
Permutation Forces!
Well, I'm going to play OSU! instead of stucking on D. Click the circle !
Is osu a dedicated meme for speedforces?
Sounds interesting.
idk yet, but I always get some idea when I playing osu,
so I did that then came up with the solution of D. :)
I like the style very much
SPEEDFORCES
spermutation forces
difficulty difference between C and D is high
I am so ridiculously bad at guessforces, its always wrong wtf
Hello fellow bad at guessforces! If you're also like me who insists on finding the pattern instead of actually solving the problem, try running brute-force solutions for smaller cases of $$$n$$$ and watch the pattern like so.
thats what I did after getting the WA, but that problem is too trivial to even require that
WrongAnswerOnPretest2Forces
I didn't like this round. When I solve anything gets me wrong answer on pretest 2! ◑﹏◐. But actually I liked the clear statements ❤
may be you are missing something small(try thinking of test cases that will fail your code and handle these cases) there is still some time so keep trying the first 3 problems are quite easy
Congratulations for being pupil ❤
thanks ❤. happy to see someone from mansourah here btw. good luck in the upcoming rounds.
Thank You ❤(✿◕‿◕✿)
D>>>>>>C
actually D is not much harder than C. It is just that... I got WA 5 times (I got the idea tho).
this is the solution I thought for E2 but couldn't code in time: (based on solution for E1)
Sort the queries wrt $$$l$$$, and maintain answer for each fixed $$$k$$$ in a segment tree, for $$$1 \leq k \leq MAX$$$.
We can see that each $$$i$$$ belongs to at-most $$$MAX/l$$$ numbers $$$k$$$ such that there exists a triple $$$(i, j, k)$$$ for which $$$lcm(i, j, k) \gt i+j+k$$$ (those $$$k$$$ are multiples of $$$i$$$). So we need to update only those values of $$$k$$$ in segment tree which stores the number of triples with largest number $$$k$$$.. Hence, summing up over $$$i$$$ from $$$1...MAX$$$, we get $$$O(MAX log(MAX))$$$ complexity for updates in total, and $$$log(N)$$$ for querying over segment tree
Idk if your approach works, but I did a sweepline w.r.t $$$r$$$, and whenever we increase $$$r$$$, we first check the two cases when $$$lcm(i, j, r) = 2r \land i + j \gt r$$$ which only happens if $$$(i, j) = (\frac{1}{2} k, \frac{2}{3} k),$$$ $$$(\frac{2}{5} k, \frac{2}{3} k)$$$, which we can simply point update on our segment tree, and then, for divisors of $$$r$$$, we first sort them and iterate them from the closest to the furthest from $$$r$$$ and we make the point updates accordingly (we should add 0, 1, 2, ... in this order). Then, we can calculate the total number of bad tuples which we can subtract from the total $$${r-l+1 \choose{3}}$$$
Its essentially the same solution, you look at it from the perspective of the number $$$k$$$, so you update $$$r$$$, while I sweepline on $$$l$$$ because I am updating the divisors and not the number $$$k$$$.
i think a few days ago i saw a contest announcement (maybe that one is fake) saying something like "no penalty for wrong submissions" so i just didn't put much effort into checking before submitting. lesson learned: check contest announcement before the contest to make sure nothing is missed
Does solution for D rely on the fact that diameter will be between (x,x+1)?
You still need to consider is there a case both the x and x+1 is 1e9.
yes, the second fact:
Shortest path goes through at most 2 edges.
D sucks, the observation is easy, but the implementation details are annoying. I spend more than 1.5hour on finding just a small bug...
How to solve F? I figured that we could first calculate the closest leaf nodes for each vertex using bfs, and then the answer for the queries is going to be the maximum of $$$min(f_u + f_v + x, depth_u + depth_v - depth_{lca})$$$, where $$$f_u$$$ is the distance to the closest leaf node from $$$u$$$, over all pairs of $$$u, v$$$. I tried to do some centroid decomposition, but it didn't work
This can be done using small to large merging + segment tree but I don't think that it will work under given constraints.
Yeah I first thought I could go for small-to-large with some data structure (BBST/Segtree), but I quickly realized the constant factor, Q = 10, and N = 1e6 would make it impossible, so I gave up
Binary search the answer and brute force through all the nodes.
Now $$$f_u$$$ is fixed, so the other node should have $$$f_v \geq something $$$ and we want to find the node having the largest distance to $$$u$$$.
Sort the nodes by $$$f$$$ in increasing order, now the valid nodes form a suffix of the array.
The key observation is we only need to consider the two nodes that form the diameter (easy to prove).
So we just maintain these two nodes and use a $$$O(nlogn)-O(1)$$$ LCA to calculate the distance and the complexity is $$$O(nqlogn)$$$.
in D, isn't shortest path between 2 points 2 * minimum or edge between them or not?
It is
yeah, that's what i thought as well. the answer should be
min(shortest edge * 2, longest edge)right? but apparently not according to pretest #2...You can't just greedily get rid of the minimums, you might need to make a longer edge (eg 4 5 7 it's better to get rid of the 5).
LCM contest!
Video Solution for C, will upload D in the morning.
Can anyone explain why this is wrong for D: https://mirror.codeforces.com/contest/1712/submission/168164434 Wrong answer pretest 6.
When I try to understand the problem C and D:
Can anyone give me hint on how to solve C?? Messed up this contest.
if you want to 0 some point you also 0 its last occurrence, then you need to zero all the points up to the last occurrence, then all their last occurrences, then all the points up to their last occurrences, etc. until the last occurrence is the point itself and the right is sorted
Binary Search over the final answer (lo = 0, hi = N)
one of the solution can be binary search, If you read the bold character correctly, every number is >0 , and we can make some of them 0. So let's find out how many from the prefix, we want to set 0. Rest is implementation.
168108660
Can anyone give a testcase for which this code will get wa? Code :https://mirror.codeforces.com/contest/1712/submission/168166282
Take a look at Ticket 16028 from CF Stress for a counter example.
really bad problem B, but D is interesting. How to solve it?
10 minutes too late for D:/
If there some effective data structure to handle D?
I realized that there are only two candidates for the diameter: 2 * minimum value of array, and the largest single edge (which is always the minimum of two adjacent values in the array). But updating the entire array for each change would be too slow.
I resorted to using TWO maps of type
<long long, set <int> >, where map[i] denotes the set of indices whose value/adj-edge is i. I think this should work, in theory, but the implementation was such a pain in the neck that I couldn't get it working even after an hour of starting.Does anyone have any suggestions for a more effective and cleaner way of updating these values?
I went for a binary search using just a copy of the original vector for each iteration.
I used only vectors, but I couldn't submit in time; so not sure if my solution is correct.
I used ordered set to maintain numbers other than the adjacent pair I am currently looking at. Helps in retrieving the Kth element fast.
Greedily replace the first k-1 minimums (I used vectors of (idx,value) so you can sort it by value, change the first few and then sort by idx). Then you have to find a position for the last value to replace. It'll either be another minimum or a value next to the maximum.
in general, we do not even need to store indexes, a sorted array is enough, because in short we are only interested in whether there are such standing next to each other in the original that we want to replace them
Just binary search on the diameter $$$d$$$, and for each adjacent elements $$$a_i$$$ and $$$a_{i + 1}$$$, count the number of elements $$$a_j$$$ left of $$$a_i$$$ with $$$2a_j \lt d$$$ and the number of elements $$$a_k$$$ right of $$$a_{i + 1}$$$ with $$$2a_k \lt d$$$.
Then the total number of modifications needed is the count above + $$$(a_i \lt d)$$$ + $$$(a_{i + 1} \lt d)$$$. If this count $$$\leq K$$$, diameter $$$d$$$ is feasible.
guessforces
what are you guessing? I didnt guess to solve
I guessed B and C
As a participant the questions were very good but I (tragically) choked on D
Same as you. By the way, I am the guy claims to be similar as you in Bilibili, In fact, we both submitted D's answer in the last few minutes coincidently
I stared at my code of D for nearly an hour, which got WA on pretest #2.
Can someone please help me? HERE
After being stupid on B and a long struggle on D, it seems that my rating will drop dramatically. :(
Take a look at Ticket 16024 from CF Stress for a counter example.
Thank you very much
The diameter isn't necessarily twice the minimum value; it can also be the weight of the single heaviest edge in the graph. consider the following test case:
The diameter is 4 here (not 6). By nuking the 4 (replace with 1e9), the new diameter becomes 6. However, your program outputs 8, probably because it only considered twice the minimum and nuked 3 (I didn't actually try understanding your code, FYI)
But isn't the aim is that we should make the diameter bigger, and replacing 3 with 1e9 get a bigger diameter?
Sorry, you're right. The example should've been one where nuking the minimum doesn't change the heaviest edge. Consider this instead:
Your program outputs 8, but I don't see how that's achievable. If you nuke the 3, then the longest edge becomes 5, which is the diameter. If you nuke anything else, then you can always use double of 3, which is 6 (optimal answer). It should be impossible to reach a diameter of 8 from just one operation.
if 3 is replaced by 1e9 then what would be the distance between 1st (value = 1e9) and 3rd(value = 100) node. Won't it be 4 + 4?? (sum of path)
The distance between 1 and 3 would be the direct single edge (1, 3), which has weight 4.
Taking two edges (twice the minimum) isn't always the shortest path between two vertices.
The diameter is always min (2 * minimum edge weight, maximum edge weight).
Oh you are right. I wrongly sorted the array!!! Thank you so much!
Such STRONG sample testcases :)
LCMforces.
In the face of 100000 level data, I often limit myself to the wrong o (n) solution and ignore the possibility of O (nlogn) level solution.
At present, I have no way to get rid of this thinking dilemma.
I'm sorry for my poor English. I hope you will forgive me.
would anybody be able to point out my mistake for D? here's one of my submissions
i ignore the
ksmallest weights, then find the longest single edge which is always going to be the minimum of some adjacent pair (i think?)so the answer should simply be
min(shortest edge * 2, longest edge)no?Because ignoring the k smallest weights doesn't necessarily optimize the longest edge. For example:
Here, the longest edge is 4. If you ignore the 3, the longest edge is still 4, so the diamter hasn't increased. The optimal choice would've been to nuke the 4, thus raising the longest edge to 5.
I chocked =(
nice contest!
Me before the round: I hit guardian on leetcode weekly 295 on 29.5, maybe today is the day, hit expert on round 813 on 8.13 Me after the round: failed miserably
So, what is the idea behind Problem E1? I'm not entirely sure, whether my attempt are correct, but what I found (by looking at big amounts of small testcases, so no proof yet):
Let's call a tuple $$$(i,j,k)$$$ valid, if it has to be counted according to the statement. $$$(i,j,k)$$$ is not valid iff $$$lcm(i,j) | k$$$ or the tuple has the form $$$(3x, 4x, 6x)$$$ or $$$(6x, 10x, 15x)$$$.
Counting the tuples with form $$$(3x, 4x, 6x)$$$ or $$$(6x, 10x, 15x)$$$ is rather straight forward, but I couldn't manage counting those with $$$lcm(i,j) | k$$$ during the contest, and right now my head is spinning and I'm taking a break. I guess we can interate over the $$$k$$$ somehow and then find the amount of corresponding $$$i$$$ and $$$j$$$ by some prime factorizations counting? But that won't be enough for E2 I guess.
You can count all divisors greater or equal $$$l$$$ for all integers in $$$[l, r]$$$ using something like Eratosthenes sieve. Let that numbers be $$$d_i$$$.
Then for each $$$k$$$ the number of pairs $$$(i, j)$$$ satisfying $$$i|k$$$, $$$j|k$$$ and $$$i \lt j$$$ is $$${d_k \choose 2}$$$ and now obviously you can add it all up (also with number of triples of form $$$(3x, 4x, 6x), (6x, 10x, 15x)$$$) to get the number of triples that don't work among all ordered triples with different elements from $$$[l, r]$$$.
Thanks! That worked out well 168245128. Didn't even need Eratosthenes to solve, checking numbers up to their root was enough. Although it is dangerously close to the timelimit with 2.5s out of 3.5s.
How did u get the idea of form(3x,4x,6x) and(6x,10x,15x) ?
Look at my commented Code in 168245128. I did a testingprogram which could output all invalid tuples with $$$l=1$$$ and $$$r=100$$$.
I've been looking hard at those tuples and found out: If $$$lcm(i,j)|k$$$ then the tuple is invalid. But not all invalid tuples satisfy $$$lcm(i,j)|k$$$.
So then I made the program print all invalid tuples which do not satisfy $$$lcm(i,j)|k$$$. Again I looked hard at them and they seemed to be very regular, so I decided to divide them by $$$gcd(i,j,k)$$$ while outputting, and then only tuples $$$(3,4,6)$$$ and $$$(6,10,15)$$$ were left. It was pretty easy to check, that a tuple in that form always will be invalid.
I guess the parts where I wrote "I looked hard at the numbers" won't help you much. Having dabbled in number theory it came to me after some time, but I can guess that this won't be easy for everyone. But I have no easier way to explain it right now.
Also at some point I was also looking at $$$lcm(i,j)|2k$$$, because all invalid tuples did satisfy this. But sadly not every tuple that satisfies $$$lcm(i,j)|2k$$$ is invalid, so that helped understand the structure a bit, but did not lead to the solution.
https://mirror.codeforces.com/contest/1712/submission/168164872 Hello can anybody help me, what is wrong in my solution for C? Maybe some testcase where it is falling?
If we input
1 4 1 3 2 4
the expected output is "1", but your program output is "0".
Is it worth it to solve all problems after contest?
You mean to copypaste other's solutions or upsolve the problems?
if you're doing that at least keep it to yourself.
I didn't want to insult him, I've seen many newbies that copypaste solution of people in hard problems after the contest, I wanted to know if he means that, to tell him to avoid doing such thing.
How to solve D?
I sumbitted E2 in the last 5 seconds successfully but didn't sumbit E1 in time...
bruh moment
E1 score was like 3x more than E2, lol MUST feel really sad..
WOW!! FAST Editorial and FAST rating
maybe its a four pointer and senary search problem don't know about number theory so maybe a typo
What are the odds I'll gain 1 rating point after the cheaters are removed? :(
Limit rating tends to 0, ask Mike to increase 1 xD
Recently after they removed cheaters my rating decreased from 1900 to 1899:)
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
I wasted a Master performance and dropped to newbie performance because of two tiny mistakes in C and D :(
Excuse me if I am naive but how do you judge whether your performance was of Expert level or Master level,Is it just qualitative or is there a quantitative measure to it (rank in contest/No of problems solved). Regards
There is a Chrome extension called carrot which displays the predicted rating change, performance during/after the contest
I am finally a Specialist // SHAHEEN // after two hard-work year .. Don't give up
The score of E2 is too low. :)
Nice contest!
I am doing virtual participation at the moment, solved ABC in 30 min, but based on what people are saying in the comments I won't even try D...
Good contest overall, even though C felt little easier than usual.
D is really not that scary, especially if you're more relaxed to realize there is a very straightforward way to solve it (which I sadly didn't realize during the intensity and stress of the actual contest). I would definitely recommend at least reading and thinking about D, and then attempt to solve it if your considered approach isn't too crazy.
problem D was very interesting and nice.
Giving contest is very important as consistency and patience is necessary for good results.
I am constantly getting this message that jangalvijay's answer is matching with you, I dont know how it is possible. How can our answer match ore than 1 times with same person. Is there a gltch?
It means that constantly it is a cheating:
Okay I saw his answer it is really matching, I might need to change my account pass:(
In this game 168170365 and 168165798 two codes were ruled duplicate，but it was just a coincidence that there was only one dichotomous idea in this problem, but it happened to use the same method.168199920,This code has the same idea as mine, but it's written in a similar way. Could it be cheating? How can you cheat when you can find out that my first submission time is the same as the person who sentenced me? I don't like cheating, and there is no cheating. I think this competition is used to improve myself. Cheating means nothing, but I just hope to get a fair answer.
168156899 This code is similar to mine. Is it cheating? This is just to show you that this is just a coincidence.
As I see in 4 (four!) rounds before you have been caught with cheating. The stock of trust in you, alas, is exhausted.
However, I have been working hard on the problems in CF these days, and I have no intention of cheating again. This is really an accident.I'm really sorry about what I did.I really have corrected it.
I hope you can give me one last chance, this is really an accident. I'm very sorry.
is this round became unrated???
Attention!
Your solution 168165798 for the problem 1712D significantly coincides with solutions ssntt66c/168165798, aruichen/168170365. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I can ensure that I don't disclose the code to others during the competition, and according to my judgment, my code submission time is earlier than that of another person. I think this may be a coincidence in thinking that leads to code similarity. I hope to get a fair judgment.
so unlucky
Attention! Your solution 168156932 for the problem 1712E1 significantly coincides with solutions sjc061031/168156932, Hu-Tao/168171393. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation.
This is so ridiculous. I found that this person got the password of mine and copied my code of C,D,E,F. He even got official rank 4 by cheating.
This person also copied my code of C,F in the previous Educational Round without being found. Interesting.
Is this round unrated? It is my first round to solve E.
Is this round unrated?!
Still waiting for rating change.
where is my rating?
We shouldn't be the victims of others' cheating. This is my second round after I came back to ACM, so sad -=_=-
Where is my +77 rating points :(
Are we going to get back the ratings or not. Please tell.
Where is my +76 rating points?
Where is my +187 rating points? Is this round unrated? Any reason?