By deltixlab, 3 years ago, translation, In English

deltix

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.

More about DELTIX

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. gop2024
3. xtqqwq
4. Maksim1744
5. VivaciousAubergine
6. maroonrk
7. jiangly
8. Rewinding
9. QAQAutoMaton
10. PubabaOnO

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

  • Vote: I like it
  • +221
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +72 Vote: I do not like it

Yet Another Waving Arm

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Are you having problems with the Waving Arm? :)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +41 Vote: I do not like it

      Opening CodeForces, a creature suddenly smile and wave to you, what a surprise:)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's funny 0v0

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

all of the Deltix rounds were good so far. hope for another great around

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Throughout the year, once per quarter, ....
Is this last round or should we expect more rounds next year?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Looking Forward to this <*_->..

»
3 years ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Looking forward to this contest! Hope every one can gain rating.

I think Deltix rounds always have high quality and wonderful problems.

»
3 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Hope This Time i can solve 4 Tasks...

»
3 years ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Deltix rounds always have interesting problems and wonderful pictures). Good luck for everyone!

»
3 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

Is it a habit to wave the hand when opening codeforces?

It still looks pleasantly surprised, even scary :)

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Should I participate in this round or enjoy being Candidate master a few more days :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +74 Vote: I do not like it

    Enjoy being Candidate master for a few days this round.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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 :)

»
3 years ago, # |
  Vote: I like it -45 Vote: I do not like it

Is It Hard?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Scoring Distribution ?

»
3 years ago, # |
Rev. 3   Vote: I like it +69 Vote: I do not like it

This was my first time testing a CF round. Hope you enjoy the round!
(Also please give me contribution uwu.)

»
3 years ago, # |
  Vote: I like it +87 Vote: I do not like it

as a tester, good luck in this amazing contest

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

very good part of deltix contests is that their problems contain interesting ideas

UPD : Also images in each problem

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do extra registration?

»
3 years ago, # |
  Vote: I like it +74 Vote: I do not like it

Successfully wasted my 45 mins in understanding problem D statement :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Me too. I feel, it was really a weird way of asking what was asked + I am stupid for net reading the announcement

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Just noticed that there are so few participants this time, why is that?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    many colleges have been re opened may be that's why they are busy doing shitty assignments

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Shitty problem statements make people quit.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          I think you should train your reading skills

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I will NEVER participate in any contest hold by DELIX.

»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

tourist surpasses 3900 :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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 ...

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

E is an easier version of 750E.

How do you solve F?

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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 :/

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Yes, possible. We decided to remove the algorithmic part of the solution from the problem.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Why did you decide this?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        because there were already a lot of problems in the competition that tested algorithmic skills

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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 :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Yes, it's possible

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    And I'm realizing after reading your comment :(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution with O(n^2 logn) passed

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can anyone show me how to solve problem E please :>.

»
3 years ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

Are the three observations to E literally meant to be:

  1. Solution is of the form $$$(b|c)^*(a|c)^*(a|b)^*$$$

  2. For a single string this can be counted in $$$O(n)$$$ with a $$$3 \cdot n$$$ linear dp of (position, current segment).

  3. 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    How can you count things of form $$$(b | c)^* (a | c)^* ( a | b)^*$$$ using a $$$3 \cdot n$$$ linear DP?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is new for me. What is the general approach to convert a linear dp to a segtree for performing updates?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    My original solution required $$$9 \times 9$$$ node matrix, though...

    But I agree that E is boring. (FG is boring too)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

any ideas on what is pretest 11 in problem E

»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

Is the complexity of standard for problem F O(n log n) ?

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    " 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]

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +16 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Problem statement was not what we are required to do i.e bad statement!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

C was nice

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A how is the case 15 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 working?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

»
3 years ago, # |
Rev. 2   Vote: I like it +75 Vote: I do not like it

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 :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same xD

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ...

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

thanks for boring, standart, absolutely non-interesting, hard-to-write problem E...

»
3 years ago, # |
  Vote: I like it +177 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So true, I had to write a brute force to understand what the problem was asking.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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".

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I really want a screencast of a contest from tourist

»
3 years ago, # |
  Vote: I like it +109 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    yeah F time limit was strict for nlogn segment tree solution.

»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Was D written in Bitcoin language?

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You could make problem C better if sequence of 1 's would be good sequence

