By deltixlab, 14 months ago, translation,

Hi, Codeforces!

We are DELTIX. Founded in 2005, DELTIX is one of the market leaders in software development for financial research and products for systematic and algorithmic trading. In 2020 DELTIX joined the EPAM family. Our mission is to turn promising ideas into breakthrough products fast.

We are experts in:

• aggregation, storage, and processing large volumes of time-series data
• data modeling
• testing and deployment of quantitative models

In our team we value such skills as:

• knowledge of algorithms
• high-performance coding
• low latency data streams processing

We are excited to announce that we have released TimeBase Web Admin Community Edition.

Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces. Today, we are excited to welcome you to the third installment of our rounds (joined Div1 и Div2) Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2), that will start on Nov/28/2021 17:35 (Moscow time). It is an open and rated round for both divisions.

We have prepared the following trophies for you:

1st place: Samsung Galaxy Z Flip3
2nd place: Samsung Galaxy Tab S7+
3rd place: Samsung Galaxy Watch4
1-100 places: branded t-shirts

Another 100 t-shirts will be distributed randomly between participants outside the top-100 but within the top-1000 and who participated in rated Codeforces rounds before.

Problems, except the last one, have been prepared by members of our team: Vladik, 4llower and AleXman111.

We would like to say a word of appreciation to:

We will offer participants 8 problems and 150 minutes to solve them. We wish everybody good luck and high ratings!

Fill out a short contact form if you are interested in employment opportunities or would like to speak with recruiters or members of our team.

Contact Form →

UPD: The scoring distribution is 500 — 1000 — 15002000 — 2750 — 3000 — 3250 — 3750.

Thank you all for participating! (editorial)

Congratulations to the winners:
1. tourist
2. DmitryGrigorev
3. xtqqwq
4. Maksim1744
5. greenheadstrange
6. maroonrk
7. jiangly
8. fantasy
9. QAQAutoMaton
10. emptyhope

We were especially delighted with the result tourist, who was able to solve all 8 problems, congratulations!

• +221

| Write comment?
 » 14 months ago, # |   +72 Yet Another Waving Arm
•  » » 14 months ago, # ^ |   +25 Are you having problems with the Waving Arm? :)
•  » » » 14 months ago, # ^ |   +41 Opening CodeForces, a creature suddenly smile and wave to you, what a surprise:)
•  » » 14 months ago, # ^ |   0 it's funny 0v0
 » 14 months ago, # |   +11 all of the Deltix rounds were good so far. hope for another great around
 » 14 months ago, # |   +21 Throughout the year, once per quarter, ....Is this last round or should we expect more rounds next year?
•  » » 14 months ago, # ^ |   +17 This is the penultimate round of the planned ones. But of course, I am sure that we will plan some other competitions further, possibly in a different format.
 » 14 months ago, # |   +13 Looking Forward to this <*_->..
 » 14 months ago, # | ← Rev. 2 →   +20 Looking forward to this contest! Hope every one can gain rating.I think Deltix rounds always have high quality and wonderful problems.
 » 14 months ago, # |   -17 Hope This Time i can solve 4 Tasks...
 » 14 months ago, # | ← Rev. 2 →   -36 .
•  » » 14 months ago, # ^ | ← Rev. 4 →   +103 .
 » 14 months ago, # |   0 Deltix rounds always have interesting problems and wonderful pictures). Good luck for everyone!
 » 14 months ago, # | ← Rev. 2 →   +26 Is it a habit to wave the hand when opening codeforces?It still looks pleasantly surprised, even scary :)
 » 14 months ago, # |   +15 Should I participate in this round or enjoy being Candidate master a few more days :)
•  » » 14 months ago, # ^ |   +74 Enjoy being Candidate master for a few days this round.
•  » » 14 months ago, # ^ |   +14 Three contests ago I was in the same situation as you are, but I participated in the round and got back into expert. However, I am so happy I did participate since the problems were worth the down rate. So, I would say yes, having a high rating is good, but seeing beautiful problems is much better :)
 » 14 months ago, # |   -45 Is It Hard?
 » 14 months ago, # |   0 Scoring Distribution ?
 » 14 months ago, # | ← Rev. 3 →   +69 This was my first time testing a CF round. Hope you enjoy the round!(Also please give me contribution uwu.)
 » 14 months ago, # |   +87 as a tester, good luck in this amazing contest
•  » » 14 months ago, # ^ |   -11 As a tester friend I want some up votes please
 » 14 months ago, # | ← Rev. 2 →   +3 very good part of deltix contests is that their problems contain interesting ideasUPD : Also images in each problem
 » 14 months ago, # |   0 How to do extra registration?
 » 14 months ago, # |   +74 Successfully wasted my 45 mins in understanding problem D statement :)
•  » » 14 months ago, # ^ |   +4 Me too. I feel, it was really a weird way of asking what was asked + I am stupid for net reading the announcement
 » 14 months ago, # |   +7 Just noticed that there are so few participants this time, why is that?
•  » » 14 months ago, # ^ |   +5 many colleges have been re opened may be that's why they are busy doing shitty assignments
•  » » 14 months ago, # ^ |   -21 Shitty problem statements make people quit.
•  » » » 14 months ago, # ^ |   +29 I don't think they were that bad.Also I don't see any issues with A (often difficult A would be the issue keeping people away)Btw, why did you refrain from submitting solutions until the very end?
•  » » » » 14 months ago, # ^ |   +3 After having read C I decided to not participate...Then later it went not so bad, so I submitted anyway. C was unecessary complecated statement, D inaczeptable complecated.
•  » » » » » 14 months ago, # ^ |   +17 I think you should train your reading skills
•  » » 14 months ago, # ^ |   0 One of the reasons was most likely AtCoder Regular Contest 130 on the same day with only a small 35 minutes gap between contests. I know that some people happily participate in multiple contests, but I don't have enough endurance for that. My choice was Codeforces this time, primarily because I'm trying not to skip rare Codeforces Div.1+2 and Global rounds. The other people may have different priorities.I also think that problem A was more difficult than usual, even though this is very subjective. It took me 10 minutes to solve this problem. And I'm not alone, because I see that a bunch of cyan/blue people from my friend list also struggled a bit.
 » 14 months ago, # |   +1 I will NEVER participate in any contest hold by DELIX.
