By Vladithur, history, 2 months ago,
##### Hi, Codeforces!

Igorfardoc and I are pleased to invite you to our Codeforces Round #813 (Div. 2), which will be held on Aug/13/2022 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.

We would like to thank:

You will be served 6 problems, one of which is divided into two subtasks, and you will have 2 hours and 15 minutes to sample them.

Hope you don't choke 😋

The score distribution is 500 — 1000 — 1500 — 2000 — (2000 — 750) — 3500

PS

UPD: Tutorial

UPD2: Congratulations to the winners!

Div. 2:

Div. 1:

• +622

 » 2 months ago, # |   +77 As a tester, don’t even think of skipping this round…
•  » » 2 months ago, # ^ |   +143 As a competitive programmer I never even think about SKIPPING A ROUND.
•  » » » 2 months ago, # ^ |   +4 So true
•  » » » 2 months ago, # ^ |   -61 cringe
•  » » » 2 months ago, # ^ |   +16 You can do anything, just don't give up!
•  » » » » 2 months ago, # ^ |   0 Hi all! Excellent! It's good that all codeforce competitions are very interesting and good! I love their jobs! Dear friends, I sincerely wish you all success and the greatest problem solving!
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +5 I read this in Naruto's voice lmao. Epic!
•  » » » » 2 months ago, # ^ |   0 dattebayo
•  » » 2 months ago, # ^ |   0 sure won't
•  » » 2 months ago, # ^ |   0 i think skiping a round is not a good practice
•  » » 2 months ago, # ^ |   +21 As a tester, I can confirn this round is great.
•  » » 2 months ago, # ^ |   -10 Codeforce is very good and interesting, isn't it? Who agrees with me? I really like him.
 » 2 months ago, # |   +31 As an author's helper, I think it will be nice PermutationMathCodeforces round.
 » 2 months ago, # |   +10 Codeforces Round 813 (Div.2) rp ++ ！！！Hope to expert！
 » 2 months ago, # |   +115 As a tester I tested this round
•  » » 2 months ago, # ^ |   +56 As a down-voter I down-voted this comment Spoiler
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -26 [Deleted]
•  » » » 2 months ago, # ^ |   -18 As a BlindingKnight-voter I BlindingKnight-voted this comment
 » 2 months ago, # |   +18 I hope I can solve ABC！
•  » » 2 months ago, # ^ | ← Rev. 2 →   +6 Best of luck
•  » » » 2 months ago, # ^ |   +3 Good luck
•  » » 2 months ago, # ^ |   0 wish u luck
 » 2 months ago, # |   +25 Hope I became CM on this round and tasks would be good.
•  » » 2 months ago, # ^ |   +7 Hope I become an Expert and you become CM.Good luck :)
 » 2 months ago, # |   +8 What's the meaning of "You will be served 6 problems, one of which is divided into two subtasks," ✍(◔◡◔)
•  » » 2 months ago, # ^ |   +25 One problem has an easy version and a hard version.
•  » » » 2 months ago, # ^ |   +3 Thank You
 » 2 months ago, # |   +8 Looking forward to it !
 » 2 months ago, # |   +13 looking forward to [ hidden reference] and [bonus versions]
•  » » 2 months ago, # ^ | ← Rev. 2 →   +15 Most of the references are not very hidden, just some quote in the start of the statement...
 » 2 months ago, # |   +205
•  » » 2 months ago, # ^ |   -8 True AF.
 » 2 months ago, # |   +13 Hope to specialist
•  » » 2 months ago, # ^ |   0 Hope to expert
•  » » » 2 months ago, # ^ |   0 Good luck
•  » » 2 months ago, # ^ |   0 Hope to Pupil
 » 2 months ago, # |   0 Thanks for releasing the score distribution very early. I liked it This round looks so balanced. Hope everyone get a positive delta :P
•  » » 2 months ago, # ^ |   +27 This round looks so balanced. My man got the time machine
•  » » » 2 months ago, # ^ |   +16 apparently not
 » 2 months ago, # | ← Rev. 2 →   +11 As a tester, this round is gud-QuangBuiCP
 » 2 months ago, # |   +7 and you will have 2 hours and 15 minutes "to sample them" Do we uniformly pick $k$ unique problems to solve or what? thinking