the approach is same but that makes implementation easier

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't it simple already?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think they did that cuz prime numbers seem more natural than "prime numbers or 1". I agree the implementation was the bottleneck.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great round. Especially loved the response of this round team, got a quick reply on every query I asked.

»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

"William satisfied all conditions from 1 and up to and including i and performed exactly i introductions."

What and the and fuck! xD

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Its grammatically correct but confusing lol.

    "William satisfied all conditions from 1 to i and performed exactly i introductions." is more appropriate

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea why this is wrong?

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

what was the pretest 9 in problem D about?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but in my code that doesn't affect the answer. Code

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

»
3 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Use Linux

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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

»
3 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Maybe you had too much of serotonin

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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...

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "William can introduce any two people"

      sorry, but this is a direct quote from the problem statement.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah!! Ok!! My bad... I think i got confused btw william introducig ppl & ppl having connections. i.e. xi, yi. Thanks.

»
3 years ago, # |
  Vote: I like it +114 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    F was tight if you solve in O(n*logn) (or I have to rethink my segment tree code)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You don't need a segment tree if you use vectors (stacks) with partials sums and binary search.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have no idea how that solution works.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You have a $$$\mathcal{O}(n \log n)$$$ solution? How does it work?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it -40 Vote: I do not like 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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        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.

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

subtle storytelling on B and E ;)

»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Congratulations tourist for achieving a new max rating!

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

So apparently I was a massive clown and did some massive clownery problem E.

my solution
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    LOL, I had the same solution xD

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Actually I think it should not depend on authors, it should be automatic. Seems like such an obvious improvement

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You should perform i introductions, but on i-th step you can use completely different introductions than on step (i — 1)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it -8 Vote: I do not like it

        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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        because i = 5, so you have 5 introductions, it can have all nodes {2, 3, 4, 6, 7} directly connected with 1

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I find the pictures of the problems equally satisfying as the problems :D

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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...

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It's funny because I sometimes make the mistake of $$$(10^9)^{0.5} = (10^3)$$$ . The inverse of your mistake if you will .

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it
    Doubt Cleared
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for report, we will rejudge before counting the final ratings.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +152 Vote: I do not like it

        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:

        1. What is exactly the accepted criteria for an appeal to rejudge?
        2. How does the rejudge process occur: is it one accepted run or multiple accepted runs?
»
3 years ago, # |
  Vote: I like it -33 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

this is the fastest system testing I have ever seen :) and it's become better when you get +32 in the end :)

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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)

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        (1,7) is not valid as distance between two next elements is not e (2)

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Please check it once more I have changed it!!

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like 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)

»
3 years ago, # |
  Vote: I like it +60 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like 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.

    1. People involved in translation have a really good level of English, almost at the native level.
    2. But okay, let's say that's still not enough. Further, all statements are checked by auto analyzers and the round coordinator.
    3. 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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like 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?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I think I broke G. I submitted $$$O(mq)$$$ to make sure my idea is correct and it ACed 137283005

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +51 Vote: I do not like it

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!

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm surprised to wake up and hear this news *_* btw, will my rate will be recalculated??

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        your rating will be recalculated after cheaters are removed

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a interesting round and there are two similar problems but different solutions and aspects.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please tell me if this should have passed or not??

According to me this solution is O(n^2). Please check someone

137337732

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

конгрутилэйшенс

»
3 years ago, # |
Rev. 4   Vote: I like it +85 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

It seems like tourist always comes first ;)

»
3 years ago, # |
  Vote: I like it +132 Vote: I do not like it

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 gop2024
3 1609 3 xtqqwq
4 1609 4 Maksim1744
5 1609 5 VivaciousAubergine
6 1609 6 maroonrk
7 1609 7 jiangly
8 1609 8 Rewinding
9 1609 9 QAQAutoMaton
10 1609 10 PubabaOnO
11 1609 11 zh0ukangyang
12 1609 12 heno239
13 1609 13 he_____hezhou
14 1609 14 ko_osaga
15 1609 15 Karry5307_AK_NOI2024
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
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 MoRanAirConditioner
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 Savior-of-Cross
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 erray
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 MahiruShiina
535 1609 537 TITANOBOXER
538 1609 540 RyoPham
545 1609 547 shino16
562 1609 564 hiva_
572 1609 574 early-morning-dreams
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 ArsenGotov
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 5phInX
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
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Where is winter one, or postponed?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.