•  » » 14 months ago, # ^ |   +36 why
•  » » 14 months ago, # ^ |   +2 Chill guys, he said DELIX. Not DELTIX :p
 » 14 months ago, # |   -11 tourist surpasses 3900 :)
•  » » 14 months ago, # ^ |   +13 No he didnt.. but hopefully soon!
 » 14 months ago, # |   0 Quite a nice contest in my opinionThough difficulty gap between D and E could be better. The way it is D seems 1700 and E is 2300
 » 14 months ago, # | ← Rev. 2 →   +9 i respect rainboy from bottom of my heart... this guy deserves a special mention ...rainboy can inspire anyone ...whenever i feel low i look up to him ...
 » 14 months ago, # |   +15 E is an easier version of 750E.How do you solve F?
 » 14 months ago, # |   +4 Would that be possible to solve D for n ~ 10^6?I realized n was small very late into the contest and was thinking about variant in which n can be bigger :/
•  » » 14 months ago, # ^ |   -7 Yes, possible. We decided to remove the algorithmic part of the solution from the problem.
•  » » » 14 months ago, # ^ |   +8 Why did you decide this?
•  » » » » 14 months ago, # ^ |   +16 because there were already a lot of problems in the competition that tested algorithmic skills
•  » » » 14 months ago, # ^ |   +15 I feel that the solution for larger N would not have been very algorithm-heavy, and would have been more suitable as a problem D than the current one. Right now, the difficulty gap between C and D is too little and that between D and E is simply too large.Larger constraints on D could have avoided a speedforces round. Thanks for the contest, looking forward to the next one :)
•  » » 14 months ago, # ^ |   +22 Yes, it's possible
•  » » 14 months ago, # ^ | ← Rev. 2 →   +17 I think it would be possible to solve with the same idea but more implementation details. Like keeping track of top-k dsu groups and their sum
•  » » 14 months ago, # ^ |   +4 And I'm realizing after reading your comment :(
•  » » 14 months ago, # ^ |   0 My solution with O(n^2 logn) passed
 » 14 months ago, # |   +9 Can anyone show me how to solve problem E please :>.
 » 14 months ago, # | ← Rev. 3 →   +25 Are the three observations to E literally meant to be: Solution is of the form $(b|c)^*(a|c)^*(a|b)^*$ For a single string this can be counted in $O(n)$ with a $3 \cdot n$ linear dp of (position, current segment). This can be generalized to performing updates / queries by using a segtree with a $3 \cdot 3$ node (starting segment, ending segment), where a given state $[l, r]$ is the min over all possible combinations of $[l, mid]$, $[mid, r]$ from its children. If so I don't see how part 3 adds any value to the problem except making it harder by just adding data structures. Its also really easy to guess since a lot of linear dp solutions can be made to support updates (and arbitrary range queries) using this type of "prefix suffix" segtree similar to how it is done for maximum subarray sum.I suspect if the queries part was removed and it was put at C it would have a similar solve count to a normal Div2C. People (including me) probably just brick on it because its an E and we except the solution to be some tricky adhoc observations and not just get linear dp and apply segtree. I spent almost 1 hour trying to observe properties about the relation between the boundaries of the middle segment before getting frustrated, thinking about data structures, realizing I could probably solve this problem using "prefix suffix" segtree if I could create a linear dp that solves it. After that it took me about 15 mins to get the linear dp, formulate the segtree state, code and debug it.
•  » » 14 months ago, # ^ |   +9 How can you count things of form $(b | c)^* (a | c)^* ( a | b)^*$ using a $3 \cdot n$ linear DP?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +7 Short explanation — Suppose I asked you to count the minimum removals to get a string $a^*b^*c^*$. If you can solve that problem do the same and just invert the costs.Longer explanation — Clearly for any array, we will have some part $[1, i]$ of the form $(b|c)^*$, $[i + 1, j]$ of the form $(a|c)^*$ and $[j + 1, n]$ of the form $(a|b)^*$ (of course one or more might actually be empty in practice such as for $bbbaaa$ which doesn't need a third segment).If we know which segment an element belongs to, we know whether it needs to be deleted (1 cost) or not (0 cost).So we just need to determine the point at which we go from segment $j$ to segment $j + 1$.So we just calculate $dp_{i, j} =$ the minimum number of deletions if the first $i$ elements are in the first $j$ segments.$dp_{i, j + k}$ updates $dp_{i + 1, j + k}$ with cost 1 if $s_i = j + k$ or 0 otherwise.My submission (137260285) actually has this dp still left in the code though note that technically does only $j$ and $j + 1$ instead of $j + k$ which is still likely correct but general $j + k \leq 3$ is safer.
•  » » 14 months ago, # ^ |   0 This is new for me. What is the general approach to convert a linear dp to a segtree for performing updates?
•  » » 14 months ago, # ^ |   +43 My original solution required $9 \times 9$ node matrix, though... But I agree that E is boring. (FG is boring too)
•  » » 14 months ago, # ^ |   +30 I disagree that E was boring (maybe because I didnt came up with any DP idea). My solution was that we want to count minimum of #a + #b + #c when we break our string in three intervals which is equivalent to (#a — #b) + 0 + (#c — #b) + total b's. Then we can use segment tree to get the solution.
 » 14 months ago, # |   +9 any ideas on what is pretest 11 in problem E