•  » » 2 months ago, # ^ | ← Rev. 2 →   +4 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.
•  » » » 2 months ago, # ^ |   0 Oh nice, that sounds promising.
 » 2 months ago, # | ← Rev. 5 →   0 Good luck to all participants of this round, as well as IOI participants. Hope to rating>=1300
 » 2 months ago, # |   +1 As a tester of the this round and the recent one, I confirm that both rounds are really great!!!
 » 2 months ago, # |   +51 As a tester give me GF contribution
 » 2 months ago, # |   +8 Problems are great! It was interesting to solve them.
 » 2 months ago, # |   +4 this contest seems suspect, I will participate from alt account
•  » » 2 months ago, # ^ |   +3 Is Marinush your alt?
•  » » » 2 months ago, # ^ |   +1 oh god damnit
•  » » » 2 months ago, # ^ |   0 oh god damnit
 » 2 months ago, # |   +8 Could anyone tell me what does "a hidden reference" mean?
 » 2 months ago, # |   -9 The emoji after "Hope you don't choke" seems susAnyways good luck to everyone who is doing the round!
 » 2 months ago, # |   0 Good luck to everyone!
•  » » 2 months ago, # ^ |   +1 good luck to you too ☺
 » 2 months ago, # |   0 I wish and hope short statements like this post. I like it
 » 2 months ago, # |   0 hope i will become specialist after this round
 » 2 months ago, # |   0 As a beginner, I never even think to Skip... It will be the great one .
•  » » 2 months ago, # ^ |   0 It will be the great one.
 » 2 months ago, # |   0 As a participant, I never skip any Div. 2's, unless it's bad.
 » 2 months ago, # |   0 Codeforces Round 813 (Div.2) rp ++ ！！！Hope to specialist！
 » 2 months ago, # |   0 Can someone explain the "hidden reference" thing??
•  » » 2 months ago, # ^ |   0 I guess it's something hidden in the problem that you can guess to get some score:)
•  » » » 2 months ago, # ^ |   0 Oh nice, good luck dude!
•  » » » 2 months ago, # ^ |   0 I will understand during the contest:)
•  » » 2 months ago, # ^ |   0 it's the module they use to mess with the rankings after the end. how do you think some people add more ranking to themselves? :)
 » 2 months ago, # |   0 So I should guess to get the rest of the scores?
 » 2 months ago, # |   +222
•  » » 2 months ago, # ^ |   +10 damn
•  » » 2 months ago, # ^ |   0 I didn't know palindromes would ever make me think that much.
•  » » 2 months ago, # ^ |   0 Shit!
 » 2 months ago, # |   +3 As a specialist, I hope I can reach expert.
•  » » 2 months ago, # ^ |   0 As a pupil,I hope I can reach specialist
 » 2 months ago, # |   0 Good luck to everyone, don't skip a contest just because you are afraid to lose rating! You got this!
 » 2 months ago, # |   0 I wish you all success so that you can solve many problems
•  » » 2 months ago, # ^ |   0 Good. I also wish you to solve many problems. I will try to do everything in my power. And I wish everyone that.
 » 2 months ago, # |   +3 Hope to get to Master.
 » 2 months ago, # | ← Rev. 2 →   0 I hope i can reach pupil, in sah allah
 » 2 months ago, # |   0 Looks like a fun round, will be participating
 » 2 months ago, # |   +17 Ah great, Round 813 on 8/13 and my birthday.Wish everyone good luck and hope I will be well enough to participate.
 » 2 months ago, # |   +19 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"
•  » » 2 months ago, # ^ |   +8 No, only in the announcement)
•  » » » 2 months ago, # ^ |   +35 Will your next round be on CodeChef
•  » » » » 2 months ago, # ^ |   +13 No.
 » 2 months ago, # |   0 Good luck to all of you. And wish I could become specialist.
 » 2 months ago, # |   -7 as a noob coder i am not going to skip rounds
 » 2 months ago, # |   +5 Hope I become specialist this time!
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 yeesss
•  » » 2 months ago, # ^ |   0 yayyyy
 » 2 months ago, # |   +11 Vladithur is a giga chad, so I'll have to participate.
 » 2 months ago, # |   +12 I am sorry, unable to attend since it is 1:35 am in my timezone. Hope others have fun
 » 2 months ago, # |   0 can anyone please explain to me the hidden reference thing?
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   +15 as a participant, i am going to participate
 » 2 months ago, # |   0 Friends, is E(2000-750) saying it's in that range of difficulty?
