Привет, Codeforces!
Вас приветствует компания DELTIX. Мы были основаны в 2005 году и являемся одним из лидеров в разработке программного обеспечения для исследований в финансовом домене и продуктов, решающих различные задачи системной и алгоритмической торговли. В 2020 году DELTIX присоединился к EPAM. Основной нашей задачей является быстрая и эффективная реализация перспективных идей в прорывные продукты.
Мы являемся экспертами по следующим направлениям:
- сбор, хранение, обработка данных
- моделирование данных
- тестирование и внедрение математических моделей
Поэтому в нашей команде ценятся такие навыки, как
- работа с алгоритмами
- написание высокоэффективного кода
- обработка потоков данных с минимальными задержками
Мы рады сообщить о выходе TimeBase Web Admin Community Edition.
Ближайший год, раз в сезон, мы будем рады приглашать вас участвовать в DELTIX раундах на Codeforces. Присоединяйтесь к третьему из серии наших раундов — объединенному раунду Div.1 и Div.2 Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2), который начнётся в 28.11.2021 17:35 (Московское время). Этот раунд будет рейтинговым и открытым для обоих дивизионов.
Призы, которые мы подготовили для вас:
1 место: Samsung Galaxy Z Flip3
2 место: Samsung Galaxy Tab S7+
3 место: Samsung Galaxy Watch4
1-100 место: фирменные футболки соревнования
А также 100 футболок достанутся случайным участникам (из тех, для кого этот раунд будет не первым рейтинговым соревнованием Codeforces), не вошедшим в топ-100, но попавшим в топ-1000.
Все задачи раунда, кроме последней, были подготовлены нашей командой: Vladik, 4llower и AleXman111.
Мы благодарим:
- KAN и budalnik за координацию раунда
- двойная благодарность budalnik за задачу, которая нашла уютное место в нашем наборе задач :)
- всех-всех тестировщиков раунда: Sugar_fan, 244mhq, Geothermal, andrew, aSmallTyphoon, _Time_Lord_, Hec, GustavoMG, phattd, ptd, kartel, bkbtpout, avoronoi, fixikmila, kartikeyasri23, Whiplash99, Ghazoo, Jon, asitnikoff, Zayadi, Ahmad7_7, Omar_Elaraby, Kart, Java и anegelytor.
- а также MikeMirzayanov за системы Codeforces и Polygon
Участникам будет предложено 8 задач и 2.5 часа на их решение. Желаем всем успешного раунда и повышения в рейтинге!
Заполните короткую анкету и расскажите о себе, если у Вас возникло желание пообщаться с рекрутерами или членами нашей команды.
UPD: Разбалловка для задач: 500 — 1000 — 1500 — 2000 — 2750 — 3000 — 3250 — 3750.
Спасибо всем за то что приняли участие. Желаем приятного дорешивания! (разбор)
Также хотим поздравить всех победителей раунда:
1. tourist
2. DmitryGrigorev
3. xtqqwq
4. Maksim1744
5. VivaciousAubergine
6. maroonrk
7. jiangly
8. heuristica
9. QAQAutoMaton
10. Crysfly
Yet Another Waving Arm
Are you having problems with the Waving Arm? :)
Opening CodeForces, a creature suddenly smile and wave to you, what a surprise:)
it's funny 0v0
all of the Deltix rounds were good so far. hope for another great around
Throughout the year, once per quarter, ....
Is this last round or should we expect more rounds next year?
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.
Looking Forward to this <*_->..
Looking forward to this contest! Hope every one can gain rating.
I think Deltix rounds always have high quality and wonderful problems.
Hope This Time i can solve 4 Tasks...
.
.
Deltix rounds always have interesting problems and wonderful pictures). Good luck for everyone!
Is it a habit to wave the hand when opening codeforces?
It still looks pleasantly surprised, even scary :)
Should I participate in this round or enjoy being Candidate master a few more days :)
Enjoy
being Candidate master for a few daysthis round.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 :)
Is It Hard?
Is It Hard?
Scoring Distribution ?
This was my first time testing a CF round. Hope you enjoy the round!
(Also please give me contribution uwu.)
as a tester, good luck in this amazing contest
As a tester friend I want some up votes please
very good part of deltix contests is that their problems contain interesting ideas
UPD : Also images in each problem
It is showing extra registration but I cannot find register button?
How to do extra registration?
Successfully wasted my 45 mins in understanding problem D statement :)
Me too. I feel, it was really a weird way of asking what was asked + I am stupid for net reading the announcement
Just noticed that there are so few participants this time, why is that?
many colleges have been re opened may be that's why they are busy doing shitty assignments
Shitty problem statements make people quit.
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?
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.
I think you should train your reading skills
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.
I will NEVER participate in any contest hold by DELIX.
why
Chill guys, he said DELIX. Not DELTIX :p
tourist surpasses 3900 :)
No he didnt.. but hopefully soon!
Quite a nice contest in my opinion
Though difficulty gap between D and E could be better. The way it is D seems 1700 and E is 2300
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 ...
E is an easier version of 750E.
How do you solve F?
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 :/
Yes, possible. We decided to remove the algorithmic part of the solution from the problem.
Why did you decide this?
because there were already a lot of problems in the competition that tested algorithmic skills
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 :)
Yes, it's possible
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
And I'm realizing after reading your comment :(
My solution with O(n^2 logn) passed
What was testcase 11 in problem E?
Can anyone show me how to solve problem E please :>.
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.
How can you count things of form $$$(b | c)^* (a | c)^* ( a | b)^*$$$ using a $$$3 \cdot n$$$ linear DP?
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.
This is new for me. What is the general approach to convert a linear dp to a segtree for performing updates?
My original solution required $$$9 \times 9$$$ node matrix, though...
But I agree that E is boring. (FG is boring too)
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.
any ideas on what is pretest 11 in problem E
Try
$$$aaabcccbbbc$$$
The answer is $$$2$$$.
Is the complexity of standard for problem F O(n log n) ?
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.
me too, my complexity is O(n(log n+log MAX)) and I get TLE. I don't know why.
I didnt have time to debug it in contest, but my complexity is same, it passes in ~ 1 sec. https://mirror.codeforces.com/contest/1609/submission/137271044
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).
" 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]
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.
Problem statement was not what we are required to do i.e bad statement!
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
nice codes nitin_05
137224965 137232569 137234971 137247368
It's because of these bastards CP is ruined
I don't get it. He comments out a lot, but why is CP ruined by that?
he added meaningless comments to avoid beeing caught cheating.
You mean, like he already had the solutions upfront?
yes
he got caught in the previous round
but most of the time he gets away.
I noticed someone in my room, qwerpoiu, replaced all of their tabs with a comment: 137223420 137229810 137240560 137253430
Now, he become an expert cheater. Nice...XD
C was nice
Problem A how is the case 15 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 working?
16 8 8 8 8 8 8 8 8 8 8 8 8 8 4
16 16 8 8 8 8 8 8 8 8 8 8 8 8 2
16 16 16 8 8 8 8 8 8 8 8 8 8 8 1
16 16 16 16 8 8 8 8 8 8 8 8 8 4 1
16 16 16 16 16 8 8 8 8 8 8 8 8 2 1
16 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
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 :)
Same xD
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 ...
thanks for boring, standart, absolutely non-interesting, hard-to-write problem E...
can't agree, it's not hard to write at all 137263169
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.
So true, I had to write a brute force to understand what the problem was asking.
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".
I really want a screencast of a contest from tourist
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.
yeah F time limit was strict for nlogn segment tree solution.
Was D written in Bitcoin language?
You could make problem C better if sequence of 1 's would be good sequence
the approach is same but that makes implementation easier
Isn't it simple already?
I think they did that cuz prime numbers seem more natural than "prime numbers or 1". I agree the implementation was the bottleneck.
Great round. Especially loved the response of this round team, got a quick reply on every query I asked.
"William satisfied all conditions from 1 and up to and including i and performed exactly i introductions."
What and the and fuck! xD
Its grammatically correct but confusing lol.
"William satisfied all conditions from 1 to i and performed exactly i introductions." is more appropriate
"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
Any idea why this is wrong?
what was the pretest 9 in problem D about?
For me, I simply forgot to clear the DSU size array after merges.
Passed test 9 after that.
but in my code that doesn't affect the answer. Code
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
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
Use Linux
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
Use Linux
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.
Maybe you had too much of serotonin
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...
"William can introduce any two people"
sorry, but this is a direct quote from the problem statement.
Ah!! Ok!! My bad... I think i got confused btw william introducig ppl & ppl having connections. i.e. xi, yi. Thanks.
Объясните, пожалуйста, разницу между "maximum" и "maximal"! :)
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.
F was tight if you solve in O(n*logn) (or I have to rethink my segment tree code)
You don't need a segment tree if you use vectors (stacks) with partials sums and binary search.
I have no idea how that solution works.
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.
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.
You have a $$$\mathcal{O}(n \log n)$$$ solution? How does it work?
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.
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.
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.
For problem D, these words are used interchangeably without any clarification from the statement:
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.
subtle storytelling on B and E ;)
Congratulations tourist for achieving a new max rating
Congratulations tourist for achieving a new max rating!
So apparently I was a massive clown and did some massive clownery problem E.
Same 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:
*a**b**c**a*b**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 137243960LOL, I had the same solution xD
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.
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
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.
Actually I think it should not depend on authors, it should be automatic. Seems like such an obvious improvement
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.
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
I understood it now. thanks
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 introductions
The 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
You should perform i introductions, but on i-th step you can use completely different introductions than on step (i — 1)
completely different introductions that mean I can just put any random introductions? can you please explain example 2:
what happen when we connect 6-7 and why the answer is 5
Nothing happens, That's the point, on 5-th step you reapply all constraints from scratch
For example you can use five edges
1-2
2-3
3-4
4-6
4-7
This way 1 is connected to [2,3,4,6,7], that's why the answer is 5
because i = 5, so you have 5 introductions, it can have all nodes {2, 3, 4, 6, 7} directly connected with 1
I find the pictures of the problems equally satisfying as the problems :D
.
For 1609D - Social Network 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...
It's funny because I sometimes make the mistake of $$$(10^9)^{0.5} = (10^3)$$$ . The inverse of your mistake if you will .
Hello there, So I was trying to understand how you maintained sum of some top components and found a bug in your code
In 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 changes
Maybe 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!!
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 way
Also 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
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
I passed problem F with the same code after contest but I got FST.
Can I apply for rejudge?
https://mirror.codeforces.com/contest/1609/submission/137269939
https://mirror.codeforces.com/contest/1609/submission/137266323
Thanks for report, we will rejudge before counting the final ratings.
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:
hello. I sent this code during the tunnel: https://mirror.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://mirror.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.
There are fluctuations, deal with it. Write the code so that it passes more often than one time out of ten
what's the difference then. the algorithm is correct. I want to have a rating calculation done.
s[pos] = cchecks 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.Just to be fair
Actually 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)
but how to write fast input in python?
Look at this https://mirror.codeforces.com/blog/entry/83441
Or at my submission https://mirror.codeforces.com/contest/1609/submission/137240879
Thanks. I will now always write fast input in my programs
this is the fastest system testing I have ever seen :) and it's become better when you get +32 in the end :)
I'm happy for you
In problem C for these testcase what should be the pairs? I am getting 12 pairs
1
10 2
1 1 1 422549 1 1 880667 81267 1 1
pairs 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
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.
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)
(1,7) is not valid as distance between two next elements is not e (2)
Please check it once more I have changed it!!
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)
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.
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.
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.
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?
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?
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.
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.
I think I broke G. I submitted $$$O(mq)$$$ to make sure my idea is correct and it ACed 137283005
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.
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!
will nitin_05 be considered as a cheater?
137224965 137232569 137234971 137247368
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.
I'm so sad that he wasn't caught
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?
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.
I'm surprised to wake up and hear this news *_* btw, will my rate will be recalculated??
your rating will be recalculated after cheaters are removed
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?
okay, nvm got it lol.
It's a interesting round and there are two similar problems but different solutions and aspects.
Please tell me if this should have passed or not??
According to me this solution is O(n^2). Please check someone
137337732
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)
конгрутилэйшенс
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.
It seems like tourist always comes first ;)
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.
Nice
Nice
Nice
Nice
OMG
Nice
Nice
Nice
Nice
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！
Where is winter one, or postponed?
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.