•  » » 14 months ago, # ^ |   +33 Try$aaabcccbbbc$The answer is $2$.
 » 14 months ago, # |   +47 Is the complexity of standard for problem F O(n log n) ?
•  » » 14 months ago, # ^ |   +10 i couldn't get the pretest with the nlogMAX solution which is very frustrating, I don't see the the point of making the time limit so tight.
•  » » » 14 months ago, # ^ |   +38 me too, my complexity is O(n(log n+log MAX)) and I get TLE. I don't know why.
•  » » » » 14 months ago, # ^ | ← Rev. 3 →   0 I didnt have time to debug it in contest, but my complexity is same, it passes in ~ 1 sec. https://codeforces.com/contest/1609/submission/137271044
 » 14 months ago, # |   +11 Can someone explain D's question ? How come after 4 edges in the second example answer is 4 ? Any person can be introduced to atmost 3 other persons right (among 1, 2, 3, 4). Plus How come after 5 edges in the second example, the answer is 5 ? (1, 2, 3, 4 have edges 6-7 have no connection to any of 1, 2, 3, 4).
•  » » 14 months ago, # ^ |   0 " Any person can be introduced to atmost 3 other persons right (among 1, 2, 3, 4)"All of them are already connected, so you can use the edge to add anyone else to this group, for example [1,2,3,4,5]
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +16 They could have given an explanation for that... What the heck.... They could have explained it better and increase the constraints. That would be better.
•  » » » » 14 months ago, # ^ |   +1 Problem statement was not what we are required to do i.e bad statement!
•  » » 14 months ago, # ^ |   0 For the first time i didnt understand the problem but the solution. Whenever you are adding an edge,if the edge makes an cycle than you can add whatever edge you want
 » 14 months ago, # |   +14 nice codes nitin_05
•  » » 14 months ago, # ^ |   +5 It's because of these bastards CP is ruined
•  » » » 14 months ago, # ^ |   +11 I don't get it. He comments out a lot, but why is CP ruined by that?
•  » » » » 14 months ago, # ^ |   +11 he added meaningless comments to avoid beeing caught cheating.
•  » » » » » 14 months ago, # ^ |   +6 You mean, like he already had the solutions upfront?
•  » » » » » » 14 months ago, # ^ |   +6 yeshe got caught in the previous roundbut most of the time he gets away.
•  » » 14 months ago, # ^ |   +5 I noticed someone in my room, qwerpoiu, replaced all of their tabs with a comment: 137223420 137229810 137240560 137253430
•  » » 14 months ago, # ^ |   +7 Now, he become an expert cheater. Nice...XD
 » 14 months ago, # |   +1 C was nice
 » 14 months ago, # |   0 Problem A how is the case 15 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 working?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +1 16 8 8 8 8 8 8 8 8 8 8 8 8 8 416 16 8 8 8 8 8 8 8 8 8 8 8 8 216 16 16 8 8 8 8 8 8 8 8 8 8 8 116 16 16 16 8 8 8 8 8 8 8 8 8 4 116 16 16 16 16 8 8 8 8 8 8 8 8 2 116 16 16 16 16 16 8 8 8 8 8 8 8 1 1....35184372088832 1 1 1 1 1 1 1 1 1 1 1 1 1 1=> sum of all = 35184372088846
 » 14 months ago, # | ← Rev. 2 →   +75 Is it just me, or someone else too faced difficulty in understanding the statement of problem D. Wasted nearly three-quarter hour understanding the problem statement, though after understanding it I felt it was quite direct :)
•  » » 14 months ago, # ^ |   0 Same xD
•  » » 14 months ago, # ^ |   0 Why the hell they didn't explain the "important" part in samples?. I have to read their simply complicated problem statement at least 15 times ...
 » 14 months ago, # |   +25 thanks for boring, standart, absolutely non-interesting, hard-to-write problem E...
•  » » 14 months ago, # ^ |   0 can't agree, it's not hard to write at all 137263169
 » 14 months ago, # |   +177 Will it kill you to just write for problem F:Let $popcount(x)$ be the number of bits equal to $1$ in the binary notation of $x$.An segment $l \leq r$ is good if $popcount(\min(A[l..r]))=popcount(\max(A[l..r]))$instead of whatever your statement is.
•  » » 14 months ago, # ^ |   0 So true, I had to write a brute force to understand what the problem was asking.
•  » » 14 months ago, # ^ |   0 Exactly, I spent 10-15 mins wondering wtf "The minimum and maximum numbers are found on the segment of the array starting at l and ending at r" means before finally realized they meant:"Find the minimum and maximum numbers of the segment of the array starting at l and ending at r"and not"Proceed if you can find some occurrences of the minimum and maximum numbers of the $\textbf{entire array}$ in the segment of the array starting at l and ending at r".
 » 14 months ago, # |   +6 I really want a screencast of a contest from tourist
 » 14 months ago, # |   +109 Conspiracy theory: F was made solely to make people waste a ton of time implementing it and then performing constant factor optimizations on it so that people wouldn't have enough time to realize how easy G is. Luckily I decided to go straight to G after getting TLE on F(a bit more than 3 seconds runtime in custom invocation) so I wasn't affected by that as much as I could've been.
•  » » 14 months ago, # ^ |   +10 yeah F time limit was strict for nlogn segment tree solution.
 » 14 months ago, # |   +31 Was D written in Bitcoin language?
 » 14 months ago, # |   +2 You could make problem C better if sequence of 1 's would be good sequencethe approach is same but that makes implementation easier