•  » » 2 months ago, # ^ |   +25 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).
•  » » » 2 months ago, # ^ |   0 Ouch, thanks!
•  » » 2 months ago, # ^ |   +7 I think E1 is easier than D.
•  » » » 7 weeks ago, # ^ |   0 I don't think so >_<
 » 2 months ago, # |   0 it will be an intersting contest
 » 2 months ago, # |   +8 I have been very lucky in the past few contests, but feel like I would eat a heavy negative delta this round. :_)
 » 2 months ago, # |   +4 Trying to reach Expert ;-)
•  » » 2 months ago, # ^ |   +3 HORAYYY!!
 » 2 months ago, # |   +21 today is 8/13 and this is round 813, wow!
 » 2 months ago, # |   +9 The Date is 8.13 and the Round is 813Wish Everyone non-negative rating changes...
 » 2 months ago, # |   0 All the Best Guys!!!
 » 2 months ago, # |   0 As a nebiw，I just want to solve two questions
 » 2 months ago, # |   0 this contest looks interesting, doesn't it...
 » 2 months ago, # |   0 Good luck to everyone participating!
 » 2 months ago, # | ← Rev. 2 →   -15 .
•  » » 2 months ago, # ^ | ← Rev. 2 →   +17 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.
 » 2 months ago, # |   0 Hope to get to Master.
•  » » 2 months ago, # ^ |   +4 Really happy right now :>.
•  » » » 2 months ago, # ^ |   +8 Nice! Good luck on future Div 1 contests!
 » 2 months ago, # |   0 i think i will become pupil after this round
 » 2 months ago, # |   0 ig i will just solve A and B...hope i solve atleast A
•  » » 2 months ago, # ^ |   0 well i solved ABC but im slow af
•  » » » 2 months ago, # ^ |   0 Exactly the same! We need more practice.
•  » » » » 2 months ago, # ^ |   0 yes broooo, lots of practice.
 » 2 months ago, # | ← Rev. 2 →   +9 This round is so NICE :3
 » 2 months ago, # |   0 first contest lessgo.........
 » 2 months ago, # |   +16 Permutation Forces!
 » 2 months ago, # |   +41
•  » » 2 months ago, # ^ |   +33 Well, I'm going to play OSU! instead of stucking on D. Click the circle !
•  » » » 2 months ago, # ^ |   0 Is osu a dedicated meme for speedforces?Sounds interesting.
•  » » » » 2 months ago, # ^ |   0 idk yet, but I always get some idea when I playing osu,so I did that then came up with the solution of D. :)
 » 2 months ago, # |   +2 I like the style very much
 » 2 months ago, # |   +6 SPEEDFORCES
 » 2 months ago, # |   -9 spermutation forces
 » 2 months ago, # |   +20 difficulty difference between C and D is high
 » 2 months ago, # |   0 I am so ridiculously bad at guessforces, its always wrong wtf
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 2 months ago, # ^ |   0 thats what I did after getting the WA, but that problem is too trivial to even require that
 » 2 months ago, # |   +18 WrongAnswerOnPretest2Forces
 » 2 months ago, # | ← Rev. 2 →   +19 I didn't like this round. When I solve anything gets me wrong answer on pretest 2! ◑﹏◐. But actually I liked the clear statements ❤
•  » » 2 months ago, # ^ |   0 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
•  » » » 2 months ago, # ^ |   +3 Congratulations for being pupil ❤
•  » » » » 2 months ago, # ^ |   0 thanks ❤. happy to see someone from mansourah here btw. good luck in the upcoming rounds.
•  » » » » » 2 months ago, # ^ |   +3 Thank You ❤(✿◕‿◕✿)
 » 2 months ago, # |   0 amazing thanks for good samples for problem c its really a life saver xD
 » 2 months ago, # |   -24 Another unbalanced round !!
 » 2 months ago, # |   +5 D>>>>>>C
•  » » 2 months ago, # ^ |   0 actually D is not much harder than C. It is just that... I got WA 5 times (I got the idea tho).
 » 2 months ago, # |   0 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) > 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
•  » » 2 months ago, # ^ |   +8 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 > 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}}$
•  » » » 2 months ago, # ^ |   0 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$.
 » 2 months ago, # |   0 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
 » 2 months ago, # |   0 Does solution for D rely on the fact that diameter will be between (x,x+1)?
•  » » 2 months ago, # ^ |   0 You still need to consider is there a case both the x and x+1 is 1e9.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 yes, the second fact: Hint 2Shortest path goes through at most 2 edges.
 » 2 months ago, # |   +16 D sucks, the observation is easy, but the implementation details are annoying. I spend more than 1.5hour on finding just a small bug...
 » 2 months ago, # | ← Rev. 2 →   0 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