•  » » 14 months ago, # ^ |   0 Isn't it simple already?
•  » » 14 months ago, # ^ |   0 I think they did that cuz prime numbers seem more natural than "prime numbers or 1". I agree the implementation was the bottleneck.
 » 14 months ago, # |   0 Great round. Especially loved the response of this round team, got a quick reply on every query I asked.
 » 14 months ago, # |   +39 "William satisfied all conditions from 1 and up to and including i and performed exactly i introductions."What and the and fuck! xD
•  » » 14 months ago, # ^ |   +7 Its grammatically correct but confusing lol."William satisfied all conditions from 1 to i and performed exactly i introductions." is more appropriate
•  » » » 14 months ago, # ^ |   0 "is more appropriate"Not sure. It is more concise yet it makes it unclear whether i is included or not. Though it is possible to deduce it from the context
 » 14 months ago, # |   +1 what was the pretest 9 in problem D about?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 For me, I simply forgot to clear the DSU size array after merges. sizeArr[a] += sizeArr[b]; sizeArr[b] = 0; // Added this line Passed test 9 after that.
•  » » » 14 months ago, # ^ |   0 but in my code that doesn't affect the answer. Code
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 I have the same problem. Can you please reply when you'll understand the mistake? code: 137269460 UPD: use multiset when storing sizes of components
 » 14 months ago, # |   +40 Then I opened the worst laptop in the universe I swear it took me 30 min just to turn it on and open Codeblocks then after submitting B it also crashed XD XD XD so i opened the first laptop luckily it worked I think this is a message from god that i should buy a new laptop instead of these 2 shitty laptops
•  » » 14 months ago, # ^ |   +7 Use Linux
•  » » » 14 months ago, # ^ |   +4 it's not OS problem in the first laptop hardware probably the second one is my brother old laptop Idk why it's so slow that's not normal man I burned 10000 calories waiting that 30 min And almost broke my hand hitting the closet
•  » » » » 14 months ago, # ^ |   +4 Use Linux
•  » » » » 14 months ago, # ^ |   -15 Use a lightweight Linux distro.
 » 14 months ago, # | ← Rev. 2 →   +17 Gonna have nightmares about A for a long time (completely my fault, made a mess of it), whereas D was too trivial for its place (C seemed harder to code).Round duration should’ve been higher in my opinion, considering how tiring it is to code E & F, unless there are better implementations than the ones I could come up with. I did like all the problems (besides C maybe), just having more time would've been nice.
•  » » 14 months ago, # ^ |   +19 Maybe you had too much of serotonin
•  » » 14 months ago, # ^ |   +1 Actually I dont feel that way. Although i literally did not understand the question during contest, but for understanding the question itself we must be given points. Was so confused about the 2nd example reg, how the answer is 4 after adding 1st 4 edges when the max number of persons one can be introduced to is n-1, here n = 4 -> (1, 2, 3, 4), until one guy above cleared that we can add any edge we want...
•  » » » 14 months ago, # ^ |   0 "William can introduce any two people"sorry, but this is a direct quote from the problem statement.
•  » » » » 14 months ago, # ^ |   0 Ah!! Ok!! My bad... I think i got confused btw william introducig ppl & ppl having connections. i.e. xi, yi. Thanks.
 » 14 months ago, # |   +114 Here is some feedback on the problems:A: Very nice easy problem, I like it.B: Very nice easy problem, I like it.C: Awful problem. Prime numbers do not play any role, the parameter $e$ does not play any role. This is fundamentally "In an array of 0, 1, 2; count subarrays without $0$ and with exactly one $2$". The statement is involved and the solution is standard.D: Nice problem. Sadly, I did not check the constraints and I thought one had to come up with a pseudo-linear solution which made me waste some time.E: Cute problem, I like it. It is one of the rare applications of segment-trees which is non-obvious from the request. I knew 750E but did not remember it and just solved the problem again.F: Solving this in $O(n\log(n)\log(a))$ with divide and conquer is easy, I have no idea of how to remove one $\log$ factor. In any case, the statement is rather dull (and, if I have to guess, the solution does not use at all that the considered quantity is the number of bits).G: Nice problem, I found the solution during the contest but was not in time to implement it. I believe the problem could have been better if there were no queries and $n$ was up to $10^5$. In this way the implementation simplifies immensely but the main ideas are still necessary to solve the problem.Thank you to the authors.