•  » » 2 months ago, # ^ |   +1 This can be done using small to large merging + segment tree but I don't think that it will work under given constraints.
•  » » » 2 months ago, # ^ |   0 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
•  » » 2 months ago, # ^ | ← Rev. 2 →   +38 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)$.
 » 2 months ago, # |   +1 in D, isn't shortest path between 2 points 2 * minimum or edge between them or not?
•  » » 2 months ago, # ^ |   0 It is
•  » » 2 months ago, # ^ | ← Rev. 3 →   +2 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...
•  » » » 2 months ago, # ^ |   +4 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).
 » 2 months ago, # |   +3 LCM contest!
 » 2 months ago, # | ← Rev. 2 →   0 as a newbie, best round everrrr <3 make more rounds!
 » 2 months ago, # |   0 Video Solution for C, will upload D in the morning.
 » 2 months ago, # | ← Rev. 2 →   0 Can anyone explain why this is wrong for D: https://codeforces.cc/contest/1712/submission/168164434 Wrong answer pretest 6.
•  » » 2 months ago, # ^ |   0 Take a look at Ticket 16030 from CF Stress for a counter example.
 » 2 months ago, # | ← Rev. 3 →   0 When I try to understand the problem C and D:
 » 2 months ago, # |   0 Can anyone give me hint on how to solve C?? Messed up this contest.
•  » » 2 months ago, # ^ |   +1 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
•  » » » 2 months ago, # ^ |   0 Oh this also seems relatively easy to implement!
•  » » 2 months ago, # ^ |   0 Binary Search over the final answer (lo = 0, hi = N)
•  » » » 2 months ago, # ^ |   0 yes I first came up with binary search messed that up didn't even pass pretests
•  » » 2 months ago, # ^ |   +1 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
 » 2 months ago, # |   0 Can anyone give a testcase for which this code will get wa? Code :https://codeforces.cc/contest/1712/submission/168166282
•  » » 2 months ago, # ^ |   +1 Take a look at Ticket 16028 from CF Stress for a counter example.
•  » » » 2 months ago, # ^ |   0 Got it, thanks.
 » 2 months ago, # |   +3 really bad problem B, but D is interesting. How to solve it?
 » 2 months ago, # |   0 10 minutes too late for D:/
 » 2 months ago, # | ← Rev. 2 →   0 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  >, 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?
•  » » 2 months ago, # ^ |   +2 I went for a binary search using just a copy of the original vector for each iteration.
•  » » 2 months ago, # ^ |   0 I used only vectors, but I couldn't submit in time; so not sure if my solution is correct.
•  » » 2 months ago, # ^ |   0 I used ordered set to maintain numbers other than the adjacent pair I am currently looking at. Helps in retrieving the Kth element fast.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 2 months ago, # ^ |   0 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
•  » » 2 months ago, # ^ |   +1 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 < d$ and the number of elements $a_k$ right of $a_{i + 1}$ with $2a_k < d$. Then the total number of modifications needed is the count above + $(a_i < d)$ + $(a_{i + 1} < d)$. If this count $\leq K$, diameter $d$ is feasible.
 » 2 months ago, # |   +2 guessforces
•  » » 2 months ago, # ^ |   0 what are you guessing? I didnt guess to solve
•  » » » 2 months ago, # ^ |   +1 I guessed B and C
 » 2 months ago, # |   +6 As a participant the questions were very good but I (tragically) choked on D
 » 2 months ago, # |   +42
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 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
 » 2 months ago, # |   0 I stared at my code of D for nearly an hour, which got WA on pretest #2.Can someone please help me? HERE
•  » » 2 months ago, # ^ |   0 After being stupid on B and a long struggle on D, it seems that my rating will drop dramatically. :(
•  » » 2 months ago, # ^ |   0 Take a look at Ticket 16024 from CF Stress for a counter example.
•  » » » 2 months ago, # ^ |   0 Thank you very much
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 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: 4 1 3 100 4 5 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)
•  » » » 2 months ago, # ^ |   0 But isn't the aim is that we should make the diameter bigger, and replacing 3 with 1e9 get a bigger diameter?
•  » » » » 2 months ago, # ^ |   +1 Sorry, you're right. The example should've been one where nuking the minimum doesn't change the heaviest edge. Consider this instead: 4 1 3 4 100 5 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.
•  » » » » » 2 months ago, # ^ |   0 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)
•  » » » » » » 2 months ago, # ^ |   0 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).
•  » » » » » 2 months ago, # ^ |   0 Oh you are right. I wrongly sorted the array!!! Thank you so much!
 » 2 months ago, # |   +11 Such STRONG sample testcases :)
 » 2 months ago, # |   0 welp, misreadeded D, solved the \$#!% out of something besides what was being asked...I guess that's the risk with such synthetic problems...? For sanity's sake, if someone could supply a motivating example of an edge weight determined by its minimum over a range...? I guess I just mentally rejected it into being the minimum of the endpoints out of spite (and that passed samples).
 » 2 months ago, # |   +1 LCMforces.
 » 2 months ago, # | ← Rev. 4 →   0 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.
 » 2 months ago, # | ← Rev. 2 →   0 would anybody be able to point out my mistake for D? here's one of my submissionsi ignore the k smallest 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?
•  » » 2 months ago, # ^ |   0 Take a look at Ticket 16025 from CF Stress for a counter example.
•  » » » 2 months ago, # ^ |   0 ty
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 Because ignoring the k smallest weights doesn't necessarily optimize the longest edge. For example: 3 1 3 4 5 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.
 » 2 months ago, # |   0 Guys, why would this solution 168154805 fail for C ?The idea here is that if there is a gap greater than 1 between the same number, i.e. the count of this number is greater than 1 and the difference between its consecutive occurence is greater than 1, then this number must be turned 0. And finally, we reach a point where all such numbers whose count is greater than 1 and also has a gap greater than 1 is turned 0. Take the rightmost 0's position, say it's $p$, so we start from $p + 1$, and each time there occurs a point $i$ such that $p_{i} > p_{i + 1}$, that's the new point, $i$ till which we remove distinct integers.Thanks for helping.
•  » » 2 months ago, # ^ |   0 Take a look at Ticket 16027 from CF Stress for a counter example.
•  » » » 2 months ago, # ^ |   0 Thank you so much, I found out where my implementation went wrong.
 » 2 months ago, # |   0 I chocked =(
 » 2 months ago, # |   0 Can anyone tell me why my code is failing in pretest 2 for question c my submission.
•  » » 2 months ago, # ^ |   0 Take a look at Ticket 16026 from CF Stress for a counter example.
 » 2 months ago, # |   0 nice contest!
 » 2 months ago, # |   0 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
 » 2 months ago, # |   +3 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 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 < 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]$.
•  » » » 2 months ago, # ^ |   0 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.
•  » » 2 months ago, # ^ |   0 How did u get the idea of form(3x,4x,6x) and(6x,10x,15x) ?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
 » 2 months ago, # |   0 https://codeforces.cc/contest/1712/submission/168164872 Hello can anybody help me, what is wrong in my solution for C? Maybe some testcase where it is falling?
•  » » 2 months ago, # ^ |   0 Take a look at Ticket 16029 from CF Stress for a counter example.
•  » » » 2 months ago, # ^ |   0 Yeah I got my mistake.I was not maximizing my prev counter value at the end of for loop.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 If we input1 4 1 3 2 4the expected output is "1", but your program output is "0".
 » 2 months ago, # |   0 Is it worth it to solve all problems after contest?
•  » » 2 months ago, # ^ |   0 You mean to copypaste other's solutions or upsolve the problems?
•  » » » 2 months ago, # ^ |   0 I mean i could try to solve till D and for E(s) i have to look into editorials.
•  » » » 2 months ago, # ^ |   0 if you're doing that at least keep it to yourself.
•  » » » » 2 months ago, # ^ |   0 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.
•  » » » » » 2 months ago, # ^ |   0 interesting.
 » 2 months ago, # |   0 I wasted so much time looking for observation in C. Turns out it can be solved with a brute force method.
•  » » 2 months ago, # ^ |   0 Me too, except I got the observation but screwed the implementation big time and suffered from correct logic but incorrect output XD.
 » 2 months ago, # |   0 How to solve D?
 » 2 months ago, # |   +77 I sumbitted E2 in the last 5 seconds successfully but didn't sumbit E1 in time...
•  » » 2 months ago, # ^ |   0 bruh moment
•  » » 2 months ago, # ^ |   0 E1 score was like 3x more than E2, lol MUST feel really sad..
 » 2 months ago, # |   +3 WOW!! FAST Editorial and FAST rating
 » 2 months ago, # |   +4
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 maybe its a four pointer and senary search problem don't know about number theory so maybe a typo
 » 2 months ago, # |   +4 What are the odds I'll gain 1 rating point after the cheaters are removed? :(