•  » » 14 months ago, # ^ |   +19 F was tight if you solve in O(n*logn) (or I have to rethink my segment tree code)
•  » » » 14 months ago, # ^ |   +3 You don't need a segment tree if you use vectors (stacks) with partials sums and binary search.
•  » » » » 14 months ago, # ^ |   0 I have no idea how that solution works.
•  » » » » » 14 months ago, # ^ |   +10 We iterate over the right boundary r of the segment. We can maintain the intervals for l where bitcount t remains the same (for both min and max). The answer will be the intersection size of those intervals. If we maintain prefix sums (as intervals will be sorted) we can update the size of intersection in logn using binary search.
•  » » » » » » 14 months ago, # ^ |   +10 Exactly. In the contest, I calculated those intersections using a segment tree and in the last 10 minutes got this approach and completed the code now to get AC T-T. I still don't get the logic to cut segment tree solutions.
•  » » » 14 months ago, # ^ |   +3 You have a $\mathcal{O}(n \log n)$ solution? How does it work?
•  » » » » 14 months ago, # ^ |   +3 Basically we create events of (l, r, i, v, b) meaning that min/max info (the events are mixed) of some info with popcount=b at range [l, r) is created (v=1) or removed (v=-1) at point i of the stack algorithm for min/max. This description might not be good but it's easy to create these events if you know how to use a stack. I think my code is reasonably easy to read. There are at most 4*N such events.Then, for each bit pass through events ordered by i. Subarrays with sum 2 should be counted (because there's +1 from min and max). That didn't pass because of TL so I did a segment tree that adds v at l and subtracts v at r (basically prefix sum update) so it wouldn't need lazy update.
•  » » 14 months ago, # ^ |   +44 Well, the main idea for G is well-known, so I think the author couldn't do that... I think F is easy to bash with brainless segment trees, but the choice of data structures and some implementation styles seems to determine AC and TL here.The thing that I disliked the most in the contest was the awful statement of D. It seems to be better now, but the original statement was just horrible. I think most people spent more time parsing the statement rather than solving it.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   -40 What "original statement" are you talking about? The condition of this problem did not change after the start of the competition.Problem G was independently invented. We are too old to participate in usaco. I'm sorry this happened.
•  » » » » 14 months ago, # ^ |   +23 For problem D, these words are used interchangeably without any clarification from the statement: introduce know each other acquaintances Btw I remember seeing that the statement was updated for D. Sorry if I remembered something wrong.For G, I think the setter not knowing G is understandable, but the coordinator should reject the problem. A-G was just speedforces hell.
 » 14 months ago, # |   +11 subtle storytelling on B and E ;)
 » 14 months ago, # |   +29 Congratulations tourist for achieving a new max rating!
 » 14 months ago, # |   +30 So apparently I was a massive clown and did some massive clownery problem E. my solutionSame as everyone we store a segment tree. But Instead of making any observations, we will store for each range a bitmask that contains $5$ T/F variables: is there *a* is there *b* is there *c* is there *a*b* is there *b*c* Where * is some string.Anyways merging seems like it will take $32 \cdot 32$ operations. But actually if we do pruning on impossible states and states that will cause us to make *a*b*c* then we only need around $100$ operations to merge. Works pretty fast lol 137243960
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 LOL, I had the same solution xD
•  » » 14 months ago, # ^ |   0 Initially, this is what we wanted, but recalling the past rounds, I decided that this would cause a lot of discontent and removed it from the main solve.
 » 14 months ago, # |   +25 Why does it always take so long to post an editorial?They should be written before the contest and automatically published after the end of contest
•  » » 14 months ago, # ^ |   +3 sorry, this is my fault. After the competition, I usually open comments and I can't resist it. Then I need some time to think about everything and come to my senses to start publishing.
•  » » » 14 months ago, # ^ |   +17 Actually I think it should not depend on authors, it should be automatic. Seems like such an obvious improvement
 » 14 months ago, # |   +2 could someone please simplify the problem statement of D.I really did not understand, what they were trying to convey.sample test case 2 in itself confused me.
•  » » 14 months ago, # ^ |   0 Simplified meaning : If you are currently at point $i$ you can add $i$ (1-based indexing) edges in your graph but all the connections up to $i$ (inclusive) must be present in your graph. Then you need to count the person having maximum friends.So simply all the connections up to $i$ must hold i.e $x_i$ and $y_i$ must be in same component for all $i$ ∈ $[1,i]$ if this exist and you still have some edges left try to connect the big components so that overall you get a big component with $i$ edges and the answer is the (number of vertices in this big component — 1).I understood this by 2nd sample test, otherwise it was very hard to understand from the problem statement
•  » » » 14 months ago, # ^ |   0 I understood it now. thanks
 » 14 months ago, # |   0 Can someone please explain D in English?Assuming that William satisfied all conditions from 1 and up to and including i and performed exactly i introductions.ok so far we performed i introductionsThe answer for each i must be calculated independently, It means that when you compute an answer for i, you should assume that no two people have been introduced to each other yet.ok so far we shouldn't perform i introductions ? :D
•  » » 14 months ago, # ^ |   +3 You should perform i introductions, but on i-th step you can use completely different introductions than on step (i — 1)
•  » » » 14 months ago, # ^ |   0 completely different introductions that mean I can just put any random introductions? can you please explain example 2: 10 8 1 2 2 3 3 4 1 4 6 7 8 9 8 10 1 4 what happen when we connect 6-7 and why the answer is 5
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   -8 Nothing happens, That's the point, on 5-th step you reapply all constraints from scratchFor example you can use five edges1-22-33-44-64-7 This way 1 is connected to [2,3,4,6,7], that's why the answer is 5
•  » » » » 14 months ago, # ^ |   +1 because i = 5, so you have 5 introductions, it can have all nodes {2, 3, 4, 6, 7} directly connected with 1
 » 14 months ago, # |   +3 I find the pictures of the problems equally satisfying as the problems :D
 » 14 months ago, # | ← Rev. 4 →   -27 .
 » 14 months ago, # |   +12 For 1609D - Социальная сеть I didn't realize n <= 1000, so I implemented it in O(nlogn): 137250023 . Idea was to keep sum of x+1 maximum size components, where x = number of edges that are useless, we can do that using case work and multiset.idk if its just me, but sometimes I think (10^3)^2 = 10^9...
•  » » 14 months ago, # ^ |   +8 It's funny because I sometimes make the mistake of $(10^9)^{0.5} = (10^3)$ . The inverse of your mistake if you will .
•  » » 14 months ago, # ^ | ← Rev. 4 →   +3 Doubt ClearedHello there, So I was trying to understand how you maintained sum of some top components and found a bug in your code SpoilerIn the add function, the else section (when added value (x) is less than iterator value (*it) and you have some excessive edges to connect more component)In that case according to me you should have decremented the iterator and added that value in answer instead of adding the value (x) as it may be possible that your iterator is pointing at some jth occurrence of iterator value. (in case there are multiple values and iterator is pointing on some greater than 1st occurrence)My submission with changesMaybe that case is hard to be thought of and to add it or maybe it is never possible to have such a situation I don't know.So can you verify that is my thought correct or is it wrong.Thanks!!
•  » » » 14 months ago, # ^ |   0 Yeah, actually, that value is always x, because we checked if did==can, this means we can add more values to sum because its still not full (did < can), but we don't have them, so when we add x to multiset we can always add it to the sum and move iterator, when you move iterator with -- it will actually point to x in multiset so in this case *(--it) == x, then its okay to do it either wayAlso note that, in multiset, 3 3 3 3 (3), new occurrence of same value will always point to the end, and find(x) will always point to first occurrence of x (3) 3 3 3 3
 » 14 months ago, # |   +29 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