•  » » 2 months ago, # ^ |   +1 Limit rating tends to 0, ask Mike to increase 1 xD
•  » » 2 months ago, # ^ |   0 Recently after they removed cheaters my rating decreased from 1900 to 1899:)
 » 2 months ago, # |   +7 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
 » 2 months ago, # | ← Rev. 2 →   -27 I bear witness that none is worthy of worship but Allah, the One alone, without partner, and I bear witness that Muhammad(may Allah bless and greet him) is His Servant and Messenger.
 » 2 months ago, # |   -31 rating changes occurred fairly quickly, satisfactorily)
 » 2 months ago, # | ← Rev. 2 →   -31 lā ʾilāha ʾillā llāhu muḥammadun rasūlu llāhi.
 » 2 months ago, # |   0 I wasted a Master performance and dropped to newbie performance because of two tiny mistakes in C and D :(
•  » » 2 months ago, # ^ |   0 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
•  » » » 2 months ago, # ^ |   0 There is a Chrome extension called carrot which displays the predicted rating change, performance during/after the contest
 » 2 months ago, # |   0 I am finally a Specialist // SHAHEEN // after two hard-work year .. Don't give up
•  » » 7 weeks ago, # ^ |   0 no more :")
 » 2 months ago, # |   -8 The score of E2 is too low. :)
 » 2 months ago, # |   +9 Nice contest!
 » 2 months ago, # |   0 great blog.
 » 2 months ago, # |   0 The problem C,i want to ask a question. If change the question "change x to 0" to "choose a x and delete it" how can solve it? for exmple: i have 4 3 3 3 4 3 4 and choose 3 then i have 4 4 4 not 4 0 0 0 4 0 4 so how to solve this problem?
 » 2 months ago, # | ← Rev. 2 →   0 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.
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   +3 problem D was very interesting and nice.
 » 2 months ago, # |   0 Giving contest is very important as consistency and patience is necessary for good results.
 » 2 months ago, # |   0 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?
•  » » 2 months ago, # ^ |   +6 It means that constantly it is a cheating: 168143783 and 168146353 168170419 and 168174818
•  » » 2 months ago, # ^ |   0 Okay I saw his answer it is really matching, I might need to change my account pass:(
 » 2 months ago, # |   -16 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.
•  » » 2 months ago, # ^ |   -19 168156899 This code is similar to mine. Is it cheating? This is just to show you that this is just a coincidence.
•  » » 2 months ago, # ^ |   +2 As I see in 4 (four!) rounds before you have been caught with cheating. The stock of trust in you, alas, is exhausted.
•  » » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 I hope you can give me one last chance, this is really an accident. I'm very sorry.
•  » » » 7 weeks ago, # ^ |   0 is this round became unrated???
 » 2 months ago, # | ← Rev. 2 →   0 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 https://codeforces.cc/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.
•  » » 7 weeks ago, # ^ |   0 so unlucky
 » 2 months ago, # |   0 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.
•  » » 2 months ago, # ^ |   0 This person also copied my code of C,F in the previous Educational Round without being found. Interesting.
 » 2 months ago, # |   0 I enjoyed solving Problems B and C :)
 » 2 months ago, # |   +15 Is this round unrated? It is my first round to solve E.
 » 7 weeks ago, # |   +16 Is this round unrated?!
•  » » 7 weeks ago, # ^ |   0 damn that's +122 gone for me
 » 7 weeks ago, # |   +28 Still waiting for rating change.
 » 7 weeks ago, # |   +16 where is my rating?
 » 7 weeks ago, # |   +9 We shouldn't be the victims of others' cheating. This is my second round after I came back to ACM, so sad -=_=-
 » 7 weeks ago, # |   +13 Where is my +77 rating points :(Are we going to get back the ratings or not. Please tell.
 » 7 weeks ago, # |   +9 Where is my +76 rating points?
 » 7 weeks ago, # |   +9 Where is my +187 rating points? Is this round unrated? Any reason?
 » 7 weeks ago, # |   0 So I got flagged on a pattern based question on code forces round 813 about finding the maximum lcm of n permutations . Can anyone help me solve this issue ?? I am linking my code link below . question b https://codeforces.cc/contest/1712/submission/168138244 question a https://codeforces.cc/contest/1712/submission/168128883 i dont even copy anyones snippet . please help .