•  » » 14 months ago, # ^ |   +11 I passed problem F with the same code after contest but I got FST.Can I apply for rejudge?https://codeforces.com/contest/1609/submission/137269939https://codeforces.com/contest/1609/submission/137266323
•  » » » 14 months ago, # ^ |   0 Thanks for report, we will rejudge before counting the final ratings.
•  » » » » 14 months ago, # ^ |   +152 First of all, I have nothing against contestants who are affected by the inconsistent running time during the system testing. I have always thought it is our own responsibility to make sure the running time of our code is not too close to the time limit. Anything less than 50ms is generally risky and highly subjective to the fluctuation. With how the situation is currently being handled, I'd like to ask: What is exactly the accepted criteria for an appeal to rejudge? How does the rejudge process occur: is it one accepted run or multiple accepted runs?
 » 14 months ago, # |   -33 hello. I sent this code during the tunnel: https://codeforces.com/contest/1609/submission/137240845. this code did not pass system testing and the time limit was exceeded on the 9th test. I sent exactly the same code after system testing and it passed all tests: https://codeforces.com/contest/1609/submission/137271529. this algorithm is absolutely correct and I ask you to reconsider my place in the rating and recalculate the rating score.
•  » » 14 months ago, # ^ |   +16 There are fluctuations, deal with it. Write the code so that it passes more often than one time out of ten
•  » » 14 months ago, # ^ |   +6 s[pos] = c checks out. Strings are immutable in python. Your soln is O(n^2) rather than O(n) what you are expecting it to be. It does get a well deserved TLE.
•  » » » 14 months ago, # ^ | ← Rev. 4 →   +20 Just to be fairActually not. If it was a string, it would runtime error.His solution seems asymptotically right, it is just that reading 2e5 lines and then outputing 1e5 while flushing every time is quite expensive in python and requires some optimizations. Pretty much like in c++ you often have to use sync_with_stdio(false) and cin.tie(nullptr)
•  » » » » 14 months ago, # ^ |   0 but how to write fast input in python?
•  » » » » » 14 months ago, # ^ |   0 Look at this https://codeforces.com/blog/entry/83441Or at my submission https://codeforces.com/contest/1609/submission/137240879
 » 14 months ago, # |   +4 this is the fastest system testing I have ever seen :) and it's become better when you get +32 in the end :)
 » 14 months ago, # | ← Rev. 4 →   0 In problem C for these testcase what should be the pairs? I am getting 12 pairs110 21 1 1 422549 1 1 880667 81267 1 1pairs in (i,j) --> j = i+e*k(1,7),(1,9),(3,7),(3,9),(5,7),(5,9),(7,9)(2,4), (2,6), (2,10),(4,6),(4,10)Given answer is 10
•  » » 14 months ago, # ^ |   0 Are you talking about problem C?If yes you didn't understand task properly. You're not supposed to find pairs (unless they fulfill certain conditions) — instead you have to find subsequnces.
•  » » » 14 months ago, # ^ | ← Rev. 3 →   0 Yeah I know. Actually I have done the same. Okay can you write the valid subsequences for above testcases.My subsequence are: (1,3,5,7), (1,3,5,7,9),(3,5,7),(3,5,7,9),(5,7),(5,7,9),(7,9)(2,4), (2,4,6), (2,4,6,10), (4,6),(4,6,10)
•  » » » » 14 months ago, # ^ |   0 (1,7) is not valid as distance between two next elements is not e (2)
•  » » » » » 14 months ago, # ^ |   0 Please check it once more I have changed it!!
•  » » » » » » 14 months ago, # ^ | ← Rev. 3 →   0 I believe you can now solve it on your own now.(Hint I can still see 2 subsequences that are invalid)(Hint 2 — 81267 is not prime)
 » 14 months ago, # |   +60 One feedback -I have participated in 2/3 Deltix rounds so far. In each of them, Both times I have read problems wrong. It seems I'm not the only one here. All CodeChef contests have a paid statement verifier whose sole job is to make sure statements are better and easily understandable. Looking at the panel it seems most of them have Russian as their first language. Since it's a sponsored round I would advise including someone for the 4th scheduled round who has experience verifying statements for CodeChef. The round would be relatively better for non-Russian speakers. Xellos and Monogon both are pretty good at it.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +31 You are right that English is not our first language. But are you sure the problem is in our English? I think we can all learn something from problems B and E. People involved in translation have a really good level of English, almost at the native level. But okay, let's say that's still not enough. Further, all statements are checked by auto analyzers and the round coordinator. ok, still bad. But there are testers who can point out our mistakes. For example, we had testers with a native level of English. Do you think these steps are not sufficient? I'm not sure which task you are specifically talking about now, but I will assume that about task F. I think I can agree that I should have added a clarification to the test case to rule out possible other understandings of the statement, but I was sure that participants who got down to this problem would not need it.
•  » » » 14 months ago, # ^ |   +20 Haven't you noticed that tons of participants are misreading/ couldn't understand/ had a hard time trying to guess what that problem statement of D and F means?
•  » » » » 14 months ago, # ^ |   +6 yes, it is foolish to deny it, there are objective signs. I think about how we can improve the situation in the future. I thought we could fix this with the number of testers, but it doesn't seem like it helps.We will look for a solution, it is a pity that you do not take part in the next round. May I invite you to test the next round?
•  » » » 14 months ago, # ^ |   -12 I've also participated in another round hold by DELIX and got a similar issue of the English problem statement.I could fairly expect that all future rounds hold by DELIX would have the same quality of English problem statement, so I won't participate in any of them.
•  » » » 14 months ago, # ^ |   +4 I think D would have caused less confusion if instead of people and friendships you had cities and roads. The idea that two cities are reachable by a sequence of roads feels more natural than the idea that people have a connection if there's a sequence of friendships that starts from one person and ends at the other.
 » 14 months ago, # |   +39 I think I broke G. I submitted $O(mq)$ to make sure my idea is correct and it ACed 137283005
•  » » 14 months ago, # ^ |   +10 it looks like it's a matter of pragmas. I suspect it can be hacked, but I haven't succeeded yet. By the way, in this task, the time limit was specially increased for your comfort, I cannot imagine how in a world where there is a pragma to balance between blocking such solutions and the comfort of participants who send good solutions, but with bad implementation.
 » 14 months ago, # |   +51 The list of participants who received random T-shirts will appear later in the comments after completing the search for cheaters. All people who receive the T-shirt will be tagged and notified.Thank you again for participating, everyone! Hopefully, enough of the participants were able to enjoy these tasks. Perhaps I will answer a couple more accusations in the comments when I get enough sleep after two nervous days of checking all the materials of the competition.Thank you, you are the best!
•  » » 14 months ago, # ^ |   +3 will nitin_05 be considered as a cheater?
•  » » » 14 months ago, # ^ |   +3 I hope that yes. The authors of the round do not participate in the verification of cheaters.I'll tag MikeMirzayanov and geranazavr555 just in case.
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +3 I'm so sad that he wasn't caught
 » 14 months ago, # |   +13 On the standings, noimi placed 84th, but on their profile it says they placed 142nd (and it looks like their rating was adjusted based on 142nd). Any idea what caused this?
•  » » 14 months ago, # ^ |   +35 A few contestants requested to be re-judged because of exceeding the time limit by a few milliseconds due to random execution time fluctuations. And their request was surprisingly granted. Most likely noimi's problem F submission was re-judged too.
•  » » » 14 months ago, # ^ |   0 I'm surprised to wake up and hear this news *_* btw, will my rate will be recalculated??
•  » » » » 14 months ago, # ^ |   0 your rating will be recalculated after cheaters are removed
 » 14 months ago, # |   0 In problem C, if there are l ones to the left and r ones to the right, and we want to count possibilities such that a prime p is somewhere in the middle, how is it coming out to be l*r? Can someone please give me the proof?
•  » » 14 months ago, # ^ |   0 okay, nvm got it lol.
 » 14 months ago, # |   0 It's a interesting round and there are two similar problems but different solutions and aspects.
 » 14 months ago, # |   0 Please tell me if this should have passed or not??According to me this solution is O(n^2). Please check someone137337732
•  » » 14 months ago, # ^ |   0 No, this solution is O(n). For each number, you only check at most 2 times: one in the forward loop and one in the backward loop. The reason is each number 1 belongs to only one segment with two ends (either a prime -> need to check or composite -> no need to check)
 » 14 months ago, # | ← Rev. 4 →   +85 For H, I just realized that my submission during the contest set maxn/maxq to 55/55 instead of 105/1005, and could pass after replacing them with the correct values. R.I.P.
 » 14 months ago, # |   +10 It seems like tourist always comes first ;)
»
14 months ago, # |
+132

Congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1609 1 tourist
2 1609 2 DmitryGrigorev
3 1609 3 xtqqwq
4 1609 4 Maksim1744
5 1609 5 greenheadstrange
6 1609 6 maroonrk
7 1609 7 jiangly
8 1609 8 fantasy
9 1609 9 QAQAutoMaton
10 1609 10 emptyhope
11 1609 11 zh0ukangyang
12 1609 12 heno239
13 1609 13 he_____hezhou
14 1609 14 ko_osaga
15 1609 15 Karry5307_AK_NOI2023
16 1609 16 ainta
17 1609 17 AliShahali1382
18 1609 18 Egor.Lifar
19 1609 18 Endagorion
20 1609 20 Cirno_9baka
21 1609 21 fivedemands
22 1609 22 Farhod_Farmon
23 1609 23 dfcmd
24 1609 24 basic_string
25 1609 25 yzc2005
26 1609 26 Isonan
27 1609 27 Radewoosh
28 1609 28 bthero
29 1609 29 BigBag
30 1609 30 receed
31 1609 31 LMOliver
32 1609 32 fanache99
33 1609 33 ecnerwala
34 1609 34 ugly2333
35 1609 35 ezLadder
36 1609 36 He_Ren
37 1609 37 PetelgeuseRomaneeconti
38 1609 38 hitonanode
39 1609 39 Torta
40 1609 40 natsugiri
41 1609 41 MyBotDear
42 1609 42 dorijanlendvaj
43 1609 43 SpyCheese
44 1609 44 waynetu
45 1609 45 gyh20
46 1609 46 Amoo_Safar
47 1609 47 ei133333
48 1609 48 satashun
49 1609 49 sansen
50 1609 50 aid
51 1609 51 MoRanSky
52 1609 52 RomaWhite
53 1609 53 froggyzhang
54 1609 54 AmShZ
55 1609 55 tabr
56 1609 56 arbuzick
57 1609 57 tfg
58 1609 58 alexxela12345
59 1609 59 353cerega
60 1609 60 lqx2005
61 1609 61 kostia244
62 1609 62 Siberian
63 1609 63 liangjiawen2007
64 1609 64 Tutis
65 1609 65 fedoseev.timofey
66 1609 66 hank55663
67 1609 67 Ra16bit
68 1609 68 AnandOza
69 1609 69 tatyam
70 1609 70 kektus
71 1609 71 Bench0310
72 1609 72 natofp
73 1609 73 Nyaan
74 1609 74 risujiroh
75 1609 75 A-SOUL_Bella
76 1609 76 balbit
77 1609 77 qwerty787788
78 1609 78 Barichek
79 1609 79 YaoBIG
80 1609 80 Tima
81 1609 81 happyguy656
82 1609 82 maspy
83 1609 83 noimi
84 1609 84 Nahida_Buer
85 1609 85 Chinese_zjc_
86 1609 86 JJLeo_
87 1609 87 Arihara_Nanami
88 1609 88 talant
89 1609 89 Amtek
90 1609 90 feecle6418
91 1609 91 flukehn
92 1609 92 golikovnik
93 1609 93 SSHS
94 1609 94 SSRS_
95 1609 95 Rafbill
96 1609 96 tmwilliamlin168
97 1609 97 dXqwq
98 1609 98 SamBankman-Fried
99 1609 99 Alice_foo_foo
100 1609 100 chinerist
135 1609 135 Nero
139 1609 137 icecuber
153 1609 152 Snow-Flower
154 1609 154 riantkb
155 1609 155 cerberus97
170 1609 170 Dart-Xeyter
191 1609 191 Onjo
199 1609 199 Gnoud__
202 1609 202 Liang_Hui
224 1609 223 vinfat
228 1609 227 haruki_K
236 1609 236 axs7384
262 1609 262 kshitij_sodani
265 1609 265 desprado2
269 1609 269 fengzhengwei
283 1609 283 noogler
290 1609 290 hieplpvip
293 1609 293 stevenkplus
300 1609 299 dblark
305 1609 305 bashkort
314 1609 314 Mamedov
318 1609 318 Jimanbanashi
324 1609 324 tatavayapmabulldogvd
332 1609 332 minhcool
333 1609 333 FutureNewbie
334 1609 334 TheDuchess
342 1609 342 caidd
356 1609 356 YxqK
361 1609 361 geospiza
365 1609 365 sare
383 1609 383 wangzhifang
397 1609 397 qiutongxue
409 1609 409 118907
413 1609 413 PCTprobability
424 1609 424 antontrygubO_o
432 1609 432 uwu
476 1609 475 CodigoL
479 1609 478 Valera_Grinenko
482 1609 482 c8kbf
495 1609 495 paula
499 1609 500 ouqingliang
500 1609 501 tem_shett
512 1609 514 _dg_
523 1609 524 kmjp
528 1609 530 Puranya_
535 1609 537 TITANOBOXER
538 1609 540 RyoPham
545 1609 547 shino16
562 1609 564 hiva_
572 1609 574 Xaxixin
573 1609 575 MysteryGuy2
576 1609 576 CLT
577 1609 579 Shun_PI
578 1609 579 shubham__36
586 1609 587 Nyaruko
588 1609 590 andrei_boaca
608 1609 609 kitsune
616 1609 618 Kregor
621 1609 623 WindFromTmw
623 1609 624 cscse
624 1609 624 qscfthmko147
625 1609 627 Brambles
649 1609 651 KyuusyouTheSavior
681 1609 683 Bellalabella
683 1609 683 kkite_gk
685 1609 687 sotanishy
695 1609 697 Gorgo
705 1609 707 andrewtam
711 1609 713 Kaizyn
712 1609 713 Wibo
714 1609 716 TheScrasse
717 1609 718 jeroenodb
729 1609 730 mkawa2
752 1609 754 sinus_070
768 1609 770 ArsenM
772 1609 773 Hypik
775 1609 776 fitisovartyom123
777 1609 778 Ziware
778 1609 778 saprykin
802 1609 803 the_hyp0cr1t3
808 1609 809 NewLul
811 1609 813 NToneE
823 1609 825 DDima
837 1609 839 what_if_i_fail
838 1609 839 Yomapeed
850 1609 853 MCuong
862 1609 865 ___dreamer__
876 1609 879 __ZMF__
900 1609 902 MVP_Harry
909 1609 912 Yoav
912 1609 915 kencho
920 1609 922 PaintItRed
939 1609 943 huan_yp
969 1609 972 Trung.Or
974 1609 978 satyam343
975 1609 978 hey_boris
976 1609 978 NHiL
991 1609 993 ale_np
993 1609 997 ttttan
995 1609 997 limabeans
•  » » 14 months ago, # ^ |   +3 Nice
•  » » 14 months ago, # ^ |   +7 Nice
•  » » 14 months ago, # ^ |   0 Nice
•  » » 14 months ago, # ^ |   +1 Nice
•  » » 14 months ago, # ^ |   +13 OMG
•  » » 14 months ago, # ^ |   +8 Nice
•  » » 14 months ago, # ^ |   0 Nice
•  » » 14 months ago, # ^ |   0 Nice
•  » » 14 months ago, # ^ |   0 Nice
•  » » 13 months ago, # ^ |   0 Thanks，I have changed my nickname from Nothing_matter to Liang_Hui, and my address has been filled in. I am looking forward to your mail！
 » 9 months ago, # |   +14 Where is winter one, or postponed?
•  » » 9 months ago, # ^ |   +10 Hello, the round was supposed to take place at the end of March, but the war forced us to change our plans. I did not consider it is appropriate time to hold the round and it was decided to postpone it. We have not decided on a new date, but I hope we will treat you to a good competition before the end of the year.Thank you for not forgetting about us and waiting for the next round, it's pleasant.